本文记录了在LeetCode练习中针对部分题目的思路与题解。
排序 题干 给你一个整数数组 nums，请你将该数组升序排列。
你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。
示例 1：
输入：nums = [5,2,3,1] 输出：[1,2,3,5]
示例 2：
输入：nums = [5,1,1,2,0,0] 输出：[0,0,1,1,2,5]
提示：
1 <= nums.length <= 5 * 104-5 * 104 <= nums[i] <= 5 * 104
题解 快速排序 思路
细节
多看多写几次吧
代码
class Solution {public : int partition (vector<int >& nums, int begin, int end) int pivot = nums[(begin + end) / 2 ]; swap (nums[begin], nums[(begin + end) / 2 ]); int le = begin + 1 , ge = end; while (le <= ge) { while (le <= ge && nums[le] < pivot) ++le; while (le <= ge && nums[ge] > pivot) --ge; if (le <= ge) { swap (nums[le], nums[ge]); ++le; --ge; } } swap (nums[begin], nums[ge]); return ge; } void quickSort (vector<int >& nums, int begin, int end) if (begin <= end) { int pivotIndex = partition (nums, begin, end); quickSort (nums, begin, pivotIndex - 1 ); quickSort (nums, pivotIndex + 1 , end); } } vector<int > sortArray (vector<int >& nums) { quickSort (nums, 0 , nums.size () - 1 ); return nums; } };
位运算 题干 描述
输入一个整数 n ，输出该数32位二进制表示中1的个数。其中负数用补码表示。
数据范围：−231<=n<=231−1−231<=n <=231−1
即范围为:−2147483648<=n<=2147483647−2147483648<=n <=2147483647
示例1
输入：
返回值：
说明：
十进制中10的32位二进制表示为0000 0000 0000 0000 0000 0000 0000 1010，其中有两个1。
示例2
输入：
返回值：
说明：
负数使用补码表示 ，-1的32位二进制表示为1111 1111 1111 1111 1111 1111 1111 1111，其中32个1
题解 思路
将1进行左移，每次进行与运算，正负数都可以使用
使用n & (n - 1)可以每次消除最低位的1，循环直至n为0，可以统计二进制中所有1的个数
细节
负数右移会出现高位1补位，循环可能无法终止，使用左移或者n & (n - 1)可以避免
代码
左移
class Solution {public : int NumberOf1 (int n) int ans = 0 ; int i = 1 ; int count = 0 ; while (count < 32 ) { if (n & i) ++ans; ++count; i = i << 1 ; } return ans; } };
n & (n - 1)
class Solution {public : int NumberOf1 (int n) int ans = 0 ; while (n != 0 ) { n = n & (n - 1 ); ++ans; } return ans; } };
双指针 题干 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]
示例 2:
提示 :
1 <= nums.length <= 104-231 <= nums[i] <= 231 - 1
进阶： 你能尽量减少完成的操作次数吗？
题解 思路
所有0移动到数组尾部并且基于原数组，换个说法就是将非0元素移动到前面，统计非0元素数目可以得到应该置0的数目
细节
注意count值的更新不要越界
代码
class Solution {public : void moveZeroes (vector<int >& nums) int count = 0 ; for (int & num : nums) { if (num != 0 ) nums[count++] = num; } while (count < nums.size ()) { nums[count++] = 0 ; } } };
题干 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意： 答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。
提示：
3 <= nums.length <= 3000-105 <= nums[i] <= 105
题解 思路
要找三个和为0的数，最笨的办法就是三重循环，如果先进行排序，则可以跳过重复值从而减少循环遍历次数
当最外层循环nums[i]确定下来，nums[j]与nums[k]的和随之确定下来为target = -nums[i]
两层循环可以用双指针更改为一层循环，因为target已经确定，left设置为i + 1，right设置为nums.size() - 1，如果sum = nums[l] + nums[r] == target则找到答案之一，跳过重复元素继续寻找；如果sum > target则需要让sum减小，left向右移只会让sum增大，因此应该把right向左移；如果sum < target则需要让sum增大，left向右移会让sum增大
细节
总而言之，言而总之，首先将数组变成有序的，当最外层循环确定当前元素时，target值就完成了锁定，双指针进行潜在答案的遍历，判断出sum与左右指针移动方向的关联
代码
class Solution {public : vector<vector<int >> threeSum (vector<int >& nums) { sort (nums.begin (), nums.end ()); vector<vector<int >> res; for (int i = 0 ; i < nums.size (); ++i) { if (i > 0 && nums[i] == nums[i - 1 ]) continue ; int l = i + 1 , r = nums.size () - 1 ; int target = -nums[i]; while (l < r) { int sum = nums[l] + nums[r]; if (sum == target) { res.push_back ({nums[i], nums[l], nums[r]}); ++l; --r; while (l < r && nums[l] == nums[l - 1 ]) ++l; while (l < r && nums[r] == nums[r + 1 ]) --r; } else if (sum < target) { ++l; } else { --r; } } } return res; } };
滑动窗口 题干 给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
示例 1:
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
0 <= s.length <= 5 * 104s 由英文字母、数字、符号和空格组成
题解 思路
滑动窗口动态维护最大值，当end右移时需要判断是否此前已有重复字符，因此需要哈希表（可以用数组代替）
如果有重复字符则以start为起始的字符串的无重复字符的最长子串是从start到end - 1，需要更新start判断新的起点是否存在更长子串
细节
本题除了字母外，字符串由数字、符号和空格组成，因此不能用长度大小26的数组，得用128的数组（基本ASCII码128个）
代码
class Solution {public : int lengthOfLongestSubstring (string s) unordered_map<char , bool > hash; int ans = 0 ; int start = 0 , end = 0 ; for (; end < s.size (); ++end) { while (hash[s[end]]) { hash[s[start]] = false ; ++start; } hash[s[end]] = true ; if (end - start + 1 > ans) ans = end - start + 1 ; } return ans; } };
普通数组 题干 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
示例 3：
输入：nums = [5,4,-1,7,8] 输出：23
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 104
进阶： 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
题解 思路
动态规划思路：判断沿用之前的连续数组还是从当前位置重新开始，如果此前的数组和小于0，舍弃并从当前位置开始建立新的；否则将当前位置纳入数组和当中
前缀和：维护当前的最小前缀和，当前位置的前缀和与最小前缀和的差就是以当前位置结尾的最大子数组和，动态更新这个值即可
细节
容易产生的误区：当前位置如果是小于0的，将它加入到连续数组中不是会让值变小吗？
解答：确实会变小，但是答案并不是最终的dp，而是通过ans实时与dp比较进行维护，因为最大值可以出现在中间的任意一段。
代码
动态规划
class Solution {public : int maxSubArray (vector<int >& nums) int dp = 0 ; int ans = -10001 ; for (int & num : nums) { if (dp > 0 ) { dp = dp + num; } else { dp = num; } if (dp > ans) { ans = dp; } } return ans; } };
前缀和
class Solution {public : int maxSubArray (vector<int >& nums) int ans = -10001 ; int sum = 0 ; int minSum = 0 ; for (int & num : nums) { sum += num; ans = max (sum - minSum, ans); if (sum < minSum) { minSum = sum; } } return ans; } };
Ax + By + Cz + Dw = N 的最小字典序解 题干 给定一个方程Ax + By + Cz + Dw = N，输入A，B，C，D，N，其中A，B，C，D，N均为正整数，x，y，z，w的范围是0-2500求字典序最小的x，y，z，w解，无解输出-1。
题解 思路
暴力三重循环 + 整除，$2500^3$会超时，可以将问题分解，求出Cz + Dw的和并且用哈希表存储z和w的值，注意按字典序
两重循环求出N - Ax + By的值，查找哈希表，顺序遍历可以保证找的第一个解是字典序最小的
细节
注意哈希表存储的key是sum，不同的z和w可能对应相同的sum，基于最小字典序的要求，只需存储第一次的value
代码
#include <iostream> #include <unordered_map> #include <vector> using namespace std;void findSolution (int A, int B, int C, int D, int N) unordered_map<int , pair<int , int >> hashMap; for (int z = 0 ; z <= 2500 ; z++) { for (int w = 0 ; w <= 2500 ; w++) { int sum = C * z + D * w; if (sum > N) break ; if (hashMap.count (sum)) continue ; hashMap[sumAB] = {z, w}; } } for (int x = 0 ; x <= 2500 ; x++) { for (int y = 0 ; y <= 2500 ; y++) { int sumCD = A * x + B * y; if (sumCD > N) break ; if (hashMap.count (N - sumCD)) { auto [z, w] = hashMap[N - sumCD]; cout << x << " " << y << " " << z << " " << w << endl; return ; } } } cout << -1 << endl; } int main () int A, B, C, D, N; cin >> A >> B >> C >> D >> N; findSolution (A, B, C, D, N); return 0 ; }
矩阵 题干 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在** 原地 ** 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[[7,4,1],[8,5,2],[9,6,3]]
示例 2：
输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] 输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
题解 思路
问题转换成矩阵左上角进行旋转，每一次交换4个数据的位置，增加一个中间临时变量来完成交换。
问题关键在于左上角的定义，偶数不用赘述；矩阵边长为奇数时，取前n / 2行，前(n + 1) / 2列。以示例1为例，即(1, 2)视作左上角的矩阵。
细节
实现时要思考清楚矩阵中的交换元素，可以结合实例去验证判断。最终是交换matrix [i] [j]和matrix [n - j -1] [i]，接下来把n - j -1代入i，i代入j得到后续的交换下标即可。
代码
void rotate (vector<vector<int >>& matrix) int n = matrix.size (); int row = n / 2 ; int col = (n + 1 ) / 2 ; for (int i = 0 ; i < row; i++) { for (int j = 0 ; j < col; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[n - j -1 ][i]; matrix[n - j - 1 ][i] = matrix[n - i -1 ][n - j - 1 ]; matrix[n - i -1 ][n - j - 1 ] = matrix[j][n - i -1 ]; matrix[j][n - i -1 ]= temp; } } }
题干 给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
示例 1 ：
输入：num = "1432219", k = 3 输出："1219" 解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。
示例 2 ：
输入：num = "10200", k = 1 输出："200" 解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例 3 ：
输入：num = "10", k = 2 输出："0" 解释：从原数字移除所有的数字，剩余为空就是 0 。
提示：
1 <= k <= num.length <= 105num 仅由若干位数字（0 - 9）组成除了 0 本身之外，num 不含任何前导零
题解 思路
数字或者字母排序可以构建单调栈来保持顺序，遍历整个字符串，当遇到字符小于栈顶字符时弹栈直至栈空或大于栈顶字符。移除过程中可能会出现移除的字母数小于k，但字符串已经是从小到大排序的了，此时仅需要取字符串的前num.size() - k位并删除前导0即可。
细节
循环条件是重点，while(k != 0 && !s.empty() && s[s.size()-1] > c)即还有字符没有删除、栈不为空、当前字符小于栈顶字符时执行弹栈。
另外string可以用来当栈使用，pop_back()函数可实现stack.pop()一样的效果
代码
class Solution {public : string removeKdigits (string num, int k) { int n = num.size (); int res = n - k; if (res == 0 ) { return "0" ; } string s = "" ; for (auto c : num) { while (k!=0 && !s.empty () && s[s.size ()-1 ] > c) { s.pop_back (); k--; } s += c; } s = s.substr (0 , res); while (s[0 ] == '0' && s.size ()!=1 ) { s.erase (s.begin ()); } return s; } };
链表 题干 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
示例 2：
示例 3：
提示：
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000
进阶： 链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
题解 思路
维护prev、cur、next三个指针，依次修改指向，顺序是prev、cur、next
cur不为空的情况下next指向cur的nextcur的next指向prev，将prev指向cur将cur指向next
循环1、2、3
细节
循环条件是cur不为空，next不需要预先设置，根据cur的情况设置next
循环跳出时cur为空，prev指向“头节点”
代码
class Solution {public : ListNode* reverseList (ListNode* head) { ListNode* prev = nullptr ; ListNode* cur = head; ListNode* next; while (cur) { next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; } };
题干 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
示例：
输入 ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 输出 [null, null, null, 1, null, -1, null, -1, 3, 4] 解释 LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {1=1} lRUCache.put(2, 2); // 缓存是 {1=1, 2=2} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4
提示：
1 <= capacity <= 30000 <= key <= 100000 <= value <= 105最多调用 2 * 105 次 get 和 put
题解 思路
LRU缓存首先要满足缓存的快速查找（哈希表 ），其次要经常修改、删除、插入（双向链表 ），这些要求让我们应该使用这两种数据结构
梳理功能然后判断应该需要哪些函数 和成员
成员 ：首先缓存本身需要容量和当前大小（int）；接着需要一个哈希表用于查找（unordered_map）哈希表的key就是查找的键，value应该是双向链表中的节点；另外需要维护一个双向链表，用于插入、修改、删除（list，但是通常面试时要自己实现，实现一个节点结构体包含前置和后置节点指针即可）；因为要经常更新节点的位置，移动到头部或者直接从尾部删除，因此创建虚拟head和tail更好，自此全部成员已确定函数 ：缓存没满，在链表首插入即可；缓存满了，链表首插入同时移除尾部。没有查到，返回-1；查到了将节点移动到首部（moveToHead），返回节点的val。因此需要一个添加到头部的函数（addToHead），移动到首部和移除尾部（removeTail）实际上都需要移除操作，但是移动到首部可以转化为移除（remove）+添加到头部实现复用，至此全部函数已确定
细节
移除节点要处理前置和后置两个节点的联系
真正删除节点的只有removeTail，因此需要返回值释放内存
代码
class Node {public : int key; int val; Node* pre; Node* next; Node () { key = 0 ; val = 0 ; pre = nullptr ; next = nullptr ; } Node (int _key, int _val) { key = _key; val = _val; pre = nullptr ; next = nullptr ; } }; class LRUCache {public : unordered_map<int , Node*> cache; int size; int capacity; Node* dummyHead; Node* dummyTail; LRUCache (int _capacity) : capacity (_capacity), size (0 ) { dummyHead = new Node (); dummyTail = new Node (); dummyHead->next = dummyTail; dummyTail->pre = dummyHead; } int get (int key) if (!cache.count (key)) return -1 ; moveToHead (cache[key]); return cache[key]->val; } void put (int key, int value) if (!cache.count (key)) { Node* node = new Node (key, value); addToHead (node); cache[key] = node; ++size; if (size > capacity) { Node* node = removeTail (); cache.erase (node->key); --size; delete node; } } else { cache[key]->val = value; moveToHead (cache[key]); } } void addToHead (Node* node) node->next = dummyHead->next; node->pre = dummyHead; dummyHead->next->pre = node; dummyHead->next = node; } void moveToHead (Node* node) removeNode (node); addToHead (node); } Node* removeTail () { Node* node = dummyTail->pre; removeNode (node); return node; } void removeNode (Node* node) node->pre->next = node->next; node->next->pre = node->pre; } };
二叉树 题干 给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3] 输出：[1,3,2]
示例 2：
示例 3：
题解 思路
递归；迭代需要依托栈，入栈直到为空，出栈并添加到返回向量中
实现
若输出方式是ACM模式，不需要额外创建中间函数，在inorderTraversal函数中调用标准输出流即可；若输出方式是核心代码模式，则需要另外创建一个向量存储返回结果，并创建一个中间函数用于更新结果向量。
代码
递归：
class Solution {public : vector<int > res; void inorder (TreeNode* root) if (root == nullptr ) { return ; } inorderTraversal (root->left); res.push_back (root->val); inorderTraversal (root->right); } vector<int > inorderTraversal (TreeNode* root) { inorder (root); return res; } };
迭代：
迭代的第一个循环条件是当前节点为空或者栈为空则结束循环。
vector<int > inorderTraversal (TreeNode* root) { vector<int > res; stack<TreeNode*> s; if (root == nullptr ) { return res; } TreeNode* cur = root; while (cur!=nullptr || !s.empty ()) { while (cur != nullptr ) { s.push (cur); cur = cur -> left; } cur = s.top (); res.push_back (cur -> val); s.pop (); cur = cur -> right; } return res; }
题干 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
示例 2：
输入：root = [5,1,4,null,null,3,6] 输出：false 解释：根节点的值是 5 ，但是右子节点的值是 4 。
提示：
树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1
题解 思路
二叉搜索树「中序遍历」得到的值构成的序列一定是升序的，因此可以通过判断中序遍历的结果是否升序来判断是不是BST
细节
上下界的递归，基本框架就是return judge(root, (long) INT_MIN - 1, (long) INT_MAX + 1)，这一部分很容易想。难点在于上下界的界定，左子树无下界，只有上界；右子树无下界，只有上届。
代码
中序遍历 判断是否递增
class Solution {public : long prev = (long ) INT_MIN - 1 ; bool ans = true ; void inorder (TreeNode* root) if (root == NULL ) return ; inorder (root->left); if (root->val <= prev) { ans = false ; return ; } else prev = root->val; inorder (root->right); } bool isValidBST (TreeNode* root) inorder (root); return ans; } };
[!Note]
INT_MIN 是CPP中的最小整数值-2147483648的宏，也可以用1<<31表示，但是要做减法运算需要转换为long 类型
上下界 递归
class Solution {public : bool judge (TreeNode* root, long low, long high) if (root == NULL ) return true ; if (root->val <= low || root->val >= high) return false ; return judge (root->left, low, root->val) && judge (root->right, root->val, high); } bool isValidBST (TreeNode* root) return judge (root, (long ) INT_MIN - 1 , (long ) INT_MAX + 1 ); } };
题干 给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3] 输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3] 输出：false
提示：
树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100
进阶： 你可以运用递归和迭代两种方法解决这个问题吗？
题解 思路
对称需要保证左子节点和右子节点同时为空，若不同时为空则两个都不能为空，并且值需要相等，此外左子节点的左子树与右子节点的右子树应该相同 ，左子节点的右子树与右子节点的左子树应该相同
递归的返回条件是判断传入节点值是否相等（包括同时为空），通过传入的参数来控制左子树和右子树的选择
细节
多看几遍，记住不要中序回文
代码
递归判断左子节点的左子树与右子节点的右子树是否相同 ，左子节点的右子树与右子节点的左子树是否相同
class Solution {public : bool check (TreeNode* l, TreeNode* r) if (!l && !r) return true ; if (!l || !r) return false ; return l->val == r->val && check (l->left, r->right) && check (l->right, r->left); } bool isSymmetric (TreeNode* root) return check (root->left, root->right); } };
题干 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。
示例 1：
输入：root = [3,1,4,null,2], k = 1 输出：1
示例 2：
输入：root = [5,3,6,2,4,null,null,1], k = 3 输出：3
提示：
树中的节点数为 n 。
1 <= k <= n <= 1040 <= Node.val <= 104
题解 思路
BST的中序遍历是递增的，符合题目要求
细节
用数组存储中序遍历结果即可，看清楚k的定义，这里选取array[k-1]
代码
class Solution {public : vector<int > array; void inorder (TreeNode* root) if (root == NULL ) return ; inorder (root->left); array.emplace_back (root->val); inorder (root->right); } int kthSmallest (TreeNode* root, int k) inorder (root); return array[k-1 ]; } };
题干 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1：
输入： root = [1,2,3,null,5,null,4]
输出： [1,3,4]
解释：
示例 2：
输入： root = [1,2,3,4,null,null,null,5]
输出： [1,3,4,5]
解释：
示例 3：
输入： root = [1,null,3]
输出： [1,3]
示例 4：
输入： root = []
输出： []
提示:
二叉树的节点个数的范围是 [0,100]
-100 <= Node.val <= 100
题解 思路
参照题目意思，右视图的定义应该使用层序遍历 去解决，每一层节点直接有优先级，优先级关系为：右右>右左>左右>左左
细节
层序遍历使用队列 实现，内循环条件基于队列的大小，本题中队列末尾对应最右侧的节点
代码
class Solution {public : vector<int > rightSideView (TreeNode* root) { vector<int > ans; if (root != NULL ) { queue<TreeNode*> q; q.push (root); TreeNode* cur = 0 ; int len = 0 ; while (!q.empty ()) { len = q.size (); cur = q.back (); ans.emplace_back (cur->val); for (int i = 0 ; i < len; ++i) { cur = q.front (); q.pop (); if (cur->left) q.push (cur->left); if (cur->right) q.push (cur->right); } } } return ans; } };
题干 给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历
示例 1：
输入：root = [1,2,5,3,4,null,6] 输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：
示例 3：
提示：
树中结点数在范围 [0, 2000] 内
-100 <= Node.val <= 100
题解 思路
不考虑空间限制的情况下，按照先序遍历 的方式将节点指针用数组存储，再迭代数组替换为右节点并清空左节点即可
细节
先序遍历时根节点也会被加入到vec中，进行展开链表的构建时需要跳过它
代码
class Solution {public : vector<TreeNode*> vec; void flattenHelper (TreeNode* root) if (root == NULL ) return ; vec.emplace_back (root); flattenHelper (root->left); flattenHelper (root->right); } void flatten (TreeNode* root) flattenHelper (root); TreeNode* cur = root; for (int i=1 ; i<vec.size (); ++i) { cur->left = NULL ; cur->right = vec[i]; cur = cur->right; } } };
题干 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历 ， inorder 是同一棵树的中序遍历 ，请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1] 输出: [-1]
提示:
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorder 和 inorder 均 无重复 元素inorder 均出现在 preorderpreorder 保证 为二叉树的前序遍历序列inorder 保证 为二叉树的中序遍历序列
题解 思路
思路1是通过递归拆分成左子树和右子树的构建，进而转化为preorder和inorder子数组的划分，缺点是cpp实现不方便
思路2不划分子数组，而是通过明确子数组的边界来代替切分，缺点是参数多，容易混淆
细节
python数组切片冒号前面的包括，后面的不包括；另外需要判断preorder和inorder是否为空，若为空则表示无法构建子树，返回None
cpp实现可以建立一个哈希表，便于查找根节点在inorder数组中的下标；左子树的size可以根据inorder根节点的下标与inorder左边界进行计算
代码
子数组/数组切片递归，python子数组实现更方便
class Solution (object ): def buildTreeHelper (self, preorder, inorder ): if not preorder or not inorder: return None root = TreeNode(preorder[0 ]) left = 0 while left < len (inorder): if inorder[left] == preorder[0 ]: break left = left + 1 right = len (inorder) - 1 - left root.left = self.buildTreeHelper(preorder[1 :left+1 ], inorder[0 :left]) root.right = self.buildTreeHelper(preorder[left+1 :], inorder[left+1 :]) return root def buildTree (self, preorder, inorder ): """ :type preorder: List[int] :type inorder: List[int] :rtype: Optional[TreeNode] """ return self.buildTreeHelper(preorder, inorder)
cpp解法，通过明确先序数组和中序数组的边界来代替数组切片
class Solution {public : unordered_map<int , int > index; TreeNode* buildTreeHelper (vector<int >& preorder, vector<int >& inorder, int preLeft, int preRight, int inLeft, int inRight) if (inRight < inLeft) return NULL ; TreeNode* root = new TreeNode (preorder[preLeft]); int rootIndex = index[preorder[preLeft]]; int leftSize = rootIndex - inLeft; root->left = buildTreeHelper (preorder, inorder, preLeft + 1 , preLeft + leftSize, inLeft, rootIndex - 1 ); root->right = buildTreeHelper (preorder, inorder, preLeft + 1 + leftSize, preRight, rootIndex + 1 , inRight); return root; } TreeNode* buildTree (vector<int >& preorder, vector<int >& inorder) { for (int i = 0 ; i < inorder.size (); ++i) { index[inorder[i]] = i; } return buildTreeHelper (preorder, inorder, 0 , preorder.size () - 1 , 0 , inorder.size () - 1 ); } };
题干 给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
示例 1：
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 输出：3 解释：和等于 8 的路径有 3 条，如图所示。
示例 2：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：3
提示:
二叉树的节点个数的范围是 [0,1000]
-109 <= Node.val <= 109 -1000 <= targetSum <= 1000
题解 思路
根据题目意思容易想到搜索每一条路径，统计和为targetsum的路径。使用递归的思想先构建辅助函数，求出以指定节点作为根节点时，经过该根节点同时节点值和为targetsum的路径数目，再双重递归将每一个节点作为根节点并求和
细节
双重递归很容易混淆，需要理清思路和结构；
pathSumHelper函数中的targetSum参数要使用long类型，因为root->val的范围是-10^9 <= Node.val <= 10^9 ，超过了int的范围
代码
class Solution {public : int pathSumHelper (TreeNode* root, long targetSum) if (root == NULL ) return 0 ; if (root->val == targetSum) { return pathSumHelper (root->left, targetSum - root->val) + pathSumHelper (root->right, targetSum - root->val) + 1 ; } else { return pathSumHelper (root->left, targetSum - root->val) + pathSumHelper (root->right, targetSum - root->val); } } int pathSum (TreeNode* root, int targetSum) if (root == NULL ) return 0 ; int ans = pathSumHelper (root, targetSum); ans += pathSum (root->left, targetSum); ans += pathSum (root->right, targetSum); return ans; } };
题干 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科 中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先 ）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2 输出：1
提示：
树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109所有 Node.val 互不相同 。
p != qp 和 q 均存在于给定的二叉树中。
题解 思路
两个节点分别位于左右子树时，说明当前节点是最近祖先；递归的终止条件：如果当前节点为空或者为p 或 q，则返回当前节点，如果只有一方为空则说明两个节点都位于这个子树，返回它的递归结果即可。
[!Note]
根据递归终止条件，实际上结果是自底向上的，因此满足深度尽可能大 这一要求
细节
比较特别的递归终止条件，需要结合理解去记忆
代码
class Solution {public : TreeNode* lowestCommonAncestor (TreeNode* root, TreeNode* p, TreeNode* q) { if (root == NULL || root == p || root == q) return root; TreeNode* left = lowestCommonAncestor (root->left, p, q); TreeNode* right = lowestCommonAncestor (root->right, p, q); if (left && right) return root; return left? left:right; } };
题干 二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1：
输入：root = [1,2,3] 输出：6 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：
输入：root = [-10,9,20,null,null,15,7] 输出：42 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
提示：
树中节点数目范围是 [1, 3 * 104]
-1000 <= Node.val <= 1000
题解 思路
递归搜索，计算经过每个节点的路径，若当前路径大于最长路径则更新最长路径
细节
辅助函数的返回值并不是经过当前节点的左路+右路+val，而应该是左路和右路的最大值+val，这样才符合更新答案的部分需要的返回值，以最后一个示例为例，路径经过节点20向下搜索时不可能既走左边又走右边，应当择最大值；考虑到递归的返回是自底向上的，因此当前的左子值和右子值都是最优解。
代码
class Solution {public : int ans = -1001 ; int dfs (TreeNode* root) if (root == NULL ) return 0 ; int left = dfs (root->left); left = max (0 , left); int right = dfs (root->right); right = max (0 , right); int val = root->val + max (left, right); if (root->val + left + right > ans) ans = root->val + left + right; return val; } int maxPathSum (TreeNode* root) dfs (root); return ans; } };
图论 题干 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] 输出：1
示例 2：
输入：grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] 输出：3
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j] 的值为 '0' 或 '1'
题解 思路
参考了题解“岛屿类问题的通用解法、DFS 遍历框架”
将树中搜索从对左右子节点递归搜索改成对矩阵周围元素的搜索
细节
边界判断方面可以基于函数实现，代码会更优雅清晰一些，边界检查的上限要通常是≥时不符合
代码
class Solution {public : bool inArea (int row, int col, int i, int j) if (i < 0 || i >= row || j < 0 || j >= col) return false ; return true ; } void update (vector<vector<char >>& grid, int i, int j) if (inArea (grid.size (), grid[0 ].size (), i, j)) { if (grid[i][j] == '1' ) { grid[i][j] = '2' ; update (grid, i - 1 , j); update (grid, i + 1 , j); update (grid, i, j - 1 ); update (grid, i, j + 1 ); } } } int numIslands (vector<vector<char >>& grid) int ans = 0 ; for (int i = 0 ; i < grid.size (); ++i) { for (int j = 0 ; j < grid[0 ].size (); ++j) { if (grid[i][j] == '1' ) { update (grid, i, j); ++ans; } } } return ans; } };
题干 在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
示例 1：
输入：grid = [[2,1,1],[1,1,0],[0,1,1]] 输出：4
示例 2：
输入：grid = [[2,1,1],[0,1,1],[1,0,1]] 输出：-1 解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。
示例 3：
输入：grid = [[0,2]] 输出：0 解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 10grid[i][j] 仅为 0、1 或 2
题解 思路
首先需要统计新鲜橘子数目，并且不断更新，才能判断最后是否全部腐烂
其次需要BFS/层序，贴合题目中的一轮一轮的模拟
最后在层序遍历的同时更新矩阵，避免重复感染好橘子
细节
因为橘子向上下左右四个方向感染，因此可以创建一个辅助数组来便于感染部分代码实现
层序遍历的模板一般是外循环判断队列是否为空，内循环根据队列当前大小（动态变化因此需要一个变量存储当前大小）决定循环次数
可能会出现的问题：1. 只有坏橘子，没有好橘子； 2. 最后一次内循环，已经全是坏橘子了，并没有传染给其他橘子
在while循环中添加一个fresh辅助判断，可以有效解决两个问题
不改变外循环条件，则在循环前进行fresh数目判断，可解决问题1；增加一个布尔变量记录是否发生感染放在内循环，用于更新ans
代码
自己写的，不是很优雅，效率也低了点
class Solution {public : bool inGrid (int row, int col, int i, int j) if (i < 0 || i >= row || j < 0 || j >= col) return false ; return true ; } int orangesRotting (vector<vector<int >>& grid) vector<vector<int >> dirs = {{-1 , 0 }, {1 , 0 }, {0 , -1 }, {0 , 1 }}; queue<pair<int , int >> q; int fresh = 0 ; for (int i = 0 ; i < grid.size (); ++i) { for (int j = 0 ; j < grid[0 ].size (); ++j) { if (grid[i][j] == 1 ) ++fresh; else if (grid[i][j] == 2 ) q.push ({i, j}); } } int size = 0 ; int ans = 0 ; while (fresh && !q.empty ()) { ++ans; size = q.size (); for (int i = 0 ; i < size; ++i) { auto cur = q.front (); for (auto dir : dirs) { if (inGrid (grid.size (), grid[0 ].size (), cur.first + dir[0 ], cur.second + dir[1 ]) && grid[cur.first + dir[0 ]][cur.second + dir[1 ]] == 1 ) { grid[cur.first + dir[0 ]][cur.second + dir[1 ]] = 2 ; q.push ({cur.first + dir[0 ], cur.second + dir[1 ]}); --fresh; } } q.pop (); } } if (fresh) return -1 ; return ans; } };
请gpt优化过的，思路没换
class Solution {public : bool inGrid (int rows, int cols, int i, int j) return i >= 0 && i < rows && j >= 0 && j < cols; } int orangesRotting (vector<vector<int >>& grid) const vector<pair<int , int >> directions = {{-1 , 0 }, {1 , 0 }, {0 , -1 }, {0 , 1 }}; queue<pair<int , int >> q; int fresh = 0 ; for (int i = 0 ; i < grid.size (); ++i) { for (int j = 0 ; j < grid[0 ].size (); ++j) { if (grid[i][j] == 1 ) { ++fresh; } else if (grid[i][j] == 2 ) { q.emplace (i, j); } } } if (fresh == 0 ) return 0 ; int minutes = 0 ; while (!q.empty ()) { int size = q.size (); bool hasRotten = false ; for (int k = 0 ; k < size; ++k) { auto [x, y] = q.front (); q.pop (); for (const auto & [dx, dy] : directions) { int nx = x + dx, ny = y + dy; if (inGrid (grid.size (), grid[0 ].size (), nx, ny) && grid[nx][ny] == 1 ) { grid[nx][ny] = 2 ; q.emplace (nx, ny); --fresh; hasRotten = true ; } } } if (hasRotten) ++minutes; } return fresh == 0 ? minutes : -1 ; } };
题干 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]] 输出：true 解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]] 输出：false 解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
提示：
1 <= numCourses <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi < numCoursesprerequisites[i] 中的所有课程对 互不相同
题解 思路
先后关系/依赖关系 转换为有向图，若能构成包含所有节点的有向无环图 则能完成所有课程。将有向无环图转化为线性排序即为拓扑排序 。
有向图有入度 /出度的概念，通过队列保存当前入度为0的节点，然后按照bfs的思想搜索并不断更新完成课程的数目，直至队列为空。
细节
通过哈希表存储从当前节点出发的边，可以快速对依赖关系做更新
代码
class Solution {public : bool canFinish (int numCourses, vector<vector<int >>& prerequisites) vector<int > count (numCourses) ; unordered_map<int , vector<int >> mp; for (auto & item : prerequisites) { ++count[item[0 ]]; mp[item[1 ]].emplace_back (item[0 ]); } queue<int > q; for (int i=0 ; i<numCourses; ++i) { if (count[i] == 0 ) q.emplace (i); } int cur; int unfinish = numCourses; while (!q.empty ()) { cur = q.front (); q.pop (); --unfinish; for (auto & item : mp[cur]) { if (count[item] > 0 ) --count[item]; if (count[item] == 0 ) q.emplace (item); } } if (unfinish) return false ; return true ; } };
题干 **Trie **（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
请你实现 Trie 类：
Trie() 初始化前缀树对象。void insert(String word) 向前缀树中插入字符串 word 。boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
示例：
输入 ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]] 输出 [null, null, true, false, true, null, true] 解释 Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // 返回 True trie.search("app"); // 返回 False trie.startsWith("app"); // 返回 True trie.insert("app"); trie.search("app"); // 返回 True
提示：
1 <= word.length, prefix.length <= 2000word 和 prefix 仅由小写英文字母组成insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次
题解 思路
用集合或者哈希表，查找效率高，查找前缀效率低
使用字典树，26叉树列举出现过的字符，查找即搜索
细节
cpp初始化成员变量的方式：Trie() : children(26), isEnd(false) {}
迭代搜索时使用临时变量node进行，初始化为Trie* node = this;，迭代node = node->children[c];
代码
自己写的，效率略低
class Trie {public : set<string> s; Trie () {} void insert (string word) s.insert (word); } bool search (string word) if (s.count (word)) return true ; return false ; } bool startsWith (string prefix) if (s.empty ()) return false ; for (auto &str : s) { bool ans = true ; for (int i=0 ; i<prefix.size (); ++i) { if (str[i] != prefix[i]) { ans = false ; break ; } } if (ans) return true ; } return false ; } };
26叉树/字典树
class Trie {public : vector<Trie*> children; bool isEnd; Trie* searchPrefix (string prefix) { Trie* node = this ; for (char c : prefix) { c -= 'a' ; if (node->children[c] == NULL ) { return NULL ; } node = node->children[c]; } return node; } Trie () : children (26 ), isEnd (false ) {} void insert (string word) Trie* node = this ; for (char c : word) { c -= 'a' ; if (node->children[c] == NULL ) { node->children[c] = new Trie (); } node = node->children[c]; } node->isEnd = true ; } bool search (string word) Trie* node = searchPrefix (word); if (node && node->isEnd) return true ; return false ; } bool startsWith (string prefix) return searchPrefix (prefix) == NULL ? false : true ; } };
回溯 题干 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1] 输出：[[0,1],[1,0]]
示例 3：
提示：
1 <= nums.length <= 6-10 <= nums[i] <= 10nums 中的所有整数 互不相同
题解 思路
回溯与深度优先搜索雷同，递归思路相似；
通过循环遍历的方式依次固定位置，从0开始到nums.size()-1例如[1, 2, 3]的全排列可以转化为1+[2, 3]、2+[1, 3]、3+[1, 2]的全排列，依次类推
细节
递归终止条件即固定到最后一位，无需遍历，此时将当前nums添加到结果集中
代码
解法一：nums作为参数不传递引用，易理解、代码简单
class Solution {public : vector<vector<int >> permute (vector<int >& nums) { dfs (nums, 0 ); return res; } private : vector<vector<int >> res; void dfs (vector<int > nums, int x) if (x == nums.size () - 1 ) { res.push_back (nums); return ; } for (int i = x; i < nums.size (); i++) { swap (nums[i], nums[x]); dfs (nums, x + 1 ); } } };
解法二：nums的引用传参，nums在递归返回后会与递归前不一致，从而影响结果，因此需要撤销交换
class Solution {public : vector<vector<int >> permute (vector<int >& nums) { dfs (nums, 0 ); return res; } private : vector<vector<int >> res; void dfs (vector<int >& nums, int x) if (x == nums.size () - 1 ) { res.push_back (nums); return ; } for (int i = x; i < nums.size (); i++) { swap (nums[i], nums[x]); dfs (nums, x + 1 ); swap (nums[i], nums[x]); } } };
题干 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的
子集
（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10nums 中的所有元素 互不相同
题解 思路
子集数目是2^n，可以使用二进制来考虑每一个元素是否加入当前集合，作为子集之一
对于cur位置，我们需要考虑a[cur]取或者不取，如果取，我们需要把a[cur]放入一个临时的答案数组中，再执行 dfs(cur+1,n)，执行结束后需要对临时数组进行回溯；如果不取，则直接执行 dfs(cur+1,n)。在整个递归调用的过程中，cur 是从小到大递增的，当cur 增加到n的时候，记录答案并终止递归。
细节
第一层循环是0到2^n-1，第二层循环是0到size，使用当前掩码mask和1 << i做&运算
递归终止条件是cur == nums.size()，表示所有位置都已经确定
代码
使用二进制掩码来判断是否添加到当前集合作为子集
class Solution {public : vector<vector<int >> subsets (vector<int >& nums) { int n = nums.size (); vector<vector<int >> ans; vector<int > temp; for (int mask = 0 ; mask < 1 << n; ++mask) { temp.clear (); for (int i = 0 ; i < n; ++i) { if (mask & 1 << i) { temp.emplace_back (nums[i]); } } ans.emplace_back (temp); } return ans; } };
回溯，添加当前元素，递归考虑cur+1之后的情况；回溯撤回添加，递归考虑cur+1之后的情况
class Solution {public : vector<int > t; vector<vector<int >> ans; void dfs (int cur, vector<int >& nums) if (cur == nums.size ()) { ans.push_back (t); return ; } t.push_back (nums[cur]); dfs (cur + 1 , nums); t.pop_back (); dfs (cur + 1 , nums); } vector<vector<int >> subsets (vector<int >& nums) { dfs (0 , nums); return ans; } };
题干 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
示例 3：
输入：digits = "2" 输出：["a","b","c"]
提示：
0 <= digits.length <= 4digits[i] 是范围 ['2', '9'] 的一个数字。
题解 思路
每个位置选择对应的每个字母，排列组合；
递归返回条件是当cur == digits.size()，说明每一位都已经确定了；
使用哈希表做映射，能够快速遍历每个数字对应的字母列表。
细节
digits作为参数传递时使用引用，减小开销；string没有emplace_back()，但是有pop_back()；成员变量mp的初始化通过函数进行。
代码
class Solution {public : vector<string> ans; string s; unordered_map<char , string> mp; void dfs (int cur, string& digits) if (cur == digits.size ()) { ans.emplace_back (s); return ; } for (int i = 0 ; i < mp[digits[cur]].size (); ++i) { s += mp[digits[cur]][i]; dfs (cur + 1 , digits); s.pop_back (); } } vector<string> letterCombinations (string digits) { mp['2' ] = "abc" ; mp['3' ] = "def" ; mp['4' ] = "ghi" ; mp['5' ] = "jkl" ; mp['6' ] = "mno" ; mp['7' ] = "pqrs" ; mp['8' ] = "tuv" ; mp['9' ] = "wxyz" ; if (!digits.empty ()) dfs (0 , digits); return ans; } };
题干 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]] 解释： 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选， 7 = 7 。 仅有这两种组合。
示例 2：
输入: candidates = [2,3,5], target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1 输出: []
提示：
1 <= candidates.length <= 302 <= candidates[i] <= 40candidates 的所有元素 互不相同 1 <= target <= 40
题解 思路
看到可选重复的我以为确认每一位的方法不可行了，实际上依旧可以套用这个模板，只需要在此基础上更改递归的选择思路，选择当前元素后可以再选当前元素，递归修改为dfs(cur)，回溯后跳过该元素进行下一个位置的确定dfs(cur+1)。这样可以保障每个元素都可以出现n次。
细节
递归终止条件除了cur == candidates.size()表示所有位置都已经确定了，还要增加target == 0，并且在此时将t添加到ans中
target - candidates[cur] >= 0 表示还能继续容纳，target == 0作为终止条件比candidates[cur] == target更符合逻辑
代码
class Solution {public : vector<vector<int >> ans; vector<int > t; void dfs (int cur, vector<int >& candidates, int target) if (cur == candidates.size ()) return ; if (target == 0 ) { ans.emplace_back (t); return ; } if (target - candidates[cur] >= 0 ) { t.emplace_back (candidates[cur]); dfs (cur, candidates, target - candidates[cur]); t.pop_back (); } dfs (cur + 1 , candidates, target); } vector<vector<int >> combinationSum (vector<int >& candidates, int target) { dfs (0 , candidates, target); return ans; } };
题干 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
提示：
题解 思路
因为要求是有效括号 组合，因此在元素选择时要先选左括号，再选右括号；
左右括号的选择条件不同，open的上限是n，而close的上限是open
细节
基于添加右括号的条件close < open，达到递归终止条件时的t一定是有效括号组合
代码
class Solution {public : void backTrace (vector<string>& ans, string& t, int open, int close, int n) if (t.size () == 2 * n) { ans.emplace_back (t); return ; } if (open < n) { t += '(' ; backTrace (ans, t, open + 1 , close, n); t.pop_back (); } if (close < open) { t += ')' ; backTrace (ans, t, open, close + 1 , n); t.pop_back (); } } vector<string> generateParenthesis (int n) { vector<string> ans; string t; backTrace (ans, t, 0 , 0 , n); return ans; } };
题干 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 输出：true
示例 2：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" 输出：true
示例 3：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" 输出：false
提示：
m == board.lengthn = board[i].length1 <= m, n <= 61 <= word.length <= 15board 和 word 仅由大小写英文字母组成
题解 思路
查找字符串，从起点开始向上下左右四个方向进行搜索，同时每个点都应作为起点进行搜索；
搜索中，访问过的应当标记避免二次访问，搜索结束后还原；
细节
终止条件包括ans已经为true，cur == word.size()即搜索完成，以及超出边界或者字符不匹配；
代码
class Solution {public : void dfs (int i, int j, int cur, vector<vector<char >>& board, string& word, bool & ans) if (ans) return ; if (cur == word.size ()) { ans = true ; return ; } if (i < 0 || i >= board.size () || j < 0 || j >= board[0 ].size () || board[i][j] != word[cur]) { return ; } char temp = board[i][j]; board[i][j] = '#' ; dfs (i + 1 , j, cur + 1 , board, word, ans); dfs (i - 1 , j, cur + 1 , board, word, ans); dfs (i, j + 1 , cur + 1 , board, word, ans); dfs (i, j - 1 , cur + 1 , board, word, ans); board[i][j] = temp; } bool exist (vector<vector<char >>& board, string word) bool ans = false ; int rows = board.size (), cols = board[0 ].size (); for (int i = 0 ; i < rows; i++) { for (int j = 0 ; j < cols; j++) { if (board[i][j] == word[0 ]) { dfs (i, j, 0 , board, word, ans); if (ans) return true ; } } } return false ; } };
二分查找 两种情况的二分查找区分 精确查找目标值和查找边界或插入位置
条件 l <= rl < r
搜索区间 闭区间 [l, r]
左闭右开区间 [l, r)
循环结束条件 l = r + 1l = r
适用场景 精确查找目标值
查找边界或插入位置
mid 计算mid = l + (r - l) / 2mid = l + (r - l) / 2
边界更新 l = mid + 1 和 r = mid - 1l = mid + 1 和 r = mid
返回值的选择
l 和 r 的关系
如果循环条件是 l <= r，循环结束时 l = r + 1。
如果循环条件是 l < r，循环结束时 l = r。
返回值的确定 ：
如果需要返回最后一个满足条件的值 ，通常返回 r。
如果需要返回第一个满足条件的值 ，通常返回 l。
具体返回值需要根据问题的语义和二分查找的实现逻辑来确定。
题干 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5 输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2 输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7 输出: 4
提示:
1 <= nums.length <= 104-104 <= nums[i] <= 104nums 为 无重复元素 的 升序 排列数组-104 <= target <= 104
题解 思路
对于有序数组中的查找，不断迭代更新上限和下限直至查找完成或不再满足循环条件l <= r
细节
循环条件是l <= r
代码
二分查找模板
class Solution {public : int searchInsert (vector<int >& nums, int target) int l = 0 , r = nums.size () - 1 ; int cur; while (l <= r) { cur = l + (r - l) / 2 ; if (nums[cur] == target) { return cur; } else if (nums[cur] > target) { r = cur - 1 ; } else { l = cur + 1 ; } } return l; } };
递归做太多，下意识用递归写了一份
class Solution {public : int div (int l, int r, vector<int >& nums, int target) if (l > r) return l; if (nums[l + (r - l) / 2 ] == target) { return l + (r - l) / 2 ; } else if (nums[l + (r - l) / 2 ] > target) { return div (l, l + (r - l) / 2 - 1 , nums, target); } else { return div (l + (r - l) / 2 + 1 , r, nums, target); } } int searchInsert (vector<int >& nums, int target) return div (0 , nums.size () - 1 , nums, target); } };
题干 给你一个满足下述两条属性的 m x n 整数矩阵：
每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出：true
示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 输出：false
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-104 <= matrix[i][j], target <= 104
题解 思路
将一维有序数组更换为二维有序矩阵，只需要找到下标之间的对应关系即可转换为一维有序数组的查找
细节
无
代码
class Solution {public : bool searchMatrix (vector<vector<int >>& matrix, int target) int l = 0 , r = matrix.size () * matrix[0 ].size () - 1 ; int i, j; while (l <= r) { i = l + (r - l) / 2 / matrix[0 ].size (); j = l + (r - l) / 2 % matrix[0 ].size (); if (matrix[i][j] == target) return true ; else if (matrix[i][j] > target) { r = l + (r - l) / 2 - 1 ; } else { l = l + (r - l) / 2 + 1 ; } } return false ; } };
题干 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1]
示例 3：
输入：nums = [], target = 0 输出：[-1,-1]
提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109nums 是一个非递减数组-109 <= target <= 109
题解 思路
在找到target数值时更新答案边界，并且设置为二分的新边界
细节
循环中不需要break跳出，因为找到target后需要设置新的边界并进行下一步迭代
代码
logn复杂度的解法，两次二分找到左边界和右边界
class Solution {public : vector<int > searchRange (vector<int >& nums, int target) { int l = 0 , r = nums.size () - 1 ; int first = -1 , last = -1 ; int mid; while (l <= r) { mid = l + (r - l) / 2 ; if (nums[mid] > target) { r = mid - 1 ; } else if (nums[mid] < target) { l = mid + 1 ; } else { first = mid; r = mid - 1 ; } } l = 0 ; r = nums.size () - 1 ; while (l <= r) { mid = l + (r - l) / 2 ; if (nums[mid] > target) { r = mid - 1 ; } else if (nums[mid] < target) { l = mid + 1 ; } else { last = mid; l = mid + 1 ; } } vector<int > ans; ans.emplace_back (first); ans.emplace_back (last); return ans; } };
非logn复杂度的解法，找到target之后向两侧拓展，测试用例没设置好估计，时长超过100%了…
class Solution {public : vector<int > searchRange (vector<int >& nums, int target) { int l = 0 , r = nums.size () - 1 ; bool flag = false ; while (l <= r) { if (nums[l + (r - l) / 2 ] == target) { l = l + (r - l) / 2 ; flag = true ; break ; } else if (nums[l + (r - l) / 2 ] > target) { r = l + (r - l) / 2 - 1 ; } else { l = l + (r - l) / 2 + 1 ; } } if (flag) { vector<int > ans; int left = l; while (left > 0 && nums[left - 1 ] == target) { --left; } ans.emplace_back (left); int right = l; while (right < nums.size () - 1 && nums[right + 1 ] == target) { ++right; } ans.emplace_back (right); return ans; } else { vector<int > ans = {-1 , -1 }; return ans; } } };
题干 整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3 输出：-1
示例 3：
输入：nums = [1], target = 0 输出：-1
提示：
1 <= nums.length <= 5000-104 <= nums[i] <= 104nums 中的每个值都 独一无二 题目数据保证 nums 在预先未知的某个下标上进行了旋转
-104 <= target <= 104
题解 思路
数组局部有序，将数组分成两段意味着一定有一段是有序的，若target在有序数组中则二分查找；若不在则继续缩小范围
细节
nums数量为0和1时可以单独考虑
判断数组是否有序时条件一使用nums[mid] >= nums[l]而不是nums[mid] > nums[l]，当数组大小为2时，可能会出现mid == l的情况，前半部分已经有序（只有一个数），但是没有被考虑进去。
代码
class Solution {public : int search (vector<int >& nums, int target) int n = nums.size (); if (!n) return -1 ; if (n == 1 ) return n == target ? 0 : -1 ; int l = 0 , r = n - 1 ; int mid; while (l <= r) { mid = l + (r - l) / 2 ; if (nums[mid] == target) return mid; if (nums[mid] >= nums[l]) { if (nums[l] <= target && target < nums[mid]) { r = mid - 1 ; } else { l = mid + 1 ; } } else { if (nums[mid] < target && target <= nums[r]) { l = mid + 1 ; } else { r = mid - 1 ; } } } return -1 ; } };
题干 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [3,4,5,1,2] 输出：1 解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
输入：nums = [4,5,6,7,0,1,2] 输出：0 解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
示例 3：
输入：nums = [11,13,15,17] 输出：11 解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
提示：
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums 中的所有整数 互不相同 nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
题解 思路
旋转数组若进行奇数次旋转则数组被分为两段，后半段的最大值小于前半段的最小值；
当中间值比当前min小时，说明中间值与当前min一定不在同一段，查找后半段即可；
当中间值大于min时，只需要搜索mid+1之后的序列即可；
细节
使用min = nums[mid];来更新答案，这样更新右边界时就应该是r = mid - 1;
代码
class Solution {public : int findMin (vector<int >& nums) int l = 0 , r = nums.size () - 1 ; int min = nums[0 ]; int mid; while (l <= r) { mid = l + (r - l) / 2 ; if (nums[mid] < min) { min = nums[mid]; r = mid - 1 ; } else { l = mid + 1 ; } } return min; } };
栈 题干 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的
字典序
最小 （要求不能打乱其他字符的相对位置）。
示例 1：
示例 2：
输入：s = "cbacdcbc" 输出："acdb"
提示：
1 <= s.length <= 104s 由小写英文字母组成
题解 思路
316与402是同一种题型，循环条件中删除k个数字变成对于栈顶字符剩余数目的考量，需要先建立一个map来映射各个字母的出现次数
细节
循环条件变为while (!res.empty() && i < res[res.size() - 1] && m[res[res.size() - 1]] > 0)，即栈不为空、栈顶字符剩余数目大于0、当前字符小于栈顶字符
代码
class Solution {public : string removeDuplicateLetters (string s) { map<char , int > m; for (auto c : s) { if (m.count (c)) { m[c] += 1 ; } else { m[c] = 1 ; } } string res = "" ; for (auto i : s) { if (res.find (i) == -1 ) { while (!res.empty () && i < res[res.size () - 1 ] && m[res[res.size () - 1 ]] > 0 ) { res.pop_back (); } res += i; } m[i] -= 1 ; } return res; } };
题干 给你两个整数数组 nums1 和 nums2，它们的长度分别为 m 和 n。数组 nums1 和 nums2 分别代表两个数各位上的数字。同时你也会得到一个整数 k。
请你利用这两个数组中的数字中创建一个长度为 k <= m + n 的最大数，在这个必须保留来自同一数组的数字的相对顺序。
返回代表答案的长度为 k 的数组。
示例 1：
输入：nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5 输出：[9,8,6,5,3]
示例 2：
输入：nums1 = [6,7], nums2 = [6,0,4], k = 5 输出：[6,7,6,0,4]
示例 3：
输入：nums1 = [3,9], nums2 = [8,9], k = 3 输出：[9,8,9]
提示：
m == nums1.lengthn == nums2.length1 <= m, n <= 5000 <= nums1[i], nums2[i] <= 91 <= k <= m + n
题解 思路
在完成了402与316后，这道题的思路很清晰，将问题转化为两个“移掉k位数字”，即在nums1中保留i位数字，nums2中保留k-i位数字（与移除类似），并且保障两个数组分别最大顺序，再通过归并算法的合并部分进行整合得到最终结果。看了其他人的题解，感觉Python的归并比Cpp简单好多，Cpp我努力过了还是写错了
细节
实现一个maxNumber函数针对单个数组排序，实现一个merge函数将两个数组进行相对位置不改变的最大排序。
merge的实现过程中当两个数组当前字符相等时，需要判断两个字符串后续的字典序，基于compare函数。
compare函数的实现思路是，比较a和b直至出现两个不相等或者a和b遍历完成，如果b遍历完成，则a的长度≥b的长度，a的后续字典序大于b；如果b没有遍历完，a遍历完成，则a的长度＜b的长度，a的后续字典序小于b；如果a和b都没有遍历结束但是出现了字符不相同的情况，返回当前字符的比较结果即可。
代码
class Solution {public : vector<int > merge (vector<int >& a, vector<int >& b) { vector<int > res; int i = 0 , j = 0 ; while (i < a.size () || j < b.size ()) { if (i < a.size () && (j >= b.size () || a[i] > b[j] || (a[i] == b[j] && compare (a, i, b, j)))) { res.push_back (a[i++]); } else { res.push_back (b[j++]); } } return res; } bool compare (vector<int >& a, int i, vector<int >& b, int j) while (i < a.size () && j < b.size () && a[i] == b[j]) { i++; j++; } return j == b.size () || (i < a.size () && a[i] > b[j]); } vector<int > maxNumber (vector<int >& s, int k) { vector<int > res; int n = s.size () - k; for (int i = 0 ; i < s.size (); i++) { while (res.size () != 0 && s[i] > res[res.size () - 1 ] && k > 0 ) { res.pop_back (); --k; } res.push_back (s[i]); } res.resize (n); return res; } vector<int > maxNumber (vector<int >& nums1, vector<int >& nums2, int k) { vector<int > max (k, 0 ) ; for (int i = 0 ; i <= k; i++) { int len1 = i; int len2 = k - i; if (len1 <= nums1.size () && len2 <= nums2.size ()) { if (len1 == 0 ) { vector<int > s2 = maxNumber (nums2, nums2.size () - len2); if (s2 > max) { max = s2; } continue ; } if (len2 == 0 ) { vector<int > s1 = maxNumber (nums1, nums1.size () - len1); if (s1 > max) { max = s1; } continue ; } vector<int > s1 = maxNumber (nums1, nums1.size () - len1); vector<int > s2 = maxNumber (nums2, nums2.size () - len2); vector<int > final = merge (s1, s2); if (final > max) { max = final ; } } } return max; } };
题干 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。int getMin() 获取堆栈中的最小元素。
示例 1:
输入： ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] 输出： [null,null,null,null,-3,null,0,-2] 解释： MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.
提示：
-231 <= val <= 231 - 1pop、top 和 getMin 操作总是在 非空栈 上调用push, pop, top, and getMin最多被调用 3 * 104 次
题解 思路
没想出什么好方法，想用stack来实现MinStack，一看题解还真是…
栈后进先出的性质可以理解为展示最新的，因此一个正常栈用于存储数据，另一个栈陪跑记录最新的最小值
细节
在push时陪跑栈的top值取出来与当前值对比，选择压入陪跑栈新的值或者继续压入top
代码
class MinStack {public : stack<int > s; stack<int > minStack; MinStack () { minStack.push (INT_MAX); } void push (int val) s.push (val); if (val < minStack.top ()) minStack.push (val); else minStack.push (minStack.top ()); } void pop () s.pop (); minStack.pop (); } int top () return s.top (); } int getMin () return minStack.top (); } };
题干 给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例 1：
输入：s = "3[a]2[bc]" 输出："aaabcbc"
示例 2：
输入：s = "3[a2[c]]" 输出："accaccacc"
示例 3：
输入：s = "2[abc]3[cd]ef" 输出："abcabccdcdcdef"
示例 4：
输入：s = "abc3[cd]xyz" 输出："abccdcdcdxyz"
提示：
1 <= s.length <= 30s 由小写英文字母、数字和方括号 '[]' 组成s 保证是一个 有效 的输入。s 中所有整数的取值范围为 [1, 300]
题解 思路
思路一
基本思路是识别字符序列，识别数字并重复；
考虑到括号嵌套，可以使用栈来处理，入栈直至遇到右括号，弹栈至左括号获取字符串，弹栈至栈空或者不为数字取出重复次数；
重复完当前字符串后压栈，可以有效解决嵌套；
思路二
字符和数字分开处理；
非括号元素时更新currentString和currentNum，基于规则可以得知没有括号的情况下不可能出现两个currentString或者currentNum；
遇到左括号时，即遇到新的一层，将当前字符串和数字压入栈；
遇到右括号时，即当前层结束，从栈中弹出数字，重复当前字符串，再从字符串栈中弹出前缀并拼接（若无前缀则与空串拼接）
细节
可以使用isdigit()函数判断字符是否为数字;
进行字符串数字的处理方式见代码1；
代码
数字栈和字符串两个栈，代码更简洁
class Solution {public : string decodeString (string s) { stack<string> charStack; stack<int > numStack; string currentString; int currentNum = 0 ; for (char c : s) { if (isdigit (c)) { currentNum = currentNum * 10 + (c - '0' ); } else if (c == '[' ) { charStack.push (currentString); numStack.push (currentNum); currentString = "" ; currentNum = 0 ; } else if (c == ']' ) { int repeatTimes = numStack.top (); numStack.pop (); string prevString = charStack.top (); charStack.pop (); string repeatedString; for (int i = 0 ; i < repeatTimes; ++i) { repeatedString += currentString; } currentString = prevString + repeatedString; } else { currentString += c; } } return currentString; } };
自己写的，一个栈，思路如上所述
class Solution {public : string decodeString (string s) { stack<char > decodeStack; string ans; string temp; int n; int digit; for (char c : s) { if (c == ']' ) { temp.clear (); n = 0 ; digit = 0 ; while (decodeStack.top () != '[' ) { temp = decodeStack.top () + temp; decodeStack.pop (); } decodeStack.pop (); while (!decodeStack.empty () && decodeStack.top () <= '9' && decodeStack.top () >= '0' ) { switch (digit) { case 0 : n += decodeStack.top () - '0' ; break ; case 1 : n += (decodeStack.top () - '0' ) * 10 ; break ; case 2 : n += (decodeStack.top () - '0' ) * 100 ; break ; } decodeStack.pop (); ++digit; } if (decodeStack.empty ()) { for (int i = 0 ; i < n; ++i) { ans += temp; } } else { string copy = temp; for (int i = 0 ; i < n - 1 ; ++i) { temp += copy; } for (char tempChar : temp) { decodeStack.push (tempChar); } } } else { decodeStack.push (c); } } temp.clear (); while (!decodeStack.empty ()) { temp = decodeStack.top () + temp; decodeStack.pop (); } ans += temp; return ans; } };
题干 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0]
示例 2:
输入: temperatures = [30,40,50,60] 输出: [1,1,1,0]
示例 3:
输入: temperatures = [30,60,90] 输出: [1,1,0]
提示：
1 <= temperatures.length <= 10530 <= temperatures[i] <= 100
题解 思路
建立单调递减栈，当遇到更高的气温时，会一路弹栈并更新之前的答案，契合要求；
遍历数组进行入栈，可以保证当前元素大于栈顶元素时一定是第一个大于栈顶元素值的元素 。
细节
栈仅用于存储下标，数值比较只需要取出下标基于temperatures数组进行比较，同时在更新距离时下标之差正好是距离
代码
暴力，超时
class Solution {public : vector<int > dailyTemperatures (vector<int >& temperatures) { vector<int > ans (temperatures.size()) ; for (int i=0 ; i<temperatures.size (); ++i) { for (int j=i; j<temperatures.size (); ++j) { if (temperatures[j] > temperatures[i]) { ans[i] = j - i; break ; } } } return ans; } };
单调（递减）栈
class Solution {public : vector<int > dailyTemperatures (vector<int >& temperatures) { stack<int > s; vector<int > ans (temperatures.size(), 0 ) ; for (int i = 0 ; i < temperatures.size (); ++i) { while (!s.empty () && temperatures[s.top ()] < temperatures[i]) { ans[s.top ()] = i - s.top (); s.pop (); } s.push (i); } return ans; } };
题干 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10
示例 2：
提示：
1 <= heights.length <=1050 <= heights[i] <= 104
题解 思路
每日温度的变体，每日温度是寻找第一个“大于” ，最大矩形是寻找第一个“小于” ；
细节
更新右边界应该正向循环，更新左边界应该逆向循环，可以保障弹栈更新时一定是第一个“小于” 自身值的元素；
代码
class Solution {public : int largestRectangleArea (vector<int >& heights) int ans = 0 ; stack<int > leftStack; stack<int > rightStack; vector<int > l (heights.size(), -1 ) ; vector<int > r (heights.size(), heights.size()) ; for (int i = 0 ; i < heights.size (); ++i) { while (!rightStack.empty () && heights[i] < heights[rightStack.top ()]) { r[rightStack.top ()] = i; rightStack.pop (); } rightStack.push (i); } for (int i = heights.size () - 1 ; i >= 0 ; --i) { while (!leftStack.empty () && heights[i] < heights[leftStack.top ()]) { l[leftStack.top ()] = i; leftStack.pop (); } leftStack.push (i); } for (int i = 0 ; i < heights.size (); ++i) { ans = max (ans, heights[i] * (r[i] - l[i] - 1 )); } return ans; } };
UI可能的关闭顺序（可能的出栈序列） 题干 输入n表示UI的编号从1至n，打开3之前必须打开2，打开2之前必须打开1；关闭2之前必须关闭3，关闭1之前必须关闭2，依此类推。输出20种可能的UI关闭顺序，不足20则全部输出。
题解 思路
理解题意后实际上就是按照1到n的顺序入栈，问可能的出栈序列。
细节
使用引用传递参数，需要考虑好回溯
回溯取消的是父调用的操作
代码
#include <iostream> #include <vector> #include <stack> using namespace std;vector<vector<int >> ans; void generateSequences (stack<int >& s, int i, int n, vector<int >& currentSequence) if (currentSequence.size () == n) { ans.push_back (currentSequence); return ; } if (i < n + 1 ) { s.push (i); generateSequences (s, i + 1 , n, currentSequence); s.pop (); } if (!s.empty ()) { int top = s.top (); currentSequence.emplace_back (top); s.pop (); generateSequences (s, i, n, currentSequence); s.push (top); currentSequence.pop_back (); } } int main () int n = 3 ; stack<int > s; vector<int > currentSequence; generateSequences (s, 1 , n, currentSequence); for (const auto & vec : ans) { for (size_t i = 0 ; i < vec.size (); ++i) { cout << vec[i] << (i + 1 < vec.size () ? " " : "\n" ); } } return 0 ; }
堆 题干 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入： s = “()”
输出： true
示例 2：
输入： s = “()[]{}”
输出： true
示例 3：
输入： s = “(]”
输出： false
示例 4：
输入： s = “([])”
输出： true
提示：
1 <= s.length <= 104s 仅由括号 '()[]{}' 组成
题解 思路
左括号入栈，右括号对比弹栈
细节
可能会出现全是左括号的情况，或者全是右括号的情况，因此需要使用open.empty()来解决这两种情况
代码
class Solution {public : bool isValid (string s) stack<char > open; char cur; for (char c : s) { if (c == '(' || c == '[' || c == '{' ) { open.push (c); } else { if (open.empty ()) { return false ; } cur = open.top (); if ((c == ')' && cur != '(' ) || (c == ']' && cur != '[' ) || (c == '}' && cur != '{' )) { return false ; } open.pop (); } } return open.empty (); } };
题干 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2 输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4 输出: 4
提示：
1 <= k <= nums.length <= 105-104 <= nums[i] <= 104
题解 思路
快速排序的思想，直到确认的元素位置在target则表示它是第k大的数，同时根据等比数列它的平均时间是O(N)
partition返回随机哨兵最终的下标，根据该下标更新左边界和右边界
partition函数采用双路快排，可以保证在出现大量与哨兵相等的元素时返回下标也在中间的位置，避免出现$N^2$的情况
细节
代码
class Solution {public : int partition (vector<int >& nums, int left, int right) swap (nums[left], nums[left + rand () % (right - left + 1 )]); int le = left + 1 ; int ge = right; while (true ) { while (le <= ge && nums[le] < nums[left]) ++le; while (le <= ge && nums[ge] > nums[left]) --ge; if (le >= ge) break ; swap (nums[le], nums[ge]); ++le; --ge; } swap (nums[left], nums[ge]); return ge; } int findKthLargest (vector<int >& nums, int k) int n = nums.size (); int target = n - k; int left = 0 ; int right = n - 1 ; int pivot = 0 ; while (true ) { pivot = partition (nums, left, right); if (pivot == target) return nums[target]; else if (pivot > target) right = pivot - 1 ; else left = pivot + 1 ; } } };
题干 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]
示例 2:
输入: nums = [1], k = 1 输出: [1]
提示：
1 <= nums.length <= 105k 的取值范围是 [1, 数组中不相同的元素的个数]题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
进阶： 你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
题解 思路
构建哈希表统计词频，排序哈希表的value取出前k个即可
细节
注意优先队列的STL模板以及使用方法
使用大顶堆则不需要对堆元素进行删除，但是最终维护堆的成本较高；使用小顶堆可以一直将堆的大小控制在k
代码
class Solution {public : struct cmp { bool operator () (pair<int , int >& a, pair<int , int >& b) return a.second > b.second; } }; vector<int > topKFrequent (vector<int >& nums, int k) { unordered_map<int , int > hashMap; for (auto num : nums) { ++hashMap[num]; } priority_queue<pair<int , int >, vector<pair<int , int >>, cmp> q; for (auto & pair : hashMap) { if (q.size () == k) { if (q.top ().second < pair.second) { q.pop (); q.emplace (pair); } } else { q.emplace (pair); } } vector<int > ans; for (int i = 0 ; i < k; ++i) { ans.emplace_back (q.top ().first); q.pop (); } return ans; } };
题干 中位数 是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
实现 MedianFinder 类:
MedianFinder() 初始化 MedianFinder 对象。void addNum(int num) 将数据流中的整数 num 添加到数据结构中。double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。
示例 1：
输入 ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] 输出 [null, null, null, 1.5, null, 2.0] 解释 MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2) medianFinder.addNum(3); // arr[1, 2, 3] medianFinder.findMedian(); // return 2.0
提示:
-105 <= num <= 105在调用 findMedian 之前，数据结构中至少有一个元素
最多 5 * 104 次调用 addNum 和 findMedian
题解 思路
建一个大于等于中位数的堆，但是是小顶堆，堆顶是最小的大于中位数的堆，再建一个小于中位数的堆，但是是大顶堆，堆顶的最大小于中位数的堆。
调节堆节点数量平衡，保证小顶堆数目最多比大顶堆数目多1（初始第一个元素一定加到小顶堆里）
细节
调节节点数目平衡的判断条件一定要写smallHeap.size() > bigHeap.size() + 1而不要写成smallHeap.size() - bigHeap.size() > 1
因为size()返回size_t类型，是个无符号整数，没有负数，当bigHeap.size()大于smallHeap.size()时不会得到负数而是反向溢出
代码
class MedianFinder {public : priority_queue<int , vector<int >, greater<int >> smallHeap; priority_queue<int > bigHeap; MedianFinder () {} void addNum (int num) if (smallHeap.empty () || num >= smallHeap.top ()) { smallHeap.emplace (num); } else if (num < smallHeap.top ()) { bigHeap.emplace (num); } if (smallHeap.size () > bigHeap.size () + 1 ) { bigHeap.emplace (smallHeap.top ()); smallHeap.pop (); } else if (bigHeap.size () > smallHeap.size ()) { smallHeap.emplace (bigHeap.top ()); bigHeap.pop (); } } double findMedian () if (smallHeap.size () == bigHeap.size ()) { double sum = smallHeap.top () + bigHeap.top (); return sum / 2 ; } else { return smallHeap.top (); } } };
贪心 题干 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 1050 <= prices[i] <= 104
题解 思路
动态维护最小值，非最小值时尝试更新答案，O(n)时间内可以完成利润计算
细节
prices本身是按照时间顺序递进的，因此正向遍历时动态更新最小值符合时间顺序
代码
class Solution {public : int maxProfit (vector<int >& prices) int ans = 0 ; int min = prices[0 ]; for (int i = 0 ; i < prices.size (); ++i) { if (prices[i] < min) { min = prices[i]; } else { ans = max (ans, prices[i] - min); } } return ans; } };
题干 给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [2,3,1,1,4] 输出：true 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4] 输出：false 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
提示：
1 <= nums.length <= 1040 <= nums[i] <= 105
题解 思路
根据题干，每个元素代表可以 跳跃的最大长度；
依次遍历每个位置并且实时更新可以到达的最大长度，如果元素代表跳跃距离就无法贪心；
细节
reach可以初始化为nums[0]
代码
class Solution {public : bool canJump (vector<int >& nums) int reach = nums[0 ]; for (int i = 1 ; i < nums.size (); ++i) { if (i > reach) return false ; reach = max (reach, i + nums[i]); } return reach >= nums.size () - 1 ; } };
题干 给定一个长度为 n 的 0 索引 整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i] i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
示例 1:
输入: nums = [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4] 输出: 2
提示:
1 <= nums.length <= 1040 <= nums[i] <= 1000题目保证可以到达 nums[n-1]
题解 思路
根据当前位置cur以及当前可跳距离nums[cur]可以得到当前可达位置范围，同时根据可达位置范围以及nums数组就可以知道哪一个可达位置能让你下一步的可达范围最大化。
听起来似乎有点绕，仔细阅读可以理解，跳跃是区间范围选择的，因此每次选择最远范围的即可，因为它的区间一定能覆盖其他选择，不理解的时候可以画图（借用一下官图）
细节
cur不需要遍历到nums.size() - 1，避免重复计算跳跃次数
代码
class Solution {public : int jump (vector<int >& nums) int ans = 0 ; int cur = 0 ; int next = 0 ; int maxPos = 0 ; while (cur < nums.size () - 1 ) { next = cur + nums[cur]; if (next >= nums.size () - 1 ) { ++ans; break ; } maxPos = cur; for (int i = cur + 1 ; i <= next && i < nums.size (); ++i) { if (i + nums[i] > maxPos) { maxPos = i + nums[i]; cur = i; } } ++ans; } return ans; } };
题干 给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1：
输入：s = "ababcbacadefegdehijhklij" 输出：[9,7,8] 解释： 划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。
示例 2：
输入：s = "eccbbbbdec" 输出：[10]
提示：
1 <= s.length <= 500s 仅由小写英文字母组成
题解 思路
细节
代码
class Solution {public : vector<int > partitionLabels (string s) { int n = s.size (); int charEnd[26 ]; for (int i = 0 ; i < n; ++i) { charEnd[s[i] - 'a' ] = i; } int start = 0 , end = 0 ; vector<int > ans; for (int i = 0 ; i < n; ++i) { if (charEnd[s[i] - 'a' ] > end) end = charEnd[s[i] - 'a' ]; if (i == end) { ans.emplace_back (end - start + 1 ); start = end + 1 ; } } return ans; } };
动态规划 题干 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
示例 2：
输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
提示：
题解 思路
经典动态规划，每一级都可以由上一级和上上一级到达，因此只需要知道到达上一级楼梯和上上一级楼梯有几种方法，相加即可。
细节
第0级和第1级台阶可以视为只有一种方法到达
代码
class Solution {public : int climbStairs (int n) vector<int > dp (n + 1 , 1 ) ; for (int i = 2 ; i <= n; ++i) { dp[i] = dp[i - 1 ] + dp[i - 2 ]; } return dp[n]; } };
题干 给定一个非负整数 numRows，numRows
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
提示:
题解 思路
每一行的数量与行数对应，头尾都是1因此可以全部初始化为1；
从第3行开始，除去头和尾，每个元素等于上一行前一个下标元素和当前下标元素相加；
细节
上一行在ans中应该是ans[i - 2]
代码
class Solution {public : vector<vector<int >> generate (int numRows) { vector<vector<int >> ans; for (int i = 1 ; i <= numRows; ++i) { vector<int > cur (i, 1 ) ; for (int j = 1 ; j < i - 1 ; ++j) { cur[j] = ans[i - 2 ][j - 1 ] + ans[i - 2 ][j]; } ans.emplace_back (cur); } return ans; } };
题干 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
1 <= nums.length <= 1000 <= nums[i] <= 400
题解 思路
思路一 是隔一个偷或者隔两个偷，因为nums都是大于0的，把每个nums都视为偷，那么就只能隔一个偷或者隔两个偷，但是需要处理两间屋子及以下的特殊情况；思路二 不将每个nums视为必偷，而是选择如果偷则+ dp[i - 2]，不偷则等于dp[i - 1]，更加符合动态规划思路，只需要初始化而不需要单独处理特殊情况
细节
dp中的i下标对应nums中i-1的屋子
代码
解法一 ：每一个视为必偷
class Solution {public : int rob (vector<int >& nums) vector<int > dp (nums.size() + 1 , 0 ) ; if (nums.size () == 1 ) { return nums[0 ]; } else if (nums.size () == 2 ) { return max (nums[0 ], nums[1 ]); } else { dp[1 ] = nums[0 ]; dp[2 ] = nums[1 ]; int ans = max (nums[0 ], nums[1 ]); for (int i = 3 ; i <= nums.size (); ++i) { dp[i] = max (nums[i - 1 ] + dp[i - 2 ], nums[i - 1 ] + dp[i - 3 ]); ans = max (ans, dp[i]); } return ans; } } };
解法二 ：不把每一个都视为必偷
class Solution {public : int rob (vector<int >& nums) vector<int > dp (nums.size() + 1 , 0 ) ; dp[1 ] = nums[0 ]; for (int i = 2 ; i <= nums.size (); ++i) { dp[i] = max (dp[i - 1 ], dp[i - 2 ] + nums[i - 1 ]); } return dp[nums.size ()]; } };
题干 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12 输出：3 解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13 输出：2 解释：13 = 4 + 9
提示：
题解 思路
$n$可以表示为一个平方数与另一个数$n - i^2$相加，基于动态规划思想，$dp[n] = dp[n - i^2] + 1$
双重循环，一个循环遍历更新dp数组，一个循环迭代小于i的平方数
细节
初始化时全部初始化为INT_MAX，再将dp[0]设置为0，可以减少一个变量初始化为INT_MAX（代码2的方法）
代码
优化过的代码
class Solution {public : int numSquares (int n) vector<int > dp (n + 1 , INT_MAX) ; dp[0 ] = 0 ; for (int i = 1 ; i <= n; ++i) { for (int j = 1 ; j * j <= i; ++j) { if (dp[i - j * j] < dp[i]) { dp[i] = dp[i - j * j]; } } ++dp[i]; } return dp[n]; } };
增加一个中间变量记录ans，用于更新dp
class Solution {public : int numSquares (int n) vector<int > dp (n + 1 , 0 ) ; for (int i = 1 ; i <= n; ++i) { int ans = INT_MAX; for (int j = 1 ; j * j <= i; ++j) { if (dp[i - j * j] < ans) ans = dp[i - j * j]; } dp[i] = ans + 1 ; } return dp[n]; } };
题干 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3 输出：-1
示例 3：
输入：coins = [1], amount = 0 输出：0
提示：
1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
题解 思路
和完全平方数一样的思路，但是更新条件更加复杂：
下标首先不能越界
其次得是有效结果即dp值不为-1
最后要比ans值更小
细节
如果ans没有发生过更新说明不存在符合条件的前置选项，此时不应该更新dp数组，保持-1作为不满足条件的标记
代码
class Solution {public : int coinChange (vector<int >& coins, int amount) vector<int > dp (amount + 1 , -1 ) ; dp[0 ] = 0 ; for (int i = 1 ; i <= amount; ++i) { int ans = INT_MAX; for (int coin : coins) { if (i - coin >= 0 && dp[i - coin] != -1 && ans > dp[i - coin]) { ans = dp[i - coin]; } } if (ans != INT_MAX) dp[i] = ans + 1 ; } return dp[amount]; } };
题干 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意： 不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。 注意，你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false
提示：
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s 和 wordDict[i] 仅由小写英文字母组成wordDict 中的所有字符串 互不相同
题解 思路
与完全平方数一样的思路，但是这次不需要维护最长或者最短；
遍历整个字符串，从当前字符串长度往前截取一个单词的长度，检查子串是否能和wordDict中单词对应，对应上则该点dp值为true；
细节
string::compare()函数的一种重载int compare(size_t pos, size_t len, const string& str) const;
参数：
pos：当前字符串中开始比较的位置。len：当前字符串中要比较的子串长度。str：要比较的另一个字符串。
返回值：
如果当前子串小于 str，返回负值。
如果当前子串等于 str，返回 0。
如果当前子串大于 str，返回正值。
代码
class Solution {public : bool wordBreak (string s, vector<string>& wordDict) const int n = s.size (); vector<bool > dp (n + 1 , false ) ; dp[0 ] = true ; for (int i = 1 ; i <= n; ++i) { for (string& word : wordDict) { if (i >= word.size () && word == s.substr (i - word.size (), word.size ()) && dp[i - word.size ()]) dp[i] = dp[i - word.size ()]; } } return dp[n]; } }; class Solution {public : bool wordBreak (string s, vector<string>& wordDict) const int n = s.size (); vector<bool > dp (n + 1 , false ) ; dp[0 ] = true ; for (int i = 1 ; i <= n; ++i) { for (string& word : wordDict) { if (i >= word.size () && s.compare (i - word.size (), word.size (), word) == 0 && dp[i - word.size ()]) dp[i] = dp[i - word.size ()]; } } return dp[n]; } };
题干 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的
子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3] 输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7] 输出：1
提示：
1 <= nums.length <= 2500-104 <= nums[i] <= 104
进阶：
你能将算法的时间复杂度降低到 O(n log(n)) 吗?
题解 思路
dp ：
依旧是完全平方数的思路，往前遍历更新最大值，dp[i]表示以nums[i]结尾的最长子序列长度
比较nums[i]与其之前的每一个nums[j]，更新dp[i]
但是这题dp[n - 1]不一定是最大的，因为nums[n - 1]可能是一个很小的数，因此是递减的，没有纳入最长递增序列
二分 ：
想要动态维护最长递增子序列可能做不到，但是动态维护最长递增子序列的结尾是可以做到的
维护一个递增数组，如果nums[i]大于递增数组尾元素更新答案并且直接加在递增数组后面
如果nums[i]小于递增数组尾元素，则用它更新递增数组，increase[i]表示长度为i+1的子序列尾元素的可能值，将对应长度子序列的尾元素都维护在当前的最小值，可以保证子序列尽可能地增长（贪心策略）
细节
二分查找和普通二分不一样，如果缩小边界的方式并不是mid + 1和mid - 1，而是mid + 1和mid 或 mid - 1 和 mid 的话，那么循环条件是l < r
代码
动态规划
class Solution {public : int lengthOfLIS (vector<int >& nums) const int n = nums.size (); vector<int > dp (n, 1 ) ; int ans = 1 ; for (int i = 1 ; i < n; ++i) { int temp = INT_MIN; for (int j = 0 ; j < i; ++j) { if (nums[i] > nums[j] && dp[j] > temp) temp = dp[j]; } if (temp != INT_MIN) dp[i] = temp + 1 ; if (dp[i] > ans) ans = dp[i]; } return ans; } };
维护递增数组，二分查找
class Solution {public : int lengthOfLIS (vector<int >& nums) vector<int > increase = {nums[0 ]}; for (int i = 1 ; i < nums.size (); ++i) { if (nums[i] > increase[increase.size () - 1 ]) increase.emplace_back (nums[i]); else if (nums[i] < increase[increase.size () - 1 ]) { int left = 0 , right = increase.size () - 1 ; int mid = 0 ; while (left < right) { mid = left + (right - left) / 2 ; if (increase[mid] >= nums[i]) { right = mid; } else { left = mid + 1 ; } } increase[right] = nums[i]; } } return increase.size (); } };
多维动态规划 题干 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
示例 2：
输入：m = 3, n = 2 输出：3 解释： 从左上角开始，总共有 3 条路径可以到达右下角。 1. 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 3. 向下 -> 向右 -> 向下
示例 3：
示例 4：
提示：
1 <= m, n <= 100题目数据保证答案小于等于 2 * 109
题解 思路
二维动态规划，当前位置可以从左方和上方走到，将它们的路径数目相加即可更新当前位置
组合数，向右走n - 1次，向下走m - 1次，总共走m + n - 2次，从m + n - 2次行走中选出n - 1次向右走就是答案
细节
动态规划第一行和第一列的路径数目都是1，只有一条路（因为只能向下和右）
组合数不能写函数来进行阶乘计算，会溢出（long long也会），只能乘法和除法同步进行，组合数的特点之一上面相乘的数目和下面相乘的数目相等
$C_{m + n - 2}^{m - 1} = \frac{(m + n -2)!}{(m - 1)!(n - 1)!} = \frac{n(n + 1)…(m+n-2)}{(m - 1)!}$，根据组合数上述性质，分母是m-1个数相乘，分子也应该是m-1个数相乘，即从n到m+n-2为n-1个数
代码
二维动态规划
class Solution {public : int uniquePaths (int m, int n) vector<vector<int >> dp (m, vector <int >(n, 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 ]; } };
数学方法，组合数
class Solution {public : int uniquePaths (int m, int n) long long ans = 1 ; for (int i = 1 , j = n; i < m; ++i, ++j) { ans = ans * j / i; } return ans; } };
题干 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace" ，它的长度为 3 。
示例 2：
输入：text1 = "abc", text2 = "abc" 输出：3 解释：最长公共子序列是 "abc" ，它的长度为 3 。
示例 3：
输入：text1 = "abc", text2 = "def" 输出：0 解释：两个字符串没有公共子序列，返回 0 。
提示：
1 <= text1.length, text2.length <= 1000text1 和 text2 仅由小写英文字符组成。
题解 思路
二维动态规划，其中dp[i][j]表示选取text1的前i个字符，text2的前j个字符时的最长公共子序列长度
text1的第i个字符和text2的第j个字符相同时，这个字符必然被加入到最长公共子序列当中，因此只需要加上选取text1的前i - 1个字符，text2的前j - 1个字符时的最长公共子序列长度即可不相同则从dp[i][j - 1]和dp[i - 1][j]中选取最大值（顺序遍历，因此dp[i][j - 1]和dp[i - 1][j]已经完成更新了）
细节
第一行与第一列初始化为0，因为dp的更新可能需要基于上一行与上一列，因此将dp数组初始化为dp[row + 1] [col + 1]更合理
dp存储的最长公共子序列长度是递增的，因此不需要动态维护答案，直接返回dp[row] [col]即可
代码
class Solution {public : int longestCommonSubsequence (string text1, string text2) if (text1 == "" || text2 == "" ) { return 0 ; } int row = text1.size (); int col = text2.size (); int dp[row + 1 ][col + 1 ]; for (int i = 0 ; i < col + 1 ; i++) { dp[0 ][i] = 0 ; } for (int i = 0 ; i < row + 1 ; i++) { dp[i][0 ] = 0 ; } for (int i = 1 ; i < row + 1 ; ++i) { for (int j = 1 ; j < col + 1 ; ++j) { if (text1[i - 1 ] == text2[j - 1 ]) { dp[i][j] = dp[i - 1 ][j - 1 ] + 1 ; } else { dp[i][j] = max (dp[i - 1 ][j], dp[i][j - 1 ]); } } } return dp[row][col]; } };
题干 给你一个字符串 s，找到 s 中最长的 回文 子串。
示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。
示例 2：
提示：
1 <= s.length <= 1000s 仅由数字和英文字母组成
题解 思路
dp思路是当前字符串头和尾相等时，如果中间的字符串是回文的则当前字符串回文使用dp[i] [j]表示字符串s从i到j的子串是否为回文
状态转移方程是dp[i] [j] = s[i] == s[j] && ((j - i) < 2 || dp[i + 1] [j - 1])，表示如果s[i] == s[j]，那么如果i到j只有一个字符或者两个字符则是回文的，或者中间字符串是回文的，则当前字符串回文
根据状态转移方程可以判断，状态依赖下一行和上一列，因此i需要逆向遍历，j需要正向遍历
细节
很巧妙的一点是j - i < 2这个判断条件可以避免dp[i + 1] [j - 1]发生越界
当i == s.size() - 1时不会发生越界，因为条件判断在j - i < 2就终止了
当j == 0时也不会发生越界，j == 0时条件判断在j - i < 2就终止了
代码
class Solution {public : string longestPalindrome (string s) { int start = 0 ; int end = 0 ; vector<vector<bool >> dp (s.size (), vector <bool >(s.size (), false )); for (int i = s.size () - 1 ; i > -1 ; --i) { for (int j = i; j < s.size (); ++j) { if (s[i] == s[j] && (j - i < 2 || dp[i + 1 ][j - 1 ])) { dp[i][j] = true ; if (j - i + 1 > end - start + 1 ) { end = j; start = i; } } } } return s.substr (start, end - start + 1 ); } };
设计 题干 给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。打乱后，数组的所有排列应该是 等可能 的。
实现 Solution class:
Solution(int[] nums) 使用整数数组 nums 初始化对象int[] reset() 重设数组到它的初始状态并返回int[] shuffle() 返回数组随机打乱后的结果
示例 1：
输入 ["Solution", "shuffle", "reset", "shuffle"] [[[1, 2, 3]], [], [], []] 输出 [null, [3, 1, 2], [1, 2, 3], [1, 3, 2]] 解释 Solution solution = new Solution([1, 2, 3]); solution.shuffle(); // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如，返回 [3, 1, 2] solution.reset(); // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3] solution.shuffle(); // 随机返回数组 [1, 2, 3] 打乱后的结果。例如，返回 [1, 3, 2]
提示：
1 <= nums.length <= 50-106 <= nums[i] <= 106nums 中的所有元素都是 唯一的 最多可以调用 104 次 reset 和 shuffle
题解 思路
reset需要存储一份原数组随机打乱可以将随机选择的数放置到当前数组末尾，然后逐步减少随机选择范围，提高效率
细节
循环应该从后往前遍历，便于选择项的交换
代码
class Solution {public : vector<int > orginalNums; vector<int > curNums; Solution (vector<int >& nums) : orginalNums (nums), curNums (nums) {} vector<int > reset () { curNums = orginalNums; return curNums; } vector<int > shuffle () { int randomIndex = 0 ; for (int i = orginalNums.size () - 1 ; i >= 0 ; --i) { randomIndex = rand () % (i + 1 ); swap (curNums[i], curNums[randomIndex]); } return curNums; } };
