细语呢喃

技术改变生活

0%

剑指 Offer题解

发表于 分类于 ， 阅读次数： 评论数：

剑指 Offer的题解，更新中

03. 数组中重复的数字

找出数组中重复的数字。

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

示例 1：

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

限制：

2 <= n <= 100000

方法一：hash表

hash表直接记录即可

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        vector<bool> vis(nums.size(), false);
        for (int num : nums) {
            if (vis[num]) {
                return num;
            }
            vis[num] = true;
        }
        return -1;
    }
};

Python

1
2
3
4
5
6
7
8
class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        vis = [False] * len(nums)
        for num in nums:
            if vis[num]:
                return num
            vis[num] = True
        return None

方法二：直接交换

由于范围为0~n-1，因此可以把nums[i]放到nums[nums[i]]的位置上（交换），相当于方法一的节省空间的版本。

需要注意的是，交换后下标不要+1，需要等到i == nums[i]的时候才+1，才不会漏掉，比如下面的数据i = 0的时候：

1
2
3
   2, 1, 3, 0
=> 3, 1, 2, 0
=> 0, 1, 2, 3

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        for (int i = 0; i < nums.size(); ) {
            if (i == nums[i]) {
                ++i;
                continue;
            }
            if (nums[i] == nums[nums[i]]) {
                return nums[i];
            }
            swap(nums[nums[i]], nums[i]);
        }
        return -1;
    }
};

04. 二维数组中的查找

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

示例:

现有矩阵 matrix 如下：

1
2
3
4
5
6
7
>[
 [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。

限制：

1
2
>0 <= n <= 1000
>0 <= m <= 1000

注意：本题与主站 240 题相同：https://leetcode-cn.com/problems/search-a-2d-matrix-ii/

题解见本博客另一篇文章Search a 2D Matrix II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        for (int i = matrix.size() - 1, j = 0; i >= 0 && j < matrix[i].size(); ){
            if (matrix[i][j] < target) {
                ++j;
            } else if (matrix[i][j] > target){
                --i;
            } else {
                return true;
            }
        }
        return false;
    }
};

05. 替换空格

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

示例 1：

1
2
>输入：s = "We are happy."
>输出："We%20are%20happy."

限制：

1
>0 <= s 的长度 <= 10000

c++稍微麻烦点，就是s[i]为空格push三个字符即可

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string replaceSpace(string s) {
        std::string ans;
        for (std::size_t i = 0; i < s.size(); ++i) {
            if (s[i] == ' ') {
                ans.push_back('%');
                ans.push_back('2');
                ans.push_back('0');
            } else {
                ans.push_back(s[i]);
            }
        }
        return ans;
    }
};

Python:

1
2
3
class Solution:
    def replaceSpace(self, s: str) -> str:
        return s.replace(' ', '%20')

06. 从尾到头打印链表

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

示例 1：

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

限制：

0 <= 链表长度 <= 10000

c++

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> ans;
        for (; head != nullptr; head = head->next) {
            ans.push_back(head->val);
        }
        std::reverse(ans.begin(), ans.end());
        return ans;
    }
};

07. 重建二叉树

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

例如，给出

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

 3
  / \
 9  20
   /  \
  15   7

0 <= 节点个数 <= 5000

同105题

简单的切片：

Python

1
2
3
4
5
6
7
8
9
10
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder or not inorder:
            return None
        
        root = TreeNode(preorder[0])
        index = inorder.index(root.val)
        root.left = self.buildTree(preorder[1 : index + 1], inorder[: index])
        root.right = self.buildTree(preorder[index + 1:], inorder[index + 1:])
        return root

带上下标：

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    TreeNode* buildTree(const vector<int>& preorder, 
                        const vector<int>& inorder,
                        int p_s, int p_e, int i_s, int i_e) {
        if (p_s >= p_e || i_s >= i_e) {
            return nullptr;
        }
        TreeNode* root = new TreeNode(preorder[p_s]);
        int index = std::find(inorder.begin() + i_s, inorder.begin() + i_e, root->val) - inorder.begin();
        int length = index - i_s;
        root->left = buildTree(preorder, inorder, p_s + 1, p_s + length + 1, i_s, index);
        root->right = buildTree(preorder, inorder, p_s + length + 1, p_e, index + 1, i_e);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return buildTree(preorder, inorder, 0, preorder.size(), 0, inorder.size());
    }
};

09. 用两个栈实现队列

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

示例 1：

1
2
3
4
>输入：
>["CQueue","appendTail","deleteHead","deleteHead"]
>[[],[3],[],[]]
>输出：[null,null,3,-1]

示例 2：

1
2
3
4
>输入：
>["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
>[[],[],[5],[2],[],[]]
>输出：[null,-1,null,null,5,2]

提示：

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

队列：先进先出；栈：后进先出

因此要pop队首的时候，只需要把元素丢到另外一个栈里面，就从后进先出变成了“先进先出”了

C++

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 CQueue {
    stack<int> s1;
    stack<int> s2;
public:
    CQueue() {}

    void appendTail(int value) {
        s1.push(value);
    }
    
    int deleteHead() {
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
        if (s2.empty()) {
            return -1;
        }
        int ans = s2.top();
        s2.pop();
        return ans;
    }
};

10- I. 斐波那契数列

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：

F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2 输出：1 示例 2：

输入：n = 5 输出：5

提示：

0 <= n <= 100

方法一： 迭代法

直接迭代就完事了 f[i] = f[i- 1] + f[i - 2]，然后优化下存储空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int fib(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        }
        const int MOD = 1000000007;
        int first = 0, second = 1;
        int third = 0;
        for (int i = 2; i <= n; ++i) {
            third = first + second;
            third %= MOD;
            first = second;
            second = third;
        }
        return third;
    }
};

方法二：矩阵快速幂

f[i] = f[i- 1] + f[i - 2] 是一个二阶的递推数列，可以用矩阵乘法表示： \[ (f[i], f[i -1]) = (f[i- 1], f[i - 2]) * \begin{pmatrix} a & b \\ c & d \end{pmatrix} \] 根据矩阵乘法，容易得到a = 1, b = 1, c= 1, d = 0 \[ \begin{align*}(f[i], f[i -1]) &= (f[i - 1], f[i - 2]) * \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \\ &= (f[i - 2], f[i - 3])* \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^2\\ &= (f[1], f[0])* \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} ^ {i-1} \end{align*} \] 于是我们求得矩阵的n - 1次方，然后乘上初始值\((1, 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
35
class Solution {
    const int MOD = 1000000007;
    vector<vector<long long>> matrix_mul(const vector<vector<long long>>& m1, const vector<vector<long long>>& m2) {
        vector<vector<long long>> res(m1.size(), vector<long long>(m2[0].size(), 0));
        for (int i = 0; i < m1.size(); ++i) {
            for (int j = 0; j < m2.size(); ++j) {
                for (int k = 0; k < m1.size(); ++k) {
                    res[i][j] = (res[i][j] + m1[i][k] * m2[k][j]) % MOD;
                }
            }
        }
        return res;
    }

    int quick_sort(int n) {
        vector<vector<long long>> matrix = {{1, 1}, {1, 0}};
        vector<vector<long long>> res = {{1, 0}, {0, 1}};
        while (n) {
            if (n & 1) {
                res = matrix_mul(res, matrix);
            }
            matrix = matrix_mul(matrix, matrix);
            n >>= 1;
        }
        return res[0][0];
    }

public:
    int fib(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        
        return quick_sort(n - 1);
    }
};

10- II. 青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

1
2
>输入：n = 2
>输出：2

示例 2：

1
2
>输入：n = 7
>输出：21

示例 3：

1
2
>输入：n = 0
>输出：1

提示：

  • 0 <= n <= 100

方法一：迭代

显然有dp[i] = dp[i - 1] + dp[i - 2]，所以和斐波那契数列基本一样（初始0的时候为1就这点不同）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int numWays(int n) {
        if (n == 0) return 1;
        if (n == 1) return 1;
        const int MOD = 1000000007;
        int first = 1, second = 1;
        int third = 0;
        for (int i = 2; i <= n; ++i) {
            third = first + second;
            third %= MOD;
            first = second;
            second = third;
        }
        return third;
    }
};

方法二: 快速幂

和斐波那契一样，只是初始值变为\((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
class Solution {
    const int MOD = 1000000007;
    vector<vector<long long>> matrix_mul(const vector<vector<long long>>& m1, const vector<vector<long long>>& m2) {
        vector<vector<long long>> res(m1.size(), vector<long long>(m2[0].size(), 0));
        for (int i = 0; i < m1.size(); ++i) {
            for (int j = 0; j < m2.size(); ++j) {
                for (int k = 0; k < m1.size(); ++k) {
                    res[i][j] = (res[i][j] + m1[i][k] * m2[k][j]) % MOD;
                }
            }
        }
        return res;
    }

    int quick_sort(int n) {
        vector<vector<long long>> matrix = {{1, 1}, {1, 0}};
        vector<vector<long long>> res = {{1, 0}, {0, 1}};
        while (n) {
            if (n & 1) {
                res = matrix_mul(res, matrix);
            }
            matrix = matrix_mul(matrix, matrix);
            n >>= 1;
        }
        return res[0][0] + res[0][1]; // 和10 斐波那契的区别是，那个初始是(1, 0)，这个是(1, 1)
    }

public:
    int numWays(int n) {
        if (n == 0) return 1;
        if (n == 1) return 1;
        if (n == 2) return 2;
        return quick_sort(n - 1) % MOD;
    }
};

11. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

示例 1：

1
2
>输入：[3,4,5,1,2]
>输出：1

示例 2：

1
2
>输入：[2,2,2,0,1]
>输出：0

与154题相同

  1. 分治法

如果num[left] < num[right]说明数组有序，返回num[left]

如果num[left] >= num[right]则左右两边查找取min即可

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def minArray(self, numbers: List[int]) -> int:
        if not numbers: return 0
        return self.find_min(numbers, 0, len(numbers) - 1)
        
    def find_min(self, numbers, left, right):
        if left == right:
            return numbers[left]
        if numbers[left] < numbers[right]:
            return numbers[left]
        else:
            mid = (left + right) >> 1
            return min(self.find_min(numbers, left, mid), self.find_min(numbers, mid + 1, right))
  1. 二分搜索

设mid = (left + right) / 2

如果

  • nums[mid] < nums[right]：说明右半部分不可能有最小的元素，因此right = mid
  • nums[mid] > nums[right]：说明旋转的元素（最小值）一定在(mid, righth]之间，因此left = mid + 1
  • nums[mid] == nums[right]：无法确定最小值的范围，但是两个元素相等，可以让right - 1来缩小范围
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def minArray(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1
        while left < right:
            mid = (left + right) >> 1
            if nums[mid] > nums[right]:
                left = mid + 1
            elif nums[mid] < nums[right]:
                right = mid
            else:
                right -= 1
        return nums[left]

下面这种写法也可以

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 minArray(vector<int>& nums) {
        int l = 0;
        int r = nums.size() - 1;
        int ans = INT_MAX;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (nums[l] < nums[mid]) {
                ans = min(ans, nums[l]);
                l = mid + 1;
            } else if (nums[l] > nums[mid]) {
                ans = min(ans, nums[mid]);
                r = mid - 1;
            } else {
                ans = min(ans, nums[l]);
                ++l;
            }
        }
        return ans;
    }
};

12. 矩阵中的路径

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。

[["a","b","c","e"], ["s","f","c","s"], ["a","d","e","e"]]

但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

示例 1：

1
2
>输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
>输出：true

示例 2：

1
2
>输入：board = [["a","b"],["c","d"]], word = "abcd"
>输出：false

提示：

  • 1 <= board.length <= 200
  • 1 <= board[i].length <= 200

注意：本题与主站 79 题相同：https://leetcode-cn.com/problems/word-search/

直接dfs即可

C++

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
class Solution {
    vector<int> _dx = {1, -1, 0, 0};
    vector<int> _dy = {0, 0, 1, -1};
    bool dfs(vector<vector<char>>& board, string word, int x, int y, int cur, vector<vector<bool>>& vis) const {
        if (cur == word.size()) return true;
        for (int k = 0; k < 4; ++k) {
            int nx = x + _dx[k];
            int ny = y + _dy[k];
            if (nx >= 0 && ny >= 0 && nx < board.size() && ny < board[0].size()
                && board[nx][ny] == word[cur] && !vis[nx][ny]) {
                vis[nx][ny] = true;
                if (dfs(board, word, nx, ny, cur + 1, vis)) {
                    return true;
                }
                vis[nx][ny] = false;
            }
        }
        return false;
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty()) return false;
        if (word.empty()) return true;
        vector<vector<bool>> vis(board.size(), vector<bool>(board[0].size(), false));
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[i].size(); ++j) {
                if (word[0] == board[i][j]) {
                    vis[i][j] = true;
                    if (dfs(board, word, i, j, 1, vis)) return true;
                    vis[i][j] = false;
                }
            }
        }
        return false;
    }
};

