CUFMH2Blog

LeetCode - 剑指Offer - Part1

LeetCode 剑指Offer
Word count: 2.4k Reading time: 12 min
2020-09-01 calculating Share

秦时明月汉时关，万里长征人未还。

剑指 Offer 01. 赋值运算符函数

写一个类的赋值运算符函数

1、返回值类型

2、参数类型

3、内存释放

4、判断参数和this是否相同

1
2
3
4
5
6
7
8
9
10
11
//	1.
A& A::operator=(const A & a) {
  if(&a==this) {
    return this;
  }
  delete [] data;	// char * data;
  data=nullptr;
  data = new char[strlen(a.data)+1];
  strcpy(data, a.data);
  return *this;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
//	2.异常安全性
//	1中如果new时出错抛出异常，则原数据已被delete，不再有效
//	2考虑改进，创建临时实例，让临时实例自己调用析构函数释放原来的内容
A& A::operator=(const A & a) {
  if(&a==this) {
    return this;	// char * data;
  }
  A temp(a);
  char * p_temp=temp.data;
  temp.data=data;
  data=p_temp;
  return *this;
}

剑指 Offer 02. 单例模式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
//	1.饿汉模式
public class Singleton{
    private static Singleton instance = new Singleton();
    private Singleton(){}
    public static Singleton newInstance(){
        return instance;
    }
}
//	2.懒汉模式
public class Singleton{
    private static Singleton instance = null;
    private Singleton(){}
    public static Singleton newInstance(){
        if(null == instance){
            instance = new Singleton();
        }
        return instance;
    }
}
//	3.DCL
public class Singleton {
    private static volatile Singleton instance = null;
    private Singleton(){}
    public static Singleton getInstance() {
        if (instance == null) { // Single Checked
            synchronized (Singleton.class) {
                if (instance == null) { // Double checked
                    instance = new Singleton();
                }
            }
        }
        return instance;
    }
}
//	4.静态内部类
public class Singleton{
    private static class SingletonHolder{
        public static Singleton instance = new Singleton();
    }
    private Singleton(){}
    public static Singleton newInstance(){
        return SingletonHolder.instance;
    }
}
//	5.枚举
class Resource{
}
public enum SomeThing {
    INSTANCE;
    private Resource instance;
    private SomeThing() {
        instance = new Resource();
    }
    public Resource getInstance() {
        return instance;
    }
}

剑指 Offer 03. 数组中重复的数字

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

限制：

2 <= n <= 100000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        //  ----------------------
        //  1.排序找相邻，看是否有重复
        //  20.69%  47.32%
        //  ----------------------
        // int len=nums.size();
        // sort(nums.begin(), nums.end());
        // for(int i=0; i<len-1; i++){
        //     if(nums[i]==nums[i+1]) {
        //         return nums[i];
        //     }
        // }
        // return -1;

        //  ----------------------
        //  2.set
        //  38.61%  27.66%
        //  ----------------------
        // unordered_set <int> numset;
        // for(int i: nums) {
        //     if(numset.count(i)==1) {
        //         return i;
        //     } else {
        //         numset.insert(i);
        //     }
        // }
        // return -1;

        //  ----------------------
        //  3.原地算法，num[i]==i
        //  86.49%  90.49%
        //  ----------------------
        int len=nums.size();
        for(int i=0;i<len;i++) {
            while(nums[i]!=i) {
                int value=nums[i];
                if(value==nums[value]) {
                    return value;
                }
                nums[i]=nums[value];
                nums[value]=value;
            }
        }
        return -1;
    }
};

剑指 Offer 04. 二维数组中的查找

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:

现有矩阵 matrix 如下：

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。

给定 target = 20，返回 false。

限制：

0 <= n <= 1000

0 <= m <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        //  85.58%  67.03%
        //  从右上角开始搜索
        if(matrix.empty() || matrix[0].empty()) {
            return false;
        }
        int len1=matrix.size(), len2=matrix[0].size();
        int i=0, j=len2-1;
        while(i<=len1-1 && j>=0) {
            if(matrix[i][j]==target) {
                return true;    //  成功
            } else if(matrix[i][j]>target) {
                j--;    //  这列不行，退到上一列
            } else {    //  matrix[i][j]<target
                i++;    //  这行不行，进入下一行
            }
        }
        return false;
    }
};

剑指 Offer 05. 替换空格

请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

示例 1：

输入：s = “We are happy.”
输出：”We%20are%20happy.”

限制：

0 <= s 的长度 <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    string replaceSpace(string s) {
        //  ----------------------
        //  1.新建一个字符串，逐个字符添加
        //  100.00%  25.92%
        //  ----------------------
        // string ans="";
        // for(auto c: s) {
        //     if(c==' ') {
        //         ans+="%20";
        //     } else {
        //         ans+=c;
        //     }
        // }
        // return ans;

        //  ----------------------
        //  2.原字符串，先扩容再从后往前加字符
        //  100.00%  90.45%
        //  ----------------------
        if(s.empty()) {
            return s;
        }
        int count=0, len=s.size();
        //  扩容
        for(int i=0;i<len;i++) {
            if(s[i]==' ') {
                count++;
            }
        }
        s.resize(len+count*2);
        //  移动
        int j=len+count*2-1;
        for(int i=len-1;i>=0;i--) {
            if(s[i]==' ') {
                s[j]='0';
                s[j-1]='2';
                s[j-2]='%';
                j-=3;
            } else {
                s[j]=s[i];
                j--;
            }
        }
        return s;
    }
};

剑指 Offer 06. 从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

限制：

