剑指offer笔记

Posted on | In | Visitors:

1. 二维数组中的查找

题目大意

一个二维数组，每一行都是递增的，每一列也是递增的。给定一个数，判断该二维数组中是否含有该数。

思路

从右上角开始，如果当前数大于target则往左边走一步，如果小于，则往下走一步，直到找到或者找不到该数为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        if (array.empty()) return false;
        int m = array.size(), n = array[0].size();
        int i = 0, j = n - 1;
        while (i < m && j >= 0){
            if (array[i][j] == target)
                return true;
            if (array[i][j] < target)
                ++i;
            else
                --j;
        }
        return false;
    }
};

相关题目

74. Search a 2D Matrix

按行递增

2. 替换空格

题目大意

将字符串中的空格替换为 %20

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

class Solution {
public:
    void replaceSpace(char *str,int length) {
        if (str == NULL || length <= 0)
            return;
        int cur_len=0, blank_num=0;
        int i=0;
        while(str[i]!='\0'){
            cur_len++;
            if (str[i] == ' ')
                blank_num++;
            i++;
        }
        
        // strlen 不会将'\0'计算在内
        int total_len = cur_len + blank_num*2;
        if (total_len > length)
            return;
        int p1 = cur_len, p2 = total_len;
        while(p2>=0 && p2>=p1){
            if (str[p1] != ' ')
                str[p2--] = str[p1--];
            else{
                str[p2--] = '0';
                str[p2--] = '2';
                str[p2--] = '%';
                p1--;
            }
        }
    }
};

3. 从尾到头打印链表

思路

使用栈或者使用递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> result;
        tailToHead(head, result);
        return result;
    }
private:
    void tailToHead(ListNode* cur, vector<int> &result){
        if (cur == NULL) return;
        tailToHead(cur->next, result);
        result.push_back(cur->val);
    }
};

4. 重建一颗二叉树

题目大意

根据前序和中序遍历的结果，恢复一棵二叉树，二叉树不含重复节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int>& pre,vector<int> vin) {
        if (vin.empty()) return NULL;
        int val = pre[0];
        TreeNode* root = new TreeNode(val);
         
        vector<int>::iterator it = vin.begin();
        for (; it!=vin.end(); ++it){
            if (*it == val)
                break;
        }
        pre = vector<int>(pre.begin()+1, pre.end());
        vector<int> left(vin.begin(), it);
        vector<int> right(it+1, vin.end());
        root->left = reConstructBinaryTree(pre, left);
        root->right = reConstructBinaryTree(pre, right);
        return root;
    }
};

5. 两个栈实现一个队列

思路

stack2存储从stack1中pop出来的数，这样stack2的栈顶就是最开始push进stack1的数。

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

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }
 
    int pop() {
        if (stack2.empty() && !stack1.empty()){
            while (!stack1.empty()){
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        if (!stack2.empty()){
            int res = stack2.top();
            stack2.pop();
            return res;
        }
        return -1;
    }
 
private:
    stack<int> stack1;
    stack<int> stack2;
};

6. 旋转数组中的最小数字

题目大意

在一个旋转排序数组中寻找最小的数(456123)

思路

  1. 和最后一个数比
  2. high下标的处理
  3. 重复数的处理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if (rotateArray.empty()) return -1;
        int low=0, high=rotateArray.size()-1, mid=0;
        while(low < high){
            mid = low + (high - low) / 2;
            if (rotateArray[mid] <  rotateArray[high])
                high = mid;
            else if (rotateArray[mid] > rotateArray[high])
                low = mid + 1;
            else
                high--;
        }
        return rotateArray[low];
    }
};

7. 斐波那契数

思路

注意不要用递归，因为递归有很多的重复计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int Fibonacci(int n) {
        if (n == 0) return 0;
        if (n <= 2) return 1;
        int last_one = 1, last_two = 1, res = 0;
        for (int i=2; i<n; ++i){
            res = last_one + last_two;
            last_two = last_one;
            last_one = res;
        }
        return res;
    }
};

8. 跳台阶

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int jumpFloor(int number) {
        int last_one = 1, last_two = 1;
        for (int i=2; i<=number; ++i){
            int t = last_one;
            last_one = last_one + last_two;
            last_two = t;
        }
        return last_one;
    }
};

9. 变态跳台阶

题目大意

每次可以跳1-n级台阶，问跳到n级台阶，一共有多少种跳法。

思路

列举n的几种情况可知，每次都是前一次的两倍的种数。

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    int jumpFloorII(int number) {
        int last = 1;
        for (int i=2; i<=number; ++i){
            last *= 2;
        }
        return last;
    }
};

10. 矩形覆盖

题目大意

使用n个2 1的小矩形覆盖2 n的大矩形，一共有多少种方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int rectCover(int number) {
        if (number == 0) return 0;
        if (number == 1) return 1;
        int last_one = 1, last_two = 1, res = 0;
        for (int i=2; i<=number; ++i){
            res = last_one + last_two;
            last_two = last_one;
            last_one = res;
        }
        return res;
    }
};

11. 二进制中1的个数

题目大意

给定一个32位无符号整数，求该整数二级制形式1的个数。

思路

遍历每一位，记录1的个数即可。

不要使用除操作，耗时较久，使用移位和与操作。

如果是有符号整数，可能会导致循环无法结束，可以左移1来遍历。

n & (n-1)的操作能够将最右边的1变为0，可以将所有的1都变为0，需要的次数即为1的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int hammingWeight(uint32_t n) {
        unsigned int sum = 0;
        while (n){
            if (n & 1)
                ++sum;
            n = n >> 1;
        }
        return sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int hammingWeight(uint32_t n) {
        unsigned int sum = 0;
        while (n){
            ++sum;
            n = (n-1) & n;
        }
        return sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

// consider signed int
class Solution {
public:
    int hammingWeight(uint32_t n) {
        unsigned int sum = 0, flag = 1;
        while (flag){
            if (flag & n)
                ++sum;
            flag = flag << 1;
        }
        return sum;
    }
};

12. 数的整数次方

题目大意

实现标准库中的pow运算。

思路

考虑一些边界条件以及优化

  1. 指数为负的情况；
  2. 底为零指数为负的情况，不能做除法；
  3. int的指数变负为正时，考虑最大的负数变为整数会越界；
  4. 提高效率，将$2^{2k+1}$装换为$2^k$的平方乘2
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

class Solution {
public:
    double myPow(double x, int n) {
        // float和double类型的比较不能直接比较
        // 考虑底为零的情况
        if ((x - 0.0) < 0.0000001 && (x - 0.0) > -0.000000001)
            return x;
        double res = 1.0;
        // 考虑为负的情况
        if (n < 0){
            x = 1 / x;
            // 考虑越界
            if (n == INT_MIN){
                res *= x;
                n += 1;
            }
            n = -n;
        }
        while (n){
            // & 和 移位运算替代取余和除法
            if (n & 1)
                res *= x;
            n >>= 1;
            x *= x;
        }
        return res;
    }
};

13. 使得数组的奇数位于偶数前面

题目大意

给定一个数组，调整数的顺序，使得偶数都在奇数后面，且奇数和偶数内部的相对位置不变。

思路

遍历数组，将两个奇数之间的偶数往后挪动一个位置，挪出的位置放置后一个奇数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        if (array.size() <= 1) return;
        for (int i=0; i!=array.size(); ++i){
            // 如果是偶数奇数的情况，讲两个奇数之间的偶数往后移动一位，放置奇数
            if (i!=0 && (array[i]&1) && !(array[i-1]&1)){
                int tmp = array[i], j;
                for (j=i; j>0 && !(array[j-1]&1); --j){
                    array[j] = array[j-1];
                }
                array[j] = tmp;
            }
        }
    }
};