Python

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
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        vis = [[False for _ in range(n)] for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if board[i][j] == word[0]:
                    vis[i][j] = True
                    if self.dfs(i, j, 1, vis, board, word):
                        return True
                    vis[i][j] = False
        return False

    def dfs(self, x, y, word_index, vis, board, word):
        if word_index == len(word):
            return True

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= len(board) or ny >= len(board[0]):
                continue
            if board[nx][ny] != word[word_index] or vis[nx][ny]:
                continue
            vis[nx][ny] = True
            if self.dfs(nx, ny, word_index + 1, vis, board, word):
                return True
            vis[nx][ny] = False
        return False

13. 机器人的运动范围

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0]的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

示例 1：

1
2
>输入：m = 2, n = 3, k = 1
>输出：3

示例 2：

1
2
>输入：m = 3, n = 1, k = 0
>输出：1

提示：

  • 1 <= n,m <= 100
  • 0 <= k <= 20

方法1

对于一个格子，只需要向下或者向右，bfs即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        ans = 0
        dx = [1, 0]
        dy = [0, 1]
        q = deque([(0, 0)])
        vis = [[False if i // 10 + i % 10 + j // 10 + j % 10 <= k else True for j in range(n)] for i in range(m)]
        vis[0][0] = True
        while q:
            cur = q.popleft()
            ans += 1
            for i in range(2):
                nx, ny = cur[0] + dx[i], cur[1] + dy[i]
                if nx < 0 or ny < 0 or nx >= m or ny >= n or vis[nx][ny]:
                    continue
                vis[nx][ny] = True
                q.append((nx, ny))

        return ans

方法2

一个位置能否达到取决于左边和上面的两个地方，因此有vis[i][j] = vis[i - 1][j] || vis[i][j - 1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        vis = [[False for j in range(n)] for i in range(m)]
        vis[0][0] = True
        ans = 1
        for i in range(m):
            for j in range(n):
                if i // 10 + i % 10 + j // 10 + j % 10 > k:
                    continue
                pre_row = i > 0 and vis[i - 1][j]
                pre_col = j > 0 and vis[i][j - 1]
                if pre_col or pre_row:
                    vis[i][j] = True
                    ans += 1
        return ans

14- I. 剪绳子

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

示例 1：

1
2
3
>输入: 2
>输出: 1
>解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

1
2
3
>输入: 10
>输出: 36
>解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示：

  • 2 <= n <= 58

注意：本题与主站 343 题相同：https://leetcode-cn.com/problems/integer-break/

  • n > 3的情况下，我们处理一个数拆分成2，要么拆分成3，（4的话相当于2个2 ， 拆成1的话乘积太小了）
  • 弄得越多段，应该乘积越大

因此可以dp，详见本博客另外一篇文章leetcode Integer Break

1
2
3
4
5
6
7
8
9
10
class Solution:
    def cuttingRope(self, n: int) -> int:
        if n <= 3: return n - 1
        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 2
        dp[3] = 3
        for i in range(4, n + 1):
            dp[i] = max(dp[i - 3] * 3, dp[i - 2] * 2)
        return dp[n]

但是还可以进一步改进：

1
2
3
4
5
6
7
8
9
10
class Solution:
    def cuttingRope(self, n: int) -> int:
        if n <= 3: return n - 1
        mod = n % 3
        if mod == 0: 
            return 3 ** (n // 3)
        elif mod == 1: 
            return 4 * 3 ** (n // 3 - 1)
        else:
            return 2 * 3 ** (n // 3)

14- II. 剪绳子 II

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

1
2
3
>输入: 2
>输出: 1
>解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

1
2
3
>输入: 10
>输出: 36
>解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示：

  • 2 <= n <= 1000

注意：本题与主站 343 题相同：https://leetcode-cn.com/problems/integer-break/

和上面一样

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def cuttingRope(self, n: int) -> int:
        if n <= 3: return n - 1
        mod = n % 3
        MOD = 1000000007
        if mod == 0: 
            return 3 ** (n // 3) % MOD
        elif mod == 1: 
            return 4 * 3 ** (n // 3 - 1) % MOD
        else:
            return 2 * 3 ** (n // 3) % MOD

c++版本，用上快速幂

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:
    int cuttingRope(int n) {
        if (n <= 3) { return n - 1; }
        int mod = n % 3;
        long long ans = 0;
        if (mod == 0) {
            ans = quick_pow(3, n / 3);
        } else if (mod == 1) {
            ans = quick_pow(3, n / 3 - 1) * 4;
        } else {
            ans = quick_pow(3, n / 3) * 2;
        }
        return ans % MOD;
    }

    long long quick_pow(long long x, int n) {
        long long ans = 1;
        while (n > 0) {
            if (n & 1) {
                ans = ans * x % MOD;
            }
            x = x * x % MOD;
            n >>= 1;
        }
        return ans;
    }

private:
    long long MOD = 1000000007;
};

15. 二进制中1的个数

请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

示例 1：

1
2
3
>输入：00000000000000000000000000001011
>输出：3
>解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

示例 2：

1
2
3
>输入：00000000000000000000000010000000
>输出：1
>解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

示例 3：

1
2
3
>输入：11111111111111111111111111111101
>输出：31
>解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

注意：本题与主站 191 题相同：https://leetcode-cn.com/problems/number-of-1-bits/

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

或者用n & (n - 1)，见leetcode 位运算

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

16. 数值的整数次方

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

示例 1:

1
2
>输入: 2.00000, 10
>输出: 1024.00000

示例 2:

1
2
>输入: 2.10000, 3
>输出: 9.26100

示例 3:

1
2
3
>输入: 2.00000, -2
>输出: 0.25000
>解释: 2-2 = 1/22 = 1/4 = 0.25

说明:

  • -100.0 < x < 100.0
  • n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

注意：本题与主站 50 题相同：https://leetcode-cn.com/problems/powx-n/

快速幂

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:
    double myPow(double x, int n) {
        if (x < 1e-12 && x > -1e-12) { return 0;}
        bool neg = false;
        long long t = n;
        if (t < 0) {
            neg = true;
            t = -t;
        }
        double ans = 1;
        while (t) {
            if (t & 1) ans = ans * x;
            x *= x;
            t >>= 1;
        }
        if (neg) {
            ans = 1.0 / ans;
        }
        return ans;
    }
};

17. 打印从1到最大的n位数

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

示例 1:

1
2
>输入: n = 1
>输出: [1,2,3,4,5,6,7,8,9]

说明：

  • 用返回一个整数列表来代替打印
  • n 为正整数

直接打印。。

c++

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<int> printNumbers(int n) {
        int temp = pow(10, n);
        vector<int> ans;
        ans.reserve(temp);
        for (int i = 1; i < temp; ++i) {
            ans.push_back(i);
        }
        return ans;
    }
};

Python

1
2
3
class Solution:
    def printNumbers(self, n: int) -> List[int]:
        return [i for i in range(1, 10 ** n)]

18. 删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

注意：此题对比原题有改动

示例 1:

1
2
3
>输入: head = [4,5,1,9], val = 5
>输出: [4,1,9]
>解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2:

1
2
3
>输入: head = [4,5,1,9], val = 1
>输出: [4,5,9]
>解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明：

  • 题目保证链表中节点的值互不相同
  • 若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

方法一

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if (head == nullptr) return nullptr;
        if (head->val == val) return head->next;
        ListNode* p = head;
        while (p->next != nullptr) {
            if (p->next->val == val) {
                p->next = p->next->next;
                break;
            }
            p = p->next;
        }
        return head;
    }
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        if not head:
            return head
        if head.val == val:
            return head.next
        
        p = head
        q = head.next
        while q:
            if q.val == val:
                p.next = q.next
                break
            p = q
            q = q.next
        return head

方法二

新建个假的Head节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if (head == nullptr) return nullptr;
        ListNode node;
        node.next = head;
        ListNode* p = &node;
        while (p->next != nullptr) {
            if (p->next->val == val) {
                p->next = p->next->next;
                break;
            }
            p = p->next;
        }
        return node.next;
    }
};

19. 正则表达式匹配

请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。

示例 1:

1
2
3
4
5
>输入:
>s = "aa"
>p = "a"
>输出: false
>解释: "a" 无法匹配 "aa" 整个字符串。

动态规划，见leetcode10题解

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:
    bool isMatch(string s, string p) {
        int m = s.size();
        int n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;
        for (int j = 2; j <= n ; ++j) {
            if (p[j - 1] == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '*') {
                    if (j >= 2)
                        dp[i][j] = dp[i][j - 2];
                    if (j >= 2 && (p[j - 2] == s[i - 1] || p[j - 2] == '.')) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                } else if (p[j - 1] == '.' || p[j - 1] == s[i - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
};

20. 表示数值的字符串

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、"5e2"、"-123"、"3.1416"、"-1E-16"、"0123"都表示数值，但"12e"、"1a3.14"、"1.2.3"、"+-5"及"12e+5.4"都不是。

这题太恶心了，题目没说清楚，数字的表示应该是A.BEC这种形式，其中：

  • A为带符号整数部分, B为小数部分，C为指数部分
  • 有小数点的只要有A或者B其中一个都可以
  • A和C为可以带符号的整数，B为无符号的整数

方法一：字符串匹配

可以写两个函数来匹配有无符号

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:
    def match_sign_num(self, s):
        if self.index < len(s) and s[self.index] in ['+', '-']:
            self.index += 1
        return self.match_unsign_num(s)

    def match_unsign_num(self, s):
        before = self.index
        while self.index < len(s) and s[self.index].isdigit():
            self.index += 1
        return before < self.index

    def isNumber(self, s: str) -> bool:
        if not s: return False
        self.index = 0
        while self.index < len(s) and s[self.index] == ' ':
            self.index += 1
        has_num = self.match_sign_num(s)
        if self.index < len(s) and s[self.index] == '.':
            self.index += 1
            has_num = self.match_unsign_num(s) or has_num
        if self.index < len(s) and s[self.index] in ['e', 'E']:
            self.index += 1
            has_num = has_num and self.match_sign_num(s)

        while self.index < len(s) and s[self.index] == ' ':
            self.index += 1
        return has_num and self.index == len(s)

方法二：有限状态机

21. 调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

示例：

1
2
3
>输入：nums = [1,2,3,4]
>输出：[1,3,2,4] 
>注：[3,1,2,4] 也是正确的答案之一。

提示：

  1. 1 <= nums.length <= 50000
  2. 1 <= nums[i] <= 10000

双指针交换即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        odd = 0
        even = len(nums) - 1
        while odd < even:
            if nums[odd] & 1:
                odd += 1
                continue
            elif nums[even] & 1 == 0:
                even -= 1
                continue
            else:
                nums[odd], nums[even] = nums[even], nums[odd]
                odd += 1
                even -= 1
        return nums

C++，有点类似快排的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int l = 0;
        int r = nums.size() - 1;
        while (l < r) {
            while (l < r && (nums[l] & 1) != 0) {
                ++l;
            }
            while (l < r && (nums[r] & 1) == 0) {
                --r;
            }
            if (l >= r) break;
            swap(nums[l], nums[r]);
        }
        return nums;
    }
};

22. 链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

示例：

1
2
3
>给定一个链表: 1->2->3->4->5, 和 k = 2.

>返回链表 4->5.

有了链表长度后，一切就很简单。。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        link_len = 0
        p = head
        while p:
            p = p.next
            link_len += 1
        
        target = link_len - k
        for i in range(target):
            head = head.next
        return head

假如不能获取长度呢？只需要遍历一遍

那么可以用双指针，一个指针先走k步即可

下面的代码假设k一定小于链表长度：

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* p = head;
        for (int i = 0; i < k && p; ++i) {
            p = p->next;
        }
        while (p) {
            p = p ->next;
            head = head->next;
        }
        return head;
    }
};

Python

1
2
3
4
5
6
7
8
9
class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        p = q = head
        for i in range(k):
            q = q.next
        while q:
            p = p.next
            q = q.next
        return p

24. 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

1
2
>输入: 1->2->3->4->5->NULL
>输出: 5->4->3->2->1->NULL

限制：

1
>0 <= 节点个数 <= 5000

注意：本题与主站 206 题相同：https://leetcode-cn.com/problems/reverse-linked-list/

方法1： 每次遍历到某个元素把它当作head

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head:
            return head
        p = head
        q = head.next
        while q:
            p.next = q.next
            q.next = head
            head = q
            q = p.next
        return head

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr) {
            return head;
        }
        ListNode* p = head;
        ListNode* q = head->next;
        while (q != nullptr) {
            p->next = q->next;
            q->next = head;
            head = q;
            q = p->next;
        }
        return head;
    }
};

