持续更新中…
0x00 前言 本文在 CS-Notes/LeetCode 的基础上又进一步做了整理与补充。
双指针
排序
贪心思想
二分查找
分治
搜索
动态规划
数学
0x01 双指针 双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。
1. 有序数组的 Two Sum 167. Two Sum II - Input array is sorted (Easy)
【题目描述】
在有序数组中找出两个数，使它们的和为 target。
【示例】
1 2 Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2
【题解】
使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。
如果两个指针指向元素的和 sum == target，那么得到要求的结果；
如果 sum > target，移动较大的元素，使 sum 变小一些；
如果 sum < target，移动较小的元素，使 sum 变大一些。
数组中的元素最多遍历一次，时间复杂度为 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 : vector <int > twoSum (vector <int >& nums, int target) int i = 0 , j = nums.size() - 1 ; while (i < j) { int sum = nums[i] + nums[j]; if (sum == target) { return {i+1 , j+1 }; } else if (sum < target) { i++; } else { j--; } } return {-1 , -1 }; } };
拓展 1 - 若 nums 为无序数组呢？ 1.Two Sum
【题解 - 1】 暴力法
由于target已给出，故对每个nums[i]，我们希望找到这样一个j，使得nums[j] = target - nums[i]。因而最简单的便是两层 for 循环了。查找复杂度为 $O(n)$ ，总复杂度为 $O(n^2)$ ；
【题解 - 2】 利用STL的Hash表改善查找算法
可以利用STL中的 unordered_map 实现，<key, value> -> <nums[j], j>。
C++ 中map是基于红黑树实现的，unordered_map则基于哈希表实现。
注意到，该问题具有对称性，即由nums[i]查nums[j]和由nums[j]查nums[i]是等价的。因此，每访问一个元素，
在hash表中查询是否存在对应的j，若找到，则直接return。
将当前项加入hash表中。
由于hash表的查询效率为 $O(1)$ ，故总复杂度为 $O(n)$ 。
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution {public : vector <int > twoSum (vector <int >& nums, int target) unordered_map <int , int > hash; for (int i = 0 ; i < nums.size(); i++) { if (hash.count(target - nums[i]) > 0 ) { return {i, hash[target - nums[i]]}; } hash[nums[i]] = i; } return {-1 , -1 }; } };
拓展 2 - 三数之和 牛客网 - 数组中相加和为0的三元组
【题目描述】
给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。
注意：
三元组（a、b、c）中的元素必须按非降序排列。（即a≤b≤c）
解集中不能包含重复的三元组。
【示例】
1 2 3 4 输入 [-2,0,1,1,2] 返回值 [[-2,0,2],[-2,1,1]]
【题解】
首先对数组进行排序（从小到大）
依次取出第 i 个数（i从0开始），并且不重复的选取（跳过重复的数）
这样问题就转换为有序数组中的两数求和问题（可以用双指针解决方法）
定义两个指针：左指针（left） 和 右指针（right），target = -num[i]
从数组两端开始往中间找，当和恰好为 target 时，加入 res 数组，并跳过重复的数。
时间复杂度：O(nlogn) + 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 class Solution {public : vector <vector <int > > threeSum(vector <int > &num) { int n = num.size(); vector <vector <int > > res; if (n < 3 ) return res; sort(num.begin(), num.end()); for (int i = 0 ; i < n - 2 ; i++) { int l = i + 1 ; int r = n - 1 ; int target = -num[i]; while (l < r) { if (num[l] + num[r] < target) l++; else if (num[l] + num[r] > target) r--; else { vector <int > vec = {num[i], num[l], num[r]}; res.push_back(vec); while (l + 1 < r && num[l] == num[l+1 ]) l++; while (r - 1 > l && num[r] == num[r-1 ]) r--; l++, r--; } } while (i + 1 < n - 2 && num[i+1 ] == num[i]) i++; } return res; } };
2. 两数平方和 633. Sum of Square Numbers (Easy)
【题目描述】 判断一个非负整数是否为两个整数的平方和。
【示例】
1 2 3 Input: 5 Output: True Explanation: 1 * 1 + 2 * 2 = 5
【题解】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution public : bool judgeSquareSum (int c) { long long i = 0 ; long long j = sqrt(c); while (i <= j) { if (i*i + j*j == c) { return true ; } else if (i*i + j*j < c) { i++; } else { j--; } } return false ; } };
3. 反转字符串中的元音字符 345. Reverse Vowels of a String (Easy)
【题目描述】 编写一个函数，以字符串作为输入，反转该字符串中的元音字母。
【示例】
1 2 3 4 5 6 7 示例 1: 输入: "hello" 输出: "holle" 示例 2: 输入: "leetcode" 输出: "leotcede"
【题解】
使用双指针，一个指针从头向尾遍历，一个指针从尾到头遍历，当两个指针都遍历到元音字符时，交换这两个元音字符。
交换时可以新开一个string，也可以直接用STL里提供的swap函数由于内部实现为引用传递，故这里可以直接对s本身进行修改。
1 2 3 4 5 6 7 template <class T >void swap (T &a, T &b) T temp = a; a = b; b = temp; }
时间复杂度为 O(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 class Solution {private : bool isVowel (char c) if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' || c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U' ) return true ; else return false ; } public : string reverseVowels (string s) int i = 0 , j = s.length(); while (i <= j) { if (!isVowel(s[i])) { i++; } else if (!isVowel(s[j])) { j--; } else { swap(s[i++], s[j--]); } } return s; } };
4. 回文字符串 680. Valid Palindrome II (Easy)
【题目描述】 给定一个非空字符串 s，最多 删除一个字符。判断是否能成为回文字符串。
【示例】
1 2 3 4 5 6 7 8 示例 1: 输入: "aba" 输出: True 示例 2: 输入: "abca" 输出: True 解释: 你可以删除c字符。
【题解】
所谓回文字符串，是指具有左右对称特点的字符串，例如 “abcba” 就是一个回文字符串
本题的关键在于最多可以删除一个字符 ，因而本题可以用双指针来判断s是否为回文串，但如果出现两个指针指向的字符不相等的情况，我们可以删除左字符或右字符，直接判断子串是否为回文串 即可。
时间复杂度O(N)；采用引用传递 的方式将大大减少空间复杂度。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution {public : bool isPalindrome (const string & s, int i, int j) while (i < j) { if (s[i++] != s[j--]) { return false ; } } return true ; } bool validPalindrome (string s) for (int i=0 , j=s.length()-1 ; i < j; i++, j--) { if (s[i] != s[j]) { return isPalindrome(s, i+1 , j) | isPalindrome(s, i, j-1 ); } } return true ; } };
5. 归并两个有序数组 88. Merge Sorted Array (Easy)
【题目描述】 把归并结果存到第一个数组上。
【示例】
1 2 3 4 5 Input: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6]
【题解 - 1】
常规思路，简单的归并问题，要熟悉vector的使用。
对于本题来说，由于 nums1 的大小本来就是 m+n，因而如果使用vector的insert操作，还需要删除最后一个元素。
iterator insert(iterator it,const T& x) ：向量中迭代器指向元素前增加一个元素x
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution {public : void merge (vector <int >& nums1, int m, vector <int >& nums2, int n) int i = 0 , j = 0 ; int temp = 0 ; while (i < m && j < n) { if (nums1[i] >= nums2[j]) { nums1.insert(nums1.begin() + i, nums2[j]); nums1.pop_back(); i++, j++, m++; } else { i++; } } while (j < n) { nums1[i++] = nums2[j++]; } } };
【题解 - 2】
正向遍历时需要插入和删除操作，十分冗余，不妨直接覆盖原值。这就需要从尾开始遍历，否则在 nums1 上归并得到的值会覆盖还未进行归并比较的值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : void merge (vector <int >& nums1, int m, vector <int >& nums2, int n) int i = m-1 , j = n-1 ; int index = m+n-1 ; while (i >= 0 || j >= 0 ) { if (i < 0 ) { nums1[index--] = nums2[j--]; } else if (j < 0 ) { nums1[index--] = nums1[i--]; } else if (nums1[i] > nums2[j]) { nums1[index--] = nums1[i--]; } else { nums1[index--] = nums2[j--]; } } } };
下面这种写法可能更熟悉一些：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution {public : void merge (int A[], int m, int B[], int n) int k = m + n - 1 ; int i = m-1 , j = n-1 ; while (i >= 0 && j >= 0 ) { if (A[i] >= B[j]) { A[k--] = A[i--]; } else { A[k--] = B[j--]; } } while (i >= 0 ) A[k--] = A[i--]; while (j >= 0 ) A[k--] = B[j--]; return ; } };
6. 判断链表是否存在环 141. Linked List Cycle (Easy)
【题目描述】 给定一个链表，判断链表中是否有环
【题解 - 1】快慢指针法
通过使用具有 不同速度 的快、慢两个指针遍历链表，空间复杂度可以被降低至 O(1)。慢指针每次移动一步，而快指针每次移动两步。
如果链表中不存在环，最终快指针将会最先到达尾部，此时我们可以返回 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 class Solution {public : bool hasCycle (ListNode *head) if (head == NULL ) { return false ; } ListNode *l1 = head, *l2 = head->next; while (l1 != NULL && l2 != NULL && l2->next != NULL ) { if (l1 == l2) { return true ; } l1 = l1->next; l2 = l2->next->next; } return false ; } };
【题解 - 2】 标记法
用一个map标记走过的地方，每访问一个结点，查看是否已经访问过。
但这种方法耗时是解法1的二倍，应该是 visited.count(l) 要比 l1 == l2 更加耗时。
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 : bool hasCycle (ListNode *head) if (head == NULL ) { return false ; } unordered_map <ListNode*, int > visited; visited[head] = 1 ; for (ListNode *l = head->next; l != NULL ; l = l->next) { if (visited.count(l) > 0 ) { return true ; } visited[l] = 1 ; } return false ; } };
7. 最长子序列（中） 524. Longest Word in Dictionary through Deleting (Medium)
【题目描述】 给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。
如果答案不止一个，返回长度最长且字典顺序最小 的字符串。
如果答案不存在，则返回空字符串。
【示例】
1 2 3 4 5 6 7 示例 1: 输入: s = "abpcplea", d = ["ale","apple","monkey","plea"] 输出: "apple" 示例 2: 输入: s = "abpcplea", d = ["a","b","c"] 输出: "a"
【题解】
简单的公共子串问题，双指针解决，注意最终答案优先级的比较即可。
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 class Solution {private : bool isSubstr (const string & s, const string & p) int i = 0 , j = 0 ; int m = s.length(), n = p.length(); while (i < m && j < n) { if (s[i] == p[j]) { i++, j++; } else { i++; } } return j==n; } int compare (const string & s1, const string & s2) int len1 = s1.length(), len2 = s2.length(); if (len1 > len2) { return 1 ; } else if (len1 < len2) { return -1 ; } else { int i = 0 , j = 0 ; while (i < len1 && j < len2) { if (s1[i] < s2[j]) { return 1 ; } else if (s1[i] > s2[j]) { return -1 ; } else { i++, j++; } } } return 0 ; } public : string findLongestWord (string s, vector <string >& d) string longestWord = "" ; for (auto iter = d.begin(); iter != d.end(); iter++) { string word = *iter; if (isSubstr(s, word) && compare(longestWord, word) < 0 ) { longestWord = word; } } return longestWord; } };
8. 最长不含重复字符的子字符串 剑指 Offer 48. 最长不含重复字符的子字符串
【题目描述】
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
【示例】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 示例 1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2: 输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3: 输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。 示例 4: 输入: "abba" 输出: 3
【题解】
由于子串是要求连续的，因此可以用一个 map<int, int> 保存当前字符上次出现的位置，并用 lastIndex 保存上一个重复字符的最大下标（为什么是最大？考虑 abba 这种情况）；
每遇到一个重复字符，更新 lastIndex 的值；
对每个字符，更新 map 中的值，并更新 maxLen。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution {public : int lengthOfLongestSubstring (string s) map <int , int > mp; int maxLen = 0 ; int lastIndex = -1 ; for (int i = 0 ; i < s.length(); i++) { if (mp.count(s[i]) > 0 ) { lastIndex = max(lastIndex, mp[s[i]]); } maxLen = max(maxLen, i - lastIndex); mp[s[i]] = i; } return maxLen; } };
0x02 排序 1. 快排序与堆排序（中） 用于求解 Kth Element 问题，也就是第K个元素的问题。
215. Kth Largest Element in an Array (Medium)
【题目描述】 在未排序的数组中找到第 k 个最大的元素。
【示例】
1 2 输入: [3,2,1,5,6,4] 和 k = 2 输出: 5
【题解 - 1】 快速选择法
在快速排序中，每次经过「划分」操作后，我们一定可以确定一个元素的最终位置 ，即 $x$ 的最终位置为 $q$ ，所以只要某次划分的 q 为倒数第 k 个下标的时候，我们就已经找到了答案。
算法步骤：
随机选择一个枢轴。
使用划分算法 将小于枢轴的元素移到左边，大于等于枢轴的元素移到右边，确定枢轴的最终位置 $pos$。
比较 $pos$ 和 $target = N - k$ 的大小
如果划分得到的 $pos$ 正好就是我们需要的下标，就直接返回 $a[q]$ ；
否则，如果 $pos$ 比目标下标小，就递归右子区间，否则递归左子区间。
快速选择算法 的平均时间复杂度为 O(N)。
直观地理解如果每次规模为 n 的问题我们都划分成 1 和 n - 1，每次递归的时候又向 n - 1 的集合中递归，这种情况是最坏的，时间代价是 O(n^2)。我们可以引入随机化来加速这个过程，它的时间代价的期望是 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 class Solution {public : inline int randomPartition (vector <int >& a, int l, int r) int i = rand() % (r - l + 1 ) + l; swap(a[i], a[r]); return partition(a, l, r); } inline int partition (vector <int >& a, int l, int r) int key = a[r], i = l - 1 ; for (int j = l; j < r; ++j) { if (a[j] <= key) { swap(a[++i], a[j]); } } swap(a[++i], a[r]); return i; } int quickSelectKthMin (vector <int >& a, int l, int r, int target) int pos = randomPartition(a, l, r); if (pos == target) { return a[pos]; } else { return pos < target ? quickSelectKthMin(a, pos + 1 , r, target) : quickSelectKthMin(a, l, pos - 1 , target); } } int findKthLargest (vector <int >& nums, int k) return quickSelectKthMin(nums, 0 , nums.size() - 1 , nums.size() - k); } };
【题解 - 2】 堆排序
维护一个大小为K的大顶堆，则堆顶元素就是第K大的元素。
利用C++的priority_queue实现，复杂度为 O(Nlogk)，实际用时与快排相差无几。
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution {public : int findKthLargest (vector <int >& nums, int k) priority_queue <int , vector <int >, greater<int > > q; for (int i = 0 ; i < nums.size(); i++) { q.push(nums[i]); if (q.size() > k) { q.pop(); } } return q.top(); } };
2. 桶排序 2.1 出现频率最多的 k 个元素（中） 347. Top K Frequent Elements (Medium)
【题目描述】 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
【示例】
1 2 3 4 示例 1: 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]
【题解】 桶排序
统计各元素出现的次数
设置若干个桶，每个桶存储出现频率相同的数 ，桶的下标表示数出现的频率，即第 i 个桶中存储的数出现的频率为 i。
把数都放到桶之后，从后向前遍历桶，最先得到的 k 个数就是出现频率最多的的 k 个数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution {public : vector <int > topKFrequent (vector <int >& nums, int k) unordered_map <int , int > freq; for (auto num: nums) { freq[num]++; } list <int > buckets[nums.size() + 1 ]; for (auto iter = freq.begin(); iter != freq.end(); iter++) { buckets[iter->second].push_back(iter->first); } vector <int > res (k) int cnt = 0 ; for (int i = nums.size(); i > 0 ; i--) { for (auto num: buckets[i]) { res[cnt++] = num; if (cnt == k) return res; } } return res; } };
2.2 按照字符出现次数对字符串排序（中） 451. Sort Characters By Frequency (Medium)
【题目描述】 给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
要求：
相同的字母必须放在一起
‘A’ 和 ‘a’ 看作两种不同的字符
显然，答案可以不唯一
【示例】
1 2 3 输入: "tree" 输出: "eert" 解释: 'e'出现两次，'r'和't'都只出现一次。因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
【题解】 桶排序
同上一题。
统计每个字符的频率
设置若干个桶，每个桶存储出现频率相同的字符 ，桶的下标表示数出现的频率，即第 i 个桶中存储的字符出现的频率为 i。
把字符都放到桶之后，从后向前遍历桶，注意输出相同字符。
【我的桶排序】
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 class Solution {public : string frequencySort (string s) unordered_map <char , int > freq; for (int i = 0 ; i < s.length(); i++) { freq[s[i]]++; } list <char > buckets[s.length() + 1 ]; for (auto iter = freq.begin(); iter != freq.end(); iter++) { buckets[iter->second].push_back(iter->first); } stringstream ss; for (int i = s.length(); i > 0 ; i--) { for (auto c: buckets[i]) { for (int k = 0 ; k < i; k++) { ss << c; } } } return ss.str(); } };
【别人家的桶排序】
利用二维vector实现buckets，似乎也还不错。
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 : string frequencySort (string s) int N = s.size(); vector <int > counts (129 , 0 ) for (auto c : s) ++counts[c]; vector <vector <char >> buckets(N + 1 ); for (int i = 1 ; i <= 128 ; ++i) { if (counts[i] > 0 ) { buckets[counts[i]].push_back(i); } } string res; for (int i = N; i > 0 ; --i) { for (auto c : buckets[i]) { res.append(i, c); } } return res; } };
3. 荷兰国旗问题 - 三向切分快排（中） 荷兰国旗包含三种颜色：红、白、蓝。
有三种颜色的球，算法的目标是将这三种球按颜色顺序正确地排列。它其实是三向切分快速排序 的一种变种，在三向切分快速排序中，每次切分都将数组分成三个区间：小于切分元素、等于切分元素、大于切分元素，而该算法是将数组分成三个区间：等于红色、等于白色、等于蓝色。
75. Sort Colors (Medium)
【题目描述】 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
【示例】
1 2 输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]
【题解】
我们用三个指针（p0, p2 和cur）来分别追踪0的最右边界，2的最左边界和当前考虑的元素。
本解法的思路是沿着数组移动 cur 指针，若 nums[cur] = 0，则将其与 nums[p0] 互换；若 nums[curr] = 2 ，则与 nums[p2] 互换。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution {public : void sortColors (vector <int >& nums) int p0 = 0 , cur = 0 , p2 = nums.size() - 1 ; while (cur <= p2) { if (nums[cur] == 0 ) { swap(nums[cur++], nums[p0++]); } else if (nums[cur] == 2 ) { swap(nums[cur], nums[p2--]); } else { cur++; } } } };
0x03 贪心思想 保证每次操作都是局部最优的，并且最后得到的结果是全局最优的。
1. 分配饼干 455. Assign Cookies (Easy)
【题目描述】 每个孩子都有一个满足度 grid，每个饼干都有一个大小 size，只有饼干的大小大于等于一个孩子的满足度，该孩子才会获得满足。求解最多可以获得满足的孩子数量。
【示例】
1 2 Input: grid[1,3], size[1,2,4] Output: 2
【题解】
给一个孩子的饼干应当尽量小并且又能满足该孩子，这样大饼干才能拿来给满足度比较大的孩子。
因为满足度最小的孩子最容易得到满足，所以先满足满足度最小的孩子。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution {public : int findContentChildren (vector <int >& g, vector <int >& s) sort(g.begin(), g.end()); sort(s.begin(), s.end()); int i = 0 , j = 0 ; while (i < g.size() && j < s.size()) { if (g[i] <= s[j]) { i++; } j++; } return i; } };
【贪心策略的证明】
在以上的解法中，我们只在每次分配时饼干时选择一种看起来是当前最优的分配方法，但无法保证这种局部最优的分配方法最后能得到全局最优解，下用反证法证明。
假设在某次选择中，贪心策略选择给当前满足度最小的孩子分配第 m 个饼干，第 m 个饼干为可以满足该孩子的最小饼干。假设存在一种最优策略，可以给该孩子分配第 n 个饼干，并且 m < n。我们可以发现，经过这一轮分配，贪心策略分配后剩下的饼干一定有一个比最优策略来得大。因此在后续的分配中，贪心策略一定能满足更多的孩子。也就是说不存在比贪心策略更优的策略，即贪心策略就是最优策略。
2. 不重叠的区间个数（中） 435. Non-overlapping Intervals (Medium)
【题目描述】 给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
【示例】
1 2 3 输入: [ [1,2], [2,3], [3,4], [1,3] ] 输出: 1 解释: 移除 [1,3] 后，剩下的区间没有重叠。
【题解】 按照贪心的思想，在每次选择中，区间的结尾最为重要，因为选择的区间结尾越小，留给后面的区间的空间越大，那么后面能够选择的区间个数也就越大。
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 : int eraseOverlapIntervals (vector <vector <int >>& intervals) if (intervals.empty()) return 0 ; sort(intervals.begin(), intervals.end()); int cnt = 0 , end = intervals[0 ][1 ]; for (int i = 1 ; i < intervals.size(); i++) { if (intervals[i][0 ] < end) { end = min(end, intervals[i][1 ]); cnt++; } else { end = intervals[i][1 ]; } } return cnt; } };
3. 投飞镖刺破气球（中） 452. Minimum Number of Arrows to Burst Balloons (Medium)
【题目描述】 气球在一个水平数轴上摆放，可以重叠，飞镖垂直投向坐标轴，使得路径上的气球都被刺破。求解最小的投飞镖次数使所有气球都被刺破。
【示例】
1 2 输入：points = [[1,2],[2,3],[3,4],[4,5]] 输出：2
【题解】
同前一题，计算不重叠的区间个数，区别在于，[1, 2] 和 [2, 3] 在本题中算是重叠区间。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : int findMinArrowShots (vector <vector <int >>& points) if (points.empty()) return 0 ; sort(points.begin(), points.end()); int cnt = 1 , end = points[0 ][1 ]; for (int i = 1 ; i < points.size(); i++) { if (points[i][0 ] <= end) { end = min(end, points[i][1 ]); } else { end = points[i][1 ]; cnt++; } } return cnt; } };
4. 根据身高和序号重组队列（难） 406. Queue Reconstruction by Height(Medium)
【题目描述】 给定一组打乱的队列，每个人用两个分量 (h, k) 描述，h 表示身高，k 表示排在前面的有 k 个人的身高比他高或者和他一样高，请据此重组队列。
【示例】
1 2 Input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]] Output: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
【题解】
插入排序：
为了使插入操作不影响后续的操作，身高较高的学生应该先做插入操作 ，否则身高较小的学生原先正确插入的第 k 个位置可能会变成第 k+1 个位置。
当身高相同时，按照k升序排序。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {private : static bool compare (vector <int > &a, vector <int > &b) return (a[0 ] > b[0 ]) || (a[0 ] == b[0 ] && a[1 ] < b[1 ]); } public : vector <vector <int >> reconstructQueue(vector <vector <int >>& people) { if (people.empty()) return people; sort(people.begin(), people.end(), compare); vector <vector <int >> queue ; for (auto person: people) { queue .insert(queue .begin() + person[1 ], person); } return queue ; } };
5. 买卖股票的最大收益 121. Best Time to Buy and Sell Stock (Easy)
**【题目描述】 **给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
【示例】
【题解】
记录前面最小的价格，并将这个最小价格作为买入价格；
然后将当前收益作为售出价格，与最大收益比较。
1 2 3 4 5 6 7 8 9 10 11 class Solution {public : int maxProfit (vector <int >& prices) int min_price = prices[0 ], max_profit = 0 ; for (int i = 1 ; i < prices.size(); i++) { max_profit = max(max_profit, prices[i] - min_price); min_price = min(min_price, prices[i]); } return max_profit; } };
6. 买卖股票的最大收益 ‖ 122. Best Time to Buy and Sell Stock II (Easy)
【题目描述】 可以进行多次交易，但多次交易之间不能交叉进行。
【示例】
1 2 3 4 输入: [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
【题解】
有一说一，这个真没想到…
对于 [a, b, c, d]，如果有 a <= b <= c <= d ，那么最大收益为 d - a。而 d - a = (d - c) + (c - b) + (b - a) ，因此当访问到一个 prices[i] 且 prices[i] - prices[i-1] > 0，那么就把 prices[i] - prices[i-1] 添加到收益中。
1 2 3 4 5 6 7 8 9 10 11 12 class Solution {public : int maxProfit (vector <int >& prices) int profit = 0 ; for (int i = 1 ; i < prices.size(); i++) { if (prices[i] > prices[i-1 ]) { profit += (prices[i] - prices[i-1 ]); } } return profit; } };
7. 种植花朵 605. Can Place Flowers (Easy)
【题目描述】
flowerbed 数组中 1 表示已经种下了花朵。花朵之间至少需要一个单位的间隔，求解能否再种下 n 朵花。
【示例】
1 2 Input: flowerbed = [1,0,0,0,1], n = 1 Output: True
【题解】
考虑当前位能否种花，即考虑相邻两位是否为1即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution {public : bool canPlaceFlowers (vector <int >& flowerbed, int n) int len = flowerbed.size(); int cnt = 0 ; for (int i = 0 ; i < len; i++) { if (flowerbed[i] == 1 ) { continue ; } int last = i == 0 ? 0 : flowerbed[i-1 ]; int next = i == len-1 ? 0 : flowerbed[i+1 ]; if (last == 0 && next == 0 ) { cnt++; flowerbed[i] = 1 ; } } return cnt >= n; } };
8. 判断是否为子序列（中） 392. Is Subsequence (Medium) 略
9. 修改一个数成为非递减数组 665. Non-decreasing Array (Easy)
【题目描述】 判断一个数组是否能只修改一个数就成为非递减数组。
【示例】
1 2 Input: [4,2,3] Output: True
【题解】
当出现 nums[i-1] > nums[i] 时，有两种修改方案，我们不妨优先令 nums[i-1] = nums[i] ，即把前一个数放小，但可能会出现 nums[i-1] 比其前面的数（如 nums[i-2] ）更小的情况。
为了探索其中的规律，我们考虑下面三种情况：
1 2 3 4，2，3 -1，4，2，3 2，3，3，2，4
如果再前面的数不存在，如case1，直接修改 nums[i-1]=2 即可.
如果再前面的数存在，且小于当前数时，如case2，-1 < 2，修改 nums[i-1]=2 即可。
如果再前面的数存在，但大于当前数时，如case3，3 > 2，若把 nums[i-1]=2 会使得 nums[i-2] > nums[i-1] ，因此只能修改 nums[i]=3 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution {public : bool checkPossibility (vector <int >& nums) int cnt = 0 ; for (int i = 1 ; i < nums.size() && cnt <= 1 ; i++) { if (nums[i-1 ] <= nums[i]) { continue ; } cnt++; if (i-2 >= 0 && nums[i-2 ] > nums[i]) { nums[i] = nums[i-1 ]; }else { nums[i-1 ] = nums[i]; } } return cnt <= 1 ; } };
10. 子数组最大的和 53. Maximum Subarray (Easy)
【题目描述】 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
【示例】
1 2 输入: [-2,1,-3,4,-1,2,1,-5,4] 输出: 6
【题解】
重点在于连续子数组，故主要是看前面的和 。若大于0，则加上，否则，从当前开始重新计算和。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution {public : int maxSubArray (vector <int >& nums) if (nums.empty()) return 0 ; int preSum = nums[0 ]; int maxSum = preSum; for (int i = 1 ; i < nums.size(); i++) { preSum = preSum > 0 ? preSum+nums[i] : nums[i]; maxSum = max(maxSum, preSum); } return maxSum; } };
11. 分隔字符串使同种字符出现在一起（难） 763. Partition Labels (Medium)
【题目描述】
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
【示例】
1 2 输入：S = "ababcbacadefegdehijhklij" 输出：[9,7,8]
【题解】
从第一个字母开始分析，假设第一个字母是 ‘a’，那么第一个区间一定包含最后一次出现的 ‘a’。但第一个出现的 ‘a’ 和最后一个出现的 ‘a’ 之间可能还有其他字母，而这些字母会让区间变大。
因此， 对于遇到的每一个字母，我们可以先找到这个字母最后一次出现的位置，再以此更新当前的最小区间。
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 > partitionLabels (string s) int end[26 ]; for (int i = 0 ; i < s.length(); i++) { end[s[i] - 'a' ] = i; } vector <int > res; int left = -1 , right = 0 ; for (int i = 0 ; i < s.length(); i++) { right = max(right, end[s[i] - 'a' ]); if (i == right) { res.push_back(right - left); left = right; } } return res; } };
0x04 二分查找 二分查找也称为折半查找，每次都能将查找区间减半，这种折半特性的算法时间复杂度为 O(logN)。
【伪代码】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 public int binarySearch (int [] nums, int key) int l = 0 , h = nums.length - 1 ; while (l <= h) { int m = l + (h - l) / 2 ; if (nums[m] == key) { return m; } else if (key < nums[m]) { h = m - 1 ; } else { l = m + 1 ; } } return -1 ; }
【注意】
有两种计算中值 m 的方式：
m = (l + h) / 2
m = l + (h - l) / 2
l + h 可能出现加法溢出，也就是说加法的结果大于整型能够表示的范围。但是 l 和 h 都为正数，因此 h - l 不会出现加法溢出问题。所以，最好使用第二种计算法方法。
【变式】
二分思想很简单，但细节真的是魔鬼…
当使用二分查找的思想解决问题时，需仔细分析两点：
如何确定index在左子区间还是右？
跳出循环的条件？应返回什么？
1. 求开方 69. Sqrt(x) (Easy)
【题目描述】 实现 int sqrt(int x) 函数。计算并返回 x 的平方根，结果只保留整数的部分，其中 x 是非负整数。
【示例】
【题解】
一个数 x 的开方 sqrt 一定在 0 ~ x 之间，且非负整数 sqrt 必满足 ，因此可以利用二分查找，每一轮查询比较 m 和 x/m 的大小，即令 key = x/m。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution {public : int mySqrt (int x) if (x <= 1 ) return x; int l = 1 , h = x; while (l <= h) { int m = l + (h-l) / 2 ; int key = x / m; if (key == m) { return m; } else if (key < m) { h = m - 1 ; } else { l = m + 1 ; } } return h; } };
2. 大于给定元素的最小元素 744. Find Smallest Letter Greater Than Target (Easy)
【题目描述】
给定一个有序的字符数组 letters 和一个字符 target，要求在找出 letters 中大于 target 的最小字符，如果找不到就返回第 1 个字符。
【示例】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 输入: letters = ["c", "f", "j"] target = "c" 输出: "f" 输入: letters = ["c", "f", "j"] target = "a" 输出: "c" 输入: letters = ["c", "f", "j"] target = "k" 输出: "c"
【题解】
当循环条件不成立时，l 总是比 r 大1，因为要找的是比target大的字母，所以取 l 。
考虑两种特殊情况：
如果符合条件的字母 比letters中的字母都小，则最后一定是 l = 0, r = -1，所以取 l 。
如果符合条件的字母 比letters中的字母都大，则最后一定是 l = n, r = n-1, 所以取 0。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution {public : char nextGreatestLetter (vector <char >& letters, char target) int n = letters.size(); int l = 0 , r = n - 1 ; while (l <= r) { int m = l + (r-l) / 2 ; if (letters[m] <= target) { l = m + 1 ; } else { r = m - 1 ; } } return l < n ? letters[l] : letters[0 ]; } };
3. 有序数组的 Single Element（中） 540. Single Element in a Sorted Array (Medium)
【题目描述】
给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
【示例】
1 2 输入: [1,1,2,3,3,4,4,8,8] 输出: 2
【题解】
假设 index 为 Single Element 在数组中的位置，显然 index 一定是偶数 ，且在 index 之后，数组中原来存在的成对状态将被改变。
如果 m 是偶数：
当 m < index 时，必有 nums[m] == nums[m+1] ；
当 m >= index 时，必有 nums[m] != nums[m+1] 。
可由此二分区间。（第一次做的时候又是m+1又是m-1的，一堆if-else嵌套，逻辑混乱不说还做不对，难想啊啊啊）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : int singleNonDuplicate (vector <int >& nums) int n = nums.size(); int l = 0 , r = n - 1 ; while (l < r) { int m = l + (r-l) / 2 ; if (m % 2 == 1 ) { m--; } if (nums[m] == nums[m+1 ]) { l = m + 2 ; } else { r = m; } } return nums[l]; } };
4. 第一个错误的版本 278. First Bad Version (Easy)
【题目描述】 给定一个元素 n 代表有 [1, 2, …, n] 版本，在第 x 位置开始出现错误版本，导致后面的版本都错误。可以调用 isBadVersion(int x) 知道某个版本是否错误，要求找到第一个错误的版本。
【示例】
1 2 3 4 5 6 7 给定 n = 5，并且 version = 4 是第一个错误的版本。 调用 isBadVersion(3) -> false 调用 isBadVersion(5) -> true 调用 isBadVersion(4) -> true 所以，4 是第一个错误的版本。
【题解】
如果第 m 个版本出错，则表示第一个错误的版本在 [l, m] 之间，令 h = m；
否则第一个错误的版本在 [m + 1, h] 之间，令 l = m + 1。
又因为 h 的赋值表达式为 h = m，因此循环条件为 l < h。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution {public : int firstBadVersion (int n) int l = 1 , r = n; while (l < r) { int m = l + (r-l) / 2 ; if (isBadVersion(m)) { r = m; } else { l = m + 1 ; } } return l; } };
5. 旋转数组的最小数字（中） 153. Find Minimum in Rotated Sorted Array (Medium)
【题目描述】 假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] 。
请找出其中最小的元素。
【示例】
1 2 输入：nums = [3,4,5,1,2] 输出：1
【题解】
整个数组是分段递增的，且左区间必定大于右区间元素。
因此，
当 m 小于右端点时，index必定在左子区间；
当 m 大于右端点时，index必定在右子区间；
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution {public : int findMin (vector <int >& nums) int n = nums.size(); int l = 0 , r = n - 1 ; while (l < r) { int m = l + (r-l) / 2 ; if (nums[m] <= nums[r]) { r = m; } else { l = m + 1 ; } } return nums[l]; } };
6. 查找区间 34. Find First and Last Position of Element in Sorted Array
【题目描述】 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
【示例】
1 2 输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]
【题解1】
二分查找到第一个target，即左端点，然后从左往右遍历，找到右端点。
左端点：第一个大于等于target的下标；
若 nums[m] < target，查找区间 $[m+1, r]$
若 nums[m] >= target，查找区间 $[l, m]$
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 > searchRange (vector <int >& nums, int target) int n = nums.size(); int l = 0 , r = n - 1 ; while (l < r) { int m = l + (r-l) / 2 ; if (nums[m] < target) { l = m + 1 ; } else { r = m; } } if (n == 0 || nums[l] != target) { return {-1 , -1 }; } while (r < n && nums[r] == target) { r++; } return {l, r-1 }; } };
【题解2 - 查左右端点】
在排序数组中查找元素的第一个和最后一个位置。
左端点略，重点是查找右端点的细节，绊了很久…
右端点 ed：第一个大于target的下标。
若 nums[m] <= target，查找区间 $[m+1, r]$
若 nums[m] > target，查找区间 $[l, m]$
务必注意 n = 0, n = 1, n = 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 class Solution {public : vector <int > searchRange (vector <int >& nums, int target) int n = nums.size(); if (n == 0 ) return {-1 , -1 }; int l, r, st, ed; l = 0 , r = n - 1 ; while (l < r) { int m = l + (r-l) / 2 ; if (nums[m] < target) { l = m + 1 ; } else { r = m; } } st = l; cout << st << endl ; l = 0 , r = n - 1 ; while (l < r) { int m = l + (r-l) / 2 ; if (nums[m] <= target) { l = m + 1 ; } else { r = m; } } ed = nums[r]==target? r: r-1 ; cout << ed << endl ; if (st <= ed && ed < n && nums[st] == target && nums[ed] == target) return {st, ed}; return {-1 , -1 }; } };
0x05 分治法 说是分治，其实完全可以归类为动态规划问题。
1. 给表达式加括号（难） 241. Different Ways to Add Parentheses (Medium)
【题目描述】 给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。
【示例】
1 2 3 4 5 输入: "2-1-1" 输出: [0, 2] 解释: ((2-1)-1) = 0 (2-(1-1)) = 2
【题解 - 带备忘录的自顶向下法】
区间选择：使用[left, right)的左闭右开区间。
区间划分：遍历字符串，根据符号来划分左右区间，直至区间内只有一个纯数字（最小子问题）。
区间合并：每个区间都有一个vector存储所有可能的计算结果，将左右两个区间的结果分别进行对应的op操作。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 class Solution {private : map <pair <int , int >, vector <int >> memo; public : int calc (const char & op, const int & x, const int & y) switch (op) { case '+' : return x + y; case '-' : return x - y; case '*' : return x * y; default : break ; } return 0 ; } vector <int > dfs (const string & input, int left, int right) if (memo.find(make_pair (left, right)) != memo.end()) { return memo[make_pair (left, right)]; } vector <int > res; for (int i = left; i < right; i++) { char op = input[i]; if (op == '+' || op == '-' || op == '*' ) { vector <int > lRes = dfs(input, left, i); vector <int > rRes = dfs(input, i+1 , right); for (auto x: lRes) for (auto y: rRes) res.push_back(calc(op, x, y)); } } if (res.size() == 0 ) { int num = stoi(input.substr(left, right - left)); res.push_back(num); } memo[make_pair (left, right)] = res; return res; } vector <int > diffWaysToCompute (string input) return dfs(input, 0 , input.size()); } };
2. 不同的二叉搜索树（难） 95. Unique Binary Search Trees II (Medium)
【题目描述】
给定一个整数 n，生成所有由 1 … n 为节点所组成的二叉搜索树。
【示例】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 输入: 3 输出: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3] ] 解释: 以上的输出对应以下 5 种不同结构的二叉搜索树： 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3
【题解】
二叉搜索树关键的性质是根节点的值大于左子树所有节点的值，小于右子树所有节点的值，且左子树和右子树也同样为二叉搜索树。因此在生成所有可行的二叉搜索树的时候，假设当前序列长度为 n，如果我们枚举根节点的值为 i，那么根据二叉搜索树的性质我们可以知道左子树的节点值的集合为 [1…i−1]，右子树的节点值的集合为 [i+1…n]。
区间选择：使用 [st, ed] 的闭区间。
区间划分：从序列 1 ..n 中取出数字 i，作为当前树的树根，根据二叉搜索树的性质我们可以知道左子树的节点值的集合为 [1…i−1]，右子树的节点值的集合为 [i+1…n]。
区间合并：每个根节点都有一个vector<TreeNode*>存储所有可能的子树。
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 class Solution {public : vector <TreeNode*> generateSubTrees (int st, int ed) if (st > ed) { return {nullptr }; } vector <TreeNode*> allTrees; for (int i = st; i <= ed; i++) { vector <TreeNode*> leftTrees = generateSubTrees(st, i-1 ); vector <TreeNode*> rightTrees = generateSubTrees(i+1 , ed); for (auto lTree: leftTrees) { for (auto rTree: rightTrees) { TreeNode* rootTree = new TreeNode(i, lTree, rTree); allTrees.push_back(rootTree); } } } return allTrees; } vector <TreeNode*> generateTrees (int n) if (n == 0 ) return {}; return generateSubTrees(1 , n); } };
0x06 搜索 岛屿数量问题 【题目描述】
给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻（上下左右为相邻），那么这两个1属于同一个岛，判断岛屿个数。
【示例】
1 2 3 4 输入 [[1,1,0,0,0],[0,1,0,1,1],[0,0,0,1,1],[0,0,0,0,0],[0,0,1,1,1]] 返回值 3
【题解】
考察bfs，遍历二维矩阵，并用一个 vis 记录已经访问过的结点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 class Solution {public : int n, m; void bfs (vector <vector <char > >& grid, vector <vector <bool >> &vis, int i, int j) if (i < 0 || i >= n || j < 0 || j >= m) return ; if (vis[i][j] || grid[i][j] == '0' ) return ; vis[i][j] = true ; bfs(grid, vis, i-1 , j); bfs(grid, vis, i+1 , j); bfs(grid, vis, i, j-1 ); bfs(grid, vis, i, j+1 ); } int solve (vector <vector <char > >& grid) n = grid.size(), m = grid[0 ].size(); vector <vector <bool >> vis(n, vector <bool >(m, false )); int count = 0 ; for (int i = 0 ; i < n; i++) { for (int j = 0 ; j < m; j++) { if (!vis[i][j] && grid[i][j] == '1' ) { bfs(grid, vis, i, j); count++; } } } return count; } };
0x07 动态规划 斐波那契数列 数列是一维的，可以定义一个一位数组 dp 记录最优解。进一步地，考虑到 dp[i] 只与 dp[i-1] 和 dp[i-2] 有关，因此可以只用两个变量来存储，使得空间复杂度为 $O(1)$ 。
1. 爬楼梯 70. Climbing Stairs (Easy)
【题目描述】
有 N 阶楼梯，每次可以上一阶或者两阶，求有多少种上楼梯的方法。
【示例】
1 2 3 4 5 输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
【题解】
第 i 个楼梯可以从第 i-1 和 i-2 个楼梯再走一步到达，走到第 i 个楼梯的方法数为走到第 i-1 和第 i-2 个楼梯的方法数之和。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution {public : int climbStairs (int n) if (n <= 2 ) return n; int pre2 = 1 , pre1 = 2 ; int cur; for (int i = 3 ; i <= n; i++) { cur = pre2 + pre1; pre2 = pre1; pre1 = cur; } return cur; } };
2. 强盗抢劫 198. House Robber (Easy)
【题目描述】
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
【示例】
1 2 3 4 输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
【题解】
由于不能抢劫邻近住户，如果抢劫了第 i -1 个住户，那么就不能再抢劫第 i 个住户，所以 $dp[i] = max{dp[i-2] + nums[i], dp[i-1]}$ 。
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution {public : int rob (vector <int >& nums) int pre2 = 0 , pre1 = 0 ; int cur; for (int i = 0 ; i < nums.size(); i++) { cur = max(pre2 + nums[i], pre1); pre2 = pre1; pre1 = cur; } return cur; } };
3. 强盗在环形街区抢劫 213. House Robber II (Medium)
【题目描述】
同上题，这个地方所有的房屋都 围成一圈 。
【示例】
1 2 3 输入：nums = [2,3,2] 输出：3 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
【题解】
“围成一圈” 意味着不能同时抢劫第一个房屋和最后一个房屋，因此不妨将原问题拆解为 1n-1 和 2n 两个子问题。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution {private : int rob (vector <int >& nums, int st, int ed) int pre2 = 0 , pre1 = 0 ; int cur; for (int i = st; i <= ed; i++) { cur = max(pre2 + nums[i], pre1); pre2 = pre1; pre1 = cur; } return cur; } public : int rob (vector <int >& nums) int n = nums.size(); if (n == 0 ) return 0 ; if (n == 1 ) return nums[0 ]; return max(rob(nums, 0 , n-2 ), rob(nums, 1 , n-1 )); } };
矩阵路径 矩阵与斐波那契数列的不同之处在于，可以有多条路径，因此必须开一个二维数组dp来记录最优解。
1. 矩阵的最小路径和 64. Minimum Path Sum (Medium)
【题目描述】
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。每次只能向右和向下移动。
【示例】
1 2 3 4 5 6 [[1,3,1], [1,5,1], [4,2,1]] 输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 解释：因为路径 1→3→1→1→1 的总和最小。
【题解】
标准的自底向上dp解法。
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 : int minPathSum (vector <vector <int >>& grid) if (grid.size() == 0 ) return 0 ; int m = grid.size(); int n = grid[0 ].size(); for (int i = 1 ; i < m; i++) { grid[i][0 ] += grid[i-1 ][0 ]; } for (int j = 1 ; j < n; j++) { grid[0 ][j] += grid[0 ][j-1 ]; } for (int i = 1 ; i < m; i++) { for (int j = 1 ; j < n; j++) { grid[i][j] += min(grid[i-1 ][j], grid[i][j-1 ]); } } return grid[m-1 ][n-1 ]; } };
2. 矩阵的总路径数 62. Unique Paths (Medium)
【题目描述】
统计从矩阵左上角到右下角的路径总数，每次只能向右或者向下移动。
【示例】
1 2 3 4 5 6 7 输入：m = 3, n = 2 输出：3 解释： 从左上角开始，总共有 3 条路径可以到达右下角。 1. 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 3. 向下 -> 向右 -> 向下
【题解】
类似斐波那契数列。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution {public : int uniquePaths (int m, int n) int dp[m][n]; for (int i = 0 ; i < m; i++) dp[i][0 ] = 1 ; for (int j = 0 ; j < n; j++) dp[0 ][j] = 1 ; for (int i = 1 ; i < m; i++) { for (int j = 1 ; j < n; j++) { dp[i][j] = dp[i-1 ][j] + dp[i][j-1 ]; } } return dp[m-1 ][n-1 ]; } };
数组区间 1. 数组区间和 303. Range Sum Query - Immutable (Easy)
【题目描述】
给定一个整数数组 nums，求出数组从索引 i 到 j（ i ≤ j）范围内元素的总和，包含 i、j 两点。
实现 NumArray 类：
NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1], … , nums[j])）
【示例】
略
【题解】
求区间 i ~ j 的和，可以转换为 sum[j + 1] - sum[i]，其中 sum[i] 为 0 ~ 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 28 29 30 31 class NumArray {public : int sum[10007 ][10007 ]; NumArray(vector <int >& nums) { int n = nums.size(); for (int i = 0 ; i < n; i++) { sum[i][i] = nums[i]; } for (int j = 1 ; j < n; j++) { sum[0 ][j] = sum[0 ][j-1 ] + nums[j]; } for (int i = 1 ; i < n; i++) { for (int j = i + 1 ; j < n; j++) { sum[i][j] = sum[i-1 ][j] - nums[i-1 ]; } } } int sumRange (int i, int j) return sum[i][j]; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class NumArray {public : int * sum; NumArray(vector <int >& nums) { int n = nums.size(); if (n > 0 ) { sum = new int [n]; sum[0 ] = nums[0 ]; for (int i = 1 ; i < n; i++) { sum[i] = sum[i-1 ] + nums[i]; } } } int sumRange (int i, int j) return i == 0 ? sum[j] : sum[j] - sum[i-1 ]; } };
2. 数组中等差递增子区间的个数（难） 413. Arithmetic Slices (Medium)
【题目描述】
如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。
【示例】
1 2 3 4 5 6 7 8 9 10 A = [0, 1, 2, 3, 4] return: 6, for 3 arithmetic slices in A: [0, 1, 2], [1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3, 4], [ 1, 2, 3, 4], [2, 3, 4]
【题解】
用 dp[i] 表示以 A[i] 为结尾的等差递增子区间的个数。
当 A[i] - A[i-1] == A[i-1] - A[i-2] 时，
在以 A[i-1] 为结尾的递增子区间的后面再加上一个 A[i]，一样可以构成新的递增子区间，dp[i-1]个；
同时， [A[i-2], A[i-1], A[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 class Solution {public : int numberOfArithmeticSlices (vector <int >& A) int n = A.size(); if (n < 3 ) return 0 ; int dp[n]; for (int i = 0 ; i < n; i++) { dp[i] = 0 ; } for (int i = 2 ; i < n; i++) { if (A[i] - A[i-1 ] == A[i-1 ] - A[i-2 ]) { dp[i] = dp[i-1 ] + 1 ; } } int res = 0 ; for (int i = 0 ; i < n; i++) { res += dp[i]; } return res; } };
分割整数 1. 分割整数的最大乘积（难） 343. Integer Break (Medim)
【题目描述】
给定一个正整数 n ，将其拆分为至少 两个正整数的和，并使这些整数的乘积最大化 。 返回你可以获得的最大乘积。
【示例】
1 2 3 输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
【题解】
由于正整数n可以拆分为n1和n2，显然包含重复子问题，因此考虑用动态规划的方法做。
定义 dp[i] 为整数 i 分割后的最大乘积，对于每个整数 i，可以拆分为 j 和 i - j ，确定一个 j 使得 dp[i] 最大即可。
基础解：把 i 拆分为两个整数，即 dp[i] = j * (i - j)
递归解：取 j 的最优解，乘上整数 i - j
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution {public : int dp[60 ]; int integerBreak (int n) dp[1 ] = 1 ; for (int i = 1 ; i <= n; i++) { for (int j = 1 ; j <= i - 1 ; j++) { dp[i] = max(dp[i], max(j * (i - j), dp[j] * (i - j))); } } return dp[n]; } };
2. 按平方数来分割整数 279. Perfect Squares(Medium)
【题目描述】
给定正整数 n ，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n ，你需要让组成和的完全平方数的个数最少。
【示例】
1 2 3 输入：n = 12 输出：3 解释：12 = 4 + 4 + 4
【题解】
递归分析： $dp[i] = min(dp[j] + dp[i-j])$
时间复杂度：$O(nlogn)$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution {public : const static int MAX = 10007 ; int dp[MAX]; int numSquares (int n) dp[1 ] = 1 ; dp[2 ] = 2 ; for (int i = 1 ; i <= n; i++) { int temp = sqrt (i); if (temp * temp == i) { dp[i] = 1 ; continue ; } dp[i] = MAX; for (int j = 1 ; j <= i / 2 ; j++) { dp[i] = min(dp[i], dp[j] + dp[i - j]); } } return dp[n]; } };
【题解 - 2】
第一种解法仍有些无脑，考虑到是按平方数来分割整数，因此在内层循环中 j 不必遍历 1~i-1，只需遍历完全平方数即可。
这样对每个整数 $i$ ，利用 $i - square_j$ 的最优解加上1即可，故由 $dp[i] = min(dp[i - square[j]] + 1)$ 。
由此，问题就只剩下如何求得所有小于等于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 class Solution {public : const static int MAX = 10007 ; int dp[MAX]; int numSquares (int n) vector <int > square = genSquareList(n); int len = square.size(); int k = 0 ; for (int i = 1 ; i <= n; i++) { if (k < len && i == square[k]) { dp[i] = 1 ; k++; continue ; } dp[i] = MAX; for (int j = 0 ; j < len; j++) { if (square[j] >= i) { break ; } dp[i] = min(dp[i], dp[i - square[j]] + 1 ); } } return dp[n]; } vector <int > genSquareList (int n) vector <int > res; int square = 1 ; int diff = 3 ; while (square <= n) { res.push_back(square); square += diff; diff += 2 ; } return res; } };
3. 分割整数构成字母字符串（难） 91. Decode Ways (Medium)
【题目描述】
一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
1 2 3 4 'A' -> 1 'B' -> 2 ... 'Z' -> 26
给你一个只含数字的 非空 字符串 num ，请计算并返回 解码 方法的 总数 。
【示例】
例如，”111” 可以将 “1” 中的每个 “1” 映射为 “A” ，从而得到 “AAA” ，或者可以将 “11” 和 “1”（分别为 “K” 和 “A” ）映射为 “KA” 。注意，”06” 不能映射为 “F” ，因为 “6” 和 “06” 不同。
1 2 3 4 5 6 7 输入：s = "226" 输出：3 解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。 输入：s = "06" 输出：0 解释："06" 不能映射到 "F" ，因为字符串开头的 0 无法指向一个有效的字符。
【题解】
定义 dp[i] 为前 i 个数字所能映射的方法数，则
若 s[i] = 0 ：
只有当 s[i-1] = 1或2 时，才可以把 s[i-1] 和 s[i] 组合起来，此时有 dp[i] = dp[i-2]
其余情况均为 dp[i] = 0，且之后的都为0
若 s[i] != 0 ：
当 s[i-1] == 1 或 s[i-1] == 2 && 1 <= s[i] <= 6 时， 既可以单独映射，也可以组合起来，因此有 dp[i] = dp[i-1] + dp[i-2]；
其余情况只能单独映射，因此 dp[i] = d[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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 class Solution {public : int dp[107 ]; int numDecodings (string s) int n = s.length(); if (n == 0 || s[0 ] == '0' ) return 0 ; if (n == 1 ) return 1 ; dp[0 ] = 1 ; if (s[1 ] == '0' ) { if (s[0 ] == '1' || s[0 ] == '2' ) { dp[1 ] = 1 ; } else { return 0 ; } } else { if ((s[0 ] == '1' ) || (s[0 ] == '2' && '1' <= s[1 ] && s[1 ] <= '6' )) { dp[1 ] = 2 ; } else { dp[1 ] = 1 ; } } for (int i = 2 ; i < n; i++) { if (s[i] == '0' ) { if (s[i-1 ] == '1' || s[i-1 ] == '2' ) { dp[i] = dp[i-2 ]; } else { return 0 ; } } else { if ((s[i-1 ] == '1' ) || (s[i-1 ] == '2' && '1' <= s[i] && s[i] <= '6' )) { dp[i] = dp[i-1 ] + dp[i-2 ]; } else { dp[i] = dp[i-1 ]; } } } return dp[n - 1 ]; } };
【一种更优雅的解法】
设 $f_i$ 表示字符串 $s$ 的前 $i$ 个字符 $s[1..i]$ 的解码方法数。在进行状态转移时，我们可以考虑最后一次解码使用了 $s$ 中的哪些字符，那么会有下面的两种情况：
第一种情况是我们使用了一个字符，即 $s[i]$ 进行解码，那么只要 $s[i] \neq 0$ ，它就可以被解码成 $\text{A} \sim \text{I}$ 中的某个字母。由于剩余的前 $i-1$ 个字符的解码方法数为 $f_{i-1}$ ，因此我们可以写出状态转移方程：
$$f_i = f_{i-1}, \quad 其中 ~ s[i] \neq 0$$
第二种情况是我们使用了两个字符，即 $s[i-1]$ 和 $s[i]$ 进行编码。与第一种情况类似，$s[i-1]$ 不能等于 0，并且 $s[i-1]$ 和 $s[i]$ 组成的整数必须小于等于 26，这样它们就可以被解码成 $\text{J} \sim \text{Z}$ 中的某个字母。由于剩余的前 $i-2$ 个字符的解码方法数为 $f_{i-2}$ ，因此我们可以写出状态转移方程：
$$f_i = f_{i-2}, \quad 其中 ~ s[i-1] \neq 0 并且 10\cdot s[i-1]+s[i] \leq 26$$
需要注意的是，只有当 $i>1$ 时才能进行转移，否则 $s[i−1]$ 不存在。
将上面的两种状态转移方程在对应的条件满足时进行累加，即可得到 $f_i$ 的值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution {public : int numDecodings (string s) int n = s.size(); vector <int > f (n + 1 ) f[0 ] = 1 ; for (int i = 1 ; i <= n; ++i) { if (s[i - 1 ] != '0' ) { f[i] += f[i - 1 ]; } if (i > 1 && s[i - 2 ] != '0' && ((s[i - 2 ] - '0' ) * 10 + (s[i - 1 ] - '0' ) <= 26 )) { f[i] += f[i - 2 ]; } } return f[n]; } };
最长递增子序列 已知一个序列 {S1, S2,…,Sn}，取出若干数组成新的序列 {Si1, Si2,…, Sim}，其中 i1、i2 … im 保持递增，即新序列中各个数仍然保持原数列中的先后顺序，称新序列为原序列的一个 子序列 。
如果在子序列中，当下标 ix > iy 时，Six > Siy，称子序列为原序列的一个 递增子序列 。
1. 最长递增子序列 300. Longest Increasing Subsequence (Medium)
【题目描述】
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
【示例】
1 2 输入：nums = [0,1,0,3,2,3] 输出：4
【题解1】
我们不妨考虑末尾数字，dp[i] 表示以 num[i] 结尾的最长递增子序列的长度，则有 $dp[i] = max_{j < i \ and \ num[j] < num[i]}(dp[j] + 1)$ 。
对于一个长度为 n 的序列，最长递增子序列并不一定会以 num[n] 为结尾，因此 dp[n] 不是序列的最长递增子序列的长度，需要遍历 dp 数组找出最大值才是所要的结果，max{ dp[i] | 1 <= i <= 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 : int dp[2507 ]; int lengthOfLIS (vector <int >& nums) int n = nums.size(); if (n == 0 ) return 0 ; dp[0 ] = 1 ; for (int i = 1 ; i < n; i++) { dp[i] = 1 ; for (int j = 0 ; j < i; j++) { if (nums[i] > nums[j]) { dp[i] = max(dp[i], dp[j] + 1 ); } } } int res = 1 ; for (int i = 0 ; i < n; i++) { res = max(res, dp[i]); } return res; } };
【题解2 - 难想】
以上解法的时间复杂度为 O(N2)，可以使用二分查找将时间复杂度降低为 O(NlogN)。
定义一个 tails 数组，其中 tails[i] 存储长度为 i + 1 的最长递增子序列的最后一个元素 。
对于一个元素 x ：
如果它大于 tails 数组所有的值，那么把它添加到 tails 后面，表示最长递增子序列长度加 1；
如果 tails[i-1] < x <= tails[i]，那么更新 tails[i] = x。
例如对于数组 [4,3,6,5]，有：
1 2 3 4 5 6 tails len num [] 0 4 [4] 1 3 [3] 1 6 [3,6] 2 5 [3,5] 2 null
可以看出 tails 数组保持有序，因此在查找 Si 位于 tails 数组的位置时就可以使用二分查找。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 class Solution {public : int tails[2507 ]; int lengthOfLIS (vector <int >& nums) int n = nums.size(); if (n == 0 ) return 0 ; int len = 0 ; for (int i = 0 ; i < n; i++) { int index = bSearch(0 , len, nums[i]); tails[index] = nums[i]; if (index == len) { len++; } } return len; } int bSearch (int l, int h, int key) while (l < h) { int mid = l + (h - l) / 2 ; if (tails[mid] == key) { return mid; } else if (tails[mid] > key) { h = mid; } else { l = mid + 1 ; } } return l; } };
2. 一组整数对能够构成的最长链 646. Maximum Length of Pair Chain (Medium)
【题目描述】
对于 (a, b) 和 (c, d) ，如果 b < c，则它们可以构成一条链。给定一个数对集合，找出能够形成的最长数对链的长度。
【示例】
1 2 3 输入：[[1,2], [2,3], [3,4]] 输出：2 解释：最长的数对链是 [1,2] -> [3,4]
【题解】
因为给定的是集合，所以首先根据数对的第一个数升序排列所有的数对。
定义 $dp[i]$ 存储以 $pairs[i]$ 结尾的最长链的长度。
对于每个 $dp[i]$ ，其长度只与前 $i$ 项有关：
当 $j < i$ 且 $pairs[j][1] < pairs[i][0]$ 时，扩展数对链，更新 $dp[i] = max(dp[i], dp[j] + 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 class Solution {public : int dp[1007 ]; int findLongestChain (vector <vector <int >>& pairs) int n = pairs.size(); sort(pairs.begin(), pairs.end(), compare); for (int i = 0 ; i < n; i++) { dp[i] = 1 ; cout << i << ":\t" << pairs[i][0 ] << ", " << pairs[i][1 ] << endl ; } for (int i = 1 ; i < n; i++) { for (int j = 0 ; j < i; j++) { if (pairs[j][1 ] < pairs[i][0 ]) { dp[i] = max(dp[i], dp[j] + 1 ); } } } int ans = 0 ; for (int i = 0 ; i < n; i++) { ans = max(ans, dp[i]); } return ans; } static int compare (const vector <int > &a, const vector <int > &b) return a[0 ] < b[0 ]; } };
3. 最长摆动子序列（难） 376. Wiggle Subsequence (Medium)
【题目描述】
如果连续数字之间的差 严格地在正数和负数之间交替，则数字序列称为摆动序列。 第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
给定一个整数序列，返回作为摆动序列的最长子序列的长度。
【示例】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 示例 1: 输入: [1,7,4,9,2,5] 输出: 6 解释: 整个序列均为摆动序列。 示例 2: 输入: [1,17,5,10,13,15,10,5,16,8] 输出: 7 解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。 示例 3: 输入: [1,2,3,4,5,6,7,8,9] 输出: 2
【题解】
每当我们选择一个元素作为摆动序列的一部分时，这个元素要么是上升的，要么是下降的，这取决于前一个元素的大小。那么列出状态表达式为：
$up[i]$ 表示以前 i 个元素 中的某一个为结尾的最长的「上升摆动序列」的长度。
$down[i]$ 表示以前 i 个元素 中的某一个为结尾的最长的「下降摆动序列」的长度。
对于 $up[i]$，
当 $nums[i] \leq nums[i-1]$ 时，我们无法选出更长的「上升摆动序列」的方案。因为对于任何以 $nums[i]$ 结尾的「上升摆动序列」，我们都可以将 $nums[i]$ 替换为 $nums[i−1]$ ，使其成为以 $nums[i - 1]$ 结尾的「上升摆动序列」。
当 $nums[i] > nums[i-1]$ 时，以 $nums[i]$ 结尾的「上升摆动序列」长度为 $down[i-1]+1$ ，因此 $up[i] = max(up[i-1], down[i-1] + 1)$ 。
对于 $down[i]$ 同理。
事实上，我们仅需要前一个状态来进行转移，所以只需要维护两个变量即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution {public : int wiggleMaxLength (vector <int >& nums) int n = nums.size(); if (n <= 1 ) return n; int up = 1 , down = 1 ; for (int i = 0 ; i < n-1 ; i++) { if (nums[i] < nums[i+1 ]) { up = down + 1 ; } else if (nums[i] > nums[i+1 ]) { down = up + 1 ; } } return max(up, down); } };
最长公共子序列 详见 [《算法导论》（二）之动规问题](https://jay1zhang.github.io/2021/01/29/Computer Science/Algorithm/%E3%80%8C%E7%AE%97%E6%B3%95%E6%80%9D%E6%83%B3%E3%80%8D%E3%80%8A%E7%AE%97%E6%B3%95%E5%AF%BC%E8%AE%BA%E3%80%8B%EF%BC%88%E4%BA%8C%EF%BC%89%E4%B9%8B%E5%88%86%E6%B2%BB-%E5%8A%A8%E8%A7%84-%E8%B4%AA%E5%BF%83%E9%97%AE%E9%A2%98/)
1. 最长公共子序列 1143. Longest Common Subsequence
【题目描述】
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
【示例】
1 2 3 输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace"，它的长度为 3。
【题解】
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 dp[1007 ][1007 ]; int longestCommonSubsequence (string text1, string text2) int n = text1.length(), m = text2.length(); for (int i = 0 ; i <= n; i++) dp[0 ][i] = 0 ; for (int i = 0 ; i <= m; i++) dp[i][0 ] = 0 ; for (int i = 1 ; i <= n; i++) { for (int j = 1 ; j <= m; j++) { if (text1[i-1 ] == text2[j-1 ]) { dp[i][j] = dp[i-1 ][j-1 ] + 1 ; } else { dp[i][j] = max(dp[i][j-1 ], dp[i-1 ][j]); } } } return dp[n][m]; } };
2. 最长公共子序列（带输出） 【题目描述 】
给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则输出-1。
【示例 】
1 2 3 4 5 6 7 输入: "1A2C3D4B56","B1D23CA45B6A" 返回: "123456" 说明: "123456"和“12C4B6”都是最长公共子序列，任意输出一个。
【题解 】
使用一个 Rec 数组来记录最优解即可，输出时可采用递归法 。
注意下面使用了二维指针 来表示二维数组，但实际上，嵌套 vector 会更简洁一些，且不易出错。不过，复习一下二维指针也没啥坏处。
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 class Solution {public : enum D { LU = 0 , U, L }; void getLCS (string &res, string &s, int ** rec, int i, int j) if (i == 0 || j == 0 ) return ; switch (rec[i][j]) { case LU: getLCS(res, s, rec, i-1 , j-1 ); res.push_back(s[i-1 ]); break ; case U: getLCS(res, s, rec, i-1 , j); break ; case L: getLCS(res, s, rec, i, j-1 ); break ; default : break ; } } string LCS (string s1, string s2) int len1 = s1.length(), len2 = s2.length(); int **dp = new int * [len1 + 1 ]; int **rec = new int * [len1 + 1 ]; for (int i = 0 ; i <= len1; i++) { dp[i] = new int [len2 + 1 ]; rec[i] = new int [len2 + 1 ]; } for (int i = 0 ; i <= len1; i++) dp[i][0 ] = 0 ; for (int j = 0 ; j <= len2; j++) dp[0 ][j] = 0 ; for (int i = 1 ; i <= len1; i++) { for (int j = 1 ; j <= len2; j++) { if (s1[i-1 ] == s2[j-1 ]) { dp[i][j] = dp[i-1 ][j-1 ] + 1 ; rec[i][j] = LU; } else if (dp[i-1 ][j] >= dp[i][j-1 ]) { dp[i][j] = dp[i-1 ][j]; rec[i][j] = U; } else { dp[i][j] = dp[i][j-1 ]; rec[i][j] = L; } } } string res; getLCS(res, s1, rec, len1, len2); if (res.length() > 0 ) return res; else return "-1" ; } };
0-1 背包 0. 标准 0-1 背包问题 【题目描述】
有一个容量为 $N$ 的背包，要用这个背包装下物品的价值最大，这些物品有两个属性：体积 $v$ 和价值 $p$。
【题解】
定义一个二维数组 $dp$ 存储最大价值，其中 $dp[i][j]$ 表示前 $i$ 件物品体积不超过 $j$ 的情况下能达到的最大价值。
设第 $i$ 件物品体积为 $v$，价值为 $p$，根据第 $i$ 件物品是否添加到背包中，可以分两种情况讨论：
第 $i$ 件物品没添加到背包，总体积不超过 $j$ 的前 $i$ 件物品的最大价值就是总体积不超过 $j$ 的前 $i-1$ 件物品的最大价值，$dp[i][j] = dp[i-1][j]$ 。
第 $i$ 件物品添加到背包中，$dp[i][j] = dp[i-1][j-v] + p$。
第 $i$ 件物品可添加也可以不添加，取决于哪种情况下最大价值更大。因此，0-1 背包的状态转移方程为：
$$dp[i][j] = max(dp[i-1][j], dp[i-1][j - v] + p)$$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public int knapsack (int V, int N, int [] volume, int [] price) int [][] dp = new int [N + 1 ][V + 1 ]; for (int i = 1 ; i <= N; i++) { int v = volume[i - 1 ], p = price[i - 1 ]; for (int j = 1 ; j <= W; j++) { if (j >= v && dp[i - 1 ][j - v] + p > dp[i - 1 ][j]) { dp[i][j] = dp[i - 1 ][j - v] + p; } else { dp[i][j] = dp[i - 1 ][j]; } } } return dp[N][V]; }
【空间优化】
观察状态转移方程可以知道，前 $i$ 件物品的状态仅与前 $i-1$ 件物品的状态有关 ，因此可以将 $dp$ 定义为一维数组，其中 $dp[j]$ 既可以表示 $dp[i-1][j]$ 也可以表示 $dp[i][j]$ 。此时，
$$dp[j] = max(dp[j], dp[j - v] + p)$$
在方程中，$dp[j-v]$ 表示的是 $dp[i-1][j-v]$ ，因此不能先求 $dp[i][j-w]$，防止将 $dp[i-1][j-w]$ 覆盖 。也就是说要先计算 $dp[i][j]$ 再计算 $dp[i][j-v]$，在程序实现时需要按倒序来循环求解。
1 2 3 4 5 6 7 8 9 10 11 12 public int knapsack (int V, int N, int [] volume, int [] price) int [] dp = new int [V + 1 ]; for (int i = 1 ; i <= N; i++) { int v = volume[i - 1 ], p = price[i - 1 ]; for (int j = V; j >= 1 ; j--) { if (j >= V) { dp[j] = Math.max(dp[j], dp[j - v] + p); } } } return dp[V]; }
【拓展】
0-1 背包问题有以下变种 ：
完全背包：物品数量为无限个
多重背包：物品数量有限制
多维费用背包：物品不仅有重量，还有体积，同时考虑这两种限制
其它：物品之间相互约束或者依赖
1. 划分数组为和相等的两部分（难） 416. Partition Equal Subset Sum (Medium)
【题目描述】
给定一个只包含正整数 的非空 数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
【示例】
1 2 3 输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 [11].
【题解】
本题与 0-1 背包问题有一个很大的不同，即：
0-1 背包问题选取的物品的容积总量 不能超过 规定的总量；
本题选取的数字之和需要 恰好等于 规定的和的一半。
作为「0-1 背包问题」，它的特点是：「每个数只能用一次」。解决的基本思路是：物品一个一个选，容量也一点一点增加去考虑 ，这一点是「动态规划」的思想，特别重要。
状态定义 ：$dp[i][j]$ 表示从数组的 $[0, i]$ 这个子区间内挑选一些正整数，每个数只能用一次，使得这些数的和恰好等于 $j$ 。
在定义状态之后，需要考虑边界情况 。以下两种情况都属于边界情况。
对于一般情况，如何确定 $dp[i][j]$ 呢？
如果 $j \ge nums[i]$ ，则对于当前的数字 $nums[i]$ ，既可以选取也可以不选取，两种情况只要有一个为真，则 $dp[i][j] = true$ ；
如果不选取 $nums[i]$ ，则 $dp[i][j] = dp[i-1][j]$ ；
如果选取 $nums[i]$ ，则 $dp[i][j] = dp[i-1][j-nums[i]]$ 。
如果 $j < nums[i]$ ，则无法选取当前数字 $nums[i]$ ，因此有 $dp[i][j] = dp[i-1][j]$ 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 class Solution {public : bool canPartition (vector <int >& nums) int n = nums.size(); if (n < 2 ) { return false ; } int sum = 0 ; for (int i = 0 ; i < n; i++) sum += nums[i]; if (sum % 2 != 0 ) { return false ; } int target = sum / 2 ; int dp[n][target + 1 ]; for (int i = 0 ; i < n; i++) { dp[i][0 ] = 1 ; } for (int i = 0 ; i < n; i++) { for (int j = 1 ; j <= target; j++) { dp[i][j] = 0 ; } } if (nums[0 ] <= target) { dp[0 ][nums[0 ]] = 1 ; } for (int i = 1 ; i < n; i++) { for (int j = 0 ; j <= target; j++) { if (nums[i] > j) { dp[i][j] = dp[i - 1 ][j]; } else { dp[i][j] = dp[i - 1 ][j] || dp[i - 1 ][j - nums[i]]; } } } return dp[n-1 ][target]; } };
【题解 - 2】
上述代码的空间复杂度是 $O(n×target)$ ，但是可以发现在计算 $dp$ 的过程中，每一行的 $dp$ 值都只与上一行的 $dp$ 值有关，因此只需要一个一维数组即可将空间复杂度降到 $O(target)$ 。
此时的转移方程为： $dp[j]=dp[j] ∣ dp[j−nums[i]]$ .
且需要注意的是第二层的循环我们需要从大到小计算 ，因为如果我们从小到大更新 $dp$ 值，那么在计算 $dp[j]$ 值的时候，**$dp[j−nums[i]]$ 已经是被更新过的状态**，不再是上一行的 $dp$ 值。
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 canPartition (vector <int >& nums) int n = nums.size(); if (n < 2 ) { return false ; } int sum = 0 ; for (int i = 0 ; i < n; i++) sum += nums[i]; if (sum % 2 != 0 ) { return false ; } int target = sum / 2 ; int dp[target + 1 ]; for (int i = 0 ; i <= target; i++) dp[i] = 0 ; dp[0 ] = 1 ; for (int i = 0 ; i < n; i++) { for (int j = target; j >= nums[i]; j--) { dp[j] |= dp[j - nums[i]]; } } return dp[target]; } };
2. 改变一组数的正负号使得它们的和为一给定数（难） 494. Target Sum (Medium)
【题目描述】
给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
【示例】
1 2 3 4 5 6 7 8 9 10 11 输入：nums: [1, 1, 1, 1, 1], S: 3 输出：5 解释： -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 一共有5种方法让最终目标和为3。
【题解】
同上一题，本题选取的数字应恰好为 S。区别在于，S是可以为负数的，且S的范围为 $[-sum, sum]$ 。
因而定义状态数组 $dp[n][2sum + 1]$ ， $dp[i][j+sum]$ 为前 $i$ 个数字，组成和为 $j$ 的方法数（$-sum \le j \le sum$）。即将数组整个向右偏移一个 sum，$[0, 2 sum]$ 映射为 $[-sum, sum]$ 。
在定义状态之后，需要考虑边界情况 ：
对于一般情况，如何确定 $dp[i][j]$ 呢？
实际上，这道题的不同仅在于从背包问题的“选”或“不选”变成了“选正号”还是“选负号”。
如果 $nums[i]$ 取正号：
要组成和为 $j$ 的组合，显然只能有 $dp[i][j] = dp[i-1][j - nums[i]]$ ，因此只需保证 $j - nums[i] >= 0$ 即可。
如果 $nums[i]$ 取负号：
要组成和为 $j$ 的组合，显然只能有 $dp[i][j] = dp[i-1][j + nums[i]]$ ，因此只需保证 $j + nums[i] <= 2*sum$ 即可。
最后， $dp[i][j]$ 应取上述两种情况之和。
第一次做这道题的时候，因为牵涉到数组映射，在分析一般情况时把自己搞晕掉了，在操作和时，又是 $j - sum - nums[i]$ 又是 $j + sum - nums[i]$ 的。
实际上，在分析一般情况的状态转移方程时，显然是没有必要再考虑数组映射的问题 的。这是因为，在遍历内层循环 $j$ 时，前 $i$ 个元素组成的和 $j$ 已经是固定了的，直接用 $j$ 减去当前元素 $nums[i]$ ，去找上一行前 $i-1$ 个元素组成的和为 $j-nums[i]$ 的个数即可，只不过 $nums[i]$ 可以取正也可以取负，要分两种情况讨论而已。
那在求边界的时候为什么需要考虑偏移 sum 呢？因为这个时候和 $j$ 是不确定的，我们已知的是只有第一个元素组成的和，显然可以取正可以取负，那么和就有两种情况：$+nums[0]$ 和 $-nums[0]$ ，表现到偏移数组中，下标就是 $sum + nums[0]$ 和 $sum - nums[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 class Solution {public : int findTargetSumWays (vector <int >& nums, int target) int n = nums.size(); int sum = 0 ; for (int i = 0 ; i < n; i++) sum += nums[i]; if (target < -sum || target > sum) { return false ; } vector <vector <int >> dp(n, vector <int >(2 *sum+1 , 0 )); dp[0 ][sum + nums[0 ]] += 1 ; dp[0 ][sum - nums[0 ]] += 1 ; for (int i = 1 ; i < n; i++) { for (int j = nums[i]; j <= 2 *sum; j++) { dp[i][j] += dp[i-1 ][j - nums[i]]; } for (int j = 0 ; j + nums[i] <= 2 *sum; j++) { dp[i][j] += dp[i-1 ][j + nums[i]]; } } return dp[n-1 ][sum + target]; } };
同上一题，本题的状态转移方程仍仅与前一个状态 $i-1$ 有关，因此也能进行空间优化。
emmm，似乎没有我想的那么简单。
因为进行空间优化的一个限制就是，必须保证 $dp[j - nums[i]]$ 是上一个状态（即前 $i-1$ 个数组成的和）的值，上题的做法是从右往左遍历解决这个问题。但对于本题来说，取正数和取负数所需要的上一个状态分别是 $dp[j - nums[i]]$ 和 $dp[j + nums[i]]$ ，刚好是不同方向的。。。这就导致了无论从左往右遍历还是从右往左遍历，一定有一个状态已经被更新过了，表示的是当前状态（前 $i$ 个元素组成的和）的值。
暂时没想到解决方案…
【题解2 - DFS解法】
基本思想：
对每个 nums[index]，都有两种选择：取正号或负号，可以据此得到递归解。
递归终止的条件为：所有的 nums 都被访问过。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution {public : int findTargetSumWays (vector <int >& nums, int target, int index) if (index == nums.size()) { return target == 0 ? 1 : 0 ; } return findTargetSumWays(nums, target - nums[index], index+1 ) + findTargetSumWays(nums, target + nums[index], index+1 ); } int findTargetSumWays (vector <int >& nums, int target) return findTargetSumWays(nums, target, 0 ); } };
思路极其简单，但时间复杂度过高。
3. 01 字符构成最多的字符串（难） 474. Ones and Zeroes (Medium)
【题目描述】
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
【示例】
1 2 3 4 5 6 7 8 9 10 示例1： 输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3 输出：4 解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。 示例2： 输入：strs = ["10", "0", "1"], m = 1, n = 1 输出：2 解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
【题解】
这道题和经典的背包问题很类似，不同的是在背包问题中，我们只有一种容量，而在这道题中，我们有 0 和 1 两种容量，因此这实际上是一道多维费用背包问题 。
由于每个物品（字符串）需要分别占用 0 和 1 的若干容量，并且所有物品的价值均为 1，因此我们可以使用二维的动态规划 。
注意在一维的标准0-1背包问题中，我们使用 $dp[i, j]$ 表示背包容量为 $j$ 时在前 $i$ 个物品中所能挑选的最大价值。经过空间优化 过后，我们仅用一个 $dp[i]$ 来存储和计算，但为了防止提前更新 （具体见上），我们采取的方案是倒序循环 。
在二维问题中，我们同样利用这个技巧，来将空间优化到 $O(mn)$ ，否则就需要三维的矩阵 $dp[k, i, j]$ 。
我们用 $dp[i, j]$ 表示在容量不超过 $i$ 个 0 和 $j$ 个 1 的情况下，尽可能地多装物品（字符串）。
那么就能得到状态转移方程：
$$dp[i, j] = Max_{k=1}^N {dp[i - cost_zeros[k], j - cost_ones[k]] + 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 class Solution {public : int findMaxForm (vector <string >& strs, int m, int n) int N = strs.size(); vector <vector <int >> goods(N, vector <int >(2 , 0 )); for (int i = 0 ; i < N; i++) { for (auto c: strs[i]) { goods[i][c - '0' ]++; } } vector <vector <int >> dp(m+1 , vector <int >(n+1 , 0 )); dp[0 ][0 ] = 0 ; for (int k = 0 ; k < N; k++) { for (int i = m; i >= goods[k][0 ]; i--) { for (int j = n; j >= goods[k][1 ]; j--) { dp[i][j] = max(dp[i][j], dp[i - goods[k][0 ]][j - goods[k][1 ]] + 1 ); } } } return dp[m][n]; } };
4. 找零钱的最少硬币数（难） 322. Coin Change (Medium)
【题目描述】
给一些面额的硬币，要求用这些硬币来组成给定面额的钱数，并且使得硬币数量最少。硬币可以重复使用。
【示例】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 示例 1： 输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1 示例 2： 输入：coins = [2], amount = 3 输出：-1 示例 3： 输入：coins = [1], amount = 0 输出：0 示例 4： 输入：coins = [1], amount = 1 输出：1
【题解】
2021-04-23：第一次解题失败！
问题在于，受到前面几道题的干扰，局限于使用「前 i 个硬币中选出面值为 j 的最小数量 」，但由于硬币可以重复使用，对于每个 j ，都有 k 种可能，k表示选择k个coins[i]，满足 k * coins[i] <= amount。
这样写出来要嵌套三个loop，直接TLE了。。。
出现这种错误思维，我认为主要是由于忘记了动规的核心思想 ——「最优子结构 」，j - 1 * coins[i], j - 2 * coins[i] …, 实际上都是有重复子问题的，因为在 j = j - coins[i] 时，我们计算的 j - 1 * coins[i] ，实际上就是此时的 j - 2 * coins[i]。
实际上，由于硬币可以重复使用，我们不必拘泥于每个面额的硬币到底用了几个，可以直接从 amount 入手。
我们定义 $dp[i]$ 表示组成金额 $i$ 所需最少的硬币数量，则转移方程为：
$$dp[i] = min_{j = 0, \dots, n-1} ~ {dp[i - coin_j] + 1}$$
即我们枚举最后一枚硬币面额是 $coin_j$ ，那么需要从 $i - coin_j$ 这个金额的状态 $dp[i - coin_j]$ 中转移过来，再算上枚举的这枚硬币数量 1 的贡献，取最小值即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution {public : int coinChange (vector <int >& coins, int amount) int MAX = amount + 1 ; vector <int > dp (amount+1 , MAX) dp[0 ] = 0 ; for (int i = 1 ; i <= amount; i++) { for (int j = 0 ; j < coins.size(); j++) { if (i >= coins[j]) { dp[i] = min(dp[i], dp[i - coins[j]] + 1 ); } } } return dp[amount] > amount ? -1 : dp[amount]; } };
5. 找零钱的硬币数组合 518. Coin Change 2 (Medium)
【题目描述】
给定不同面额的硬币和一个总金额，计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
【示例】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 示例 1: 输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 示例 2: 输入: amount = 3, coins = [2] 输出: 0 解释: 只用面额2的硬币不能凑成总金额3。 示例 3: 输入: amount = 10, coins = [10] 输出: 1
【错误解法】
跟前一道题十分相似，但如果直接照搬，将得到如下的错误解法：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution {public : int change (int amount, vector <int >& coins) vector <int > dp (amount + 1 , 0 ) dp[0 ] = 1 ; for (int i = 1 ; i <= amount; i++) { for (int j = 0 ; j < coins.size(); j++) { if (i >= coins[j]) { dp[i] += dp[i - coins[j]]; } } } return dp[amount]; } };
错误的原因是，组合数是可能重复的，比如对于示例1：
$i = 1$ ，dp[1] = dp[0] = 1，表示 1
$i = 2$ ，dp[2] = dp[1] + dp[0] = 2，表示 1 + 1, 2
$i = 3$ ，dp[3] = dp[2] + dp[1] = 3，表示 1 + 1 + 1, 2 + 1, 1 + 2，这里显然重复计算了。
【题解】
实际上，交换两层循环的位置就能避免这个问题。
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution {public : int change (int amount, vector <int >& coins) vector <int > dp (amount + 1 , 0 ) dp[0 ] = 1 ; for (int i = 0 ; i < coins.size(); i++) { for (int j = coins[j]; j <= amount; j++) { dp[j] += dp[j - coins[i]]; } } return dp[amount]; } };
但具体为啥要这样做。。我暂时没太想明白。。呕了。。
6. 字符串按单词列表分割 139. Word Break (Medium)
【题目描述】
【示例】
【题解】
7. 组合总和 377. Combination Sum IV (Medium)
【题目描述】
【示例】
【题解】
股票交易 字符串编辑 1. 最短编辑距离 【题目描述】
给定两个字符串str1和str2，再给定三个整数ic，dc和rc，分别代表插入、删除和替换一个字符的代价，请输出将str1编辑成str2的最小代价。
【题解】
状态转移方程在《「算法进阶」高级算法设计》中有详细介绍，这里不再赘述。唯一需要注意的是初始化方法 ，易错。
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 minEditCost (string s1, string s2, int ic, int dc, int rc) int n = s1.length(), m = s2.length(); int dp[n+1 ][m+1 ]; for (int i = 0 ; i <= n; i++) dp[i][0 ] = i * dc; for (int j = 0 ; j <= m; j++) dp[0 ][j] = j * ic; for (int i = 1 ; i <= n; i++) { for (int j = 1 ; j <= m; j++) { int insertCost = dp[i][j-1 ] + ic; int deleteCost = dp[i-1 ][j] + dc; int replaceCost = dp[i-1 ][j-1 ] + ((s1[i-1 ] == s2[j-1 ])? 0 : rc); dp[i][j] = min(min(insertCost, deleteCost), replaceCost); } } return dp[n][m]; } };
0x08 数学
素数分解
每一个数都可以分解成素数的乘积，例如 $84 = 2^2 * 3^1 * 5^0 * 7^1 * 11^0 * 13^0 * 17^0 * …$
整除
令 $x = 2^{m0} * 3^{m1} * 5^{m2} * 7^{m3} * 11^{m4} * …$
令 $y = 2^{n0} * 3^{n1} * 5^{n2} * 7^{n3} * 11^{n4} * …$
如果 x 整除 y（y mod x == 0），则对于所有 $i$，$mi <= ni$。
最大公约数最小公倍数
x 和 y 的最大公约数为：$gcd(x,y) = 2^{min(m0,n0)} * 3^{min(m1,n1)} * 5^{min(m2,n2)} * …$
x 和 y 的最小公倍数为：$lcm(x,y) = 2^{max(m0,n0)} * 3^{max(m1,n1)} * 5^{max(m2,n2)} * …$
1. 素数（质数） 生成素数序列 【埃氏筛法】
埃氏筛法求素数的思想是，我们首先假定所有正整数都是素数，然后从小到大遍历，逐步的筛除其中的合数。
问题的关键在于如何筛除合数 ？
我们考虑这样一个事实：如果 x 是质数，那么 $x$ 的倍数 $2x, 3x, …$ 一定是合数。
最朴素的作法是：
当前数 $x$ 的所有倍数均为合数，即 $2x, 3x, 4x, …, kx$，直到 $ki > n$。
然后令 x++，重复上述步骤，继续筛除合数。
事实上，这里还可以继续优化：
对于一个质数 x，从 $2x$ 开始标记其实是冗余的，而应该直接从 $xx$ 开始标记，因为 $2x, 3x, …$ 这些数一定在 $x x$ 之前就被 2 的所有倍数、3 的所有倍数等标记过了。
因此有如下代码：
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 #include <cstdio> #include <vector> using namespace std ;void findPrime (int n) vector <bool > isPrime (n + 1 , true ) vector <int > prime; for (int i = 2 ; i <= n; i++) { if (isPrime[i]) { prime.push_back(i); for (int j = i*i ; j <= n; j += i) { isPrime[j] = false ; } } } for (int i = 0 ; i < prime.size(); i++) { printf ("%d " , prime[i]); } printf ("\n" ); } int main () int n; scanf ("%d" ,&n); findPrime(n); return 0 ; }
【线性筛法】
埃氏筛其实还是存在冗余的标记操作，即有很多数被筛除了不止1次。比如6，在素数为2的时候处理1次，为3时候又标记一次。
那么如何优化这些冗余操作 呢？一种作法是，对于每个合数，我们保证它只会被其最小的质因数筛去 。
算法的核心步骤如下：
对每个数 $i$ ， 它与所有素数的积 i * prime[j] 一定是合数，筛除它们。
当 i % prime[j] == 0 时，打破循环。
其实我不太能理解如何证明该算法的正确性。
核心代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 for (int i = 2 ; i <= n; ++i) { if (isPrime[i]) { prime.push_back(i); } for (int j = 0 ; j < prime.size() && i * prime[j] <= n; ++j) { isPrime[i * prime[j]] = false ; if (i % prime[j] == 0 ) { break ; } } }
分解质因数 将一个正整数分解质因数。例如：输入90,打印出 90 = 2 * 3 * 3 * 5。
程序分析：对n进行分解质因数，应先找到一个最小的质数k，然后按下述步骤完成：
如果这个质数恰等于n，则说明分解质因数的过程已经结束，打印出即可。
如果n>k，但n能被k整除，则应打印出k的值，并用n除以k的商,作为新的正整数n, 重复执行第一步。
如果n不能被k整除，则用k+1作为k的值,重复执行第一步。
分解质因数代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include <bits/stdc++.h> using namespace std ;int main () int n; scanf ("%d" ,&n); for (int i = 2 ; i <= n; i++) { while (n != i) { if (n % i == 0 ) { printf ("%d*" , i); n = n / i; } else { break ; } } } printf ("%d\n" , n); return 0 ; }
计数质数 【题目描述】
统计所有小于非负整数 n 的质数的数量。
【题解】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution {public : int countPrimes (long n) vector <bool > isPrime (n, true ) int count = 0 ; for (long i = 2 ; i < n; i++) { if (!isPrime[i]) { continue ; } count++; for (long j = i * i; j < n; j += i) { isPrime[j] = false ; } } return count; } };
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 countPrimes (int n) vector <bool > isPrime (n, true ) vector <int > prime; for (int i = 2 ; i < n; i++) { if (isPrime[i]) { prime.push_back(i); } for (int j = 0 ; j < prime.size(); j++) { if (i * prime[j] < n) { isPrime[i * prime[j]] = false ; } if (i % prime[j] == 0 ) { break ; } } } return prime.size(); } };
2. 最大公约数与最小公倍数
1 2 3 int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
1 2 3 int lcm(int a, int b) { return a * b / gcd(a, b); }
3. 相遇问题 最少移动次数使数组元素相等 II / 462. Minimum Moves to Equal Array Elements II (Medium)
【题目描述】
给定一个非空整数数组，找到使所有数组元素相等所需的最小移动数，其中每次移动可将选定的一个元素加1或减1。
【示例】
1 2 3 4 5 6 7 输入: [1,2,3] 输出: 2 说明： 只有两个动作是必要的（记得每一步仅可使其中一个元素加1或减1）： [1,2,3] => [2,2,3] => [2,2,2]
【题解】
这是个典型的相遇问题，移动距离最小的方式是所有元素都移动到中位数。理由如下：
设 m 为中位数。a 和 b 是 m 两边的两个元素，且 b > a。
要使 a 和 b 相等，它们总共移动的次数为 b - a，这个值等于 (b - m) + (m - a)，也就是把这两个数移动到中位数的移动次数。
【解法1】
先排序，再从两边往中间夹，时间复杂度 $O(nlogn)$ 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution {public : int minMoves2 (vector <int >& nums) sort(nums.begin(), nums.end()); int l = 0 , r = nums.size() - 1 ; int move = 0 ; while (l <= r) { move += nums[r] - nums[l]; l++; r--; } return move; } };
【解法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 class Solution {public : int partition (vector <int >& A, int l, int r) int x = A[r]; int i = 0 ; for (int j = 0 ; j <= r-1 ; j++) { if (A[j] <= x) { swap(A[i], A[j]); i++; } } swap(A[i], A[r]); return i; } int findKthElement (vector <int >& nums, int k) int l = 0 , r = nums.size() - 1 ; while (l <= r) { int q = partition(nums, l, r); if (q == k) { break ; } else if (q > k) { r = q - 1 ; } else { l = q + 1 ; } } return nums[k]; } int minMoves2 (vector <int >& nums) int median = findKthElement(nums, nums.size() / 2 ); int move = 0 ; for (auto num: nums) { move += abs (median - num); } return move; } };
4. 多数投票问题 多数元素 / Majority Element (Easy)
【题目描述】
找到数组中出现次数多于 n / 2 的元素
【示例】
1 2 3 4 5 输入：[3,2,3] 输出：3 输入：[2,2,1,1,1,2,2] 输出：2
【解法1】
先对数组排序，最中间那个数出现次数一定多于 n / 2。
1 2 3 4 5 6 7 class Solution {public : int majorityElement (vector <int >& nums) sort(nums.begin(), nums.end()); return nums[nums.size() / 2 ]; } };
【解法2】
遍历数组 nums，并用一个 map<int, int> 记录数组中元素出现的个数。最后再遍历一遍map，找出出现次数大于n/2的元素。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution {public : int majorityElement (vector <int >& nums) map <int , int > mp; for (auto num: nums) { mp[num]++; } for (map <int , int >::iterator iter = mp.begin(); iter != mp.end(); iter++) { if (iter->second > nums.size() / 2 ) { return iter->first; } } return -1 ; } };
5. 其他问题 1）平方数 367. Valid Perfect Square (Easy)
【题目描述】
给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要使用任何内置的库函数，如 sqrt() 。
【题解】
平方序列：1,4,9,16,..
间隔：3,5,7,…
观察到平方序列的间隔为等差数列 ，使用这个特性可以得到从 1 开始的平方序列。
1 2 3 4 5 6 7 8 9 10 11 12 class Solution {public : bool isPerfectSquare (int num) int diff = 3 ; int i = 1 ; while (i < num) { i += diff; diff += 2 ; } return i == num; } };
经过运行会发现，当 num = 2147483647 时，i += diff 会出现整数溢出。
因此，不妨反过来考虑，从 num 开始往下递减。
1 2 3 4 5 6 7 8 9 10 11 class Solution {public : bool isPerfectSquare (int num) int diff = 1 ; while (num > 0 ) { num -= diff; diff += 2 ; } return num == 0 ; } };
2）3的n次方 326. Power of Three (Easy)
【题目描述】
给定一个整数，写一个函数来判断它是否是 3 的幂次方。
【题解1 - 迭代法】
1 2 3 4 5 6 7 8 9 10 11 class Solution {public : bool isPowerOfThree (int n) if (n < 1 ) return false ; while (n % 3 == 0 ) { n /= 3 ; } return n == 1 ; } };
【题解2 - 整数限制】
我们可以看到 $n$ 为 int 型整数，因此最大值为 $2^{31} - 1 = 2147483647$ 。
因此，我们知道了3的幂的最大值为 $3^{⌊log_3INT_MAX⌋} = 3^{⌊19.56⌋} = 3^{19} = 1162261467$ 。
也就是说，只有当 $n$ 在 $3^0, 3^1, …, 3^{19}$ 之间时返回 true，故可直接用 $3^{19}$ 除以 n 看余数是否为0即可。
1 2 3 4 5 6 class Solution {public : bool isPowerOfThree (int n) return n > 0 && 1162261467 % n == 0 ; } };
3）乘积数组 238. Product of Array Except Self (Medium)
【题目描述】
给定一个数组，创建一个新数组，新数组的每个元素为原始数组中除了该位置上的元素之外所有元素的乘积。
要求时间复杂度为 O(N)，并且不能使用除法。
【示例】
1 2 输入: [1,2,3,4] 输出: [24,12,8,6]
【题解】
这似乎是一个简单的问题，可以在线性时间和空间内解决。先计算给定数组所有元素的乘积，然后对数组中的每个元素 x，将总的乘积除以 x 来求得除自身值的以外数组的乘积。然而这样的解决方法有一个问题，就是如果输入数组中出现 0，那么这个方法就失效了。
实际上，我们可以利用索引左侧所有数字的乘积和右侧所有数字的乘积（即前缀与后缀 ）相乘得到答案。
我们用两个数组 $L$ 和 $R$ 分别保存前缀乘积和后缀乘积，即 L[i] 表示前 i-1个元素乘积，R[i] 表示后 i+1个元素乘积；
对于给定索引 $i$，我们将使用它左边所有数字的乘积乘以右边所有数字的乘积，即 L[i]*R[i]。
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 > productExceptSelf (vector <int >& nums) int n = nums.size(); vector<int> L(n), R(n), ans(n); L[0 ] = 1 ; for (int i = 1 ; i < n; i++) { L[i] = nums[i-1 ] * L[i-1 ]; } R[n-1 ] = 1 ; for (int i = n-2 ; i >= 0 ; i--) { R[i] = nums[i+1 ] * R[i+1 ]; } for (int i = 0 ; i < n; i++) { ans[i] = L[i]*R[i]; } return ans; } };
显然，上面的做法开了两个额外的数组空间。实际上，我们只需要 ans 数组即可。
首先用 ans 数组代替 L ，然后动态计算 R ，并顺带计算最终结果 ans 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : vector <int > productExceptSelf (vector <int >& nums) int n = nums.size(); vector <int > ans (n) ans[0 ] = 1 ; for (int i = 1 ; i < n; i++) { ans[i] = nums[i-1 ] * ans[i-1 ]; } int post = 1 ; for (int i = n-1 ; i >= 0 ; i--) { ans[i] = ans[i] * post; post *= nums[i]; } return ans; } };
4）找出数组中的乘积最大的三个数 628. Maximum Product of Three Numbers (Easy)
【题目描述】
在数组中找出由三个数组成的最大乘积，并输出这个乘积。
【题解】
蛮简单的，注意一些细节即可，如是否会溢出。
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 maximumProduct (vector <int >& nums) int max1, max2, max3; int min1, min2; max1 = max2 = max3 = -1000 ; min1 = min2 = 1000 ; for (auto n: nums) { if (n > max1) { max3 = max2; max2 = max1; max1 = n; } else if (n > max2) { max3 = max2; max2 = n; } else if (n > max3) { max3 = n; } if (n < min1) { min2 = min1; min1 = n; } else if (n < min2) { min2 = n; } } return max(max1*max2*max3, max1*min1*min2); } };