14. 链表中的倒数第k个结点

思路

使用快慢指针，对于k越界情况的处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if (pListHead == NULL) return NULL;
        ListNode* fast = pListHead, *low = pListHead;
        for (int i=0; i<k; ++i){
            if (fast)
                fast = fast->next;
            else
                return NULL;
        }
        while (fast){
            low = low->next;
            fast = fast->next;
        }
        return low;
    }
};

15. 翻转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if (pHead == NULL || pHead->next == NULL) return pHead;
        ListNode *p = NULL, *q = pHead, *t = NULL;
        while (q){
            t = q->next;
            q->next = p;
            p = q;
            q = t;
        }
        return p;
    }
};

16. 合并排序链表

思路

如果某条链表已经排序完，剩下链表的合并可以放到while内部也可以放到外面，外面效率更高。

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

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        ListNode fake(0);
        ListNode*cur= &fake;
        while (pHead1 && pHead2){
            if (pHead1->val < pHead2->val){
                cur->next = pHead1;
                pHead1 = pHead1->next;
            }
            else {
                cur->next = pHead2;
                pHead2 = pHead2->next;
            }
            cur = cur->next;
        }
        if (pHead1){
            cur->next = pHead1;
        }
        if (pHead2){
            cur->next = pHead2;
        }
        return fake.next;
    }
};

17. 树的子结构

题目大意

给定两棵二叉树A和B，判断B是不是A的子结构。认为空树不是任意一棵树的子结构。

注意此题和subtree of another tree不同，A的子树B要求B的根节点是A中的某个结点，且叶子结点是A的叶子结点。

子结构只需要在B的结构在A中出现过即可。

思路

遍历A的每个节点作为B的根节点，如果遍历完所有节点仍然没有找到A的子结构是B，那么就返回false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        if (!pRoot1 || !pRoot2) return false;
        if ((!pRoot1 && pRoot2) || (pRoot1 && !pRoot2)) return false;
        return (isSame(pRoot1, pRoot2) || HasSubtree(pRoot1->left, pRoot2) || HasSubtree(pRoot1->right, pRoot2));
    }
private:
    bool isSame(TreeNode* p1, TreeNode* p2){
        if (!p2) return true;
        if ((!p1 && p2) || (p1 && !p2)) return false;
        return (p1->val == p2->val) && isSame(p1->left, p2->left) && isSame(p1->right, p2->right);
    }
};

18. 二叉树的镜像

思路

左子树右子树交换，且左子树和右子树的子树再继续交换。

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    void Mirror(TreeNode *pRoot) {
        if (!pRoot) return;
        TreeNode* t = pRoot->left;
        pRoot->left = pRoot->right;
        pRoot->right = t;
        Mirror(pRoot->left);
        Mirror(pRoot->right);
    }
};

19. 顺时针打印矩阵

题目大意

给定一个二维矩阵，返回顺时针打印的结果。

思路

传入左上角和右下角的坐标，每次打印这一圈的结果。这样一圈一圈的将矩阵打印出来。

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

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        vector<int> result;
        if (matrix.empty()) return result;
        int m = matrix.size(), n = matrix[0].size();
        int x1 = 0, y1 = 0, x2 = m - 1, y2 = n - 1;
        while (x1 <= x2 && y1 <= y2){
            myPrint(matrix, result, x1++, y1++, x2--, y2--);
        }
        return result;
    }
private:
    void myPrint(vector<vector<int> > &matrix, vector<int> &result, int x1, int y1, int x2, int y2){
        for (int i=y1; i<=y2; ++i){
            result.push_back(matrix[x1][i]);
        }
        for (int i=x1+1; i<=x2; ++i){
            result.push_back(matrix[i][y2]);
        }
        if (x2 > x1){
            for (int i=y2-1; i>=y1; --i){
                result.push_back(matrix[x2][i]);
            }
        }
        if (y1 < y2){
            for (int i=x2-1; i>x1; --i){
                result.push_back(matrix[i][y1]);
            }
        }
        
    }
};

20. 包含min函数的栈

题目大意

定义一个栈的数据结构，使得可以以O(1)的时间复杂度得到栈中最小元素是多少。

思路

用一个minStack记录每个位置栈中的最小元素

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

class Solution {
public:
    void push(int value) {
        ss.push(value);
        if (minStack.empty() || value < minStack.top()){
            minStack.push(value);
        }else{
            minStack.push(minStack.top());
        }
    }
    void pop() {
        if (!ss.empty()){
            ss.pop();
            minStack.pop();
        }
    }
    int top() {
        if (!ss.empty()){
            return ss.top();
        }
        return -1;
    }
    int min() {
        if (!minStack.empty()){
            return minStack.top();
        }
        return -1;
    }
private:
    stack<int> ss;
    stack<int> minStack;
};

21. 栈的弹出顺序是否合理

题目大意

给定两个数组，第一个数组表示入栈的顺序，第二个数组表示出栈的顺序。试判断出栈数组是否合理。

思路

模拟出栈过程，如果栈顶元素不是当前出栈元素，则入栈一直到栈顶元素为出栈元素为止；如果入栈元素都入栈了还找不到出栈元素，则不是一个合理的出栈顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> tmp;
        int index = 0;
        for (int i=0; i!=popV.size(); ++i){
            while (index < popV.size() && (tmp.empty() || tmp.top() != popV[i])){
                tmp.push(pushV[index++]);
            }
            if (!tmp.empty() && tmp.top()==popV[i])
                tmp.pop();
            else
                return false;
        }
        return true;
    }
};

22. 层次遍历二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    vector<int> PrintFromTopToBottom(TreeNode* root) {
        vector<int> res;
        if (root == NULL) return res;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()){
            int k = q.size();
            for (int i=0; i<k; ++i){
                TreeNode* t = q.front();
                q.pop();
                res.push_back(t->val);
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
        }
        return res;
    }
};

23. 判断是否是合法的搜索二叉树后序遍历序列

题目大意

给定一个序列，判断是否是合法的搜索二叉树的后序遍历序列。

思路

根据后序找到根节点，判断左子树是否都小于根节点，右子树是否多大于根节点。再递归判断左子树和右子树

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

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if (sequence.empty()) return false;
        int n = sequence.size(), i=0, j=0;
        bool res = true;
        for (; i<n-1; ++i){
            if (sequence[i] > sequence[n-1])
                break;
        }
        j = i;
        for (; j<n-1; ++j){
            if (sequence[j] < sequence[n-1])
                return false;
        }
        if (i > 0){
            vector<int> left(sequence.begin(), sequence.begin()+i);
            res &= VerifySquenceOfBST(left);
        }
        if (i < n-1){
            vector<int> right(sequence.begin()+i+1, sequence.end());
            res &= VerifySquenceOfBST(right);
        }
        return res;
         
    }
};

24. 二叉搜索树与双向链表

题目大意

给定一棵二叉搜索树，将其转换为一个双向链表，要求不能创建新的节点。

思路

  1. 递归，转换为三个节点的二叉搜索树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        TreeNode* last = NULL;
        transfer(pRootOfTree, &last);
        while (last && last->left){
            last = last->left;
        }
        return last;
    }
private:
    void transfer(TreeNode *root, TreeNode **last){
        if (!root) return;
        transfer(root->left, last);
        root->left = *last;
        if (*last){
            (*last)->right = root;
        }
        *last = root;
        transfer(root->right, last);
    }
};

25. 二叉树中和为某一值的路径

题目大意

找出二叉树中所有路径和为给定值的路径，路径的开始和结束分别是是根节点和叶子节点。

