代码随想录
写在最前面：
数组 T704.二分搜索法(左开右闭？左闭右闭？) 前提：升序排列的数组
左闭右闭
1 2 3 4 5 6 7 l = 0 ; r = nums.size ()-1 ; while (l <= r){ if l = mid + 1 ; else if r = mid -1 ; }
左闭右开
1 2 3 4 5 6 7 l = 0 ; r = nums.size; while (l < r){ if l = mid + 1 ; else if r = mid; }
整数溢出问题：用l + (r - l) / 2代替(l + r) / 2
T27.删除重复元素 快慢双指针法
Erase 的时间复杂度不是O1 而是 On
理解双指针：**快指针指向更新后的数组元素。**当快指针指向合法元素时，执行覆盖操作；指向非法元素时，则++。
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution {public : int removeElement (vector<int >& nums, int val) int sidx = 0 ; for (int fidx = 0 ; fidx < nums.size (); fidx++) { if (nums[fidx] != val) { swap (nums[fidx], nums[sidx]); sidx++; } } return sidx; } };
这是一道值得反复巩固的思路。返回的 sid 等于 val 出现的次数。
把最近一个不等于 val 的值交换到数组前面。
拓展：值得再做一次删除重复元素 如果基于一个字符串句子，每个单词间可能有多个空格，要求每个单词间仅保留一个空格。
fastIndex 作为先锋探路。
slowIndex 之前的数据均为最后保留珍藏。
始终铭记：从 fastIndex 拿数字到 slowIndex 去。
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 #include <iostream> using namespace std;void removeRe (string &str, char val) int slow = 0 ; for (int fast = 0 ; fast < str.size (); fast++) { if (str[fast] == val) { continue ; } else { str[slow++] = str[fast]; } } str.resize (slow); } void reduce (string &str, char val) int slow = 0 ; for (int fast = 0 ; fast < str.size (); fast++) { if (fast >= 1 && str[fast] == val && str[fast - 1 ] == val) { continue ; } else { str[slow] = str[fast]; slow++; } } str.resize (slow); } int main () string str = " hello you are my ideal lover" ; removeRe (str, ' ' ); cout << str; return 0 ; }
T977.有序数组的平方（双指针法） 双指针的方法，使得排序的时间复杂度为 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 # include <iostream> # include <vector> # include <algorithm> using namespace std;class Solution { public : vector<intsortedSquares(vector<int >& nums) { vector<intsorted(nums.size()); int i = 0; int j = nums.size()-1; int k = nums.size()-1; for (;i<=j;){ if (nums[i]*nums[i]>=nums[j]*nums[j]){ sorted[k] = nums[i]*nums[i]; i++; k--; } else { sorted[k] = nums[j]*nums[j]; j--; k--; } } return sorted; } }; int main() { vector<intnums = {-4, -1, 0, 3, 10}; Solution solution; vector<intsorted = solution.sortedSquares(nums); for (int num : sorted) { cout << num << " "; } cout << endl; }
T209.长度最小的子数组 找到数组中连续的最小连续的子数组，使得数组的和大于目标值。
T59.螺旋矩阵II 自己拿下，就是在找规律的时候有点纠结。关键点在于如何确认每次旋转的次数，旋转的变长以及每次旋转的起点。
二维数组/容器的定义与初始化方法vector<vector<int>res(n, vector<int>(n, 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 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 #include <iostream> #include <vector> using namespace std;class Solution { public : vector<vector<int >generateMatrix(int n) { // 定义一个二维数组 vector<vector<int >res(n, vector<int >(n, 0)); // 要转 r 圈 int r = n / 2; int length = n - 1; // length = 4 // 起点 int row = 0; int col = 0; // 计数器 int cnt = 1; while (r 0){ for (int i = 0; i< length; i++){ res[row][col+i] = cnt++; } col = col + length; // col = 4 for (int i = 0; i<length; i++){ res[row + i][col] = cnt++; } row = row + length; //row = 4 for (int i = 0; i<length; i++){ res[row][col - i] = cnt++; } col = col - length; // col = 0 for (int i = 0; i<length; i++){ res[row -i][col] = cnt ++; } row = row - length; // row = 0 r --; length -= 2; col ++; row ++; } if (n % 2 == 1){ res[row][col] = cnt; } return res; } }; int main() { Solution solution; vector<vector<int >res = solution.generateMatrix(4); for (int i = 0; i<res.size(); i++){ for (int j = 0; j<res[i].size(); j++){ cout << res[i][j] << " "; } cout << endl; } }
链表 基础知识
定义结构体的时候记得写构造函数
区别我大二的写法，当时没有结合面向对象 的思想
1 2 3 4 5 6 7 8 9 10 11 12 13 14 typedef struct Node { double data; Node*next; }*DataList; void InitList (DataList&list) list= new Node; list->next=NULL ; } int main () DataList list; InitList (list); }
要始终记住虚节点的思想ListNode* dummy = new ListNode(0)
T203.移除链表元素
确定题干有没有提供哨兵位头节点，没有的话手动加上会简化操作
while 的终止条件要充分考虑到循环体中访问到的所有变量是否为空值
用一个 if 判断即可完成：
cur->next 如果等于 val 则换掉 cur->next
否则往后移动 cur
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public : ListNode* removeElements (ListNode* head, int val) { ListNode* dummy = new ListNode (0 ); dummy->next = head; head = dummy; ListNode* cur = head; while (cur!= NULL && cur -next != NULL ){ if (cur -next -val == val){ ListNode* temp = cur->next; cur->next = cur->next->next; delete temp; }else { cur = cur->next; } } ListNode* temp = head; head = head -next; delete temp; return head; } };
T707.设计链表 第一步肯定是先能跑通：设计出打印函数和尾插函数
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 # include <iostream> using namespace std;class MyLinkedList {public : struct LinkNode { int val; LinkNode* next; LinkNode (int val): val (val), next (nullptr ) {} }; MyLinkedList () { dummy = new LinkNode (0 ); } void addAtTail (int val) LinkNode* newNode = new LinkNode (val); LinkNode* cur = dummy; while (cur -next != nullptr ){ cur = cur -next; } cur -next = newNode; } void print () LinkNode* cur = dummy -next; while (cur != nullptr ){ cout << cur -val << " " ; cur = cur -next; } cout << endl; } private : LinkNode* dummy; }; int main () MyLinkedList* obj = new MyLinkedList (); obj->addAtTail (2 ); obj->addAtTail (2 ); obj->print (); return 0 ; }
这里是完整的代码：整个代码在写的过程中还是容易出现许多的问题：
代码的重复度比较高，先写完尾插 。由尾插可以修改得到在指定索引处增加与删除节点。
因为这个代码涉及到了索引下表，所以需要引入私有变量 size。当访问范围＞size需要做好处理；其次，在删除末尾元素时，需要带上>=号。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 class MyLinkedList {public : struct LinkNode { int val; LinkNode* next; LinkNode (int val): val (val), next (nullptr ) {} }; MyLinkedList () { dummy = new LinkNode (0 ); size = 0 ; } int get (int index) if (index < 0 || index >= size) return -1 ; LinkNode* cur = dummy -next; while (index--){ cur = cur -next; } return cur -val; } void addAtHead (int val) LinkNode* newNode = new LinkNode (val); newNode -next = dummy -next; dummy -next = newNode; size++; } void addAtTail (int val) LinkNode* newNode = new LinkNode (val); LinkNode* cur = dummy; while (cur -next != nullptr ){ cur = cur -next; } cur -next = newNode; size++; } void addAtIndex (int index, int val) if (index < 0 || index size) return ; LinkNode* newNode = new LinkNode (val); LinkNode* cur = dummy; while (index--){ cur = cur -next; } newNode -next = cur -next; cur -next = newNode; size++; } void deleteAtIndex (int index) if (index < 0 || index >= size) return ; LinkNode* cur = dummy; while (index-- ){ cur = cur -next; } LinkNode* temp = cur -next; cur -next = temp -next; delete temp; size--; } void print () LinkNode* cur = dummy -next; while (cur != nullptr ){ cout << cur -val << "->" ; cur = cur -next; } cout << "nullptr" << endl; } private : LinkNode* dummy; int size; };
T206.反转链表
在脑中提前构思好最开始的情况和结束的情况。
充分考虑下面几个点
**是否需要哨兵位？**在反转链表中这个空节点没有实际的意义。带上空节点反而增加了复杂度，所以不需要哨兵位。
**想好用几个变量来代换？**实际需要用三个：pre，cur，next。其中 next 的作用比较小，主要涉及到的反转利用的是 cur 和 pre。
最后要注意点是需要在循环结束时 ，返回最末尾的“头”，但此时cur == nullptr所以将 head 赋值给 pre。
这里用的是双指针法 （next 指针的作用不是很大）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public : ListNode* reverseList (ListNode* head) { ListNode* pre = nullptr ; ListNode* cur = head; while (cur != nullptr ){ ListNode* next = cur -next; cur -next = pre; pre = cur; cur = next; } head = pre; return head; } };
还有一个递归法，暂时不考虑了。
T24. 两两交换链表中的节点 仿照反转链表的思路，创建三个指针去实现。
运行时错误：典型错解
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 : ListNode* swapPairs (ListNode* head) { ListNode* dummy = new ListNode (0 ); dummy -next = head; ListNode* pre = dummy; ListNode* cur = dummy -next; ListNode* next = dummy -next -next; while (cur != nullptr && next != nullptr ){ cur -next = next -next; next -next = cur; pre -next = next; pre = cur; cur = pre ->next; next = cur ->next; } ListNode* newHead = dummy->next; delete dummy; return newHead; } };
1 2 Line 21: Char 30: runtime error: member access within null pointer of type 'ListNode' (solution.cpp) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:30:30
正确做法 ：
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 : ListNode* swapPairs (ListNode* head) { ListNode* dummy = new ListNode (0 ); dummy -next = head; ListNode* pre = dummy; while (pre ->next != nullptr && pre -next -next != nullptr ){ ListNode* cur = pre->next; ListNode* next = cur ->next; cur ->next = next ->next; next -next = cur; pre -next = next; pre = cur; } ListNode* newHead = dummy->next; delete dummy; return newHead; } };
T19.删除链表的倒数第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 class Solution {public : ListNode* removeNthFromEnd (ListNode* head, int n) { ListNode* dummy = new ListNode (0 ); dummy -next = head; head = dummy; ListNode* fast = head; ListNode* slow = head; for (int i = 0 ; i < n; i++){ fast = fast -next; } while (fast -next){ fast = fast -next; slow = slow -next; } ListNode* tmp = slow -next; slow -next = tmp ->next; delete tmp; return head->next; delete dummy; } };
T160.链表相交 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 : ListNode *getIntersectionNode (ListNode *headA, ListNode *headB) { int lenA = 0 , lenB = 0 ; ListNode* pA = headA; while (pA != nullptr ){ lenA++; pA = pA -next; } ListNode* pB = headB; while (pB != nullptr ){ lenB++; pB = pB -next; } if (lenA < lenB){ swap (headA, headB); swap (lenA, lenB); } int gap = lenA - lenB; for (int i = 0 ; i < gap; i++){ headA = headA -next; } while (headA != nullptr && headB != nullptr ){ if (headA == headB){ return headA; } headA = headA -next; headB = headB -next; } return nullptr ; } };
T142.环形链表II 一个非常经典的技巧题
任务分为两步骤。
第一步：找到快慢指针的相交点。
第二步：一个指针从相交点出发，一个指针从头出发。相交点即为环的入口。
弄清楚其中的数学原理。
假设 ：从 head 到环的入口路径长度为 $x$；slow 指针环内 走的路径长度为 $y$ ；slow 指针在与 fast 指针相遇后，剩余的环路径长度为$z$。
slow 指针走过的路径长度很容易求：$x+y$ 。需要说明的是 slow 一定会在一圈之内被 fast 指针追击到，所以不需要考虑 slow 在环内走入第 2 圈。
fast 指针走过的路径长度为$x+y+N(y+z)$。此时理解这个 N 的物理含义很关键，代表的是在与 slow 没相遇的这段日子里，fast 指针单独走过的圈数。
根据 fast 走两步，slow 走一步可得一个二倍的关系。
$(x+y+N(y+z)) =2 * (x+y)$ 可以进一步推导出 ：
由此可以得到一个很重要的数学关系从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点 。
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 : ListNode *detectCycle (ListNode *head) { ListNode* fast = head; ListNode* slow = head; while (fast != nullptr && fast -next != nullptr ){ fast = fast -next -next; slow = slow ->next; if (fast == slow){ ListNode* index1 = fast; ListNode* index2 = head; while (index1 != index2){ index1 = index1 -next; index2 = index2 -next; } return index1; } } return nullptr ; } };
哈希表 基础知识 哈希表的 O(1) 平均时间复杂度，推荐使用 std::unordered_set 与 std::unordered_map。
std::unordered_set 的基本操作头文件与命名空间
需要包含头文件 <unordered_set>，并通常使用 std 命名空间。
1 2 3 #include <iostream> #include <unordered_set> using namespace std;
插入元素
使用 insert() 方法或直接利用初始化列表。
1 2 3 4 unordered_set<intmySet; mySet.insert(10); mySet.insert(20); mySet.insert(30);
查找元素
使用 find() 方法，如果元素存在，返回指向该元素的迭代器；否则返回 mySet.end()。
1 2 3 if (mySet.find (20 ) != mySet.end ()){ cout << "Found 20" << endl; }
删除元素
使用 erase() 方法删除指定的元素。
遍历所有元素
可以使用范围 for 循环或迭代器遍历集合中的所有元素。
1 2 3 4 for (auto it = mySet.begin (); it != mySet.end (); ++it){ cout << *it << " " ; } cout << endl;
其他常用操作
检查大小 ：mySet.size()是否为空 ：mySet.empty()清空容器 ：mySet.clear()
std::unordered_map 的基本操作头文件与命名空间
需要包含头文件 <unordered_map>。
1 2 3 #include <iostream> #include <unordered_map> using namespace std;
插入键值对
可以通过 operator[] 或 insert() 方法添加键值对。
1 2 3 4 5 unordered_map<string, intmyMap; myMap["apple"] = 5; myMap["banana"] = 10; // 或者 myMap.insert({"cherry", 15});
查找元素
使用 find() 方法来查找某个键。
1 2 3 4 auto it = myMap.find ("apple" );if (it != myMap.end ()){ cout << "apple: " << it->second << endl; }
删除元素
使用 erase() 方法来删除指定键的元素。
遍历所有键值对
使用范围 for 循环遍历整个 map。
1 2 3 for (const auto &pair : myMap){ cout << pair.first << " -" << pair.second << endl; }
其他常用操作
检查大小 ：myMap.size()是否为空 ：myMap.empty()清空容器 ：myMap.clear()
示例代码 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 #include <iostream> #include <unordered_set> #include <unordered_map> using namespace std;int main () unordered_set<intmySet; mySet.insert(10); mySet.insert(20); mySet.insert(30); cout << "unordered_set 中的元素: "; for (auto it = mySet.begin(); it != mySet.end(); ++it) { cout << *it << " "; } cout << endl; // 查找与删除 if (mySet.find(20) != mySet.end()) { cout << "找到了 20" << endl; mySet.erase(20); } cout << "删除 20 后的 unordered_set: "; for (auto num : mySet) { cout << num << " "; } cout << endl; // 使用 unordered_map unordered_map<string, intmyMap; myMap["apple"] = 5; myMap["banana"] = 10; myMap.insert({"cherry", 15}); cout << "unordered_map 中的键值对:" << endl; for (const auto &pair : myMap) { cout << pair.first << " -" << pair.second << endl; } // 查找与删除 auto it = myMap.find("apple"); if (it != myMap.end()) { cout << "找到了 key \"apple\" 对应的 value: " << it->second << endl; } myMap.erase("banana"); cout << "删除 \"banana\" 后的 unordered_map:" << endl; for (const auto &pair : myMap) { cout << pair.first << " -" << pair.second << endl; } return 0; }
unordered_set 与 unordered_map 使用哈希表实现，适合快速查找、插入和删除操作。插入操作可以用 insert() 或 operator[]（仅限 unordered_map）。
查找操作使用 find()，返回迭代器，判断是否等于容器的 end() 来确定是否找到。
删除操作使用 erase()，可以按值或键删除。
遍历可以使用范围 for 循环或者迭代器。
迭代器范围构造
unordered_set<intnums_set(nums1.begin(), nums1.end());nums1 数组的元素初始化一个 unordered_set，这是一种快速去重的方法。return vector<int>(result_set.begin(), result_set.end());unordered_set 转换成 vector，这种方法通过迭代器将容器中的元素拷贝到新的 vector 中。
T242.有效的字母异位词 利用数组做哈希表 这个方法很常见
但是如果针对 Unicode 这个方法就不适用了，还得回归到 map。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public : bool isAnagram (string s, string t) int nums[26 ] = {0 }; for (char i : s){ nums[i - 'a' ] += 1 ; } for (char i :t){ nums[i - 'a' ] -=1 ; } for (int i = 0 ; i<26 ; i++){ if (nums[i] != 0 ) return false ; } return true ; } };
T349.两个数组的交集 题目意思很简单，要整明白迭代器的基本使用方法。
范围初始化类型转换（迭代器）
find（）的使用
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution {public : vector<intintersection(vector<int >& nums1, vector<int >& nums2) { // 将 nums1 变成一个集合 unordered_set<ints (nums1.begin(), nums1.end()); unordered_set<intret; for (auto i :nums2){ if (s.find(i) != s.end()){ ret.insert(i); } } return vector<int >(ret.begin(), ret.end()); } };
引申：T350.两个数组的交集 II T349 的第一步是用 set去重，但这一题要求及时同一个元素重复了也需要算作为交集的一部分。所以引入了 map
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : vector<intintersect(vector<int >& nums1, vector<int >& nums2) { unordered_map<int , intcountMap; vector<intresult; // 记录 nums1 中每个元素的出现次数 for (int num : nums1) { countMap[num]++; } // 遍历 nums2，找到在 nums1 中也出现的元素 for (int num : nums2) { if (countMap[num] 0) { result.push_back(num); countMap[num]--; } } return result; } };
T202.快乐数 判断整个过程是否有环
第一种做法：双指针法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution {public : int happy (int n) int ret = 0 ; while (n != 0 ) { int tmp = n % 10 ; ret += tmp * tmp; n /= 10 ; } return ret; } bool isHappy (int n) int fast = happy (n); int slow = n; while (slow != fast) { slow = happy (slow); fast = happy (happy (fast)); } if (fast == 1 ) return true ; return false ; } };
第二种做法：用集合
这种做法无论是在长度还是理解难度上都比双指针法更易理解
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 happy (int n) int ret = 0 ; while (n != 0 ) { int tmp = n % 10 ; ret += tmp * tmp; n /= 10 ; } return ret; } bool isHappy (int n) unordered_set<ints; int tmp = happy(n); while (s.find(tmp) == s.end()){ s.insert(tmp); tmp = happy(tmp); } if (tmp == 1) return true ; return false ; } };
T1.两数之和 看了一下提交记录也是老朋友了。
但之前是用 Python 写的，当时使用字典的，代码很方便。
这次做第一想法是用数组哈希表，但是发现测试数据包含了负数，不好给数据直接做统一的初始化。
进而联想到直接用 map 映射。关键在于理解 map 的键和值分别代表什么。
每次遍历值时，用 find 确认是否存在当前元素正好互补的另一半。如果有的话就直接返回构造的数据结构。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution {public : vector<inttwoSum(vector<int >& nums, int target) { unordered_map<int , intm; vector<intret; for (int i = 0; i < nums.size(); i++) { if (m.find(target - nums[i]) == m.end()) { m[nums[i]] = i; } else { ret.push_back(m[target - nums[i]]); ret.push_back(i); return ret; } } return ret; } };
T454.四数相加 II 上来无脑暴力测试用例通过 30/133。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution {public : int fourSumCount (vector<int >& nums1, vector<int >& nums2, vector<int >& nums3, vector<int >& nums4) int count = 0 ; for (int i = 0 ; i < nums1. size (); i++) { for (int j = 0 ; j < nums2. size (); j++) { for (int k = 0 ; k < nums3. size (); k++) { for (int l = 0 ; l < nums4. size (); l++) { if (nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0 ) { count++; } } } } } return count; } };
解决方案是将四重循环两两拆分，引入 map 存储 a+b 结果出现的次数。并用 c+d 与 -（a+b）做比较。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution {public : int fourSumCount (vector<int >& nums1, vector<int >& nums2, vector<int >& nums3, vector<int >& nums4) unordered_map<int , intumap; for (int i = 0; i < nums1.size(); i++) { for (int j = 0; j < nums2.size(); j++) { umap[nums1[i] + nums2[j]]++; } } int cnt = 0; for (int i = 0; i < nums3.size(); i++) { for (int j = 0; j < nums4.size(); j++) { if (umap.find(-nums3[i] - nums4[j]) != umap.end()){ cnt += umap[-nums3[i] - nums4[j]]; } } } return cnt; } };
map++的初始状态为 0？
关键点： 1 2 3 for (auto i : magazine) { umap[i]++; }
unordered_map<char, intumap; 这行代码定义了一个 unordered_map，键类型为 char，值类型为 int。在 unordered_map中，如果你访问一个不存在的键，它会自动为该键插入一个默认值。
对于 int 类型，默认值是 0。
对于其他类型，默认值通常是类型的默认构造值，比如 nullptr 或者 false 等。
T383.赎金信 秒杀
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution {public : bool canConstruct (string ransomNote, string magazine) unordered_map<char , intumap; for (auto i : magazine) { umap [i]++; } for (auto i: ransomNote) { if (umap[i] == 0) return false ; umap [i]--; } return true ; } };
T15.三数之和 后面这两题有点难度。先跳过。
字符串 T344.反转字符串 用指针操作完成
注意获取收元素地址的写法
在当前代码中，s 是一个 vector<char类型，而不是一个 C 风格的字符串数组。因此，不能直接将 s 赋值给 char* 类型的指针 front。
1 2 3 4 void reverseString (vector<char >& s) char * tail = &s[0 ] + s.size () - 1 ; char * front = &s[0 ]; }
当然如果传入的是 char*
1 2 3 4 void reverseString (char s[], int n) char *tail = s + n - 1 ; char *front = s; }
第一种用指针移动的写法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public : void reverseString (vector<char &s) { char *tail = &s[0 ] + s.size () - 1 ; char *front = &s[0 ]; while (front < tail) { swap (*tail, *front); front++; tail--; } } };
第二种用下标
1 2 3 4 5 6 7 8 9 10 class Solution { public : void reverseString (vector<char &s) { for (int i = 0 , j = s.size () - 1 ; i < j; i++, j--){ swap (s[i], s[j]); } } };
调用标准库函数
1 2 3 4 5 6 7 8 class Solution { public : void reverseString (vector<char &s) { reverse (s.begin (),s.end ()); } };
T541. 反转字符串II 在上一题 d 基础上加上一些判断条件第一反应使用迭代器反转。
此处需要注意的是：
在 reverseStr 方法中使用调用方式。reverse 是一个标准库函数，应该使用 std::reverse。此外，std::reverse 的参数是迭代器，而不是字符串对象 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution {public : string reverseStr (string s, int k) { int cnt = 0 ; while (cnt < s.size ()) { if (s.size () - cnt >= k) { std::reverse (s.begin () + cnt, s.begin () + cnt + k); } else { std::reverse (s.begin () + cnt, s.end ()); } cnt += 2 * k; } return s; } };
「卡玛网」替换数字 简单的字符串拼接，需要复习一下 string 的相关操作。
还有一种是不额外开辟新空间的做法：双指针法。
双指针法
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 <iostream> using namespace std;int main () string s; while (cin >s) { int count = 0 ; int sOldSize = s.size (); for (int i = 0 ; i < s.size (); i++) { if (s[i] >= '0' && s[i] <= '9' ) { count++; } } s.resize (s.size () + count * 5 ); int sNewSize = s.size (); for (int i = sNewSize - 1 , j = sOldSize - 1 ; j < i; i--, j--) { if (s[j] '9' || s[j] < '0' ) { s[i] = s[j]; } else { s[i] = 'r' ; s[i - 1 ] = 'e' ; s[i - 2 ] = 'b' ; s[i - 3 ] = 'm' ; s[i - 4 ] = 'u' ; s[i - 5 ] = 'n' ; i -= 5 ; } } cout << s << endl; } }
开辟新空间拼接字符串
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <iostream> #include <string> using namespace std;int main () string s; cin >s; string result; for (auto it : s) { if (it >= '0' && it <= '9' ) { result += "number" ; } else { result += it; } } cout << result << endl; return 0 ; }
问题升级一下：将文本中所有 Apple 修改为 banana。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <iostream> #include <string> using namespace std;int main () string s; getline (cin, s); string target = "Apple" ; string replacement = "banana" ; size_t pos = 0 ; while ((pos = s.find (target, pos)) != string::npos) { s.replace (pos, target.length (), replacement); pos += replacement.length (); } cout << s << endl; return 0 ; }
T151.翻转字符串里的单词 主要的问题有两个：
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 #include <iostream> #include <string> #include <algorithm> using namespace std;class Solution {public : void removeSpace (string& s) int sidx = 0 ; for (int fidx = 0 ; fidx < s.size (); fidx++) { if (s[fidx] != ' ' ) { if (sidx != 0 ) s[sidx++] = ' ' ; while (fidx < s.size () && s[fidx] != ' ' ) { s[sidx++] = s[fidx++]; } } } s.resize (sidx); } void reverseLetter (string& s, int start, int end) while (start < end) { swap (s[start++], s[end--]); } } string reverseWords (string s) { removeSpace (s); reverse (s.begin (), s.end ()); int start = 0 ; for (int end = 0 ; end <= s.size (); end++) { if (end == s.size () || s[end] == ' ' ) { reverseLetter (s, start, end - 1 ); start = end + 1 ; } } return s; } }; int main () Solution solution; string s1 = "the sky is blue" ; string s2 = " hello world " ; string s3 = "a good example" ; cout << solution.reverseWords (s1) << endl; cout << solution.reverseWords (s2) << endl; cout << solution.reverseWords (s3) << endl; return 0 ; }
「卡玛网」右旋字符串
如果不申请开辟新的空间的话可以用 substr 直接将字符串拼接。这里就需要复习常见一些操作方法。
如果是针对当前字符串进行反转而不申请新的空间的话，思路可以参考上一道题目。反转两次
1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include <iostream> using namespace std;int main () int n; string str; cin >n >str; n = n % str.size (); string str1 = str.substr (str.size () - n); string str2 = str.substr (0 , str.size () - n); cout << str1 + str2; return 0 ; }
不开辟额外空间
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include <iostream> using namespace std;void reverseStr (string &str, int start, int end) while (start <= end) { swap (str[start], str[end]); start++; end--; } } int main () int n; string str; cin >n >str; reverseStr (str, 0 , str.size () - 1 ); reverseStr (str, 0 , n - 1 ); reverseStr (str, n, str.size () - 1 ); cout << str; }
T28. 找出字符串中第一个匹配项的下标 KMP题
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 : void getNext (int * next, const string& s) int j = -1 ; next[0 ] = j; for (int i = 1 ; i < s.size (); i++) { while (j >= 0 && s[i] != s[j + 1 ]) { j = next[j]; } if (s[i] == s[j + 1 ]) { j++; } next[i] = j; } } int strStr (string haystack, string needle) if (needle.size () == 0 ) { return 0 ; } vector<intnext(needle.size()); getNext(&next[0], needle); int j = -1; // j 用于 needle 的指针 for (int i = 0; i < haystack.size(); i++) { while (j >= 0 && needle[j + 1 ] != haystack[i]) { j = next[j]; } if (needle[j + 1 ] == haystack[i]) { j++; } if (j == (needle.size () - 1 )) { return i - needle.size () + 1 ; } } return -1 ; } };
T459.重复的子字符串 这题主要是复习一下KMP算法
前缀表（用于确定匹配错误后，模式串从哪开始重新计算）
最大公共前后缀
前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串 。**后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。 **
找到的不匹配的位置， 那么此时我们要看它的前一个字符的前缀表
暴力方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution {public : bool repeatedSubstringPattern (string s) string range; for (int i = 1 ; i < s.size (); i++) { range = s.substr (0 , i); int pos = 0 ; for (int j = i; j < s.size (); j++) { if (s[j] != range[pos % range.size ()]) { break ; } else { pos++; if (pos % range.size () == 0 && j == s.size () - 1 ) return true ; } } } return false ; } };
用 KMP 算法
利用next 的最后一个元素找出最长公共前后缀的长度。判断整个字符串长度能否能整除（整个字符串长度-最长公共前后缀的长度）
栈与队列 T232.用栈实现队列 没想得那么难。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 class MyQueue {public : stack<intin; stack<intStOut; MyQueue() {} void push(int x) { in.push(x); } int pop() { int ret; if (StOut.empty()) { while (!in.empty()) { int x = in.top(); in.pop(); StOut.push(x); } } ret = StOut.top(); StOut.pop(); return ret; } int peek() { int ret = this ->pop(); StOut.push(ret); return ret; } bool empty() { return in.empty() && StOut.empty(); } }; /** * Your MyQueue object will be instantiated and called as such: * MyQueue* obj = new MyQueue(); * obj->push (x); * int param_2 = obj->pop (); * int param_3 = obj->peek (); * bool param_4 = obj->empty (); */
T225.用队列实现栈 与用栈实现队列不同的是，此处不需要用in和out队列，因为如何处理进出的顺序都是一样的。
所以这里使用两个队列的目的是实现备份。
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 MyStack {public : queue<inta; queue<intb; MyStack() {} void push(int x) { a.push(x); } int pop() { int ret; while (!a.empty()) { if (a.size() == 1) { ret = a.front(); a.pop(); } else { int tmp = a.front(); a.pop(); b.push(tmp); } } while (!b.empty()) { int tmp = b.front(); b.pop(); a.push(tmp); } return ret; } int top() { return a.back(); } bool empty() { return a.empty(); } }; /** * Your MyStack object will be instantiated and called as such: * MyStack* obj = new MyStack(); * obj->push(x); * int param_2 = obj->pop (); * int param_3 = obj->top (); * bool param_4 = obj->empty (); */
到此为止，应该熟练掌握stack 与queue 这两种数据结构的操作，做好整理。
T20.有效的括号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public : bool isValid (string s) stack<charstack; for (auto i : s) { if (i == '(' || i == '[' || i == '{') { stack.push(i); } else { if (stack.empty()) return false ; if ((i == ')' && stack.top() == '(') || (i == ']' && stack.top() == '[') || (i == '}' && stack.top() == '{')) { stack.pop(); } else { return false ; } } } return stack.empty(); } };
T1047.删除字符串中的所有相邻重复项
判断空的位置 ：要铭记：所有判断空的条件需要放在第一个。比如这里的 if 判断空栈。栈溢出 ：系统输出的异常是Segmentation fault（当然不是所有的Segmentation fault 都是栈溢出导致的）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution {public : string removeDuplicates (string s) { stack<charstack; string str = ""; for (auto i : s) { if (stack.empty() || stack.top() != i) { stack.push(i); } else { stack.pop(); } } while (!stack.empty()) { str += stack.top(); stack.pop(); } reverse(str.begin(), str.end()); return str; } };
T150.逆波兰表达式求值 作为一道中等难度的题，也没有很复杂。
顺带需要复习一下前中后缀的转化。这里的逆波兰表达式是一种后缀表达式。
后缀表达式对计算机来说是非常友好 不需要根据优先级回退。
需要注意以下两点
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 evalRPN (vector<string>& tokens) int val = 0 ; stack<intstack; // int res; for (auto i : tokens) { // if (i == "+" || i == "-" || i == "*" || i == "/") { if (i == "+" || i == "-" || i == "*" || i == "/") { int right = stack.top(); stack.pop(); int left = stack.top(); stack.pop(); if (i == "+") stack.push(left + right); else if (i == "-") stack.push(left - right); else if (i == "*") stack.push(left * right); else if (i == "/") stack.push(left / right); } else stack.push(stoi(i)); } return stack.top(); } };
T239.滑动窗口最大值 一眼看过去感觉就很简单，标为一个困难的题肯定有他的原因，第一步先试试暴力。
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 max (queue<intq) int max = INT32_MIN; while (!q.empty ()) { max = max < q.front () ? q.front () : max; q.pop (); } return max; } vector<intmaxSlidingWindow(vector<int >& nums, int k) { queue<intq; vector<intv; for (auto i : nums) { if (q.size() < k - 1) { q.push(i); // continue ; } else { q.push(i); v.push_back(max(q)); q.pop(); } } return v; } };
不出意外出意外了。
引入**单调队列。**维持队列里的元素单调递增或递减
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 : class myQueue { public : deque<intq; void pop(int val) { if (!q.empty() && val == q.front()) { q.pop_front(); } } void push(int val) { while (!q.empty() && val q.back()) { q.pop_back(); } q.push_back(val); } int getMaxVal() { return q.front(); } }; vector<intmaxSlidingWindow(vector<int >& nums, int k) { myQueue myq; vector<intres; for (int i = 0; i < k; i++) { myq.push(nums[i]); } res.push_back(myq.getMaxVal()); for (int i = k; i < nums.size(); i++) { myq.pop(nums[i - k]); myq.push(nums[i]); res.push_back(myq.getMaxVal()); } return res; } };
精简版：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public : vector<intmaxSlidingWindow(vector<int >& nums, int k) { deque<intdq; vector<intv; for (int i = 0; i < nums.size(); i++) { // 移除滑动窗口外的元素 if (!dq.empty() && dq.front() == i - k) { dq.pop_front(); } // 移除所有小于当前元素的元素 while (!dq.empty() && nums[dq.back()] < nums[i]) { dq.pop_back(); } // 添加当前元素的索引 dq.push_back(i); // 从第 k 个元素开始记录结果 if (i >= k - 1) { v.push_back(nums[dq.front()]); } } return v; } };
分析一下这个双向队列的题：
这个 pop 操作只有在容器容量达到 k 的时候才会触发（即最少连续 k 次 push 都没有在过程中弹出任何元素）。从队头 弹出当前最大的元素。
push 的过程中会从队列尾部 拿出所有小于当前入队的元素。
T347.前 K 个高频元素 如果用暴力的方法排序时间复杂度为nlogn。不满足题目要求
如果换用大顶堆、小顶堆：只维护前 k 个元素，时间复杂度为nlogk。
优先级队列priority_queue帮我实现了堆的结构
二叉树 基础知识 初始化一棵树
1 2 3 4 5 6 struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode (int x) : val (x), left (NULL ), right (NULL ) {} };
二叉树的递归遍历 这个就比较简单了，要能非常熟练地写出来。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution {public : void traversal (TreeNode* root, vector<int >& res) if (root == nullptr ) return ; res.push_back (root->val); traversal (root->left, res); traversal (root->right, res); } vector<intpreorderTraversal(TreeNode* root) { vector<intres; traversal(root, res); return res; } };
二叉树的非递归遍历 前序遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public : vector<intpreorderTraversal(TreeNode *root) { stack<TreeNode *st; vector<intres; if (root == nullptr ) return res; st.push(root); while (!st.empty()) { TreeNode *cur = st.top(); res.push_back(cur->val); st.pop(); if (cur->right) st.push(cur->right); if (cur->left) st.push (cur->left); } return res; } };
后序遍历(由前序遍历改进)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Solution {public : vector<intpostorderTraversal(TreeNode* root) { stack<TreeNode*s; vector<intres; if (root == nullptr ) return res; s.push(root); while (!s.empty()) { TreeNode* cur = s.top(); res.push_back(cur->val); s.pop(); if (cur->left) s.push(cur->left); if (cur->right) s.push (cur->right); } reverse (res.begin (), res.end ()); return res; } };
中序遍历
和前面直接入栈的方法不同。
需要用指针到达最底部的左侧
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution {public : vector<intinorderTraversal(TreeNode* root) { stack<TreeNode*st; vector<intres; TreeNode* p = root; if (p == nullptr ) return res; while (!st.empty() || p != nullptr ) { if (p) { st.push(p); p = p->left; } // 先移动到最左边 else { p = st.top(); res.push_back(p->val); st.pop(); p = p->right; } } return res; } };
有了这个思路又可以改写前序遍历，只需要移动一行
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 class Solution {public : vector<intpreorderTraversal(TreeNode* root) { stack<TreeNode*st; vector<intres; TreeNode* p = root; if (p == nullptr ) return res; while (!st.empty() || p != nullptr ) { if (p) { st.push(p); res.push_back(p->val); p = p->left; } // 先移动到最左边 else { p = st.top(); st.pop(); p = p->right; } } return res; } };
二叉树的层序遍历 102. 二叉树的层序遍历
用一个队列实现，不需要递归。
这道题不同的是返回的是一个二维动态数组，所以需要在遍历的同时将不同层数的节点进行区分，所以需要引入一个 size 变量记录每一层的数量。
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<vector<int >levelOrder(TreeNode* root) { queue<TreeNode*q; vector<vector<int >res; if (root != nullptr ) q.push(root); while (!q.empty()) { int size = q.size(); // 记录当前队列中有多少个，有多少个就连续打出多少个（同一层） vector<intmidRes; for (int i = 0; i < size; i++) { TreeNode* tmp = q.front(); midRes.push_back(tmp->val); q.pop(); if (tmp->left != nullptr ) q.push(tmp->left); if (tmp->right != nullptr ) q.push (tmp->right); } res.push_back (midRes); } return res; } };
T226.翻转二叉树 递归的方法实现，比较简单，一看就会。
1 2 3 4 5 6 7 8 9 10 11 class Solution {public : TreeNode* invertTree (TreeNode* root) { if (root == nullptr ) return root; swap (root->left, root->right); invertTree (root->left); invertTree (root->right); return root; } };
也可以用前序遍历的非递归方式进行反转。
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 : TreeNode* invertTree (TreeNode* root) { stack<TreeNode*st; // vector<intres; if (root == nullptr ) // return res; return root; st.push(root); while (!st.empty()) { TreeNode* cur = st.top(); // res.push_back(cur->val); swap(cur->left, cur->right); st.pop (); if (cur->right) st.push (cur->right); if (cur->left) st.push (cur->left); } return root; } };
T101.对称二叉树 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution {public : bool compare (TreeNode* left, TreeNode* right) if ((left == nullptr && right != nullptr ) || (left != nullptr && right == nullptr )) { return false ; } if (left == nullptr && right == nullptr ) return true ; if (left->val != right->val) return false ; bool b1 = compare (left->left, right->right); bool b2 = compare (left->right, right->left); return b1 && b2; } bool isSymmetric (TreeNode* root) if (root == nullptr ) return true ; return compare (root->left, root->right); } };
T104.二叉树的最大深度 简单的一题
1 2 3 4 5 6 7 8 class Solution {public : int maxDepth (TreeNode* root) if (nullptr == root) return 0 ; int depth = max (maxDepth (root->left),maxDepth (root->right))+1 ; return depth; } };
当然也可以用层序遍历的模板（队列实现 BFS）
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 maxDepth (TreeNode* root) if (root==nullptr ) return 0 ; queue<TreeNode*qu; qu.push(root); int cnt = 0; while (!qu.empty()){ cnt++; int size = qu.size(); for (int i = 0; i < size; i++) { TreeNode* cur = qu.front(); qu.pop(); if (cur->left) qu.push (cur->left); if (cur->right) qu.push (cur->right); } } return cnt; } };
拓展：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 43 44 45 class Solution {public : int maxDepth (Node* root) if (root == nullptr ) return 0 ; queue<Node*qu; qu.push(root); int cnt = 0; while (!qu.empty()) { cnt++; int size = qu.size(); for (int i = 0; i < size; i++) { Node* cur = qu.front(); qu.pop(); for (int j = 0; j < cur->children.size (); j++) { if (cur->children[j] != nullptr ) qu.push (cur->children[j]); } } } return cnt; } };
T111.二叉树的最小深度 和上一题的变化比较大，从简单的一层到两层开始用代码推理。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution {public : int minDepth (TreeNode* root) if (root == nullptr ) return 0 ; if (root->left == nullptr && root->right != nullptr ) { return 1 + minDepth (root->right); } if (root->right == nullptr && root->left != nullptr ) { return 1 + minDepth (root->left); } return (min (minDepth (root ->left), minDepth (root->right))+1 ); } };
T222.完全二叉树的节点个数 1 2 3 4 5 6 7 8 9 10 class Solution {public : int countNodes (TreeNode* root) if (root == nullptr ) return 0 ; int leftCnt = countNodes (root->left); int rightCnt = countNodes (root->right); return leftCnt + rightCnt + 1 ; } };
T110.平衡二叉树 这题要判断是否是一个平衡二叉树，根据平衡二叉树的定义：左右子树的高度差不能超过 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 {public : int getHeight (TreeNode* root) if (root == nullptr ) return 0 ; int leftHeight = getHeight (root->left); if (leftHeight == -1 ) return -1 ; int rightHeight = getHeight (root->right); if (rightHeight == -1 ) return -1 ; if (abs (leftHeight - rightHeight) > 1 ) return -1 ; else return (max (leftHeight, rightHeight) + 1 ); } bool isBalanced (TreeNode* root) return getHeight (root) == -1 ? false : true ; } };
T257.二叉树的所有路径 这个题也比较绕，整体就是一个前序递归遍历，但是额外加了一个 path 用于记录路径。
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 : void getPath (TreeNode* root, string path, vector<string>& res) if (root == nullptr ) { return ; } if (!path.empty ()) { path += "->" ; } path += to_string (root->val); if (root->left == nullptr && root->right == nullptr ) { res.push_back (path); return ; } getPath (root->left, path, res); getPath (root->right, path, res); } vector<stringbinaryTreePaths(TreeNode* root) { vector<stringres; getPath(root, "", res); return res; } };
T404.左叶子之和 这题自己可以写出来，但是难理解的地方在于这个 if 夹在中间的位置
我的理解是整个树的节点可以非为两类
这是一种后续遍历的递归方法
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 sumOfLeftLeaves (TreeNode* root) if (root == nullptr ) return 0 ; int leftCount = 0 ; int rightCount = 0 ; leftCount = sumOfLeftLeaves (root->left); if (root->left != nullptr && root->left->left == nullptr && root->left->right == nullptr ) { leftCount = sumOfLeftLeaves (root->left) + root->left->val; } rightCount = sumOfLeftLeaves (root->right); return leftCount + rightCount; } };
T513.找树左下角的值 题目可以改写为：深度最大的叶子节点
由层序遍历简单变形一下
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 : int findBottomLeftValue (TreeNode* root) queue<TreeNode*q; // vector<vector<int >res; if (root != nullptr ) q.push(root); int tmpint; while (!q.empty()) { int size = q.size(); // 记录当前队列中有多少个，有多少个就连续打出多少个（同一层） // vector<intmidRes; for (int i = 0; i < size; i++) { TreeNode* tmp = q.front(); if (i == 0) tmpint = tmp->val; // midRes.push_back(tmp->val); q.pop(); if (tmp->left != nullptr ) q.push (tmp->left); if (tmp->right != nullptr ) q.push (tmp->right); } } return tmpint; } };
T112. 路径总和 参考 T257
记录路径
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 class Solution {public : void target (TreeNode* root, vector<intpath, vector<vector<int >>& res) if (root == nullptr ) return ; path.push_back (root->val); if (root->left == nullptr && root->right == nullptr ) { res.push_back (path); } target (root->left, path, res); target (root->right, path, res); } bool hasPathSum (TreeNode* root, int targetSum) vector<vector<int >res; vector<intpath; target(root, path, res); for (vector<intv : res) { int sum = 0; for (auto i = v.begin(); i != v.end();i++) sum += *i; if (sum == targetSum) return true ; } return false ; } };
在写这个代码的过程中要铭记回溯原理：
显式回溯
1 2 3 4 5 6 7 8 9 10 11 12 void target (TreeNode* root, vector<int >& path, vector<vector<int >>& res) if (root == nullptr ) return ; path.push_back (root->val); if (root->left == nullptr && root->right == nullptr ) { res.push_back (path); } target (root->left, path, res); target (root->right, path, res); path.pop_back (); }
隐式回溯
1 2 3 4 5 6 7 8 9 10 11 12 void target (TreeNode* root, vector<intpath, vector<vector<int >>& res) if (root == nullptr ) return ; path.push_back (root->val); if (root->left == nullptr && root->right == nullptr ) { res.push_back (path); } target (root->left, path, res); target (root->right, path, res); }
更简洁高效的算法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution {public : bool dfs (TreeNode* root, int targetSum) if (!root) return false ; targetSum -= root->val; if (!root->left && !root->right) { return targetSum == 0 ; } return dfs (root->left, targetSum) || dfs (root->right, targetSum); } bool hasPathSum (TreeNode* root, int targetSum) return dfs (root, targetSum); } };
T617.合并二叉树 一口气写下来的方法，但是有很多地方值得优化，特别是调用递归时，不能解引用空指针。
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 : TreeNode* mergeTrees (TreeNode* root1, TreeNode* root2) { if (root1 == nullptr && root2 == nullptr ) { return nullptr ; } TreeNode* newnode = new TreeNode (0 ); if (root1 == nullptr && root2 != nullptr ) { newnode->val = root2->val; } if (root1 != nullptr && root2 == nullptr ) { newnode->val = root1->val; } if (root1 != nullptr && root2 != nullptr ) { newnode->val = root1->val + root2->val; } newnode->left = mergeTrees (root1 ? root1->left : nullptr , root2 ? root2->left : nullptr ); newnode->right = mergeTrees (root1 ? root1->right : nullptr , root2 ? root2->right : nullptr ); return newnode; } };
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 : TreeNode* mergeTrees (TreeNode* root1, TreeNode* root2) { if (root1 == nullptr ) return root2; if (root2 == nullptr ) { return root1; } TreeNode* newnode = new TreeNode (root1->val + root2->val); newnode->left = mergeTrees (root1->left, root2->left); newnode->right = mergeTrees (root1->right, root2->right); return newnode; } };
拓展 这里写迭代器就遇到问题了。
第一点：vector 的 erase 里必须传的是迭代器对象，而不是一个具体的数值或者是元素对象
第二点：res.erase(v); 会使迭代器失效 ，导致 v++ 可能访问非法内存。
1 2 3 4 5 6 7 for (auto v = res.begin (); v != res.end (); v++) { int sum = 0 ; for (auto i = v.begin (); i != v.end (); i++) sum += *i; if (sum != targetSum) res.erase (v); }
所以引入求和的方法int sum = accumulate(it->begin(), it->end(), 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 37 38 39 40 41 42 43 44 45 46 47 class Solution {public : void target (TreeNode* root, vector<intpath, vector<vector<int >>& res) if (root == nullptr ) return ; path.push_back (root->val); if (root->left == nullptr && root->right == nullptr ) { res.push_back (path); } target (root->left, path, res); target (root->right, path, res); } vector<vector<int >pathSum(TreeNode* root, int targetSum) { vector<vector<int >res; vector<intpath; target(root, path, res); for (auto it = res.begin(); it != res.end();) { int sum = accumulate(it->begin(), it->end(), 0); if (sum != targetSum) it = res.erase(it); // `erase()` 返回新的有效迭代器 else ++it; } return res; } };
T106.从中序与后序遍历序列构造二叉树
理解推导的整个流程
利用后序最后一个节点去切割中序遍历为两个部分
这个中序的左半部分元素 m 正好对应后序的前 m 个元素；中序的右半部分 n 个元素正好对应后序的 m 个元素后的 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 43 44 45 46 47 class Solution {public : TreeNode* traversal (vector<int >& inorder, vector<int >& postorder) { if (inorder.empty () || postorder.empty ()) return nullptr ; int tmp = postorder[postorder.size () - 1 ]; TreeNode* newnode = new TreeNode (tmp); int idx = 0 ; for (; idx < inorder.size (); idx++) { if (inorder[idx] == tmp) break ; } vector<intmidleft(inorder.begin(), inorder.begin() + idx); vector<intmidright(inorder.begin() + idx + 1, inorder.end()); // 切割后序遍历 vector<intpostleft(postorder.begin(), postorder.begin() + midleft.size()); vector<intpostright(postorder.begin() + midleft.size(), postorder.end() - 1); newnode->left = traversal(midleft, postleft); newnode->right = traversal(midright, postright); return newnode; } TreeNode* buildTree(vector<int >& inorder, vector<int >& postorder) { if (inorder.empty() || postorder.empty()) return nullptr ; return traversal(inorder, postorder); } };
T106.从中序与后序遍历序列构造二叉树
理解推导的整个流程
利用后序最后一个节点去切割中序遍历为两个部分
这个中序的左半部分元素 m 正好对应后序的前 m 个元素；中序的右半部分 n 个元素正好对应后序的 m 个元素后的 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 43 44 45 46 47 class Solution {public : TreeNode* traversal (vector<int >& inorder, vector<int >& postorder) { if (inorder.empty () || postorder.empty ()) return nullptr ; int tmp = postorder[postorder.size () - 1 ]; TreeNode* newnode = new TreeNode (tmp); int idx = 0 ; for (; idx < inorder.size (); idx++) { if (inorder[idx] == tmp) break ; } vector<intmidleft(inorder.begin(), inorder.begin() + idx); vector<intmidright(inorder.begin() + idx + 1, inorder.end()); // 切割后序遍历 vector<intpostleft(postorder.begin(), postorder.begin() + midleft.size()); vector<intpostright(postorder.begin() + midleft.size(), postorder.end() - 1); newnode->left = traversal(midleft, postleft); newnode->right = traversal(midright, postright); return newnode; } TreeNode* buildTree(vector<int >& inorder, vector<int >& postorder) { if (inorder.empty() || postorder.empty()) return nullptr ; return traversal(inorder, postorder); } };
T 654.最大二叉树 自己靠感觉写的感觉比题解的好理解。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution {public : TreeNode* constructMaximumBinaryTree (vector<int >& nums) { if (nums.empty ()) return nullptr ; auto maxIt = max_element (nums.begin (), nums.end ()); int maxVal = *maxIt; int maxIndex = distance (nums.begin (), maxIt); TreeNode* newnode =new TreeNode (maxVal); vector<intleft (nums.begin(), nums.begin()+maxIndex); vector<intright (nums.begin()+maxIndex+1, nums.end()); newnode->left = constructMaximumBinaryTree(left); newnode->right = constructMaximumBinaryTree (right); return newnode; } };
这里可以参考GPT 提供的针对动态数组利用迭代器找最大值。
贪心算法 T455.分发饼干 比较简单的一题，想好怎么个流程再下笔。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : int findContentChildren (vector<int >& g, vector<int >& s) sort (g.begin (), g.end ()); sort (s.begin (), s.end ()); int cnt = 0 ; int index = s.size () - 1 ; for (int i = g.size () - 1 ; i >= 0 ; i--) { if (index >= 0 && g[i] <= s[index]) { cnt++; index--; } } return cnt; } };
使用 sort ：反转 vector 需要使用 sort 函数，需要传入迭代器范围
反向排序 ：如果需要实现反方向排序
1 std::sort (nums.rbegin (), nums.rend ());
复杂结构体排序（结构体） ：
1 2 3 4 5 6 7 8 9 10 struct Student { std::string name; int score; }; bool cmp (const Student& a, const Student& b) return a.score b.score; } std::vector<Studentstudents; std::sort(students.begin(), students.end(), cmp);
vector 的 erase 使用 ：参数需要传入迭代器
1 2 3 4 5 6 std::vector<intvec{1, 2, 3, 4, 5}; auto it = vec.begin() + 2; // 指向3it = vec.erase(it); // 删除3，vec变为{1, 2, 4, 5}，it指向4 // 删除区间[vec.begin(), vec.begin()+2) vec.erase(vec.begin(), vec.begin() + 2); // vec变为{4, 5}
T376.摆动序列 没看题解自己用栈完成了一版答案。一开始没有考虑到如果遇到更小/更大的数字也需要更新栈顶
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 class Solution { public : int wiggleMaxLength (vector<int &nums) { stack<ints; s.push(nums[0]); int flag = 0; for (int i = 1; i < nums.size(); i++) { if (nums[i] == s.top()) continue ; else { if (s.size() == 1) { flag = nums[i] s.top() ? 1 : -1; s.push(nums[i]); } else { if (flag == 1) { if (nums[i] < s.top()) { s.push(nums[i]); flag = -flag; } else if (nums[i] s.top()) { s.pop(); s.push(nums[i]); } } else { if (nums[i] s.top()) { s.push(nums[i]); flag = -flag; } else if (nums[i] < s.top()) { s.pop(); s.push(nums[i]); } } } } } return s.size(); } };
利用代码随想录里的贪心算法思路。只有当前一个差值和当前差值符号相反时才更新计数序列数量
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : int wiggleMaxLength (vector<int >& nums) if (nums.size () <= 1 ) return nums.size (); int curDiff = 0 ; int preDiff = 0 ; int result = 1 ; for (int i = 0 ; i < nums.size () - 1 ; i++) { curDiff = nums[i + 1 ] - nums[i]; if ((preDiff <= 0 && curDiff 0 ) || (preDiff >= 0 && curDiff < 0 )) { result++; preDiff = curDiff; } } return result; } };
动态规划 动规是由前一个状态推导出来的，而贪心是局部直接选最优的。
刷题小总结 针对 01背包问题 大致可以变形出几种常见的设问：
物品的种类 N，背包的容量 M，weight[N],value[N]。
计算在 M 的限制下，能装载的最大价值数（01 背包典型例题）
计算在 M 的限制，下最大的重量（分割等和子集）
计算能达到重量 weight 的方法数量（目标和）
求组合数：动态规划：518.零钱兑换II (opens new window) 求排列数：动态规划：377. 组合总和 Ⅳ (opens new window) 、动态规划：70. 爬楼梯进阶版（完全背包） (opens new window) 求最小数：动态规划：322. 零钱兑换 (opens new window) 、动态规划：279.完全平方数
01背包问题 ：先遍历物品，再逆序遍历背包容量
完全背包问题：根据问题类型选择遍历顺序
求组合数（不考虑顺序）：先遍历物品，再正序遍历容量
求排列数（考虑顺序）：先遍历容量，再遍历物品
求最小值或最大价值：遍历顺序可能无关
T509. 斐波那契数 没啥好说的，只需要维护两个数组。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution {public : int fib (int n) if (n <= 1 ) return n; vector<intdp(3); dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[2] = dp[0] + dp[1]; int tmp = dp[1]; dp[1] = dp[2]; dp[0] = tmp; } return dp[2]; } };
T70.爬楼梯 这题没啥好说的了
T746. 使用最小花费爬楼梯 也是一遍过的简单题
1 2 3 4 5 6 7 8 9 10 11 12 class Solution {public : int minCostClimbingStairs (vector<int >& cost) vector<intdp(1005); dp[0] = 0; dp[1] = 0; for (int i = 2; i <= cost.size(); i++) { dp[i] = min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]); } return dp[cost.size()]; } };
T62.不同路径 简单题，但要明确什么如何初始化。
1 2 3 4 5 6 7 8 9 10 11 12 class Solution {public : int uniquePaths (int m, int n) vector<vector<int >dp(m + 1, vector<int >(n + 1, 1)); for (int i = 2; i <= m; i++) { for (int j = 2; j <= n; j++) { dp[i][j] = dp[i][j-1] + dp [i-1][j]; } } return dp[m][n]; } };
T63.不同路径 II 简单的一题但是 debug 了好几次
问题集中在：
开始初始化的方式不能像上题一样全为 1，而是要考虑是否可能会出现石头
对二维数组取 m 和 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 class Solution {public : int uniquePathsWithObstacles (vector<vector<int >>& obstacleGrid) int m = obstacleGrid.size (); int n = obstacleGrid[0 ].size (); vector<vector<int >dp(m, vector<int >(n, 0)); for (int i = 0; i < m && obstacleGrid[i][0] != 1; i++) dp[i][0] = 1; // 初始化第一列 for (int i = 0; i < n && obstacleGrid[0][i] != 1; i++) dp[0][i] = 1; // 初始化第一行 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (obstacleGrid[i][j] == 1) { dp[i][j] = 0; continue ; } else dp[i][j] = dp[i][j - 1] + dp[i - 1][j]; } } return dp[m - 1][n - 1]; } };
T343.整数拆分 这道题在做的过程中有些乱了，整理一下：
首先需要明确 dp 数组的意义：dp[i] 表示整数 i 拆分之后的乘积最大值。
确定起点，这里 dp[0] 和 dp[1]，没有意义，所以不需要赋值。
思考状态转换的公式，dp[i - j] * j 表示至少有 3 个数组成的乘积；(i - j) * j 表示只有两个数组成的乘积。
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution {public : int integerBreak (int n) vector<intdp(n + 1, 0); // 初始化dp数组 dp[2] = 1; for (int i = 3; i <= n; i++) { for (int j = 1; j < i; j++) { dp[i] = max(dp[i], max(dp[i - j] * j, (i - j) * j)); } } return dp[n]; } };
T96.不同的二叉搜索树 复习一下 BST 的概念。
「卡玛网」01背包问题 应该是第三次做这个题目了，理解也更深刻了。
理解 dp[i][j] ：
i 为物品序号，指的是可以使用序号[0,i]的物品。
j 代表背包的容量，代码实现需要遍历背包的容量。
dp[i][j] 代表可以使用前 i 种序号对应的物品，j 表示容量的限制。
两种情况 ：
背包当前 j 容量装不下第 i 号物品：dp[i][j] = dp[i-1][j]
背包当前 j 容量装得下第 i 号物品：dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight] + value[i])
初始化方法 ：
1 2 3 4 5 6 7 8 9 10 11 12 vector<intweight(n, 0); // 存储每件物品所占空间 vector<intvalue(n, 0); // 存储每件物品价值 vector<vector<int >dp(weight.size(), vector<int >(bagweight + 1, 0)); // 初始化, 因为需要用到dp[i - 1]的值 // j < weight[0]已在上方被初始化为0 // j >= weight[0]的值就初始化为value[0] for (int j = weight[0]; j <= bagweight; j++){ dp[0][j] = value[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 37 38 39 40 41 42 #include <bits/stdc++.h> using namespace std;int main () int n, bagweight; cin >n >bagweight; vector<intweight(n, 0); // 存储每件物品所占空间 vector<intvalue(n, 0); // 存储每件物品价值 for (int i = 0; i < n; ++i) { cin >weight[i]; } for (int j = 0; j < n; ++j) { cin >value[j]; } vector<vector<int >dp(weight.size(), vector<int >(bagweight + 1, 0)); // 初始化, 因为需要用到dp[i - 1]的值 // j < weight[0]已在上方被初始化为0 // j >= weight[0 ]的值就初始化为value[0 ] for (int j = weight[0 ]; j <= bagweight; j++) { dp[0 ][j] = value[0 ]; } for (int i = 1 ; i < weight.size (); i++) { for (int j = 0 ; j <= bagweight; j++) { if (weight[i]>j) dp[i][j] = dp[i-1 ][j]; else { dp[i][j] = max (dp[i-1 ][j],dp[i-1 ][j-weight[i]]+value[i]); } } } cout << dp[n - 1 ][bagweight] << endl; return 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 37 38 39 40 41 42 43 #include <iostream> #include <vector> using namespace std;int main () int t, s; cin >t >s; vector<intweight(t); vector<intvalue(t); vector<intdp(s + 1); for (int i = 0; i < t; i++) { cin >weight[i]; } for (int i = 0; i < t; i++) { cin >value[i]; } // 初始化 for (int i = 0; i <= s; i++) { if (i < weight[0]) dp[i] = 0; else dp[i] = value[0]; } for (int i = 1; i < t; i++) { for (int j = s; j >= 0 ; j--) { if (j >= weight[i]) { dp[j] = max (dp[j], dp[j - weight[i]] + value[i]); } else dp[j] = dp[j]; } } cout << dp[s]; return 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 #include <iostream> #include <vector> using namespace std;int main () int t, s; cin >t >s; vector<intweight(t); vector<intvalue(t); for (int i = 0; i < t; i++) cin >weight[i]; for (int i = 0; i < t; i++) cin >value[i]; vector<intdp(s + 1, 0); for (int i = 0; i < t; i++) { for (int j = s; j >= weight[i]; j--) { dp[j] = max (dp[j], dp[j - weight[i]] + value[i]); } } cout << dp[s]; return 0 ; }
T416.分割等和子集 本质是能否将sum/2 的背包装满 ？
这具体是什么意思需要绕一下：这里不再有价值的概念，而是只有重量。背包最多能承重 sum/2。而 01 背包解决的就是最大的容量，如果背包能达到这个理论的最大值，那么就是可以可分割的等和自己。
然后就是要熟练使用这个滚动数组了，二维太麻烦了 。记住两层循环的原理：第一层是从小到大遍历物品序号；第二层是从大到小遍历容量，为了省去多余赋值的步骤，需要将循环的重点设定在 nums[i]。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : bool canPartition (vector<int >& nums) int sum = 0 ; for (int i : nums) { sum += i; } if (sum % 2 != 0 ) return false ; vector<intdp(sum / 2 + 1, 0); // 开辟的空间要+1，以便下面的循环访问 for (int i = 0; i < nums.size(); i++) { for (int j = sum / 2; j >= nums[i]; j--) { dp[j] = max (dp[j], dp[j - nums[i]] + nums[i]); } } return (dp[sum / 2 ] == sum / 2 ) ? true : false ; } };
T1049.最后一块石头的重量II 修改一下返回值就可以了，和 T416 是一模一样的题目。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution {public : int lastStoneWeightII (vector<int >& stones) int sum = 0 ; for (int i : stones) { sum += i; } vector<intdp(sum / 2 + 1, 0); // 开辟的空间要+1，以便下面的循环访问 for (int i = 0; i < stones.size(); i++) { for (int j = sum / 2; j >= stones[i]; j--) { dp[j] = max (dp[j], dp[j - stones[i]] + stones[i]); } } return sum - 2 * (dp[sum / 2 ]); } };
T494.目标和 题目的的题面让人么有思路，用两个数学式子转换一下题意就变得很清晰。
背包的大小是 plus，每种物品只能用一次，计算能凑出大小为 plus 的方法数，其实也是利用上一行的两数之和来作为状态转化公式。
二维数组的做法：
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 class Solution {public : int findTargetSumWays (vector<int >& nums, int target) int sum = 0 ; for (int i : nums) sum += i; int plus = target + sum; if (plus % 2 != 0 || abs (target) sum) return 0 ; plus = plus / 2 ; int N = nums.size (); vector<vector<int >dp(N, vector<int >(plus + 1, 0)); // 从这里开始就是用 nums 来凑出这个总价值为 plus 的 01 背包问题了 // 但是此时的 dp[i][j]不再是总价值了，而是利用前 i // 个物品，能凑出该总价值为 j 的方案数量 // 首先初始化 dp[0][0] = 1; if (nums[0] <= plus) dp[0][nums[0]] = 1; int numZero = 0; for (int i = 0; i < nums.size(); i++) { if (nums[i] == 0) numZero++; dp[i][0] = (int )pow(2.0, numZero); } // 然后再计算状态转换公式 for (int i = 1; i < nums.size(); i++) { for (int j = 0; j <= plus; j++) { if (nums[i] <= j) dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]]; else dp[i][j] = dp[i - 1][j]; } } return dp[N - 1][plus]; } };
一维数组的做法：
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 : int findTargetSumWays (vector<int >& nums, int target) int sum = 0 ; for (int i : nums) sum += i; int plus = target + sum; if (plus % 2 != 0 || abs (target) sum) return 0 ; int M = plus / 2 ; int N = nums.size (); vector<intdp(M + 1, 0); // 首先初始化 dp[0] = 1; for (int i = 0; i < N; i++) { for (int j = M; j >= nums[i]; j--) { dp[j] = dp[j] + dp[j - nums[i]]; } } return dp[M]; } };
T474.一和零 难度在于理解，这道题有两个限制条件：既要满足不超过 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 class Solution {public : int findMaxForm (vector<string>& strs, int m, int n) vector<vector<int >dp(m + 1, vector<int >(n + 1, 0)); for (string str : strs) { int one = 0, zero = 0; for (char ch : str) { if (ch == '0') zero++; if (ch == '1') one++; } for (int i = m; i >= zero; i--) { for (int j = n; j >= one; j--) { if (zero <= m && one <= n) { dp[i][j] = max (dp[i][j], dp[i - zero][j - one] + 1 ); } } } } return dp[m][n]; } };
「卡玛网」完全背包问题 一维数组的方法：
注意区分这个和 01背包的区别：
只有 01 背包问题的滚动数组需要从尾部开始遍历
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 #include <iostream> #include <vector> using namespace std;int main () int t, s; cin >t >s; vector<intweight(t); vector<intvalue(t); for (int i = 0; i < t; i++) cin >weight[i]>>value[i]; vector<intdp(s + 1, 0); for (int i = 0; i <= s; i++) { for (int j = 0; j <t; j++) { if (i>=weight[j]) dp[i] = max (dp[i], dp[i - weight[j]] + value[j]); } } cout << dp[s]; return 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 37 38 39 40 41 42 43 #include <iostream> #include <vector> using namespace std;int main () int t, s; cin >t >s; vector<intweight(t); vector<intvalue(t); for (int i = 0; i < t; i++) cin >weight[i] >value[i]; vector<vector<int >dp(t, vector<int >(s + 1, 0)); // 初始化 for (int i = weight[0]; i <= s; i++) { // if (weight[0]>=i) dp[0 ][i] = max (dp[0 ][i - weight[0 ]] + value[0 ], value[0 ]); } for (int i = 1 ; i < t; i++) { for (int j = 0 ; j <= s; j++) { if (weight[i] j) dp[i][j] = dp[i - 1 ][j]; else dp[i][j] = max (dp[i - 1 ][j], dp[i][j - weight[i]] + value[i]); } } cout << dp[t - 1 ][s]; return 0 ; }
T518.零钱兑换II 完全背包问题+达到某个数值的组合 问题
计算满足条件的方法数，并且是一个完全背包：画二维矩阵找出这个迭代方法与合理的迭代方向。
一维数组方法：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution {public : int change (int amount, vector<int >& coins) int M = amount; int N = coins.size (); vector<uint64_tdp(M + 1, 0); // 首先初始化 dp[0] = 1; for (int i = 0; i < N; i++) { for (int j = coins[i]; j <=M; j++) { dp[j] += dp[j-coins[i]]; } } return dp[M]; } };
T377. 组合总和 Ⅳ 达到某个数值统计排列 种类数量+完全背包问题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution {public : int combinationSum4 (vector<int >& nums, int target) int M = target; int N = nums.size (); vector<uint64_tdp(M+1, 0); dp[0] = 1; for (int i = 1; i <= M; i++) { for (int j = 0; j < N; j++) { if (i>=nums[j]) dp[i] = dp[i] + dp[i-nums[j]]; } } return dp[M]; } };
「卡码」爬楼梯（升级版） 达到某个数值统计排列 种类数量+完全背包问题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include <iostream> #include <vector> using namespace std;int main () int M,N; cin>>M>>N; vector<intdp(M+1,0); dp[0] = 1; for (int i =1;i<=M;i++){ for (int j = 1;j<=N;j++){ if (i>=j) dp[i] = dp[i]+dp[i-j]; } } cout<<dp[M]; return 0 ; }
T322. 零钱兑换 求组合种类数量+完全背包问题
需要注意这里是取较小值，所以要进行初始化。
这里考虑的是计算组合的数量，所以将遍历背包放在内层循环。反之如果是统计组合数，需要放在外层循环。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution {public : int coinChange (vector<int >& coins, int amount) vector<vector<uint64_t >dp(coins.size(), vector<uint64_t >(amount + 1, INT_MAX)); int N = coins.size(), M = amount; for (int i = 0; i <= M; i++) { if (i % coins[0] == 0) dp[0][i] = i/coins[0]; } for (int i = 1; i < N; i++) { for (int j = 0; j <= M; j++) { if (j >= coins[i]) dp[i][j] = min (dp[i - 1 ][j], dp[i][j - coins[i]] + 1 ); else dp[i][j] = dp[i - 1 ][j]; } } if (dp[N - 1 ][M] == INT_MAX) return -1 ; else return dp[N - 1 ][M]; } };
T279.完全平方数 完全背包问题：求最小值：遍历背包和物品的顺序没有影响
背包是 i 取值是 1～n
物品是完全平方数，有无限个完全平方数可供选择。
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution {public : int numSquares (int n) vector<intdp(n + 1, INT_MAX); dp[0] = 0; for (int i = 1; i <= n; i++) { for (int j = 1; i >= j * j; j++) { dp[i] = min (dp[i], dp[i - j * j] + 1 ); } } return dp[n]; } };
此处跳过一题 「卡玛网」多重背包问题 也是由 01 背包问题演变过来的，将可以使用的次数展开为不同的物品。循环的前两层和 01 背包问题完全一致，只不过加了一层 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 26 27 28 29 30 31 32 33 #include <iostream> #include <vector> using namespace std;int main () int M, N; cin >M >N; vector<intweight(N, 0); vector<intvalue(N, 0); vector<intcount(N, 0); for (int i = 0; i < N; i++) cin >weight[i]; for (int i = 0; i < N; i++) cin >value[i]; for (int i = 0; i < N; i++) cin >count[i]; vector<intdp(M + 1, 0); for (int i = 0; i < N; i++) { for (int j = M; j >= weight[i]; j--) { for (int k = 0 ; k <= count[i] && j >= k * weight[i]; k++) { dp[j] = max (dp[j], dp[j - k * weight[i]] + k * value[i]); } } } cout << dp[M]; return 0 ; }
T198.打家劫舍 dp[i] 表示打劫完前 0～i 家后最多能赚到的💰。
这个状态转移方程很重要dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);表示视野始终看不到前面的一家。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution {public : int rob (vector<int >& nums) if (nums.size () == 1 ) return nums[0 ]; if (nums.size () == 2 ) return max (nums[1 ], nums[0 ]); vector<uint64_tdp(nums.size(), 0); dp[0] = nums[0]; dp[1] = max(nums[0],nums[1]); for (int i = 2; i < nums.size(); i++) { dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]); } return dp[nums.size() - 1]; } };
T213.打家劫舍 II 围成一个圈，其实也不难，分两种情况套路，考虑第一个元素就不能考虑尾部的那个元素。
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 : int rob (vector<int >& nums) if (nums.size () == 1 ) return nums[0 ]; if (nums.size () == 2 ) return max (nums[1 ], nums[0 ]); vector<uint64_tdp1(nums.size(), 0); dp1[0] = nums[0]; dp1[1] = max(nums[1], nums[0]); for (int i = 2; i < nums.size() - 1; i++) { dp1[i] = max(dp1[i - 1], dp1[i - 2] + nums[i]); } // 计算从第二个元素到最后一个元素的最大值 vector<uint64_tdp2(nums.size(), 0); dp2[1] = nums[1]; for (int i = 2; i < nums.size(); i++) { dp2[i] = max(dp2[i - 1], dp2[i - 2] + nums[i]); } return max(dp1[nums.size() - 2], dp2[nums.size() - 1]); } };
跳过一个打家劫舍三 T121.买卖股票的最佳时机 这题初始化了一个二维动态数组，之所以要维护两列是因为
这里需要理解的是
dp[i][0]表示当前日期持有股票的现金最大值；
当然包括在第 i 天买入股票
随着天数的变化这个数据理论上来说是逐渐变大的，但是不会是一个非负数 。
dp[i][1]表示当前日期不持有这这张股票的最大值。
可能是在第 i 天之前卖出了，也可能是第 i 天卖出股票。
如果在第 i 天卖出了利润更高，那么会覆盖在第 i 天卖出之前的数据。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution {public : int maxProfit (vector<int >& prices) vector<vector<int >dp(prices.size(), vector<int >(2)); // 初始化 // 股票只买卖一次。dp[i][0]表示当前日期没有持有股票的现金最大值；dp[i][1]表示当前日期不持有这这张股票的最大值。 dp[0][0] = -prices[0]; dp[0][1] = 0; for (int i = 1; i < prices.size(); i++) { dp[i][0] = max(dp[i - 1][0], -prices[i]); dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]); } return dp[prices.size() - 1][1]; } };
自己取消题干的一个假设：如果不能在同一天卖,最终的利润可以为负数？
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution {public : int maxProfit (vector<int >& prices) int n = prices.size (); if (n == 0 ) return 0 ; vector<vector<int >dp(n, vector<int >(2)); // 初始化 dp[0][0] = -prices[0]; // 第一天买入 dp[0][1] = -1e9; // 设为极小值，表示第一天无法卖出 for (int i = 1; i < n; i++) { dp[i][0] = max(dp[i - 1][0], -prices[i]); // 继续持有 or 今天买入 dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]); // 继续不持有 or 今天卖出 } return dp[n - 1][1]; // 可能是负数 } };
T122.买卖股票的最佳时机II 唯一的变化就是 dp[i][0] 的推导可以从
第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
第i天买入股票，所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即：dp[i - 1][1] - prices[i]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution {public : int maxProfit (vector<int >& prices) vector<vector<int >dp(prices.size(), vector<int >(2)); // 初始化 // 股票只买卖一次。dp[i][0]表示当前日期没有持有股票的现金最大值；dp[i][1]表示当前日期不持有这这张股票的最大值。 dp[0][0] = -prices[0]; dp[0][1] = 0; for (int i = 1; i < prices.size(); i++) { dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]); } return dp[prices.size() - 1][1]; } };
123.买卖股票的最佳时机 III 分为四种状态讨论，
dp[0][1] = -prices[0]; // 第一次持有股票
dp[0][2] = 0; // 第一次不持有股票
dp[0][3] = -prices[0]; // 第二次持有股票
dp[0][4] = 0; // 第二次不持有股票
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 maxProfit (vector<int >& prices) vector<vector<int >dp(prices.size(), vector<int >(5)); dp[0][1] = -prices[0]; // 第一次持有股票 dp[0][2] = 0; // 第一次不持有股票 dp[0][3] = -prices[0]; // 第二次持有股票 dp[0][4] = 0; // 第二次不持有股票 for (int i = 1; i < prices.size(); i++) { // dp[i][0] = dp[i - 1][0]; // dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]); dp[i][1] = max(dp[i - 1][1], -prices[i]); dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]); dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]); dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]); } return dp[prices.size() - 1][4]; } };
T188.买卖股票的最佳时机IV 仿照上一题改一下就出来了
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 maxProfit (int k, vector<int >& prices) vector<vector<int >dp(prices.size(), vector<int >(2 * k + 1)); for (int i = 1; i <= 2 * k; i++) { if (i % 2 != 0) dp[0][i] = -prices[0]; } for (int i = 1; i < prices.size(); i++) { // dp[i][0] = dp[i - 1][0]; // dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]); dp[i][1] = max(dp[i - 1][1], -prices[i]); dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]); for (int j = 3; j <= 2 * k; j += 2) { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]); dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] + prices[i]); } } return dp[prices.size() - 1][2 * 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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 #include <iostream> #include <map> #include <vector> #include <algorithm> using namespace std;struct Product { string name; int quantity; int total_sales; }; bool compare (const Product &a, const Product &b) if (a.quantity != b.quantity) return a.quantity b.quantity; return a.name < b.name; } int main () map<string, pair<int , int >sales_data; // 商品名称 -(销售数量, 销售额) string name; int quantity, price; string date; while (cin >name >quantity >price >date) { sales_data[name].first += quantity; sales_data[name].second += quantity * price; } vector<Productproducts; for (const auto &entry : sales_data) { products.push_back({entry.first, entry.second.first, entry.second.second}); } sort(products.begin(), products.end(), compare); for (const auto &product : products) { cout << product.name << " " << product.quantity << " " << product.total_sales << endl; } return 0; }