方法2:

cur和pre双指针，每次pre为cur后面一个元素，遍历的时候将pre->next指向cur即可

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head:
            return head
        cur = None
        pre = head
        while pre:
            temp = pre.next
            pre.next = cur
            cur = pre
            pre = temp
        return cur

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* new_head = nullptr;
        while (head) {
            ListNode* p = head->next;
            head->next = new_head;
            new_head = head;
            head = p;
        }
        return new_head;
    }
};

25. 合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

1
2
>输入：1->2->4, 1->3->4
>输出：1->1->2->3->4->4

限制：

1
>0 <= 链表长度 <= 1000

注意：本题与主站 21 题相同：https://leetcode-cn.com/problems/merge-two-sorted-lists/

和插入排序类似

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode head, *p = &head;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                p->next = l1;
                l1 = l1->next;
            } else {
                p->next = l2;
                l2 = l2->next;
            }
            p = p->next;
        }
        p->next = l1 ? l1 : l2;
        return head.next;
    }
};

26. 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如: 给定的树 A:

3 / \ 4 5 / \ 1 2 给定的树 B：

4 / 1 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

1
2
>输入：A = [1,2,3], B = [3,1]
>输出：false

示例 2：

1
2
>输入：A = [3,4,5,1,2], B = [4,1]
>输出：true

限制：

1
>0 <= 节点个数 <= 10000

递归进行判断即可， 注意dfs过程中，如果B为空，说明匹配完成，返回true

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    bool dfs(TreeNode* A, TreeNode* B) {
        if (!B) { return true;}
        return A && A->val == B->val && dfs(A->left, B->left) && dfs(A->right, B->right);
    }
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if (B == nullptr || A == nullptr) {
            return false;
        }
        return dfs(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }
};

27. 二叉树的镜像

难度简单80

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：

   4
 /   \
 2     7
/ \   / \

1 3 6 9

镜像输出：

     4
   /   \
 7     2
/ \   / \

9 6 3 1 示例 1：

1
2
>输入：root = [4,2,7,1,3,6,9]
>输出：[4,7,2,9,6,3,1]

限制：

1
>0 <= 节点个数 <= 1000

注意：本题与主站 226 题相同：https://leetcode-cn.com/problems/invert-binary-tree/

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if (!root) return root;
        std::swap(root->left, root->right);
        mirrorTree(root->left);
        mirrorTree(root->right);
        return root;
    }
};

28. 对称的二叉树

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

   1
  / \
 2   2
/ \ / \

3 4 4 3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

  1
 / \
 2   2
  \   \
  3    3

示例 1：

1
2
>输入：root = [1,2,2,3,4,4,3]
>输出：true

示例 2：

1
2
>输入：root = [1,2,2,null,3,null,3]
>输出：false

限制：

1
>0 <= 节点个数 <= 1000

注意：本题与主站 101 题相同：https://leetcode-cn.com/problems/symmetric-tree/

C++

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    bool dfs(TreeNode* a, TreeNode* b) {
        if (a == nullptr) return b == nullptr;
        if (b == nullptr) return a == nullptr;
        return a->val == b->val && dfs(a->left, b->right) && dfs(a->right, b->left);
    }
public:
    bool isSymmetric(TreeNode* root) {
        return root == nullptr || dfs(root->left, root->right);
    }
};

29. 顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 1：

1
2
>输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
>输出：[1,2,3,6,9,8,7,4,5]

示例 2：

1
2
>输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
>输出：[1,2,3,4,8,12,11,10,9,5,6,7]

限制：

  • 0 <= matrix.length <= 100
  • 0 <= matrix[i].length <= 100

注意：本题与主站 54 题相同：https://leetcode-cn.com/problems/spiral-matrix/

方法一

按层模拟，注意只有一行和一列的特殊情况即可。

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<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return {};
        int left = 0;
        int top = 0;
        int bottom = matrix.size() - 1;
        int right = matrix[0].size() - 1;
        vector<int> ans;
        ans.reserve(matrix.size() * matrix[0].size());
        
        while (left <= right && top <= bottom) {
            // left to right
            for (int i = left; i <= right; ++i) {
                ans.push_back(matrix[top][i]);
            }
            ++top;
            if (top > bottom) break;

            // top to bottom
            for (int i = top; i <= bottom; ++i) {
                ans.push_back(matrix[i][right]);
            }
            --right;
            if (left > right) break;

            // right to left
            for (int i = right; i >= left; --i) {
                ans.push_back(matrix[bottom][i]);
            }
            --bottom;
            if (top > bottom) break;

            // bottm to top

            for (int i = bottom; i >= top; --i) {
                ans.push_back(matrix[i][left]);
            }
            ++left;
        }
        return ans;
    }
};

方法二

初始位置是矩阵的左上角，初始方向是向右，当下标超出界限或者进入之前访问过的位置时，顺时针旋转，进入下一个方向。

当所有节点都访问过的时候，恰好可以退出

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<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return {};
        int left = 0;
        int top = 0;
        int bottom = matrix.size() - 1;
        int right = matrix[0].size() - 1;

        vector<vector<bool>> vis(matrix.size(), vector<bool>(matrix[0].size()));
        vector<int> ans;
        const int total_num = matrix.size() * matrix[0].size();
        ans.reserve(total_num);
        vector<int> dx = {0, 1, 0, -1};
        vector<int> dy = {1, 0, -1, 0};
        int cur_x = 0;
        int cur_y = 0;
        int dir_index = 0;
        for (int temp_i = 0; temp_i < total_num; ++temp_i) {
            vis[cur_x][cur_y] = true;
            ans.push_back(matrix[cur_x][cur_y]);
            int nx = cur_x + dx[dir_index];
            int ny = cur_y + dy[dir_index];
            if (nx < 0 || ny < 0 || nx >= matrix.size() || ny >= matrix[0].size() || vis[nx][ny]) {
                dir_index = (dir_index + 1) % 4;
            }
            cur_x = cur_x + dx[dir_index];
            cur_y = cur_y + dy[dir_index];
        }
        return ans;
    }
};

30. 包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

1
2
3
4
5
6
7
8
>MinStack minStack = new MinStack();
>minStack.push(-2);
>minStack.push(0);
>minStack.push(-3);
>minStack.min();   --> 返回 -3.
>minStack.pop();
>minStack.top();      --> 返回 0.
>minStack.min();   --> 返回 -2.

提示：

  1. 各函数的调用总次数不超过 20000 次

注意：本题与主站 155 题相同：https://leetcode-cn.com/problems/min-stack/

用两个栈，一个是正常的，一个是保存当前最小元素的栈min_s即可

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 MinStack {
    std::stack<int> s;
    std::stack<int> min_s;
public:
    /** initialize your data structure here. */
    MinStack() {}
    
    void push(int x) {
        s.push(x);
        if (min_s.empty() || min_s.top() >= x) {
            min_s.push(x);
        }
    }
    
    void pop() {
        int x = s.top();
        s.pop();
        if (x == min_s.top()) {
            min_s.pop();
        }
    }
    
    int top() {
        return s.top();
    }
    
    int min() {
        return min_s.top();
    }
};

31. 栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

示例 1：

1
2
3
4
5
>输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
>输出：true
>解释：我们可以按以下顺序执行：
>push(1), push(2), push(3), push(4), pop() -> 4,
>push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2：

1
2
3
>输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
>输出：false
>解释：1 不能在 2 之前弹出。

提示：

  1. 0 <= pushed.length == popped.length <= 1000
  2. 0 <= pushed[i], popped[i] < 1000
  3. pushed 是 popped 的排列。

注意：本题与主站 946 题相同：https://leetcode-cn.com/problems/validate-stack-sequences/

给定了Push的顺序和pop的顺序，因此可以直接模拟