思路

递归

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

class Solution {
public:
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int> > result;
        vector<int> tmp;
        if (!root) return result;
        myFindPath(root, expectNumber, result, tmp);
        return result;
    }
private:
    void myFindPath(TreeNode* root, int sum, vector<vector<int> >& res, vector<int>& tmp){
        if (!root) return;
        if (root->val == sum && !root->left && !root->right){
            tmp.push_back(root->val);
            res.push_back(tmp);
            tmp.pop_back();
            return;
        }
        tmp.push_back(root->val);
        if (root->left){
            myFindPath(root->left, sum-root->val, res, tmp);
        }
        if (root->right){
            myFindPath(root->right, sum-root->val, res, tmp);
        }
        tmp.pop_back();
    }
};

26. 复杂链表复制

题目大意

带有random指针的链表的复制

思路

  1. 使用cache记录复制前后节点的对应关系
  2. 插空 拆分法
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

class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        RandomListNode copyHead(0);
        RandomListNode *p1 = pHead, *p2 = &copyHead;
        map<RandomListNode*, RandomListNode*> cache;
        while(p1){
            p2->next = new RandomListNode(p1->label);
            cache[p1] = p2->next;
            p2 = p2->next;
            p1 = p1->next;
        }
        
        p1 = pHead;
        p2 = copyHead.next;
        while(p1){
            if (p1->random){
                p2->random = cache[p1->random];
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        return copyHead.next;
    }
};
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

class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        if (pHead == NULL) return pHead;
        RandomListNode* p = pHead;
        while (p){
            RandomListNode* t = p->next;
            p->next = new RandomListNode(p->label);
            p = p->next;
            p->next = t;
            p = p->next;
        }
        
        RandomListNode *p1 = pHead, *copy = pHead->next, *p2 = copy;
        while(p1){
            if (p1->random){
                p1->next->random = p1->random->next;
            }
            p1 = p1->next->next;
        }
        
        p1 = pHead;
        while(p1){
            p1->next = p2->next;
            p1 = p1->next;
            if (p1){
                p2->next = p1->next;
                p2 = p2->next;
            }
        }
        return copy;
    }
};

27. 字符串全排列

题目大意

  1. 没有重复字符的字符串全排列
  2. 有重复字符的字符串全排列
  3. 没有重复字符的字符全组合(不一定用上所有字符,且不考虑组合之间的字母顺序，如12和21属于同一种)
  4. 有重复字符的字符全组合
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

class Solution {
public:
    vector<string> Permutation(string str) {
        int n = str.size();
        vector<int> visited(n, 0);
        vector<string> res;
        if (n == 0) return res;
        sort(str.begin(), str.end());
        string tmp = "";
        dfs(str, res, visited, tmp);
        return res;
    }
private:
    void dfs(string str, vector<string>& res, vector<int>& visited, string tmp){
        if (tmp.size() == str.size()){
            res.push_back(tmp);
            return;
        }
        for (int i=0; i!=str.size(); ++i){
            if (visited[i] == 1)
                continue;
            if (i!=0 && visited[i-1] == 0 && str[i-1] == str[i])
                continue;
            visited[i] = 1;
            dfs(str, res, visited, tmp+str[i]);
            visited[i] = 0;
        }
    }
};

28. 数组中出现次数超过一半的数

题目大意

如果数组中存在一个数，出现次数超过数组长度的一半，则输出该数；如果不存在则输出0

思路

  1. 计数法
    • 记录当前数出现的次数，如果下一个数与当前数不等，次数则减1
    • 如果存在该数，则最后记录的数就是出现次数超过一半的数
    • 需要遍历一遍数组，判断该数出现的次数
  2. 按位计数法
    • 对每一位进行统计，如果该位出现1的次数超过数组长度的一半，设置最后返回的结果该位为1；
    • 最后判断位计数的结果是否是真的出现了超过数组长度一半的次数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if (numbers.empty()) return 0;
        int num = numbers[0], times = 1;
        for (int i=1; i<numbers.size(); ++i){
            if (times == 0){
                num = numbers[i];
            }
            if (num != numbers[i]){
                times--;
            }else{
                times++;
            }
        }
        times = 0;
        for (int i=0; i<numbers.size(); ++i){
            if (numbers[i] == num)
                times++;
        }
        return times > numbers.size() / 2 ? num : 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int mask = 1, bitCount = 0, res = 0;
        for (int i=0; i<32; ++i){
            for (int j=0; j<numbers.size(); ++j){
                if (numbers[j] & mask){
                    bitCount++;
                }
            }
            if (bitCount > numbers.size()/2){
                res |= mask;
            }
            bitCount = 0;
            mask = mask << 1;
        }
        for (int i=0; i<numbers.size(); ++i){
            if (res == numbers[i])
                bitCount++;
        }
        return bitCount > numbers.size() / 2 ? res : 0;
    }
};

补充

给定一个长度为n的数组，找出数组中出现次数超过n/3的数(https://leetcode.com/problems/majority-element-ii/description/)

29. 最小的k个数

题目大意

经典的题目，找到数组中最小的k个数

思路

  1. 使用最大堆
  2. 使用快排思想的partition(牛客网的IDE很坑爹，k存在=-1的测试样例)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        if (k > input.size()) return res;
        priority_queue<int> q;
        for (int i=0; i<input.size(); ++i){
            q.push(input[i]);
            if (q.size() > k) q.pop();
        }
        for (int i=0; i<k; ++i){
            res.push_back(q.top());
            q.pop();
        }
        return res;
    }
};
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

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        // 略坑，k的输入是可能小于0的，据我观察这个小于0的值就是-1
        // 1. 直接在外面判断 k <= 0
        // 2. 在外面判断k==input.size() 将mid == k-1 改为mid==k也可以通过
        // 因为 k=-1,而mid最小是可以到达-1的，因此可以通过。所以猜测k的最小值是-1
        if (k > input.size() || k <= 0) return vector<int>();
        int mid = 0, n = input.size();
        int low = 0, high = n - 1;
        while (1){
            mid = partition(input, low, high);
            if (mid == k-1){
                break;
            }else if (mid < k-1){
                low = mid + 1;
            }else{
                high = mid - 1;
            }
        }
        return vector<int>(input.begin(), input.begin()+k);
    }
private:
    int partition(vector<int> &nums, int low, int high){
        int t = nums[low];
        while (low < high){
            while (low < high && nums[high] > t) high--;
            if (low < high){
                nums[low++] = nums[high];
            }
            while (low < high && nums[low] < t) low++;
            if (low < high){
                nums[high--] = nums[low];
            }
        }
        nums[low] = t;
        return low;
    }
};

30. 连续子数组的最大和

给定一个有正有负的整数数组，要求连续子数组的最大和是多少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int result = INT_MIN, sum = 0;
        for (int i=0; i<array.size(); ++i){
            if (sum > 0){
                sum += array[i];
            }else{
                sum = array[i];
            }
            result = max(result, sum);
        }
        return result;
    }
};

31. 从1到n整数中1出现的次数

题目大意

统计从1到n整数中1出现的次数。

思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        int base = 1, a = 0, b = 0;
        int res = 0;
        for (; base<=n; base *= 10){
            a = n / base;
            b = n % base;
            res += (a + 8) / 10 * base + (a % 10 == 1 ? b+1 : 0);
        }
        return res;
    }
};

32. 将数组的数拼接成最小的数

题目大意

将数组中的数拼接组成一个数，要求返回数字形式最大的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

