记录书中一些比较经典的题目。
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1
的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
根据鸽巢原理，不断将数字交换到自身对应的下标上，直到发现重复的数字。
虽然代码中有两重循环，但每个数字最多只要交换两次就能找到属于它自己的位置，因此总的时间复杂度为
\(O(n)\) 。空间复杂度为 \(O(1)\) 。
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 (); i++) { while (nums[i] != i) { if (nums[nums[i]] == nums[i]) { return nums[i]; } int temp = nums[i]; nums[i] = nums[temp]; nums[temp] = temp; } } return -1 ; } };
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1
和
n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
方法一：二分查找
对区间 [1,n] （注意不是对数组 nums
）进行二分查找，每次只需统计前一半区间内的数字个数，如果大于区间长度，则说明这段区间一定有重复数字，否则另一半区间内一定有重复数字，然后继续对该半个区间进行划分。
一共划分 \(\log n\)
次，每次统计个数需要花费 O(n) 的时间，所以总的时间复杂度为
\(O(n\log n)\) 。空间复杂度为 \(O(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 Solution {public : int findDuplicate (vector<int > &nums) int lo = 1 , hi = nums.size () - 1 ; while (lo <= hi) { if (lo == hi) return lo; int mid = lo + ((hi - lo) >> 1 ); int cnt = count (nums, lo, mid); if (cnt > mid - lo + 1 ) { hi = mid; } else { lo = mid + 1 ; } } return -1 ; } int count (vector<int > &nums, int lo, int hi) int cnt = 0 ; for (int i : nums) { if (i >= lo && i <= hi) { cnt++; } } return cnt; } };
方法二：快慢指针
如果将数组看成链表，每个元素的下一个元素是其值作为下标对应的元素，我们发现，如果数组中存在重复元素，那么链表中一定会形成环，而环的入口就是那个重复的元素。于是我们的目标变成找到环的入口。
我们设置两个指针 slow 和 fast
，前者每走一步，后者走两步。假设 slow 走了 \(n\) 步时与 fast 相遇，则此时
fast 走了 \(2n\)
步，且其多走的 \(n\)
步一定是环周长的整数倍。然后我们再设置一个指针 entry
，让它从起点开始和 slow （从与 fast
的相遇点开始）一起同速前进，当它们再相遇时，指向的就是环的入口。
为什么 entry 和 slow
一定会在入口相遇呢？我们假设起点距离入口为 \(m\) ，则 slow 和
fast 相遇时，slow 已经在环中走了 \(n-m\) 步，如果再走 \(m\) 步，则一定会回到环的入口处（ \(n\) 是周长的整数倍），而此时
enrty 也走到了环的入口。
总结一下，这个算法有两个关键点：
先通过快慢指针得到 \(n\)
是环周长的整数倍，这个结论之后要用到。
slow 和 fast 相遇后，我们只知道此时
slow 再走 \(m\)
步就会回到环的入口处，但并不知道 \(m\)
具体是多少。设置 enrty 的目的就是通过它和 slow
的相遇来指示已同时到达环的入口。
时间复杂度 \(O(n)\) ，空间复杂度
\(O(1)\) 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution {public : int findDuplicate (vector<int > &nums) int slow = 0 ; int fast = 0 ; do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow != fast); int entry = 0 ; while (entry != slow) { entry = nums[entry]; slow = nums[slow]; } return entry; } };
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组
[3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
旋转数组由两段递增序列组成，且左子序列中的元素均不小于右子序列中的元素。
采用二分查找的思想，考虑三种情况：
中间元素小于最右元素，说明中间元素在右子序列中，排除其右侧部分；
中间元素大于最右元素，说明中间元素在左子序列中，排除其左侧部分；
中间元素等于最右元素，此时无法判断应排除哪一侧（例如最左、中间、最右元素均相等的情况），但至少可以排除最右元素，因为即使最右元素是最小值，我们还可以取与之相等的中间元素。
值得一提的是，该算法也兼容数组整体递增（把前 0
个元素搬到数组末尾）的特殊情况。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution {public : int minArray (vector<int > &numbers) int lo = 0 , hi = numbers.size () - 1 ; while (lo < hi) { int mid = lo + ((hi - lo) >> 1 ); if (numbers[mid] < numbers[hi]) hi = mid; else if (numbers[mid] > numbers[hi]) lo = mid + 1 ; else hi--; } return numbers[lo]; } };
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。
回溯法，通过将 board 中的元素置 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 36 class Solution {public : bool exist (vector<vector<char >> &board, string word) if (word.empty ()) return true ; int n = board.size (); int m = board[0 ].size (); if (word.size () > n * m) return false ; for (int i = 0 ; i < n; i++) { for (int j = 0 ; j < m; j++) { if (dfs (board, word, 0 , i, j)) return true ; } } return false ; } bool dfs (vector<vector<char >> &board, string word, int index, int i, int j) if (index >= word.size ()) return true ; if (i < 0 || j < 0 || i >= board.size () || j >= board[0 ].size ()) return false ; if (board[i][j] == word[index]) { board[i][j] = 0 ; if (dfs (board, word, index + 1 , i, j + 1 ) || dfs (board, word, index + 1 , i + 1 , j) || dfs (board, word, index + 1 , i, j - 1 ) || dfs (board, word, index + 1 , i - 1 , j)) return true ; board[i][j] = word[index]; } return false ; } };
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m
段（m、n都是整数，n>1并且m>1），每段绳子的长度记为
k[0],k[1]...k[m] 。请问 k[0]*k[1]*...*k[m]
可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
方法一：动态规划
注意考虑余下的 i - j 长度段不再剪的情况，即取
i - j 和 dp[i-j] 的最大值。
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution {public : int cuttingRope (int n) vector<int > dp (n + 1 ) ; dp[1 ] = 1 ; for (int i = 2 ; i <= n; i++) { for (int j = 1 ; j < i; j++) { dp[i] = max (dp[i], max (i - j, dp[i-j]) * j); } } return dp[n]; } };
方法二：贪心
当 n <= 3 时，由于题目要求至少剪一刀，返回
n - 1 。
当 n > 3 时，先尽可能多地剪出长度为 3
的片段，然后根据余下的长度分三种情况讨论：
余 0 ：直接返回 \(3^n\) 。
余 1 ：\(3+1=2+2\) ，即返回 \(3^{n-1} * 4\) 。
余 2 ：返回 \(3^n * 2\) 。
（详细证明见《剑指Offer》或 Leetcode 题解）
1 2 3 4 5 6 7 8 9 10 11 12 class Solution {public : int cuttingRope (int n) if (n <= 3 ) return n - 1 ; int q = n / 3 ; int r = n % 3 ; if (r == 0 ) return (int )pow (3 , q); if (r == 1 ) return (int )pow (3 , q - 1 ) * 4 ; return (int )pow (3 , q) * 2 ; } };
请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把
9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出
2。
方法一：有几位循环几次
左移 flag 而不是右移 n
，因为后者为负数时会导致死循环。
1 2 3 4 5 6 7 8 9 10 11 12 class Solution {public : int hammingWeight (uint32_t n) int cnt = 0 ; unsigned int flag = 1 ; while (flag) { if (n & flag) cnt++; flag = flag << 1 ; } return cnt; } };
方法二：有几个 1 循环几次
把一个整数减去 1，再和原整数做与运算，会把该整数最右边的 1 变成
0。
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; } };
实现函数double Power(double base, int
exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。
题目看似简单却暗藏杀机，至少有以下几点需要注意：
注意指数为负时可能引发的除零错误（虽然 LeetCode
上没有这种测试用例）。
注意边界情况。本题 n 的范围是 \([-2^{31},2^{31}-1]\) ，当 n
恰好为 \(-2^{31}\) 时，其绝对值将超出
32 位整型的表示范围 \([-2^{31},2^{31}-1]\) ，因此需要转换为
long long 类型。
注意时间复杂度。朴素的累乘会超时，这里我们用快速幂算法，复杂度可降到
\(O(\log n)\) 。
此外，还可以在一些小细节上做优化，例如用与运算代替求余运算符、用右移运算代替除法运算符。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution {public : double myPow (double x, int n) double res = 1.0 ; long long N = n; if (N < 0 ) { N = -N; x = 1.0 / x; } while (N) { if (N & 1 ) res *= x; x *= x; N >>= 1 ; } return res; } };
请实现一个函数用来匹配包含'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。
方法一：递归
首先定义一下“字符匹配”：字符串中的字符和模式中的字符相同，或模式中的字符为'.'。
设置两个指针 i 和 j
分别指向字符串的当前字符和模式的当前字符，分情况讨论：
模式中的第二个字符不是'*'
如果字符串中的第一个字符和模式中的第一个字符相匹配，则 i
和 j
都向后移动一个字符，然后匹配剩余的字符串和模式；否则直接返回
false 。
模式中的第二个字符是'*'
如果字符串中的第一个字符和模式中的第一个字符相匹配，则有三种情况：
'*'匹配字符串中的 0 个字符
仅在模式上向后移动两个字符，而字符串不动，相当于'*'和它前面的字符直接被忽略；
'*'匹配字符串中的 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 class Solution {public : bool isMatch (string s, string p) return _isMatch(s, p, 0 , 0 ); } bool _isMatch(string &s, string &p, int i, int j) { if (i == s.size () && j == p.size ()) return true ; if (i < s.size () && j == p.size ()) return false ; if (j + 1 < p.size () && p[j+1 ] == '*' ) { if (i < s.size () && (s[i] == p[j] || p[j] == '.' )) { return _isMatch(s, p, i, j + 2 ) || _isMatch(s, p, i + 1 , j + 2 ) || _isMatch(s, p, i + 1 , j); } else { return _isMatch(s, p, i, j + 2 ); } } if (i < s.size () && (s[i] == p[j] || p[j] == '.' )) return _isMatch(s, p, i + 1 , j + 1 ); return false ; } };
方法二：动态规划
定义状态 dp[i][j] 为 s 的前 i
个字符 s[0..i-1] 是否匹配 p 的前
j 个字符 p[0..j-1] 。
根据 s[i-1] 和 p[j-1] 的关系分类讨论：
s[i-1] 和 p[j-1]
匹配（同方法一中字符匹配的定义）
只要看 s 的前 i-1 个字符是否匹配
p 的前 j-1 个字符，即
dp[i][j] = dp[i-1][j-1] ；
p[j-1] 是'*'
考虑以下两种情况的或运算，即两者中成立一个就匹配：
p[j-1] 是正常字符却和 s[i-1] 不相同
只能是 dp[i][j] = false（代码中省略了，因为初值默认就是
false ）。
此外，还要尤其注意一下 dp 数组的初始化：
dp[0][0] = true ，表示空字符串和空模式是匹配的；dp[1..n][0] = false
，表示非空字符串和空模式是不匹配的；dp[0][1..m]
需要讨论，空字符串是有可能与非空模式相匹配的，因为'*'包括匹配 0
次的情况：
如果模式的当前字符 p[j-1]
是'*'，且模式向前两个字符的状态是匹配的，即dp[0][j-2] = true
，则 dp[0][j] = true ；
否则 dp[0][j] = false 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution {public : bool isMatch (string s, string p) int n = s.size (), m = p.size (); vector<vector<bool >> dp (n + 1 , vector <bool >(m + 1 )); dp[0 ][0 ] = true ; for (int j = 2 ; j <= m; j++) { if (p[j-1 ] == '*' && dp[0 ][j-2 ]) dp[0 ][j] = true ; } for (int i = 1 ; i <= n; i++) { for (int j = 1 ; j <= m; j++) { if (s[i-1 ] == p[j-1 ] || p[j-1 ] == '.' ) { dp[i][j] = dp[i-1 ][j-1 ]; } else if (p[j-1 ] == '*' ) { dp[i][j] = dp[i][j-2 ] || ((s[i-1 ] == p[j-2 ] || p[j-2 ] == '.' ) && dp[i-1 ][j]); } } } return dp[n][m]; } };
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
如果前序遍历和其对称遍历的序列一样，则二叉树是对称的。
注意这两个方向的遍历是可以同时进行并及时判别的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution {public : bool isSymmetric (TreeNode* root) if (root == nullptr ) return true ; return _isSymmetric(root->left, root->right); } bool _isSymmetric(TreeNode* root1, TreeNode* root2) { if (root1 == nullptr && root2 == nullptr ) return true ; if (root1 == nullptr || root2 == nullptr ) return false ; if (root1->val != root2->val) return false ; return _isSymmetric(root1->left, root2->right) && _isSymmetric(root1->right, root2->left); } };
请实现 copyRandomList
函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个
next 指针指向下一个节点，还有一个 random
指针指向链表中的任意节点或者 null。
分三步走：
沿着 next
复制每一个节点，并将复制的节点接在对应的原节点后面。
从头遍历链表，将每个复制节点的 random 设为原节点的
random 的下一个节点。
将链表拆分成原链表和复制链表。
这种方法既能达到 \(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 class Solution {public : Node* copyRandomList (Node* head) { if (head == nullptr ) return nullptr ; Node* curr = head; while (curr != nullptr ) { Node* copy = new Node (curr->val); copy->next = curr->next; curr->next = copy; curr = copy->next; } curr = head; while (curr != nullptr ) { Node* copy = curr->next; if (curr->random != nullptr ) copy->random = curr->random->next; curr = curr->next->next; } Node* head_copy = head->next; curr = head; while (curr != nullptr ) { Node* copy = curr->next; curr->next = copy->next; if (copy->next != nullptr ) copy->next = copy->next->next; curr = curr->next; } return head_copy; } };
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
基于递归的中序遍历，head
表示整个双向链表的首节点，pre 表示上一个根节点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution {private : Node* head = nullptr ; Node* pre = nullptr ; public : Node* treeToDoublyList (Node* root) { if (!root) return root; inorder (root); head->left = pre; pre->right = head; return head; } void inorder (Node* root) if (root->left) inorder (root->left); root->left = pre; if (pre) pre->right = root; else head = root; pre = root; if (root->right) inorder (root->right); } };
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
方法一：追加
从空字符串开始不断向末尾追加字符。
通过先对输入字符串进行排序，然后每次循环中判断前一个字符是否访问过且和当前字符相同，从而避免因存在重复字符而生成重复的排列。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution {public : vector<string> permutation (string s) { vector<string> res; vector<bool > visited (s.size()) ; string t; sort (s.begin (), s.end ()); dfs (res, visited, s, t); return res; } void dfs (vector<string>& res, vector<bool >& visited, string& s, string& t) if (t.size () == s.size ()) { res.push_back (t); return ; } for (int i = 0 ; i < s.size (); i++) { if (visited[i]) continue ; if (i > 0 && s[i-1 ] == s[i] && visited[i-1 ]) continue ; visited[i] = true ; t.push_back (s[i]); dfs (res, visited, s, t); t.pop_back (); visited[i] = false ; } } };
方法二：交换
直接在输入字符串上两两字符做交换。
通过判断待交换元素之间是否有与当前元素相同的元素，从而实现对重复情况的剪枝。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution {public : vector<string> permutation (string s) { vector<string> res; dfs (res, s, 0 ); return res; } void dfs (vector<string>& res, string& s, int start) if (start == s.size () - 1 ) { res.push_back (s); return ; } for (int i = start; i < s.size (); i++) { if (duplicate (s, start, i)) continue ; swap (s[start], s[i]); dfs (res, s, start + 1 ); swap (s[start], s[i]); } } bool duplicate (string& s, int start, int i) for (int j = start; j < i; j++) { if (s[j] == s[i]) return true ; } return false ; } };