如果pop的元素等于栈顶，那么就pop元素，如果是合法的pop序列，最后push数组一定为空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        if(pushed.size() != popped.size())  return false;
        if (pushed.empty()) return true;
        std::size_t i = 0;
        std::stack<int> q;
        for (int num : pushed) {
            q.push(num);
            while (!q.empty() && i < pushed.size() && q.top() == popped[i]) {
                ++i;
                q.pop();
            }
        }
        return q.empty();
    }
};

32 - I. 从上到下打印二叉树

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

例如: 给定二叉树: [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

返回：

1
>[3,9,20,15,7]

提示：

  1. 节点总数 <= 1000

直接BFS即可

c++

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> levelOrder(TreeNode* root) {
        if (!root) return {};
        queue<TreeNode*> q;
        vector<int> ans;
        q.push(root);
        while (!q.empty()) {
            auto* cur = q.front();
            q.pop();
            ans.push_back(cur->val);
            if (cur->left) {
                q.push(cur->left);
            }
            if (cur->right) {
                q.push(cur->right);
            }
        }
        return ans;
    }
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        if not root: return []
        q = deque([root])
        ans = []
        while q:
            cur = q[0]
            ans.append(cur.val)
            q.popleft()
            if cur.left:
                q.append(cur.left)
            if cur.right:
                q.append(cur.right)
        return ans

32 - II. 从上到下打印二叉树 II

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

例如: 给定二叉树: [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

返回其层次遍历结果：

1
2
3
4
5
>[
 [3],
 [9,20],
 [15,7]
>]

提示：

  1. 节点总数 <= 1000

注意：本题与主站 102 题相同：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

上面的代码改改即可

C++

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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (root == nullptr) return ans;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            int cur_size = q.size();
            vector<int> row;
            row.reserve(cur_size);
            for (int i = 0 ; i < cur_size; ++i) {
                auto* cur = q.front();
                q.pop();
                row.push_back(cur->val);
                if (cur->left) q.push(cur->left);
                if (cur->right) q.push(cur->right);
            }
            ans.emplace_back(std::move(row));
        }
        return ans;
    }
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        q = deque([root])
        ans = []
        while q:
            len_q = len(q)
            row = []
            for _ in range(len_q):
                cur = q[0]
                row.append(cur.val)
                q.popleft()
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
            ans.append(row)
        return ans

32 - III. 从上到下打印二叉树 III

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

例如: 给定二叉树: [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

返回其层次遍历结果：

1
2
3
4
5
>[
 [3],
 [20,9],
 [15,7]
>]

提示：

  1. 节点总数 <= 1000

和上面的不同就是多了个双数逆序打印的东西，判断即可

C++

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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (root == nullptr) return ans;
        queue<TreeNode*> q;
        q.push(root);
        bool is_reverse = false;
        while(!q.empty()) {
            int cur_size = q.size();
            vector<int> row;
            row.reserve(cur_size);
            for (int i = 0 ; i < cur_size; ++i) {
                auto* cur = q.front();
                q.pop();
                row.push_back(cur->val);
                if (cur->left) q.push(cur->left);
                if (cur->right) q.push(cur->right);
            }
            if (is_reverse) {
                std::reverse(row.begin(), row.end());
            }
            ans.emplace_back(std::move(row));
            is_reverse = !is_reverse;
        }
        return ans;
    }
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        q = deque([root])
        ans = []
        h = 1
        while q:
            len_q = len(q)
            row = []
            for _ in range(len_q):
                cur = q[0]
                row.append(cur.val)
                q.popleft()
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
            ans.append(row if h & 1 else row[::-1])
            h += 1
        return ans

33. 二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树：

1
2
3
4
5
    5
   / \
  2   6
 / \
1   3

示例 1：

1
2
>输入: [1,6,3,2,5]
>输出: false

示例 2：

1
2
>输入: [1,3,2,6,5]
>输出: true

提示：

  1. 数组长度 <= 1000

方法1

二叉树的后序遍历顺序为：左子树、右子树、根节点

因此数组的最后一个就是根节点，可以从后往前找，找到第一个小于根节点的下标index，则[s,index]必须是左子树，右子树为[index+1, e-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
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = self.right = None

class Solution:
    def find_larger_index(self, nums, s, e, t):
        for i in range(e, s - 1, -1):
            if nums[i] < t:
                return i
        return -1

    def dfs(self, nums: List[int], s: int, e: int) -> bool:
        if s > e: return None
        root = TreeNode(nums[e])
        index = self.find_larger_index(nums, s, e, nums[e])
        if index >= s:
            root.left = self.dfs(nums, s, index)
            root.right = self.dfs(nums, index + 1, e - 1)
        else:
            root.right = self.dfs(nums, s, e - 1)
        return root

    def inorder(self, nums, root):
        if not root: return
        self.inorder(nums, root.left)
        nums.append(root.val)
        self.inorder(nums, root.right)

    def verifyPostorder(self, postorder: List[int]) -> bool:
        root = self.dfs(postorder, 0, len(postorder) - 1)
        inorder = []
        self.inorder(inorder, root)
        for i in range(1, len(inorder)):
            if inorder[i] < inorder[i - 1]:
                return False
        return True

但其实可以改进一下，在递归过程直接判断左子树必须都小于根节点即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def find_larger_index(self, nums, s, e, t):
        for i in range(e, s - 1, -1):
            if nums[i] < t:
                return i
        return s - 1

    def dfs(self, nums: List[int], s: int, e: int) -> bool:
        if s > e: return True
        root = nums[e]
        index = self.find_larger_index(nums, s, e, root)
        for i in range(s, index + 1):
            if nums[i] > root:
                return False
        return self.dfs(nums, s, index) and self.dfs(nums, index + 1, e - 1)

    def verifyPostorder(self, postorder: List[int]) -> bool:
        return self.dfs(postorder, 0, len(postorder) - 1)

C++

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 {
    bool dfs(const vector<int>& postorder, int l, int r, int min_v, int max_v) {
        if (l > r) return true;
        //cout << l << " " << r << ";" << min_v << "," << max_v << endl;
        int root = postorder[r];
        if (root < min_v || root > max_v) {
            return false;
        }
        
        int left_index = l - 1;
        for (int i = r; i >= l; --i) {
            if (postorder[i] < root) {
                left_index = i;
                break;
            }
        }
        return dfs(postorder, l, left_index, min_v, root) && dfs(postorder, left_index + 1, r - 1, root, max_v);
    }
public:
    bool verifyPostorder(vector<int>& postorder) {
        return dfs(postorder, 0, postorder.size() - 1, INT_MIN, INT_MAX);
    }
};

方法2

二叉树的后序遍历顺序为：左子树、右子树、根节点，而后续遍历的逆序为：根节点、右子树、左子树

对于逆序的后续遍历列表\([r_{n}, r_{n-1},...,r_1]\)，

  • \(r_i > r_{i+1}\)：说明节点\(r_i\)一定是节点\(r_{i+1}\)的右子节点。
  • \(r_i < r_{i+1}\)：说明节点\(r_i\)是[i + 1, ...n]中某个元素的左子节点，此时\([r_{i}, r_{i-1},...,r_1]\)的元素都要小于root节点

因此我们可以维护一个单调递增的栈，若发现栈顶的元素大于当前的postorder[i]，说明进了左子树，我们可以不断的pop元素来找它的父节点，同时判断是否满足root < postorder[i]

算法复杂度O(n)

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        stack<int> q;
        // p_i > p_{i+1} => right
        // p_i < p_{i+1} => left
        int root = INT_MAX;
       for (int i = postorder.size() - 1; i >= 0; --i) {
           while (!q.empty() && postorder[i] < q.top()) {
               root = q.top();
               q.pop();
           }
           if (root < postorder[i]) return false;
           q.push(postorder[i]);
       }
       return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def verifyPostorder(self, nums: List[int]) -> bool:
        q = []
        parent = float("+inf")
        for i in range(len(nums) - 1, -1, -1):
            while q and q[-1] > nums[i]:
                parent = q.pop()
            
            if nums[i] > parent:
                return False
            q.append(nums[i])
        return True

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

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例: 给定如下二叉树，以及目标和 sum = 22，

1
2
3
4
5
6
7
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

返回:

1
2
3
4
>[
  [5,4,11,2],
  [5,8,4,5]
>]

提示：

  1. 节点总数 <= 10000

注意：本题与主站 113 题相同：https://leetcode-cn.com/problems/path-sum-ii/

dfs即可

C++

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 {
    void dfs(TreeNode* root, vector<int>& cur, vector<vector<int>>& ans, int target) {
        if (root == nullptr) {
            return;
        }
        cur.push_back(root->val);
        target -= root->val;
        if (root->left == nullptr && root->right == nullptr && target == 0) {
            ans.push_back(cur);
        } else {
            dfs(root->left, cur, ans, target);
            dfs(root->right, cur, ans, target);
        }
        cur.pop_back();
    }

public:
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        vector<int> cur;
        vector<vector<int>> ans;
        dfs(root, cur, ans, target);
        return ans;
    }
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def dfs(self, cur, cur_sum, root, target, ans):
        if not root:
            return
        
        cur_sum += root.val
        cur.append(root.val)
        if cur_sum == target and not root.left and not root.right:
            ans.append(cur[:])
        else:
            self.dfs(cur, cur_sum, root.left, target, ans)
            self.dfs(cur, cur_sum, root.right, target, ans)
        cur.pop()

    def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
        ans = []
        cur = []
        self.dfs(cur, 0, root, target, ans)
        return an

35. 复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例 1：

img 
1
2
>输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
>输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

img 
1
2
>输入：head = [[1,1],[2,1]]
>输出：[[1,1],[2,1]]

示例 3：

img

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

示例 4：

1
2
3
>输入：head = []
>输出：[]
>解释：给定的链表为空（空指针），因此返回 null。

提示：

  • -10000 <= Node.val <= 10000
  • Node.random 为空（null）或指向链表中的节点。
  • 节点数目不超过 1000 。

用个hash表保存即可

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
"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""
class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        p = head
        node_dict = {}
        new_head = Node(-1)
        q = new_head
        while p:
            if p not in node_dict:
                node_dict[p] = Node(p.val)
            q.next = node_dict[p]
            q = q.next
            p = p.next

        p = head
        q = new_head.next
        while p:
            if p.random:
                q.random = node_dict[p.random]
            p = p.next
            q = q.next
        return new_head.next

也可以递归的写，更简单一些

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    std::unordered_map<Node*, Node*> _map;
public:
    Node* copyRandomList(Node* head) {
        if (!head) return head;
        if (_map.find(head) != _map.end()) return _map[head];

        Node* new_node = new Node(head->val);
        _map[head] = new_node;
        new_node->next = copyRandomList(head->next);
        new_node->random = copyRandomList(head->random);
        return new_node;
    }
};

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

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

为了让您更好地理解问题，以下面的二叉搜索树为例：

img

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

img

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

利用中序遍历即可

C++

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 {
    Node* _head = nullptr;
    Node* _pre = nullptr;

    void dfs(Node* root) {
        if (root == nullptr) return;
        dfs(root->left);
        if (_head == nullptr) {
            _head = root;
        }
        root->left = _pre;
        if (_pre != nullptr) {
            _pre->right = root;
        }
        _pre = root;
        dfs(root->right);
    }
public:
    Node* treeToDoublyList(Node* root) {
        _head = _pre = nullptr;
        dfs(root);
        if (_head != nullptr) {
            _head->left = _pre;
            _pre->right = _head;
        }
        return _head;
    }
};