bool cmp(int a, int b){
    return to_string(a) + to_string(b) < to_string(b) + to_string(a);
}
class Solution {
public:
    string PrintMinNumber(vector<int> numbers) {
        sort(numbers.begin(), numbers.end(), cmp);
        string result = "";
        for (int i=0; i<numbers.size(); ++i){
            result += to_string(numbers[i]);
        }
        return result;
    }
};

33. 计算从小到大顺序的第n个丑数

题目大意

丑数定义：只包含质因子 2、3、5的数。默认认为1是第一个丑数

思路

新的丑数 肯定是某个丑数 乘以2 或 乘以3 或 乘以5的结果，所以记录乘2、乘3、乘5的在丑数序列中的位置，每次取得最小的作为新的丑数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if (index < 1) return 0;
        vector<int> cache(index);
        cache[0] = 1;
        int index2 = 0, index3 = 0, index5 = 0;
        for (int i=1; i<index; ++i){
            cache[i] = min(cache[index2] * 2, min(cache[index3] * 3, cache[index5] * 5));
            if (cache[i] == cache[index2] * 2) index2++;
            if (cache[i] == cache[index3] * 3) index3++;
            if (cache[i] == cache[index5] * 5) index5++;
        }
        return cache[index-1];
    }
};

34. 第一次只出现一次的字符

题目大意

找到字符串中第一次只出现一次的字符

思路

先统计字符串中每个字符出现的次数，再重新遍历字符串，第一个字符出现次数为1的字符即为所求字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        map<char, int> cache;
        for (int i=0; i!=str.size(); ++i){
            cache[str[i]]++;
        }
        for (int i=0; i!=str.size(); ++i){
            if (cache[str[i]] == 1)
                return i;
        }
        return -1;
    }
};

35. 数组中的逆序对

题目大意

给定一个数组，统计数组中的逆序对数量，一个逆序对定义为：后面的数比前面的数小则成为一对逆序对。

思路

普通思路是遍历整个数组，每次都会去和前面的每个数比较，在比较的过程中记录逆序对的个数。该方法的时间复杂度是 $O(n^2)$

使用归并排序的方法，在归并的过程中，统计逆序对个数。因为归并排序时，前后两个数组是有序的，所以当前一个数组的某个数比后一个数组某个数大时，那么后一个数组该数以及该数之前的数都可以构成逆序对，可以快速进行计算。时间复杂度为 $O(nlogn)$

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

class Solution {
public:
    int InversePairs(vector<int> data) {
        int n = data.size();
        vector<int> tmp(n, 0);
        return mergeSort(data, tmp, 0, n) % 1000000007;
    }
private:
    long mergeSort(vector<int> &data, vector<int> &tmp, int s, int e){
        // 如何tmp不使用引用就会超时，不懂是为什么
        // 在每次申请临时tmp时，申请e-s长度的tmp而不是data.size()长度的tmp即可通过
        // 可能是因为data太大的原因。
        // 其实也是，能复用tmp就尽量复用吧，复制耗时比较多
        int length = e - s, m = 0;
        long left = 0, right = 0, count = 0;
        if (length > 1){
            m = s + (e - s) / 2;
            left = mergeSort(data, tmp, s, m);
            right = mergeSort(data, tmp, m, e);
             
            int s1 = m-1, s2 = e-1, cur = e-1;
            //vector<int> tmp(length, 0);
            while (s1 >= s && s2 >= m){
                if (data[s1] > data[s2]){
                    count += s2 - m + 1;
                    tmp[cur--] = data[s1--];
                }else
                    tmp[cur--] = data[s2--];
            }
            while (s1 >= s)
                tmp[cur--] = data[s1--];
            while (s2 >= m)
                tmp[cur--] = data[s2--];
            for (int i=s; i!=e; ++i)
                data[i] = tmp[i];
        }
        return left + right + count;
    }
};

36. 两个链表的第一个公共节点

题目大意

给定两个链表，找到链表的第一个公共节点

思路

将两个链表各自的首尾相连，各自在各自的链表上前进，当两个指针相遇时，就是第一个公共节点。

需要判断是否有公共部分：

  1. 提前在外面判断，即判断两个链表最后一个节点是否相同即可
  2. 在while内部判断，需要进行两次判断，一次判断是否是第一个公共节点，一个判断是否存在公共节点，我们假设在两个链表后面插入一个空节点，空节点相当于两条链表的公共节点，如果相遇在空节点上，则没有公共节点。
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

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if (pHead1 == NULL || pHead2 == NULL)
            return NULL;
        ListNode *low = pHead1, *high = pHead2;
        while (low != high){
            low = low->next;
            high = high->next;
            if (low == high) return low; // 如果相遇到为空的点，那么两个链表不存在公共节点
            // 空节点说明到达了尾部，要跳过空节点，进入到头节点
            // 注意，不能将该步骤移到while的开始部分，while需要两次判断low和high是否相等
            // 第一次是判断是不是公共节点，第二次是判断是不是有公共节点
            if (low == NULL)
                low = pHead1;
            if (high == NULL)
                high = pHead2;
        }
        return low;
    }
};

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if (!pHead1 || !pHead2) return NULL;
        ListNode *p1 = pHead1, *p2 = pHead2;
        while(p1->next){
            p1 = p1->next;
        }
        while (p2->next){
            p2 = p2->next;
        }
        if (p1 != p2) return NULL;
         
        p1 = pHead1;
        p2 = pHead2;
        while (p1 != p2){
            if (p1->next){
                p1 = p1->next;
            }else{
                p1 = pHead1;
            }
            if (p2->next){
                p2 = p2->next;
            }else{
                p2 = pHead2;
            }
        }
        return p1;
    }
};

37. 数字在排序数组中出现的次数

题目大意

排序数组，很容易就想到用二分法。根据二分法的判断条件不同，使得最后high指针分别停留在数字区间的两端，这样将两次的high指针指向的位置相减就是区间数字的个数。

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:
    int GetNumberOfK(vector<int> data ,int k) {
        int low = 0, high = data.size() - 1, mid = 0;
        int start = 0;
        while (low <= high){
            mid = low + (high - low) / 2;
            if (data[mid] < k) low = mid + 1;
            else high = mid - 1;
        }
        start = high;
        low = 0;
        high = data.size() - 1;
        while (low <= high){
            mid = low + (high - low) / 2;
            if (data[mid] <= k) low = mid + 1;
            else high = mid - 1;
        }
        return high - start;
    }
};

38. 二叉树的最大深度

题目大意

二叉树的深度指的就是最大深度；可能也会求二叉树的最小深度。

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    int TreeDepth(TreeNode* pRoot)
    {
        if (!pRoot) return 0;
        if (!pRoot->left) return 1 + TreeDepth(pRoot->right);
        if (!pRoot->right) return 1 + TreeDepth(pRoot->left);
        return 1 + max(TreeDepth(pRoot->left), TreeDepth(pRoot->right));
    }
};

39. 判断一棵树是否为平衡二叉树

题目大意

判断一棵树是否为平衡二叉树。

思路

平衡二叉树的定义：

  1. 左子树和右子树的高度差不超过1
  2. 左子树和右子树也是平衡二叉树

根据概念定义，有两个需要递归判断的部分，一个是左子树和右子树的高度差，一个是左子树和右子树是不是均为平衡二叉树。

在判断左子树和右子树高度时，可以考虑使用缓存，因为有大量的重复计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if (!pRoot) return true;
        int left = getHeight(pRoot->left);
        int right = getHeight(pRoot->right);
        return abs(left - right) <= 1 && IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);
    }