0 <= 链表长度 <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        //  ----------------------
        //  1.链表入栈，栈出vector
        //  71.32%  28.76%
        //  ----------------------
        // if(!head) {
        //     return vector<int>(0);
        // }
        // vector<int> res;
        // stack<int> s;
        // while(head){
        //     s.push(head->val);
        //     head=head->next;
        // }
        // while(!s.empty()) {
        //     res.push_back(s.top());
        //     s.pop();
        // }
        // return res;

        //  ----------------------
        //  2.翻转链表
        //  96.58%  98.75%
        //  ----------------------
        //  翻转完链表直接入vector
        if(!head) {
            return vector<int>(0);
        }
        vector<int> res;
        head=reverse(head);
        while(head) {
            res.push_back(head->val);
            head=head->next;
        }
        return res;
    }

    //  链表翻转函数
    ListNode * reverse(ListNode * head) {
        if(!head || !head->next) {
            return head;
        }
        ListNode * curr=head, * prev=nullptr;
        while(curr) {
            ListNode * temp=curr->next;
            curr->next=prev;
            prev=curr;
            curr=temp;
        }
        return prev;
    }
};

剑指 Offer 07. 重建二叉树*

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

3
/ \
9 20
/ \
15 7

限制：

0 <= 节点个数 <= 5000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        //  99.91%  64.25%
        int len=preorder.size();
        if(len==0) {
            return nullptr;
        }
        TreeNode * res=getNode(preorder, inorder, 0, len-1, 0, len-1);
        return res;
    }
  	//	采用四个浮标来记录子前序，子中序的位置
    TreeNode* getNode(vector<int>& preorder, vector<int>& inorder,
        int p1, int p2, int i1, int i2) {
        TreeNode * res=new TreeNode(preorder[p1]);
        if(p1==p2) {    //  只有一个结点
        } else if(preorder[p1]==inorder[i1]) {  //  左子树为空
            res->right=getNode(preorder, inorder, p1+1, p2, i1+1, i2);
            return res;
        } else if(preorder[p1]==inorder[i2]) {  //  右子树为空
            res->left=getNode(preorder, inorder, p1+1, p2, i1, i2-1);
        } else {    //  都不为空，计算左子树大小
            int i=i1-1;
            while(preorder[p1]!=inorder[++i]) {}
            res->left=getNode(preorder, inorder, p1+1, p1+i-i1, i1, i-1);
            res->right=getNode(preorder, inorder, p1+i-i1+1, p2, i+1, i2);
        }
        return res;
    }
};

剑指 Offer 08. 二叉树的下个节点

给一个二叉树的其中一个节点（数据结构）。

除了正常的成员外，每个节点有一个指向父节点的指针。

求中序序列中这个节点的下一个节点，要求返回这个节点（数据结构）。

1
2
3
4
5
6
//	1.为空则返回空
//	2.该节点有右子树，则返回右子树的最右节点
//	3.无右子树，但它是父节点的左节点，则返回父节点
//	4.无右子树，且它是父节点的右节点，沿着父节点向上找，直到找到一个新节点
//		新节点的左节点是该父节点，则返回这个新节点
//	5.如果一直找不到，则不存在下一个节点

剑指 Offer 09. 用两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

示例 1：

输入：
[“CQueue”,”appendTail”,”deleteHead”,”deleteHead”]
[[],[3],[],[]]
输出：[null,null,3,-1]
示例 2：

输入：
[“CQueue”,”deleteHead”,”appendTail”,”appendTail”,”deleteHead”,”deleteHead”]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]
提示：

1 <= values <= 10000
最多会对 appendTail、deleteHead 进行 10000 次调用

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */

class CQueue {
    //  61.91%  89.46%
private:
    stack<int> s1, s2;
public:
    CQueue() {}
    //  两个栈可以同时都存数据
    // ---------   ----------
    //      s1 |   | s2
    // ---------   ----------
    void appendTail(int value) {
        s1.push(value);
    }
    
    int deleteHead() {
        int res = -1;
        if(!s2.empty()) {
            res=s2.top();
            s2.pop();
            return res;
        } else if(!s1.empty()) {
            while(!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
            res=s2.top();
            s2.pop();
        }
        return res;
    }
};

剑指 Offer 10. 斐波那契数列

青蛙跳台阶

注意一下效率问题即可，避免在递归中重复计算某些项。

-> 动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    //  100.00% 43.52%
    int fib(int n) {
    if(n==0 || n==1)   return n;
    int a=1, b=0;
    //	青蛙跳台阶
    //	100.00%	80.35%
    //	if(n<2)   return 1;
    //	int a=1, b=1;
    for(int i=1; i<n; i++) {
      a=a+b;
      b=a-b;
      a%=1000000007;
    }
    return a;
  }
};
CATALOG
  1. 1. 剑指 Offer 01. 赋值运算符函数
  2. 2. 剑指 Offer 02. 单例模式
  3. 3. 剑指 Offer 03. 数组中重复的数字
  4. 4. 剑指 Offer 04. 二维数组中的查找
  5. 5. 剑指 Offer 05. 替换空格
  6. 6. 剑指 Offer 06. 从尾到头打印链表
  7. 7. 剑指 Offer 07. 重建二叉树*
  8. 8. 剑指 Offer 08. 二叉树的下个节点
  9. 9. 剑指 Offer 09. 用两个栈实现队列
  10. 10. 剑指 Offer 10. 斐波那契数列
Total : 27
2020
2019
3D-Game-Programming&Design SYSU-Course AR/MR Software-Testing LeetCode 剑指Offer
3D-Game-Programming-Design Software-Testing Programming