Python

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
"""
# Definition for a Node.
class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
"""
class Solution:
    def dfs(self, root):
        if not root: return
        self.dfs(root.left)
        if not self.head:
            self.head = self.p = root
        else:
            self.p.right = root
            root.left = self.p
            self.p = root
        self.dfs(root.right)
       

    def treeToDoublyList(self, root: 'Node') -> 'Node':
        self.head = self.p = None
        self.dfs(root)
        if self.head:
            self.head.left = self.p
            self.p.right = self.head    
        return self.head

37. 序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树。

示例:

1
2
3
4
5
6
7
8
>你可以将以下二叉树：
   1
  / \
 2   3
    / \
   4   5

>序列化为 "[1,2,3,null,null,4,5]"

注意：本题与主站 297 题相同：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

序列化就是标准BFS

反序列化用一个i指向当前的子节点，一个队列来维护当前节点即可

C++

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
class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (root == nullptr) return "";
        queue<TreeNode*> q;
        q.push(root);
        stringstream ss;
        while (!q.empty()) {
            int n = q.size();
            for (int i = 0; i < n; ++i) {
                TreeNode* cur = q.front();
                q.pop();
                if (cur != nullptr) {
                    ss << cur->val << ",";
                    q.push(cur->left);
                    q.push(cur->right);
                } else {
                    ss << "null,";
                }
            }
        }
        cout << ss.str() << endl;
        return ss.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        TreeNode* root = nullptr;
        TreeNode* cur = nullptr;
        queue<TreeNode*> q;
        bool is_left = true;
        for (int i = 0; i < data.size();) {
            int end = std::find(data.begin() + i, data.end(), ',') - data.begin();
            if (end == data.size()) break;
            
            const string cur_str = data.substr(i, end - i);
            i = end + 1;
    
            if (root == nullptr) {
                root = new TreeNode(stoi(cur_str));
                q.push(root);
                continue;
            }
            if (is_left) {
                cur = q.front();
                q.pop();
            }
            TreeNode* next = nullptr;
            if (cur_str != "null") {
                int val = stoi(cur_str);
                next = new TreeNode(val);
                q.push(next);
            }
            if (is_left) {
                cur->left = next;
            } else {
                cur->right = next;
            }
            is_left = !is_left;
        }
        return root;
    }
};

Python

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
class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if not root: return "[]"
        ans = []
        q = deque([root])
        while q:
            cur = q[0]
            q.popleft()
            if cur:
                q.append(cur.left)
                q.append(cur.right)
                ans.append(str(cur.val))
            else:
                ans.append("null")
        return '[{}]'.format(','.join(ans))

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if data == '[]': return None
        data = data[1:-1].split(',')
        root = TreeNode(int(data[0]))
        i = 1
        q = deque([root])
        while q:
            cur = q.popleft()
            if i >= len(data):
                break
            
            if data[i] != 'null':
                cur.left = TreeNode(int(data[i]))
                q.append(cur.left)
            i += 1
            if data[i] != 'null':
                cur.right = TreeNode(int(data[i]))
                q.append(cur.right)
            i += 1
        return root

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

38. 字符串的排列

难度中等132

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:

1
2
>输入：s = "abc"
>输出：["abc","acb","bac","bca","cab","cba"]

限制：

1
>1 <= s 的长度 <= 8

可以类似STL的写个next_permutation的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def next_permutation(self, nums):
        i = len(nums) - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        if i < 0:
            return False

        j = len(nums) - 1
        while j > i and nums[i] >= nums[j]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
        nums[i + 1:] = nums[i + 1:][::-1]
        return True

    def permutation(self, s: str) -> List[str]:
        if not s: return []
        nums = sorted([c for c in s])
        ans = [''.join(nums)]
        while self.next_permutation(nums):
            ans.append(''.join(nums))
        return ans

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

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

1
2
>输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
>输出: 2

限制：

1
>1 <= 数组长度 <= 50000

进行投票即可，如果当前元素与element相同，cnt+=1，否则cnt -= 1。 当Cnt= 0的时候，设置element为当前的元素

这是因为超过一半次数的元素，其cnt必然大于长度的一半

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        cnt = 1
        element = nums[0]
        for i in range(1, len(nums)):
            if nums[i] == element:
                cnt += 1
            else:
                cnt -= 1
                if cnt == 0:
                    element = nums[i]
                    cnt += 1
        return element

40. 最小的k个数

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：

1
2
>输入：arr = [3,2,1], k = 2
>输出：[1,2] 或者 [2,1]

示例 2：

1
2
>输入：arr = [0,1,2,1], k = 1
>输出：[0]

限制：

  • 0 <= k <= arr.length <= 10000
  • 0 <= arr[i] <= 10000

方法1：排序

1
2
3
class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        return sorted(arr)[:k]

方法２，利用最大堆

c++本身就是最大堆

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:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if (!k) return {};
        priority_queue<int> q;
        for (int v : arr) {
            if (q.size() < k) {
                q.push(v);
                continue;
            } else if (q.top() > v) {
                q.pop();
                q.push(v);
            }
        }
        vector<int> ans;
        ans.reserve(k);
        while (!q.empty()) {
            ans.push_back(q.top());
            q.pop();
        }
        return ans;
    }
};

python的heapq是最小堆

1
2
3
4
5
6
7
8
9
10
class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if not k: return []
        q = [-x for x in arr[:k]]
        heapq.heapify(q)
        for i in range(k, len(arr)):
            if arr[i] < -q[0]:
                heapq.heappop(q)
                heapq.heappush(q, -arr[i])
        return [-x for x in q]

方法3. 利用快排的思想， 如果想要达到期望O(n)还需要加上随机的操作

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
class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if (k == 0) return {};
        srand((unsigned)time(NULL));
        quick_sort(arr, 0, arr.size() - 1, k);
        vector<int> ans(arr.begin(), arr.begin() + k);
        return ans;
    }

    void quick_sort(vector<int>& arr, int l, int r, int k) {
        if (l >= r) return;
        int i = partition(arr, l, r);
        int left_num = i - l + 1;
        if (k == left_num) {
            return;
        } else if (k < left_num) {
            quick_sort(arr, l, i - 1, k);
        } else { // k > left_num
            quick_sort(arr, i + 1, r, k - left_num);
        }
    }

    void random_choose(vector<int>& arr, int l, int r) {
        int t = rand() % (r - l + 1) + l;
        swap(arr[r], arr[r]);
    }

    int partition(vector<int>& arr, int l, int r) {
        random_choose(arr, l, r);
        int temp = arr[r];
        int left = l - 1;
        for (int i = l; i < r; ++i) {
            if (arr[i] < temp) {
                left++;
                swap(arr[left], arr[i]);
            }
        }
        swap(arr[left + 1], arr[r]);
        return left + 1;
    }
};

41. 数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

  • void addNum(int num) - 从数据流中添加一个整数到数据结构中。
  • double findMedian() - 返回目前所有元素的中位数。

示例 1：

1
2
3
4
>输入：
>["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
>[[],[1],[2],[],[3],[]]
>输出：[null,null,null,1.50000,null,2.00000]

示例 2：

1
2
3
4
>输入：
>["MedianFinder","addNum","findMedian","addNum","findMedian"]
>[[],[2],[],[3],[]]
>输出：[null,null,2.00000,null,2.50000]

限制：

  • 最多会对 addNum、findMedian 进行 50000 次调用。

注意：本题与主站 295 题相同：https://leetcode-cn.com/problems/find-median-from-data-stream/

想想一个排好序的数组，中位数就是中间的元素。如何动态的维护中间的元素呢？

维护一个最大堆和最小堆，最大堆保存数组左边的，最小堆保存数组右边的，保证左边的个数比右边的多，但不多于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
class MedianFinder {
    priority_queue<int> left;
    priority_queue<int> right;
public:
    MedianFinder() {}
    
    void addNum(int num) {
        if (left.empty() || num <= left.top()) {
            left.push(num);
            if (right.size() + 1 < left.size()) {
                int temp = left.top();
                left.pop();
                right.push(-temp);
            }
        } else { // num > left.top()
            right.push(-num);
            if (right.size() > left.size()) {
                int temp = right.top();
                right.pop();
                left.push(-temp);
            }
        }
    }
    
    double findMedian() {
        return (left.size() + right.size()) & 1? left.top() : (left.top() - right.top()) * 0.5;
    }
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class MedianFinder:
    def __init__(self):
        self.left = []
        self.right = []

    def addNum(self, num: int) -> None:
        if not self.left or -self.left[0] > num:
            heapq.heappush(self.left, -num)
            if len(self.right) + 1 < len(self.left):
                temp = heapq.heappop(self.left)
                heapq.heappush(self.right, -temp)
        else:
            heapq.heappush(self.right, num)
            if len(self.right) > len(self.left):
                temp = heapq.heappop(self.right)
                heapq.heappush(self.left, -temp)

    def findMedian(self) -> float:
        return -self.left[0] if (len(self.left) + len(self.right)) & 1 else (-self.left[0] + self.right[0]) * 0.5

42. 连续子数组的最大和

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例1:

1
2
3
>输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
>输出: 6
>解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

提示：

  • 1 <= arr.length <= 10^5
  • -100 <= arr[i] <= 100

注意：本题与主站 53 题相同：https://leetcode-cn.com/problems/maximum-subarray/

cur_sum < 0的时候重新计数即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }
        int ans = nums[0];
        int cur_sum = 0;
        for (int num : nums) {
            if (cur_sum < 0) {
                cur_sum = 0;
            }
            cur_sum += num;
            ans = max(ans, cur_sum);
        }
        return ans;
    }
};

44. 数字序列中某一位的数字

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数，求任意第n位对应的数字。

示例 1：

1
2
>输入：n = 3
>输出：3

示例 2：

1
2
>输入：n = 11
>输出：0

限制：

  • 0 <= n < 2^31

注意：本题与主站 400 题相同：https://leetcode-cn.com/problems/nth-digit/

首先求出n是几位数，1~9有9个数，10~99有90个数，可以根据这个规律求出

假设求出为cnt位，则从\(10^{cnt - 1}\)开始往后的 (n - 1) / cnt个数， 比如求第11个数，cnt求出为2位，则从10开始往后1个数为base_num

最后从base_num中找到（n - 1）% cnt个即可

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def findNthDigit(self, n: int) -> int:
        if n == 0: return 0
        num = 9
        cnt = 1
        while n > num * cnt:
            n -= num * cnt
            cnt += 1
            num *= 10
        
        base_num = 10 ** (cnt - 1) + (n - 1) // cnt
        return int(str(base_num)[(n - 1) % cnt])

45. 把数组排成最小的数

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例 1:

1
2
>输入: [10,2]
>输出: "102"

示例 2:

1
2
>输入: [3,30,34,5,9]
>输出: "3033459"

提示:

  • 0 < nums.length <= 100

说明:

  • 输出结果可能非常大，所以你需要返回一个字符串而不是整数
  • 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

两个字符串a和b，若a+b < b + a则a排前面

Python