private:
    int getHeight(TreeNode* root){
        if (!root) return 0;
        if (cache.find(root) != cache.end()){
            return cache[root];
        }
        int left = getHeight(root->left);
        int right = getHeight(root->right);
        int result = max(left, right) + 1;
        cache[root] = result;
        return result;
    }
    map<TreeNode*, int> cache;
};

40. 数组中只出现一次的数字

题目大意

给定一个数组，只有两个数字出现过一次，其他数字都出现过两次，找出只出现一次的两个数。

思路

将数组分为两个部分，一部分包含其中一个只出现过一次的数字，这样可以通过异或的方式得到只出现一次的数字。

找到两个只出现过一次的数字的不同的位，根据该不同的位去划分两个数组即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        int flag = 0;
        for (int i=0; i<data.size(); ++i){
            flag ^= data[i];
        }
        flag = flag & (flag ^ (flag - 1));
        for (int i=0; i<data.size(); ++i){
            if (data[i] & flag){
                *num1 ^= data[i];
            }else{
                *num2 ^= data[i];
            }
        }
    }
};

41. 和为S的连续正序列

题目大意

给定一个整数，返回所有连续和为该整数的正整数序列。

思路

连续整数序列因为是对称的，所以序列和可以简化为 N * 平均值。

序列长度为偶数时，平均值的小数位是0.5((sum % n) * 2 == n)，当序列长度为奇数时，平均值为整数(sum % n == 0)。

根据序列长度可以找到序列的第一个整数是多少。

遍历可能的序列长度，[2, sum / 2 + 1](3是特殊情况，所以是闭区间)

根据求和公式 $s = (1+n) * \frac{n}{2}$ 得到 $n = \sqrt{2n}$，所以区间为[2, $\sqrt{2n}$]

代码

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

class Solution {
public:
	vector<vector<int> > FindContinuousSequence(int sum) {
		vector<vector<int> > res;
		vector<int> tmp;
		for (int i = sum / 2 + 1; i >= 2 ; --i) {
			if (i & 1)
				tmp = is_odd(sum, i);
			else
				tmp = is_even(sum, i);
			if (!tmp.empty())
				res.push_back(tmp);
		}
		return res;
	}
private:
	vector<int> is_odd(int sum, int i) {
		vector<int> res;
		float mid = sum / float(i);
		if (sum / i - mid < 0.000000001 && sum / i - mid > -0.0000000001) {
			int start = sum / i - (i - 1) / 2;
			if (start <= 0)
				return res;
			for (int k = 0; k < i; ++k)
				res.push_back(start++);
		}
		return res;
	}

	vector<int> is_even(int sum, int i) {
		vector<int> res;
		float mid = sum / float(i);
		if (mid - sum / i - 0.5 < 0.0000000001 && mid - sum / i - 0.5 > -0.0000000001) {
			int start = sum / i - i / 2 + 1;
			if (start <= 0)
				return res;
			for (int k = 0; k < i; ++k)
				res.push_back(start++);
		}
		return res;
	}
};
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

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int> > result;
        if (sum <= 2) return result;
        int start;
        // 优化1：根据求和公式计算上边界
        for (int count=sqrt(2*sum); count>=2; --count){
            vector<int> tmp;
            // 优化2：精简每次的判断条件
            if (count % 2 && (sum % count) == 0){
                start = sum / count - count / 2;
            }
            else if ((count % 2) == 0 && (sum % count) * 2 == count){
                start = sum / count - count / 2 + 1;
            }
            else 
                continue;
            if (start <= 0)
                continue;
            for (int i=0; i<count; ++i){
                tmp.push_back(start++);
            }
            result.push_back(tmp);
        }
        return result;
    }
};

42. 和为S的两个数

题目大意

给定一个排序数组和一个整数sum，要求乘积最小的和为sum的两个数

思路

和相同的两个数，两个数字差值越大乘积越小，所以直接low、high指针从头尾开始找，找到的第一对满足条件的两个数则为最终结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        if (array.empty()) return vector<int>();
        vector<int> res(2);
        int low = 0, high = array.size()-1;
        while (low < high){
            if (array[low] + array[high] == sum){
                res[0] = array[low++];
                res[1] = array[high--];
                break;
            }else if (array[low] + array[high] < sum){
                low++;
            }else{
                high--;
            }
        }
        return res[0] + res[1] == sum ? res : vector<int>();
    }
};

43. 左旋转字符串

题目大意

给定一个字符串，向左旋转n位。如给定xyzabc，左旋转3位得到abcxyz

思路

和反转词序的题思路相同，可以将xyz部分和abc部分做了一次翻转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    string LeftRotateString(string str, int n) {
        int len = str.size();
        if (len <= n) return str;
        reverseStr(str, 0, n-1);
        reverseStr(str, n, len-1);
        reverseStr(str, 0, len-1);
        return str;
    }
private:
    void reverseStr(string &str, int s, int e){
        char t;
        while (s < e){
            t = str[s];
            str[s++] = str[e];
            str[e--] = t;
        }
    }
};

44. 翻转单词顺序

思路

先翻转单词内部的字母顺序，再翻转整个字符串的顺序

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

class Solution {
public:
    string ReverseSentence(string str) {
        int cur1 = 0, cur2 = 0, last = 0;
        int len = str.size();
        int count = 0;
        while(cur2 < len){
            if (str[cur2] == ' '){
                cur2++;
                continue;
            }
            if (count > 0) str[cur1++] = ' ';
            last = cur1;
            while (cur2 < len && str[cur2] != ' '){
                str[cur1++] = str[cur2++];
            }
            count++;
            reverseStr(str, last, cur1-1);
        }
        reverseStr(str, 0, len-1);
        return str;
    }
private:
    void reverseStr(string &str, int s, int e){
        while (s < e){
            char t = str[s];
            str[s++] = str[e];
            str[e--] = t;
        }
    }
};

45. 扑克牌顺子

题目大意

给定一些牌，0可以表示任意一张牌，问这些牌是否能凑成顺子。

思路

考虑0的个数，以及需要填充的gap的个数，判断0是否能填充这些gap

如果有两种非零牌相同，那么必然无法凑成顺子了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        if (numbers.empty()) return false;
        sort(numbers.begin(), numbers.end());
        int zero=0, gap=0;
        for (int i=0; i!=numbers.size(); ++i){
            if (numbers[i] == 0) zero++;
            if (i!=0 && numbers[i-1] != 0){
                if (numbers[i-1] == numbers[i])
                    return false;
                else
                    gap += numbers[i] - numbers[i-1] - 1;
            }
        }
        return zero >= gap;
    }
};

46. 约瑟夫环

题目大意

0-n-1个人围成一个圈，从0喊到m-1，m-1的人被淘汰。然后从下一个人开始继续，请问最后活下来的是哪个人

思路

推导

f(n,m)表示n个小朋友，第m个人出局剩下的最后一个人;g(n-1, m)表示淘汰了f(n,m)中第m个人后按照规则剩下的那个人；
f(n,m) = g(n-1,m) = (f(n-1, m) + m) % n 下标差了m
递推公式f(n,m) = (f(n-1, m) + m)% n

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if (n == 0 || m == 0) return -1;
        int last = 0;
        for (int i=2; i<=n; ++i){
            last = (last + m) % i;
        }
        return last;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if (n == 0 || m == 0) return -1;
        map<int, int> cache;
        for (int i=0; i<n-1; ++i){
            cache[i] = i+1;
        }
        cache[n-1] = 0;
        
        int cur = 0, last = 0;
        for (int i=0; i<n-1; ++i){
            for (int j=1; j<m; ++j){
                last = cur;
                cur = cache[cur];
            }
            cache[last] = cache[cur];
            cur = cache[last];
        }
        return cur;
    }
};

47. 1+2+…+n

题目大意

求1+2…+n，要求不能使用循环、乘除和判断语句

思路

可以考虑使用递归，用短路原则结束递归。

1
2
3
4
5
6
7
8

class Solution {
public:
    int Sum_Solution(int n) {
        n && (n += Sum_Solution(n-1));
        return n;
    }
};

48. 不用加减乘除做加法

题目大意

在不用+、-、*、\的基础上实现加法操作

思路

两个数num1和num2相加

  1. n1 = num1&num2的结果表示两个数该位上都是1，则需要进位，可以用左移操作替代
  2. n2 = num1^num2的结果表示两个数位上只有一个位置是1
  3. n1 & n2 如果为零，说明不需要再进位了，那么n1 | n2就是最终求和的结果；否则一直继续1和2步骤
1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    int Add(int num1, int num2)
    {
        int carry = 0;
        while (num1 & num2){
            carry = (num1 & num2) << 1;
            num1 = num1 ^ num2;
            num2 = carry;
        }
        return num1 | num2;
    }
};

49. atoi

题目大意

atoi，不是合法数值的返回0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int StrToInt(string str) {
        if (str.empty()) return 0;
        int res = 0, cur = 0, sign = 1;
        while(cur < str.size() && str[cur] == ' ') cur++;
        if (cur < str.size() && (str[cur] == '+' || str[cur] == '-')){
            sign = (str[cur] == '-') ? -1 : 1;
            cur++;
        }
        while (cur < str.size()){
            if (str[cur]<'0' || str[cur]>'9') return 0;
            int tmp = str[cur] - '0';
            if (sign == 1 && (res > INT_MAX / 10 || res == INT_MAX / 10 && tmp >= INT_MAX % 10))
                return INT_MAX;
            if (sign == -1 && (res > INT_MAX / 10 || res == INT_MAX / 10 && tmp >= INT_MAX % 10 + 1))
                return INT_MIN;
            res = res * 10 + tmp;
            cur++;
        }
        return res * sign;
    }
};

50. 数组中的重复数字

题目大意

在一个长度为n的数组中，数字的大小都在0到n-1之间。其中有若干个数字是重复的，重复的次数并不知道。

思路

注：只有一个重复数字的数组，找到重复数字的方法总结：

  1. 如果可以改变原数组
    • 排序
    • 做标记
  2. 如果可以使用额外的空间
    • hash
  3. 既要求不能改变原数组，又要求空间复杂度O(1)，且时间复杂度小于O(n^2)
    • 判断循环链表的入口
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    bool duplicate(int numbers[], int length, int* duplication) {
        // we can't use minus to flag 0
        int cur = 0, index = 0;
        for (int i=0; i<length; ++i){
            index = numbers[i];
            if (index >= length)
                index -= length;
            if (numbers[index] >= length){
                *duplication = index;
                return true;
            }
            cur = index;
            numbers[index] = length + numbers[index];
        }
        return false;
    }
};

51. 构建乘积数组

题目大意

给定一个数组A，返回数组B，B[i] = A[1] A[2]…A[i-1] A[i+1]…

不可以使用除法。

思路

如果暴力的话就是$n^2$复杂度了。可以考虑两个数组，一个数组存储左边所有数的乘积，一个数组存储右边所有数的乘积，这样两个数组对应位置相乘就是最后的B数组了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
 vector<int> multiply(const vector<int>& A) {
      int n = A.size();
      if (n <= 1) return A;
      vector<int> forward(n), backward(n);
      forward[0] = 1;
      backward[n - 1] = 1;
      for (int i = 1; i < n; ++i) {
           forward[i] = forward[i - 1] * A[i-1];
           cout << forward[i] << " ";
      }
      for (int i = n - 2; i >= 0; --i) {
           backward[i] = backward[i + 1] * A[i+1];
      }
      for (int i = 0; i < n; ++i)
           forward[i] *= backward[i];
      return forward;
 }
};

52. 正则表达式匹配

题目大意

匹配符号包括’.’和’*’,分别匹配任意字符和他之前的字符匹配任意次(包括0次)

思路

暴力匹配？？？

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

class Solution {
public:
    bool match(char* str, char* pattern)
    {
        char tmp;
        while (*str != '\0'){
            // 如果当前是.或者相等，则同时++
            if (*pattern == '.' || *str == *pattern){
                tmp = *pattern;
                str++;
                pattern++;
                continue;
            }
            // 如果不等，但是当前pattern是*，则判断是不是和前面一个相同或者是不是前一个pattern是.
            if (*pattern == '*'){
                if (tmp == '.' || *str == tmp){
                    tmp = *str;
                    str++;
                    continue;
                }else{
                    pattern++;
                    continue;
                }
            }
            // 如果当前就是匹配不上，判断下一个是不是*，如果是则跳过两个pattern
            if (*(pattern+1) == '*'){
                pattern = pattern + 2;
            }else return false;
        }
        if (*pattern == '\0' || (*(pattern+1) == '*' && *(pattern+2) == '\0') || *pattern=='*') return true;
        return false;
    }
};

53. 表示数值的字符串

题目大意

判断一个字符串是否能表示数字，例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。 但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。

思路

判断+- Ee .出现的位置是否合法，具体见code

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

class Solution {
public:
    bool isNumeric(char* string)
    {
        int cursor = 0;
        int eCount = 0, dotCount = 0;
        while (*string != '\0'){
            if (*string == '+' || *string =='-'){
                // +- 只会出现在开头或者eE的后面
                if (!(cursor == 0 || (*(string-1) == 'e' || *(string-1) == 'E')))
                    return false;
            }
            else if ((*string == 'e') || (*string == 'E')){
                // eE 不会出现在开头，不能同时出现两次，且不能出现在最后
                if (cursor != 0 && eCount == 0 && *(string+1) != '\0'){
                    eCount++;
                }else
                    return false;
            }
            else if (*string == '.'){
                // . 不会出现在开头，不能出现两次，不能出现在eE后面
                if (cursor != 0 && dotCount == 0 && eCount == 0){
                    dotCount++;
                }else
                    return false;
            }
            // 不能出现除了 +- eE . 数字之外的字符
            else if (*string > '9' || *string < '0') return false;
            cursor++;
            string++;
        }
        return true;
    }
};

54. 字符流中第一个不重复的字符

题目大意

两个接口，一个接口可以向字符流中插入字符，一个接口返回当前字符流中第一个不重复的字符。

思路

两个要求，我们得知道字符流来的顺序，第二我们得知道哪些字符已经不是出现两次了。

map存储字符出现的次数，queue存储字符流，队头是第一个不重复的字符。

每当字符流来的时候，我们需要将队头出现不止一次的字符pop掉直到维持队头是第一个不重复的字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution
{
public:
  //Insert one char from stringstream
    void Insert(char ch)
    {
        count[ch]++;
        q.push(ch);
        while (!q.empty() && count[q.front()] > 1) q.pop();
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
        return q.empty() ? '#' : q.front();
    }
private:
    map<char, int> count;
    queue<char> q;
};

55. 链表中环的入口节点

题目大意

给定一个链表，如果有环，返回环的入口节点，否则输出null。

思路

经典题，但是low和high必须同时从头节点开始，且判断是否有环时 while的条件不能是 low!=high

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:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        if (pHead == NULL) return pHead;
        ListNode* low = pHead, *high = pHead;
        while (high){
            low = low->next;
            high = high->next;
            if (high) high = high->next;
            if (low == high) break;
        }
        if (high == NULL) return NULL;
        low = pHead;
        while (low != high){
            low = low->next;
            high = high->next;
        }
        return low;
    }
};

56. 删除排序链表中的重复节点