1
2
3
4
5
class Solution:
    def minNumber(self, nums: List[int]) -> str:
        nums = list(map(str, nums))
        nums = sorted(nums, key=cmp_to_key(lambda a, b: 1 if a + b > b + a else -1))
        return "".join(nums)

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string minNumber(vector<int>& nums) {
        vector<std::string> str_nums;
        for (int num : nums) {
            str_nums.emplace_back(std::to_string(num));
        }

        std::sort(str_nums.begin(), str_nums.end(), [](const std::string&a, const std::string& b) {return a + b < b + a;});
        
        stringstream ss;
        for (const std::string& num : str_nums) {
            ss << num;
        }
        return ss.str();
    }
};

46. 把数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例 1:

1
2
3
>输入: 12258
>输出: 5
>解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

提示：

  • 0 <= num < 2^31

通过次数56,690

提交次数105,188

简单dp即可，若前一个数和当前的数在10~25之间，则dp[i] += dp[i - 2]

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int translateNum(int num) {
        string str_num = to_string(num);
        vector<int> dp(str_num.size(), 0);
        dp[0] = 1;
        for (size_t i = 1; i < str_num.size(); ++i) {
            if (str_num[i - 1] == '1' || str_num[i - 1] == '2' && str_num[i] <= '5') {
                dp[i] = i >= 2? dp[i - 2] : 1;
            }
            dp[i] += dp[i - 1];
        }
        return dp[str_num.size() - 1];
    }
};

47. 礼物的最大价值

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

示例 1:

1
2
3
4
5
6
7
8
>输入: 
>[
 [1,3,1],
 [1,5,1],
 [4,2,1]
>]
>输出: 12
>解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

提示：

  • 0 < grid.length <= 200
  • 0 < grid[0].length <= 200

直接dp即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        if (grid.empty()) return 0;
        vector<vector<int>> dp(grid.size(), vector<int>(grid[0].size()));

        for (std::size_t i = 0; i < grid.size(); ++i) {
            for (std::size_t j = 0; j < grid[i].size(); ++j) {
                int temp = 0;
                if (i > 0) {
                    temp = dp[i - 1][j];
                }
                if (j > 0) {
                    temp = max(temp, dp[i][j - 1]);
                }
                dp[i][j] = grid[i][j] + temp;
            }
        }
        return dp.back().back();
    }
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def maxValue(self, grid: List[List[int]]) -> int:
        if not grid: return 0
        m = len(grid)
        n = len(grid[0])
        dp = [[0 for _ in range(n)] for _ in range(m)]

        dp[0][0] = grid[0][0]
        for i in range(1, m):
            dp[i][0] = grid[i][0] + dp[i - 1][0]
        for j in range(1, n):
            dp[0][j] = grid[0][j] + dp[0][j - 1]
        
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
        return dp[-1][-1]

48. 最长不含重复字符的子字符串

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例 1:

1
2
3
>输入: "abcabcbb"
>输出: 3 
>解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3
>输入: "bbbbb"
>输出: 1
>解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
4
>输入: "pwwkew"
>输出: 3
>解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
    请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

  • s.length <= 40000

注意：本题与主站 3 题相同：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> vis(128, -1);
        int start = 0, ans = 0;
        for (int j = 0; j < s.size(); ++j) {
            if (vis[s[j]] >= 0) {
                for (; start <= vis[s[j]]; ++start) {
                    vis[s[start]] = -1;
                }
            }
            vis[s[j]] = j;
            ans = max(j - start + 1, ans);
        }
        return ans;
    }
};

方法2： 动态规划

设dp[j]为以s[j]结尾不重复字符的长度， i = vis[s[j]]则为s[j]字符上一次出现的位置。

则有：

  • j - i < dp[j - 1]： 说明上一次出现的位置在j - 1的子串里，只能重新开始，dp[j] = j - i
  • j - i > dp[j - 1]： 说明上一次出现的位置不在j - 1的子串里面，因此dp[j] = dp[j - 1] + 1

考虑一个特殊的情况，若s[j]第一次出现（i < 0）必然有上面第二个式子成立。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> vis(128, -1);
        int last_max = 0, ans = 0;
        for (int j = 0; j < s.size(); ++j) {
            int i = vis[s[j]];
            if (last_max < j - i) {
                last_max += 1;
            } else {
                last_max = j - i;
            }
            vis[s[j]] = j;
            ans = max(ans, last_max);
        }
        return ans;
    }
};

49. 丑数

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例:

1
2
3
>输入: n = 10
>输出: 12
>解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:

  1. 1 是丑数。
  2. n 不超过1690。

注意：本题与主站 264 题相同：https://leetcode-cn.com/problems/ugly-number-ii/

题解见本博客另一篇文章　264. Ugly Number II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> dp(n, 1);
        int a = 0, b = 0, c = 0;
        for (int i = 1; i < n; ++i) {
            int cur = min({dp[a] * 2, dp[b] * 3, dp[c] * 5});
            if (cur == dp[a] * 2) ++a;
            if (cur == dp[b] * 3) ++b;
            if (cur == dp[c] * 5) ++c;
            dp[i] = cur;
        }
        return dp.back();
    }
};

51. 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

1
2
>输入: [7,5,6,4]
>输出: 5

限制：

1
>0 <= 数组长度 <= 50000

方法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
class Solution {
    int ans = 0;
    vector<int> temp;

    void merge_sort(int i, int j, vector<int>& nums) {
        if (i >= j) return;
        int mid = (i + j) >> 1;
        merge_sort(i, mid, nums);
        merge_sort(mid + 1, j, nums);
        merge(i, mid, j, nums);
    }

    void merge(int ls, int le, int re, vector<int>&nums) {
        int rs = le + 1;
        int i = ls, j = rs, x = 0;
        while (i <= le && j <= re) {
            if (nums[i] <= nums[j]) {
                temp[x++] = nums[i++];
            } else {
                temp[x++] = nums[j++];
                ans += le - i + 1;
            }
        }

        while (i <= le) {
            temp[x++] = nums[i++];
        }
        while (j <= re) {
            temp[x++] = nums[j++];
        }

        for (i = ls; i <= re; ++i) {
            nums[i] = temp[i - ls];
        }
    }

public:
    int reversePairs(vector<int>& nums) {
        temp.reserve(nums.size());
        merge_sort(0, nums.size() - 1, nums);
        return ans;
    }
};

方法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
36
37
38
39
40
41
42
43
44
45
46
class FenwickTree {
    vector<int> _sum;
    int _n;
public:
    FenwickTree(int n) : _n(n + 1), _sum(n + 1, 0) {}

    inline int lowbit(int x) { return x & -x; }

    int sum(int x) {
        int ans = 0;
        while (x > 0) {
            ans += _sum[x];
            x -= lowbit(x);
        }
        return ans;
    }

    void add(int x, int a) {
        while (x < _n) {
            _sum[x] += a;
            x += lowbit(x);
        }
    }
};

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        if (nums.empty()) return 0;
        vector<int> temp_nums(nums);
        sort(temp_nums.begin(), temp_nums.end());
        unordered_map<int, int> nums2id;
        for (std::size_t i = 0; i < temp_nums.size(); ++i) {
            nums2id[temp_nums[i]] = i + 1;
        }

        int ans = 0;
        FenwickTree tree(nums.size());
        for (int i = nums.size() - 1; i >= 0; --i) {
            int index = nums2id[nums[i]];
            ans += tree.sum(index - 1);
            tree.add(index, 1);
        }
        return ans;
    }
};

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

输入两个链表，找出它们的第一个公共节点。

如下面的两个链表：

img

在节点 c1 开始相交。

示例 1：

img

1
2
3
>输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
>输出：Reference of the node with value = 8
>输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

img

1
2
3
>输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
>输出：Reference of the node with value = 2
>输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

img

1
2
3
4
>输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
>输出：null
>输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
>解释：这两个链表不相交，因此返回 null。

注意：

  • 如果两个链表没有交点，返回 null.
  • 在返回结果后，两个链表仍须保持原有的结构。
  • 可假定整个链表结构中没有循环。
  • 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
  • 本题与主站 160 题相同：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

题解见本博客另外一篇文章 leetcode Intersection of Two Linked Lists

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* p = headA;
        ListNode* q = headB;
        while (p != q) {
            p = p ? p->next : headB;
            q = q ? q->next : headA;
        }
        return p;
    }
};

Python

1
2
3
4
5
6
7
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        p, q = headA, headB
        while p != q:
            p = p.next if p else headB
            q = q.next if q else headA
        return p

53 - I. 在排序数组中查找数字 I

统计一个数字在排序数组中出现的次数。

示例 1:

1
2
>输入: nums = [5,7,7,8,8,10], target = 8
>输出: 2

示例 2:

1
2
>输入: nums = [5,7,7,8,8,10], target = 6
>输出: 0

限制：

1
>0 <= 数组长度 <= 50000

注意：本题与主站 34 题相同（仅返回值不同）：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

调包：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int lower_index = std::lower_bound(nums.begin(), nums.end(), target) - nums.begin();
        if (lower_index == nums.size() || nums[lower_index] != target) {
            return 0;
        }
        int upper_index = std::upper_bound(nums.begin(), nums.end(), target) - nums.begin();
        return upper_index - lower_index;
    }
};
1
2
3
4
5
6
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        lower_index = bisect.bisect_left(nums, target)
        if len(nums) == lower_index or target != nums[lower_index]:
            return 0
        return bisect.bisect_right(nums, target) - lower_index