题目大意

给定一个排序链表，删除链表中的重复节点。比如1->2->3->3->4->5的结果是1->2->5.

思路

新建头节点

  1. 如果cur和cur->next相等，则一直删除重复节点直到不等为止，然后last指向第一个不等节点，继续循环
  2. 如果不等，则last指向当前节点，并将last和cur指针向后移动一位。
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

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        ListNode head(0);
        head.next = pHead;
        ListNode *last = &head, *cur = pHead, *t;
        while (cur && cur->next){
            if (cur->val == cur->next->val){
                int val = cur->val;
                while (cur && cur->val == val){
                    t = cur;
                    delete cur;
                    cur = t->next;
                }
                last->next = cur;
            }else{
                last = cur;
                cur = cur->next;
            }
        }
        return head.next;
    }
};

57. 二叉树的下一个节点

题目大意

给定一个二叉树的某个节点，返回中序遍历的后一个节点。每个节点不仅有左子树、右子树，还有指向父节点的指针。

思路

是否有右子树

  1. 有，则后一个节点是右子树的最深处的左节点
  2. 没有
    • 如果是父节点的左子树，那么父节点就是后一个节点
    • 如果没有父节点，那么该节点是中序遍历的最后一个节点
    • 如果是父节点的右子树，找到父节点的父节点的右子树，如果没有右子树就继续向上找，直到找到父节点的右子树为止，否则该节点是中序遍历的最后一个节点
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

/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
        
    }
};
*/
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
        if (!pNode) return pNode;
        if (!pNode->right){
            if (!pNode->next) return pNode->next;
            if (pNode->next->left == pNode) return pNode->next;
            pNode = pNode->next;
            while (pNode){
                if (pNode->next && pNode == pNode->next->left)
                    return pNode->next;
                if (!pNode->next) return pNode->next;
                pNode = pNode->next;
            }
        }
        TreeLinkNode *cur = pNode->right;
        while (cur && cur->left){
            cur = cur->left;
        }
        return cur;
    }
};
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

class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
        // 如果NULL
        if (!pNode) return pNode;
        // 如果为根节点或者有右子树，则一定是返回右子树的最左边的子节点
        if (!pNode->next || pNode->right){
            TreeLinkNode *t = pNode->right;
            while (t && t->left){
                t = t->left;
            }
            return t;
        }
        // 如果是父节点的左节点，直接返回父节点
        if (pNode == pNode->next->left){
            return pNode->next;
        // 如果是父节点的右节点，需要一直往上找到第一个父节点，父节点的儿子是左节点
        }else{
            while (pNode->next->next){
                if (pNode->next == pNode->next->next->left)
                    return pNode->next->next;
                pNode = pNode->next;
            }
            return NULL;
        }
        
    }
};

58. 判断二叉树是否对称

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
        if (!pRoot) return true;
        return isSame(pRoot->left, pRoot->right);
    }
private:
    bool isSame(TreeNode *left, TreeNode *right){
        if (!left && !right) return true;
        if (!left || !right) return false;
        return left->val == right->val && isSame(left->left, right->right) && isSame(left->right, right->left);
    }

};

59. 之字形打印字符串

思路

  1. reverse 耗时
  2. 直接下标索引
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

class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int> > res;
        if (!pRoot) return res;
        queue<TreeNode*> q;
        q.push(pRoot);
        TreeNode* cur;
        int flag = 1;
        while (!q.empty()){
            vector<int> tmp;
            int k = q.size();
            for (int i=0; i<k; ++i){
                cur = q.front();
                q.pop();
                tmp.push_back(cur->val);
                if (cur->left) q.push(cur->left);
                if (cur->right) q.push(cur->right);
            }
            if (flag % 2){
                res.push_back(tmp);
            }else{
                reverse(tmp.begin(), tmp.end());
                res.push_back(tmp);
            }
            flag++;
        }
        return res;
    }
     
};
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

class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int> > result;
        if (!pRoot) return result;
        queue<TreeNode*> q;
        q.push(pRoot);
        TreeNode *tmp;
        int k = 0, isOdd = 1;
        while (!q.empty()){
            k = q.size();
            vector<int> t(k);
            for (int i=0; i<k; ++i){
                tmp = q.front();
                q.pop();
                if (isOdd){
                    t[i] = tmp->val;
                }else{
                    t[k-i-1] = tmp->val;
                }
                if (tmp->left) q.push(tmp->left);
                if (tmp->right) q.push(tmp->right);
            }
            result.push_back(t);
            isOdd = isOdd ^ 1;
        }
        return result;
    }
    
};

60. 层次遍历二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
        vector<vector<int> > Print(TreeNode* pRoot) {
            vector<vector<int> > result;
            if (!pRoot) return result;
            queue<TreeNode*> q;
            q.push(pRoot);
            while (!q.empty()){
                int k = q.size();
                vector<int> t;
                for (int i=0; i<k; ++i){
                    TreeNode* tmp = q.front();
                    q.pop();
                    t.push_back(tmp->val);
                    if (tmp->left) q.push(tmp->left);
                    if (tmp->right) q.push(tmp->right);
                }
                result.push_back(t);
            }
            return result;
        }
    
};

61. 序列化二叉树

题目大意

序列化、反序列化一棵二叉树

思路

  1. 层次遍历序列化

  • 序列化

    • 层次遍历，相邻节点用,隔开，空节点用#表示。

  • 反序列化

    • 新建一个节点塞进队列中，依次读取序列化结果，读取出的两个就是队列头部节点的左子树和右子树
  1. 递归的前序遍历

  • 序列化

    • 序列化当前节点，左节点、右节点

  • 反序列化

    • 反序列化当前节点，左子树和右子树
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// 层次遍历
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    char* Serialize(TreeNode *root) {    
        if (root == NULL)
            return NULL;
        string str;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()){
            int k = q.size();
            for (int i=0; i<k; ++i){
                TreeNode *tmp = q.front();
                q.pop();
                if (tmp == NULL)
                    str += '#';
                else{
                    str += to_string(tmp->val);
                    q.push(tmp->left);
                    q.push(tmp->right);
                }
                str += ',';
            }
        }
        int length = str.size();
        char *res = new char[length+1];
        for (int i=0; i<length; ++i){
            res[i] = str[i];
        }
        res[length] = '\0';
        return res;
    }
    TreeNode* Deserialize(char *str) {
        if (str == NULL) return NULL;
        TreeNode* res=NULL;
        queue<TreeNode*> q;
        while (*str != '\0'){
            if (q.empty()){
                res = new TreeNode(get(&str));
                q.push(res);
                str++;
                continue;
            }
            TreeNode *root = q.front(), *left = NULL, *right = NULL;
            q.pop();
            if (*str != '#'){
                left = new TreeNode(get(&str));
                q.push(left);
            }else
                str++;
            str++;
            if (*str != '#'){
                right = new TreeNode(get(&str));
                q.push(right);
            }else
                str++;
            str++;
            root->left = left;
            root->right = right;
        }
        return res;
    }
private:
    int get(char **p){
        int res = 0;
        while (**p != ','){
            res = 10 * res + (**p - '0');
            (*p)++;
        }
        return res;
    }
};
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