手写二分

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 {
    int lower_bound(const vector<int>& nums, int target) {
        int l = 0;
        int r = nums.size();
        while (l < r) {
            int mid = l + ((r - l) >> 1);
            if (nums[mid] < target){
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }

    int upper_bound(const vector<int>& nums, int target) {
        int l = 0;
        int r = nums.size();
        while (l < r) {
            int mid = l + ((r - l) >> 1);
            if (nums[mid] <= target){
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }

public:
    int search(vector<int>& nums, int target) {
        int lower_index = lower_bound(nums, target);
        if (lower_index == nums.size() || nums[lower_index] != target) {
            return 0;
        }
        int upper_index = upper_bound(nums, target);
        return upper_index - lower_index;
    }
};

53 - II. 0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例 1:

1
2
>输入: [0,1,3]
>输出: 2

示例 2:

1
2
>输入: [0,1,2,3,4,5,6,7,9]
>输出: 8

限制：

1
>1 <= 数组长度 <= 10000

二分，对于mid，如果之前的有序，必然有nums[mid] == mid，否则，nums[mid] > mid

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int l = 0;
        int r = nums.size();
        while (l < r){
            int mid = l + ((r - l) >> 1);
            if (mid < nums[mid]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

54. 二叉搜索树的第k大节点

给定一棵二叉搜索树，请找出其中第k大的节点。

示例 1:

1
2
3
4
5
6
7
>输入: root = [3,1,4,null,2], k = 1
  3
 / \
1   4
 \
  2
>输出: 4

示例 2:

1
2
3
4
5
6
7
8
9
>输入: root = [5,3,6,2,4,null,null,1], k = 3
      5
     / \
    3   6
   / \
  2   4
 /
1
>输出: 4

限制：

1 ≤ k ≤ 二叉搜索树元素个数

二叉搜索树可以用中序遍历转为有序数组。题目求的是第k大的元素，所以可以先遍历右子树-中间节点-左子树，从而求得第k大的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    int _ans = 0;
    void dfs(TreeNode* root, int& k) {
        if (!root) return;
        dfs(root->right, k);
        if (--k == 0) {
            _ans = root->val;
        }
        dfs(root->left, k);
    }
public:
    int kthLargest(TreeNode* root, int k) {
        dfs(root, k);
        return _ans;
    }
};

55 - I. 二叉树的深度

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

例如：

给定二叉树 [3,9,20,null,null,15,7]，

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

返回它的最大深度 3 。

提示：

  1. 节点总数 <= 10000

注意：本题与主站 104 题相同：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

直接递归遍历即可

1
2
3
4
5
6
7
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1; 
    }
};

55 - II. 平衡二叉树

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

1
2
3
4
5
6
7
      1
     / \
    2   2
   / \
  3   3
 / \
4   4

返回 false 。

限制：

  • 1 <= 树的结点个数 <= 10000

注意：本题与主站 110 题相同：https://leetcode-cn.com/problems/balanced-binary-tree/

dfs求深度即可

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def dfs(self, root) -> int:
        if not root: return 0
        left_d = self.dfs(root.left)
        right_d = self.dfs(root.right)
        if left_d > right_d + 1 or left_d + 1 < right_d:
            return -10000
        return max(left_d, right_d) + 1

    def isBalanced(self, root: TreeNode) -> bool:
        depth = self.dfs(root)
        return depth >= 0

56 - I. 数组中数字出现的次数

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：

1
2
>输入：nums = [4,1,4,6]
>输出：[1,6] 或 [6,1]

示例 2：

1
2
>输入：nums = [1,2,10,4,1,4,3,3]
>输出：[2,10] 或 [10,2]

限制：

  • 2 <= nums.length <= 10000

题解见本博客另外一篇文章 single-number-iii

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        x = 0
        for num in nums:
            x ^= num
        
        ans = [0, 0]
        x = x & -x
        for num in nums:
            ans[num & x == 0] ^= num
        return ans

用了reduce函数

1
2
3
4
5
6
7
8
class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        x = functools.reduce(lambda a, b: a ^ b, nums, 0)
        x = x & -x
        ans = [0, 0]
        for num in nums:
            ans[num & x == 0] ^= num
        return ans

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int x = 0;
        for (int num : nums) {
            x ^= num;
        }
        
        const int low_bit = x & (-x);
        vector<int> res(2, 0);
        for (int num : nums) {
            res[(num & low_bit) == 0] ^= num;
        }
        return res;
    }
};

56 - II. 数组中数字出现的次数 II

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1：

1
2
>输入：nums = [3,4,3,3]
>输出：4

示例 2：

1
2
>输入：nums = [9,1,7,9,7,9,7]
>输出：1

限制：

  • 1 <= nums.length <= 10000
  • 1 <= nums[i] < 2^31

题解见本博客另外一篇文章 single-number-ii

方法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            int cnt = 0;
            for (int num : nums) {
                cnt += (num >> i) & 1;
            }
            ans |= (cnt % 3) << i;
        }
        return ans;
    }
};

方法2

1
2
3
4
5
6
7
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        one = two = 0
        for num in nums:
            one = one ^ num & ~two
            two = two ^ num & ~one
        return one

57. 和为s的两个数字

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

示例 1：

1
2
>输入：nums = [2,7,11,15], target = 9
>输出：[2,7] 或者 [7,2]

示例 2：

1
2
>输入：nums = [10,26,30,31,47,60], target = 40
>输出：[10,30] 或者 [30,10]

限制：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6

方法1,：hash表，复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_set<int> vis;
        for (int num : nums) {
            int key = target - num;
            if (vis.find(key) != vis.end()) {
                return {num, key};
            }
            vis.insert(num);
        }
        return {};
    }
};

方法2： 由于是有序的数组，因此可以用双指针的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for (int i = 0, j = nums.size() - 1; i < j; ) {
            if (nums[i] + nums[j] == target) {
                return {nums[i], nums[j]};
            } else if (nums[i] + nums[j] < target) {
                ++i;
            } else {
                --j;
            }
        }
        return {};
    }
};

57 - II. 和为s的连续正数序列

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：

1
2
>输入：target = 9
>输出：[[2,3,4],[4,5]]

示例 2：

1
2
>输入：target = 15
>输出：[[1,2,3,4,5],[4,5,6],[7,8]]

限制：

  • 1 <= target <= 10^5

方法1， 枚举起点和终点，复杂度\(O(target \sqrt{target})\) // 长度不超过sqrt(target)

方法2：

枚举起点，直接用等差数列通项公式计算出需要多少个数才能到target，O(n) \[ \frac{(i + i + n - 1) * n}{2} = target \] 求上面的n即可

需要注意的是开根号出来需要是整数，最后求根公式的结果要是个偶数。

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:
    vector<vector<int>> findContinuousSequence(int target) {
        int end = target >> 1;
        vector<vector<int>> ans;
        for (int i = 1; i <= end; ++i) {
            long long temp = 2 * i - 1;
            long long x = (temp * temp + 8 * target);
            long long sqrt_x = sqrt(x);
            if (sqrt_x * sqrt_x != x) {
                continue;
            }
            int double_n = sqrt_x + (1 - 2 * i);
            if (double_n & 1) {
                continue;
            }
            int n = double_n >> 1;
            int e = i + n - 1;
            vector<int> cur(n, 0);
            for (int j = 0; j < n; ++j) {
                cur[j] = i + j;
            }
            ans.emplace_back(std::move(cur));
        }
        return ans;
    }
};

方法3

利用双指针滑动窗口。

当前为i...j，

  • 若sum(i, j) < target ，说明j需要往上加，使得和变大，这样才可能为target
  • 若sum(i, j) > target，说明i要往上加，使得和变小
  • 若sum(i, j) == target，则找到了

这个其实也是方法1的改进版本，若[i, j]为解(和为target)，那么[i + 1, j]的和必然小于target, 下一次遍历应该从j + 1开始，而不是l + 2

那么这个方法可能错过解吗？比如[i + 1, x - 1]是个解，会不会遍历的时候变成[i, x]导致错过？ 答案是否定的，[i, x]能便利到必然说明 [i, x -1]小于解，而sum[i + 1, x - 1] < sum[i, x - 1]

c++代码如下

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:
    vector<vector<int>> findContinuousSequence(int target) {
        int end = target >> 1;
        vector<vector<int>> ans;
        for (int i = 1, j = 1; i <= end; ) {
            int sum = (i + j) * (j - i + 1) >> 1;
            if (sum == target) {
                vector<int> cur(j - i + 1, 0);
                for (int x = i; x <= j; ++x) {
                    cur[x - i] = x;
                }
                ans.emplace_back(std::move(cur));
                ++i;                
            } else if (sum < target){
                ++j;
            } else {
                ++i;
            }
        }
        return ans;
    }
};

58 - I. 翻转单词顺序

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。

示例 1：

1
2
>输入: "the sky is blue"
>输出: "blue is sky the"

示例 2：

1
2
3
>输入: "  hello world!  "
>输出: "world! hello"
>解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

1
2
3
>输入: "a good   example"
>输出: "example good a"
>解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：

  • 无空格字符构成一个单词。
  • 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
  • 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

注意：本题与主站 151 题相同：https://leetcode-cn.com/problems/reverse-words-in-a-string/

注意：此题对比原题有改动

双指针遍历即可。。

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:
    string reverseWords(string s) {
        stringstream ss;
        for (int i = static_cast<int>(s.size()) - 1; i >= 0; ) {
            if (s[i] == ' ') {
                --i;
                continue;
            }
            int j = i - 1;
            for (; j >= 0 && s[j] != ' '; --j) {

            }
            ss << (s.substr(j + 1, i - j)) << " ";
            i = j;
        }
        string ans = ss.str();
        if (!ans.empty())
            ans.pop_back();
        return ans;
    }
};

python

1
2
3
class Solution:
    def reverseWords(self, s: str) -> str:
        return ' '.join(s.strip().split()[::-1])

58 - II. 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

示例 1：

1
2
>输入: s = "abcdefg", k = 2
>输出: "cdefgab"

示例 2：

1
2
>输入: s = "lrloseumgh", k = 6
>输出: "umghlrlose"

限制：

  • 1 <= k < s.length <= 10000

看代码吧。。太水了

c++

1
2
3
4
5
6
class Solution {
public:
    string reverseLeftWords(string s, int n) {
        return s.substr(n, s.size() - n) + s.substr(0, n);
    }
};

Python

1
2
3
class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        return s[n:] + s[:n]

59 - I. 滑动窗口的最大值

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
>输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
>输出: [3,3,5,5,6,7] 
>解释: 

 滑动窗口的位置                最大值
>---------------               -----
>[1  3  -1] -3  5  3  6  7       3
1 [3  -1  -3] 5  3  6  7       3
1  3 [-1  -3  5] 3  6  7       5
1  3  -1 [-3  5  3] 6  7       5
1  3  -1  -3 [5  3  6] 7       6
1  3  -1  -3  5 [3  6  7]      7

提示：

你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

注意：本题与主站 239 题相同：https://leetcode-cn.com/problems/sliding-window-maximum/

维护一个单调队列，题解详情还有分块法见另外一篇题解sliding-window-maximum

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:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if (nums.empty()) return {};
        deque<int> q;
        for (int i = 0; i < k; ++i) {
            while (!q.empty() && nums[i] > nums[q.back()]) {
                q.pop_back();
            }
            q.emplace_back(i);
        }
        vector<int> ans = {nums[q.front()]};
        for (int i = k; i < nums.size(); ++i) {
            if (q.front() + k <= i) {
                q.pop_front();
            }
            while (!q.empty() && nums[i] > nums[q.back()]) {
                q.pop_back();
            }
            q.emplace_back(i);
            ans.emplace_back(nums[q.front()]);
        }
        return ans;
    }
};

59 - II. 队列的最大值

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

示例 1：

1
2
3
4
>输入: 
>["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
>[[],[1],[2],[],[],[]]
>输出: [null,null,null,2,1,2]

示例 2：

1
2
3
4
>输入: 
>["MaxQueue","pop_front","max_value"]
>[[],[],[]]
>输出: [null,-1,-1]

限制：

  • 1 <= push_back,pop_front,max_value的总操作数 <= 10000
  • 1 <= value <= 10^5

和上一题一样，维护一个单调队列即可

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 MaxQueue {
    deque<int> _q;
    deque<int> _nums;
public:
    MaxQueue() {}
    
    int max_value() {
        if (_nums.empty()) return -1;
        return _q.front();
    }
    
    void push_back(int value) {
        while (!_q.empty() && _q.back() < value) {
            _q.pop_back();
        }
        _q.push_back(value);
        _nums.push_back(value);
    }
    
    int pop_front() {
        if (_nums.empty()) return -1;
        int temp = _nums[0];
        _nums.pop_front();
        if (temp == _q.front()) {
            _q.pop_front();
        }
        return temp;
    }
};

60. n个骰子的点数

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

示例 1:

1
2
>输入: 1
>输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]

示例 2:

1
2
>输入: 2
>输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]

限制：

1
>1 <= n <= 11

明显是个dp的过程。一个骰子的时候范围从[1, 6], 两个骰子从[2, 12]， 也就是n个骰子从[n, 6 * n].

设dp[i][j]为i个骰子和为j的概率，则dp[i][j + x] += dp[i - 1][j] * 1.0 / 6.0， 其中，\(x \in [1,6]\)表示这一层可能的取值，而dp[i - 1][j]就是上一层和为j的概率。

另外，空间复杂度可以优化为O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<double> dicesProbability(int n) {
        vector<double> last(1, 1.0);
        for (int i = 1; i <= n; ++i) {
            vector<double> dp(6 * i + 1, 0.0);
            for (int j = i - 1; j <= (i - 1) * 6; ++j) {
                for (int x = 1; x <= 6; ++x) {
                    dp[j + x] += last[j] / 6.0;
                }
            }
            last = dp;
        }
        vector<double> ans(last.begin() + n, last.end());
        return ans;
    }
};

61. 扑克牌中的顺子

从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

示例 1:

1
2
>输入: [1,2,3,4,5]
>输出: True

示例 2:

1
2
>输入: [0,0,1,2,5]
>输出: True

限制：

数组长度为 5

数组的数取值为 [0, 13] .

简单的思路：排序看看大小王的数目，看看两个数的差值是不是可以用大小王来填补（这里需要注意两个数相等的情况）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isStraight(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        std::size_t start = 0;
        while (start < nums.size() && nums[start] == 0) {
            ++start;
        }
        int zero_num = start;
        for (std::size_t i = start; i + 1 < nums.size(); ++i) {
            if (nums[i] + 1 == nums[i + 1]) { continue; }
            int need_zero = nums[i + 1] - nums[i] - 1;
            if (need_zero > zero_num || need_zero == -1) { return false; }
            zero_num -= need_zero;
        }
        return true;
    }
};

方法2：排序，看大小王的个数就能得到数组中最小的元素，然后max - min < 5说明有解

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool isStraight(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int num_joker = 0;
        for (std::size_t i = 0; i < nums.size(); ++i) {
            if (nums[i] == 0) ++ num_joker;
            else if (i + 1 < nums.size() && nums[i] == nums[i + 1]) return false;
        }
        return nums.back() - nums[num_joker] < 5;
    }
};

62. 圆圈中最后剩下的数字

0,1,...,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

示例 1：

1
2
>输入: n = 5, m = 3
>输出: 3

示例 2：

1
2
>输入: n = 10, m = 17
>输出: 2

限制：

  • 1 <= n <= 10^5
  • 1 <= m <= 10^6

这道题其实就是经典的约瑟夫问题。

以[0, 1, 2, 3, 4]这个为例，删除的过程如下：

1
2
3
4
5
6
 0  1  2  3  4
[0, 1, 2, 3, 4]       删除
[3, 4, 0, 1]          重新编号，删除0
[1, 3, 4]			  重新编号，删除4
[1, 3, 1, 3]		  重新编号，删除1
[3]

重新编号相当于把整个数组往前移动了m位，因此我们是可以从最后的结果反推出一开始的下标的：

1
2
3
4
5
最后剩下的3下标为0，
1. 上一轮其下标应该是： (0 + m) % 2 = 1 // 2为上一轮长度，所以这样
2. 在上一轮下表应该是:  (1 + m) % 3 = 1
3. 继续往上有4个元素， (1 + m) % 4 = 0
4. 最后为 (0 + m) % 5 = 3

因此代码就很简单了：

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int lastRemaining(int n, int m) {
        int ans = 0;
        for (int i = 2; i <= n; ++i) {
            ans = (ans + m) % i;
        }
        return ans;
    }
};

63. 股票的最大利润

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

示例 1:

1
2
3
4
>输入: [7,1,5,3,6,4]
>输出: 5
>解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
    注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

1
2
3
>输入: [7,6,4,3,1]
>输出: 0
>解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

限制：

1
>0 <= 数组长度 <= 10^5

注意：本题与主站 121 题相同：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

维护一个当前i之前的最小价格，然后看看当前卖出的利润prices[i] - cur_min是否为解即可

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
        int ans = 0;
        int cur_min = prices.front();
        for (std::size_t i = 0; i < prices.size(); ++i) {
            ans = max(ans, prices[i] - cur_min);
            cur_min = min(prices[i], cur_min);
        }
        return ans;
    }
};

64. 求1+2+…+n

求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

示例 1：

1
2
>输入: n = 3
>输出: 6

示例 2：

1
2
>输入: n = 9
>输出: 45

限制：

  • 1 <= n <= 10000

方法1，递归

1
2
3
4
5
6
7
class Solution {
public:
    int sumNums(int n) {
        n && (n += sumNums(n - 1));
        return n;
    }
};

方法2：俄罗斯农民乘法

小学数学是这样的：

1
2
3
4
5
6
7
   88
x  99
----------
  792
+792
----------
 8712

可以表示为

1
2
3
88 * 99 = 88 * 9 * 10^0 + 88 * 9 * 10^1
        = 792 + 7920
        = 8712

如果将第二个数表示为二进制，则有

1
2
3
4
5
6
7
8
88 * 0110 0011(2) = 88 * 0 * 2^7 
                  + 88 * 1 * 2^6 
                  + 88 * 1 * 2^5 
                  + 88 * 0 * 2^4 
                  + 88 * 0 * 2^3 
                  + 88 * 0 * 2^2 
                  + 88 * 1 * 2^1
                  + 88 * 1 * 2^0

因此可以写出如下quick_mul的代码，这里也弄了个quick_pow的代码供对比，基本上是比较类似的。

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 {
    int quick_pow(int n, int t) {
        int res = 1;
        while (t) {
            if (t & 1) {
                res = res * n;
            }
            n *= n;
            t >>= 1;
        }
        return res;
    }

    int quick_mul(int a, int b) {
        int ans = 0;
        while (b) {
            if (b & 1) {
                ans += a;
            }
            b >>= 1;
            a <<= 1;
        }
        return ans;
    }

public:
    int sumNums(int n) {
        return quick_mul(n, n + 1) >> 1;
    }
};

那么不用乘法和while怎么做？n 二进制展开最多不会超过 14 位，我们手动展开 14 层代替循环即可。

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
class Solution {
    int quick_mul(int a, int b) {
        int ans = 0;
        //1
        (b & 1) && (ans += a);
        b >>= 1;
        a <<= 1;
        //2
        (b & 1) && (ans += a);
        b >>= 1;
        a <<= 1;
        //3
        (b & 1) && (ans += a);
        b >>= 1;
        a <<= 1;
        //4
        (b & 1) && (ans += a);
        b >>= 1;
        a <<= 1;
        //5
        (b & 1) && (ans += a);
        b >>= 1;
        a <<= 1;
        //6
        (b & 1) && (ans += a);
        b >>= 1;
        a <<= 1;
        //7
        (b & 1) && (ans += a);
        b >>= 1;
        a <<= 1;
        //8
        (b & 1) && (ans += a);
        b >>= 1;
        a <<= 1;
        //9
        (b & 1) && (ans += a);
        b >>= 1;
        a <<= 1;
        //10
        (b & 1) && (ans += a);
        b >>= 1;
        a <<= 1;
        //11
        (b & 1) && (ans += a);
        b >>= 1;
        a <<= 1;
        //12
        (b & 1) && (ans += a);
        b >>= 1;
        a <<= 1;
        //13
        (b & 1) && (ans += a);
        b >>= 1;
        a <<= 1;
        //14
        (b & 1) && (ans += a);
        b >>= 1;
        a <<= 1;
        return ans;
    }

public:
    int sumNums(int n) {
        return quick_mul(n, n + 1) >> 1;
    }
};

65. 不用加减乘除做加法

难度简单106

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

示例:

1
2
>输入: a = 1, b = 1
>输出: 2

提示：

  • a, b 均可能是负数或 0
  • 结果不会溢出 32 位整数

方法1

异或操作符可以理解为%2加法，因此可以利用这个性质按位加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int add(int a, int b) {
        int ans = 0;
        int flag = 0;
        for (int i = 0; i < 32; ++i) {
            int x = (a >> i) & 1;
            int y = (b >> i) & 1;
            int t = x ^ y ^ flag;
            if (x == 1 && y == 1 || x == 1 && flag == 1 || y == 1 && flag == 1) {
                flag = 1;
            } else {
                flag = 0;
            }
            ans |= t << i;
        }
        return ans;
    }
};

方法2

其实可以更快一些，a ^ b的时候若两个位的数字相同，则结果变成了0，此时需要进位，而我们可以容易求得这些进位的位置为a & b​，然后下一次计算加上a & b << 1即可，直到进位为0就得到了最后的结果。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int add(int a, int b) {
        while (b != 0) {
            int c = (unsigned int)(a & b) << 1;
            a ^= b;
            b = c;
        }
        return a;
    }
};

66. 构建乘积数组

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

示例:

1
2
>输入: [1,2,3,4,5]
>输出: [120,60,40,30,24]

提示：

  • 所有元素乘积之和不会溢出 32 位整数
  • a.length <= 100000

构建两个数组left和right，left[i]表示从0到i的乘积，right[i]表示从n - 1到i的乘积，因此答案就是left[i - 1] * right[i + 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
class Solution {
public:
    vector<int> constructArr(vector<int>& a) {
        if (a.empty()) return {};
        if (a.size() < 2) return {0};
        int n = a.size();
        vector<int> left(n);
        vector<int> right(n);
        left[0] = a[0];
        right.back() = a.back();
        for (int i = 1; i < n; ++i) {
            left[i] = left[i - 1] * a[i];
            right[n - i - 1] = right[n - i] * a[n - i - 1];
        }
        vector<int> ans(n);
        for (int i = 0; i < n; ++i) {
            if (i == 0) {
                ans[i] = right[i + 1];
            } else if (i == n - 1){
                ans[i] = left[i - 1];
            } else {
                ans[i] = left[i - 1] * right[i + 1];
            }
        }
        return ans;
    }
};

68 - I. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

img

示例 1:

1
2
3
>输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
>输出: 6 
>解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

1
2
3
>输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
>输出: 2
>解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

  • 所有节点的值都是唯一的。
  • p、q 为不同节点且均存在于给定的二叉搜索树中。

注意：本题与主站 235 题相同：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (p->val > q->val) return lowestCommonAncestor(root, q, p);
        while (root) {
            if (p->val <= root->val && root->val <= q->val)  {
                return root;
            } else if (p->val > root->val) {
                root = root->right;
            } else {
                root = root->left;
            }
        }
        return nullptr;
    }
};

68 - II. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

img

示例 1:

1
2
3
>输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
>输出: 3
>解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:

1
2
3
>输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
>输出: 5
>解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

说明:

  • 所有节点的值都是唯一的。
  • p、q 为不同节点且均存在于给定的二叉树中。

注意：本题与主站 236 题相同：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

题解见本博客另外一篇文章 二叉树最近公共祖先详解（LCA问题详解）

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left && right) return root;
        return left ? left : right;
    }
};
请我喝杯咖啡吧~