class Solution {
public:
    char* Serialize(TreeNode *root) {    
        if (root == NULL) return NULL;
        string str;
        mySerialize(root, str);
        int length = str.size();
        char *res = new char[length + 1];
        for (int i=0; i<length; ++i)
            res[i] = str[i];
        res[length] = '\0';
        return res;
    }
    TreeNode* Deserialize(char *str) {
        if (str == NULL) return NULL;
        TreeNode *res = myDeserialize(&str);
        return res;
    }
private:
    void mySerialize(TreeNode *root, string &str){
        if (root == NULL){
            str += '#';
            //str += ',';
            return;
        }
        str += to_string(root->val);
        str += ',';
        mySerialize(root->left, str);
        mySerialize(root->right, str);
    }
    TreeNode* myDeserialize(char **cur){
        if (**cur == '#'){
            (*cur)++;
            return NULL;
        }
        int num = 0;
        while (**cur != '\0' && **cur != ','){
            num = 10 * num + (**cur - '0');
            (*cur)++;
        }
        if (**cur == '\0') return NULL;
        if (**cur == ',') (*cur)++;
        TreeNode *root = new TreeNode(num);
        root->left = myDeserialize(cur);
        root->right = myDeserialize(cur);
        return root;
    }
};

62. 二叉搜索树的第k个节点

题目大意

给定一棵二叉搜索树，找到从小到大的第k个节点。

思路

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        if (!pRoot) return NULL;
        TreeNode* res = NULL;
        findK(pRoot, &res, k);
        return res;
    }
private:
    void findK(TreeNode *root, TreeNode **res, int &k){
        if (!root) return;
        findK(root->left, res, k);
        k--;
        if (k == 0){
            *res = root;
            return;
        }
        findK(root->right, res, k);
    }
    
};

63. 数据流中的中位数

题目大意

一个数据流中，求当前数据流的中位数。

思路

  1. 二分法

    • 插入时用二分法查找，维持已有数据流的顺序
    • 获取中位数时，根据已有数据流的长度，索引中位数

  2. 两个优先级队列

    • 思路比较巧妙，使用一个大顶堆，使用一个小顶堆，而大顶堆存中位数前一半的数，小顶堆存储中位数后一半的数；
    • 这样，如果是偶数个数，那么大顶堆和小顶堆堆顶的平均数就是中位数；如果是奇数个数，那么较多的那个堆的堆顶元素就是中位数
    • 每次插入时，均需要调整堆的高度，使得两个堆的高度差最多只差一个
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

class Solution {
public:
    void Insert(int num)
    {
        if (p.empty() || num <= p.top()) p.push(num);
        else q.push(num);
        if (p.size() + 1 == q.size()) {
            p.push(q.top());
            q.pop();
        }
        if (p.size() == q.size() + 2){
            q.push(p.top());
            p.pop();
        }
    }

    double GetMedian()
    { 
        return (p.size() == q.size()) ? (p.top() + q.top()) / 2 : p.top();
    }
private:
    priority_queue<double, vector<double>, less<double>> p;
    priority_queue<double, vector<double>, greater<double>> q;
};

64. 滑动窗口的最大值

题目大意

给定一个数组和一个窗口大小，依次在数组滑动，返回每个窗口的最大值。

思路

  1. 暴力法，暴力滑过各个窗口取得最大值，时间复杂度是O(nk)，每个窗口计算时重复比较了很多数
  2. 堆
    • 用一个堆记录当前值的排序顺序，每滑动一个窗口，往堆中插入一个数，堆顶元素即使当前窗口的最大值
    • 问题在于，如何弹出已经超过该窗口的元素。堆中元素包含下标，如果堆顶元素的小标超过了当前窗口的最小小标值，那么就pop掉。
    • 时间复杂度O(nlogk)
  3. 双端队列
    • 队列中存储的是降序排列的元素，自然队列头部是当前窗口的最大值，如果当前要插入的元素大于尾部数据，则弹出尾部数据，直到找到比该元素大的数插入；
    • 问题在于，如何判断某个元素是否已经超过了该窗口，此时，可以考虑队列中存储下标，如果下标超过了当前窗口的最小下标，那么就需要pop掉；
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

struct cmp{
    bool operator()(pair<int, int> &q, pair<int, int> &p){
        return q.first < p.first;
    }
};
 
class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> res;
        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> q;
        for (int i=0; i<num.size(); ++i){
            q.push(make_pair(num[i], i));
            if (i >= size-1){
                // 因为size是 unsigned int 所以不能为i-size不会小于0，小于0则溢出
                // 所以不能使用 <= i-size 的条件
                while (!q.empty() && q.top().second < i-size+1)
                    q.pop();
                res.push_back(q.top().first);
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> res;
        deque<int> q;
        for (int i=0; i<num.size(); ++i){
            while (!q.empty() && num[q.back()] < num[i]) q.pop_back();
            q.push_back(i);
            while (!q.empty() && q.front() < res.size()) q.pop_front();
            if (i >= size - 1){
                res.push_back(num[q.front()]);
            }
        }
        return res;
    }
};

65. 矩阵中路径

题目大意

给定一个字符矩阵，给定一个字符串，判断是否存在某个路径能够组成该字符串，要求路径不能覆盖重复的位置。

思路

dfs遍历，以矩阵每个节点为开始节点，dfs遍历是否存在路径。用一个visited矩阵记录是否已经走过该节点。

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
 
 class Solution {
public:
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        if (str == NULL || (rows ==0 && cols == 0)) return false;
        vector<vector<char> > maze(rows, vector<char>(cols));
        vector<vector<int> > visited(rows, vector<int>(cols));
        for (int i=0; i<rows; ++i){
            for (int j=0; j<cols; ++j){
                maze[i][j] = *matrix;
                matrix++;
            }
        }
        for (int i=0; i<rows; ++i){
            for (int j=0; j<cols; ++j){
                visited[i][j] = 1;
                if (maze[i][j] == *str && isPath(maze, visited, i, j, str))
                    return true;
                visited[i][j] = 0;
            }
        }
        return false;
    }
private:
    bool isPath(vector<vector<char> > &maze, vector<vector<int> > &visited, int i, int j, char* str){
        if (*(str+1) == '\0'){
            return true;
        }
        for (int k=0; k<4; ++k){
            int x = i + dir[k][0];
            int y = j + dir[k][1];
            if (x >=0 && x < maze.size() && y >= 0 && y < maze[0].size() && visited[x][y]==0 && *(str+1) == maze[x][y]){
                visited[x][y] = 1;
                if (isPath(maze, visited, x, y, str+1))
                    return true;
                visited[x][y] = 0;
            }
        }
        return false;
    }
    int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
};

66. 机器人的运动范围

题目大意

机器人从(0,0)开始，每次可以往上下左右四个方向走动。每次到的位置不能是横坐标和纵坐标的数位之和超过k的位置。求机器人能达到多少格子。

思路

dfs，同时设置sum的条件。

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
 
 class Solution {
public:
    int movingCount(int threshold, int rows, int cols)
    {
        if (threshold < 0) return 0;
        int res = 1;
        vector<vector<int> > visited(rows, vector<int>(cols));
        visited[0][0] = 1;
        calCount(visited, threshold, rows, cols, 0, 0, res);
        return res;
    }
private:
    void calCount(vector<vector<int> > &visited, int threshold, int rows, int cols, int x, int y, int &res){
        for (int d=0; d<4; ++d){
            int xx = x + dir[d][0];
            int yy = y + dir[d][1];
            if (xx >= 0 && xx < rows && yy >= 0 && yy < cols && visited[xx][yy] == 0){
                int sum = 0;
                while (xx) {
                    sum += xx % 10;
                    xx = xx / 10;
                }
                while (yy){
                    sum += yy % 10;
                    yy = yy / 10;
                }
                xx = x + dir[d][0];
                yy = y + dir[d][1];
                visited[xx][yy] = 1;
                if (sum <= threshold){
                    res++;
                    calCount(visited, threshold, rows, cols, xx, yy, res);
                }
            }
        }
    }
    int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
};