> For the complete documentation index, see [llms.txt](https://navining.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://navining.gitbook.io/lintcode/master.md). # LintCode刷题笔记 | | | - | | 复杂度 | 可能对应的语法 | 备注 | | -------- | ----------------------------------------------------- | --------------- | | O(1) | 位运算 | 常数级复杂度，一般面试中不会有 | | O(logn) | 二分法，倍增法，快速幂算法，辗转相除法 | | | O(n) | 枚举法，双指针算法，单调栈算法，KMP算法，Rabin Karp，Manacher's Algorithm | 又称作线性时间复杂度 | | O(nlogn) | 快速排序，归并排序，堆排序 | | | O(n^2) | 枚举法，动态规划，Dijkstra | | | O(n^3) | 枚举法，动态规划，Floyd | | | O(2^n) | 与组合有关的搜索问题 | | | O(n!) | 与排列有关的搜索问题 | | ## 双指针 ### 相向双指针 #### Reverse **415: Valid Palindrome** ``` while (left < right) { // left找到合法的字符 while (left < right && isValid(s[left])) { left++; } // right找到合法的字符 while (left < right && isValid(s[right])) { right--; } // 判断是否相等 if (left < right && toupper(s[left]) != toupper(s[right])) { return false; } left++; right--; } ``` **819: Valid Palindrome II** ``` // 找到第一个不满足回文的地方 while (left < right) { if (s[left] != s[right]) { break; } left++; right--; } // 判断去掉这个字符的情况下是不是回文串 return isPalindrom(s, left+1, right) || isPalindrom(s, left, right-1); ``` #### Two Sum **56: Two Sum** 哈希表：时间复杂度O(n) 空间复杂度O(n) 适合寻找下标 排序+双指针：时间复杂度O(nlogn) 空间复杂度O(1) 适合排序好的数据 ``` while (left < right) { if (nums[left] + nums[right] < target) { // 向大的方向找 left++; } else if (nums[left] + nums[right] > target) { // 向小的方向找 right--; } else { return {nums[left], nums[right]}; } } ``` **57: Three Sum** 先拿出一个element，在剩下的里面找two sum 和Two Sum区别： 1. 去重 ``` if (i > 0 && nums[i] == nums[i - 1]) { continue; } while (start < end) { if (start > i + 1 && nums[start - 1] == nums[start]) { start++; continue; } ... } ``` 1. 找到target后不return，继续找 **533：两数和的最接近值** two sum的过程中打擂台，更新最小的difference #### Partition **464: 快速排序** 三个要点 ``` // 1. 选择pivot int pivot = A[(left + right) / 2]; ​ // 2. 循环条件一定要是<= while (left <= right) { // 3. 选择>=piovt的元素交换到pivot右边，而不是> while (left <= right && A[left] < pivot) { left++; } while (left <= right && A[right] > pivot) { right--; } if (left <= right) { swap(nums[left++], nums[right--]); } } ``` left指向右侧的第一个位置 **5: 第k大元素** 采用quick select，和快排一个思想 交换完一遍后，所有大于等于pivot的元素都在pivot左边 循环退出后有两种情况，i和j中间有0个或1个元素 ，要分成三段找 ``` if (j - start + 1 >= k) { // 在[start, j]里找 return quickSelect(nums, start, j, k); } else if (i - start < k) { // 在[i, end]里找 return quickSelect(nums, i, end, k - (i - start)); } else { // 正好在j和i中间 return nums[j + 1]; } ``` **148：颜色分类** 遍历一遍，0扔到左边，1不管，2扔到右边 注意交换完2后当前index不加一，要再次判断交换来的数 **143：排颜色 II** rainbow sort 复杂度`O(nlogk)` 小于等于k/2分在左边，大于k/2分在右边 不仅需要index的区间，还需要color的区间 ### 背向双指针 **200: Longest Palindromic Substring** 中心线枚举，分成奇数长度和偶数长度两种情况 ``` for (int i = 0; i < s.length(); i++) { // 奇数情况，最小值是单个字符 string odd = getPalindrome(s, i, i); // 偶数情况，最小值是两个字符 string even = getPalindrom(s, i, i+1); } ​ string getPalindrom(string &s, int left, int right) { // 背向双指针 while (left >= 0 && right < s.length()) { if (s[left] != s[right]) { break; } left--; right++; } return s.substr(left + 1, right - left - 1); } ``` ### 同向双指针 特点：不回头 模板 左指针for循环 右指针while循环 ``` int j = 1; for (int i = 0; i < n; i++) { while (j < n && i和j的搭配不满足条件) { j++; } if (j >= n) { break; } 处理ij的这次搭配 } ``` **610：两数差** 注意点：target取绝对值，j要一直比i大`max(j, i+1)` **1870：全零子串的数量** j停在不是0的地方，注意超出边界后不用break **512：数组去重** i指向最后一个不重复的数字，j寻找下一个不等于i的数，并给i+1 **386：最多有k个不同字符的最长子字符串** 先移动j，再移动i使窗口内保持k种不同的字符 **103：带环链表II** 当判断有环时(slow==fast)时，从头移动慢指针，同时移动快指针，两指针相遇处即为环的入口 **1246：替换后的最长重复字符** 注意点：退出循环有两种，j指针越界或者替换次数大于k，他们更新结果的方式不同。i指针右移后哈希表次数要减一，同时要再次更新出现次数最多的字符 ## 二分法 二分法模板 ``` int findPosition(vector nums, int target) { if (nums.empty()) { return -1; } ​ int start = 0, end = nums.size() - 1; // 要点1: start + 1 < end while (start + 1 < end) { // 要点2：start + (end - start) / 2 int mid = start + (end - start) / 2; // 要点3：=, <, > 分开讨论，mid 不+1也不-1 if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { start = mid; } else { end = mid; } } ​ // 要点4: 循环结束后，单独处理start和end if (nums[start] == target) { return start; } if (nums[end] == target) { return end; } return -1; } } ``` ### 排序数据集二分 **457: 经典二分查找** **458：目标最后出现的位置** 要点: 找到相等元素后继续在右边查找`start = mid;` 循环退出后先判断end再判断start **14：目标第一次出现的位置** 要点: 找到相等元素后继续在左边查找`end = mid;` 循环退出后先判断start再判断end **460：在排序数组中找最接近的K个数** 先找到最接近的数，再用背向双指针 `O(logn) + k` **65：两个排序数组的中位数** 转换为找第k小的问题，其中k=(n+m)/2。每次比较A数组的第k/2小和B数组的第k/2小的数，谁小就扔掉谁的前k/2个数，然后继续寻找第(k-k/2)小的数，直到k==1或者其中一个数组为空。用一个参数记录两个数组起始位置 **931: K 个有序数组的中位数** 可以用priority\_queue+k路归并，但是会超时 双重二分：先在答案集上二分，找第k/2个数。countLessOrEqual返回小于等于target的数量 countLessOrEqual在每个数组上二分，求所有小于target元素的数量之和 ``` class Solution { public: double findMedian(vector> &nums) { if (nums.empty()) { return 0; } int n = 0; for (vector & A : nums) { n += A.size(); } if (n == 0) { return 0; } if (n % 2 == 0) { return findKth(nums, n / 2) / 2.0 + findKth(nums, n / 2 + 1) / 2.0; } return findKth(nums, n / 2 + 1); } private: int findKth(vector> &nums, int k) { int lb = INT_MAX, ub = INT_MIN; for (vector & A : nums) { if (A.empty()) { continue; } lb = min(lb, A[0]); ub = max(ub, A.back()); } int start = lb, end = ub; while (start + 1 < end) { int mid = start + (end - start) / 2; int count = countLessOrEqual(nums, mid); if (count < k) { start = mid + 1; } else if (count > k) { end = mid; } else { end = mid; } } if (countLessOrEqual(nums, start) >= k) { return start; } return end; } ​ int countLessOrEqual(vector> &nums, int key) { int count = 0; for (vector & A : nums) { count += rank(A, key); } return count; } int rank(vector &A, int key) { if (A.size() == 0) { return 0; } int start = 0, end = A.size() - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; if (A[mid] < key) { start = mid + 1; } else if (A[mid] > key) { end = mid; } else { start = mid + 1; } } if (A[start] > key) { return start; } if (A[end] > key) { return end; } return A.size(); } }; ``` ### 未排序数据集二分 **585：山脉序列中的最大值** 比较nums\[mid]和nums\[mid+1] **75：寻找峰值** 比较nums\[mid-1], nums\[mid]和nums\[mid+1] **28：搜索二维矩阵** 把二维坐标转换成一维坐标，不用搜索两次 **625：数组划分II** 使用三个指针 ``` while (mid <= end) { if (nums[mid] < low) { swap(nums[mid++], nums[start++]); } else if (nums[mid] > high) { swap(nums[mid], nums[end--]); } else { mid++; } } ``` **160：寻找旋转排序数组中的最小值 II** 分为三种情况讨论：mid小于end，大于end和等于end，第三种情况`end--` **62：搜索旋转排序数组** 先判断mid在哪个递增数组上，再判断target在mid的哪边 ``` if (A[mid] > A[start]) { if (A[start] <= target && target < A[mid]) { end = mid; } else { start = mid; } } else { if (A[mid] < target && target <= A[end]) { start = mid; } else { end = mid; } } ``` 或者先找到最小值，把数组分为两半，再分别二分 **63：搜索旋转排序数组 II** 有重复数据，只能先找到最小值，分成两半再二分 ### 答案集二分 **183：木材加工** 在答案集中二分的典型例子 **254：丢鸡蛋** ``` int dropEggs(int n) { // write your code here long result = 0; int x = 0; while (result < n) { x++; result += x; } return x; } ``` **428：x的n次幂** 递归求`pow(x, n/2)`，记得考虑负数情况（把结果取倒数） **437：书籍复印** 最快用时max(pages)，最慢用时sum(pages)，在此区间上搜索满足<=k的最小值 ## 复杂度小于O(n)的算法 ### 快速幂算法 O(log(n)) (a+b)%c = (a%c+b%c)%c (a\*b)%c = (a%c\*b%c)%c (a-b)%c = (a%c-b%c+c)%c **140：快速幂** 利用a^n = a^(n/2)^2，先算出a^(n/2)，再分奇偶处理 非递归方法：二进制 ### 辗转相除法 O(log(n)) 用**较大的数**除以**较小的数**，再用**除数**除以出现的**余数**（第一余数），再用**第一余数**除以出现的**余数**（第二余数），如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。 ### 分解质因数 O(√n) 1. 记up = sqrt{n}，作为质因数k的上界, 初始化k=2。 2. 当k <= up 且 n不为1 时，执行步骤3，否则执行步骤4。 3. 当n被k整除时，不断整除并覆盖n，同时结果中记录k，直到n不能整出k为止。之后k自增，执行步骤2。 4. 当n不为1时，把n也加入结果当中，算法结束 ### 分块检索法 O(√n) 将长度为N的空间分成√n大小的小区间 ## BFS ### 三种实现方法 #### 单队列 ``` queue q; // 把第一层的节点放到队列中 q.push(0); int visited[][] = {}; // 把起点设为visited visited[0][0] = 1; // 当前步数 int step = 0; // while队列非空 while (!q.empty()) { // 要用一个数保存当前size，否则会变 int size = q.size(); // 遍历当前层 for (int n = 0; n < size; n++) { // 拿出一个节点 int cur = q.front(); q.pop(); // 判断终点 if (终点) return; // 把子节点放入队列中 ...... } // 步数+1 step++; } ``` #### 双队列 每次用一个新的队列储存当前层的元素 #### dummy node 类似linkedlist的头节点前一个 还是用单队列，每次一层结束后放入一个nullptr标记 ### 图 需要一个visited字典记录走过的点（可以用set）。注意：应在把neighbour放入队列的同时做标记 #### Adjacency List 每个点上储存自己的邻居(类似树的储存方式)，可以用list或set ``` class GraphNode { public: int label; list neighbors; }; ``` ### 分层遍历 图的层次遍历、简单图的最短路径 两种方法： 1. 用distance记录当前最短距离，for遍历每层 2. 把{node，distance}一起放入visited hashmap中，既可以判断是否走过，也可以记录当前距离。可以省去层级遍历 如果要找具体路径： 1. 如果要找所有最短路径，把path加入queue中 2. 如果只要找一条路径，可以用一个prev map，类似链表的方式找到前一个节点 **120：单词接龙** 最短路径问题。每次变换一个字母（26个字母），再在字典中查找能不能转换 可以使用双向BFS，先建立一个图，再从两边出发 **121: 单词接龙II** 这题用bfs储存路径会超出内存限制，应该先用bfs储存到终点的距离，再用dfs导出答案 使用BFS去計算每個字變成終點的字的距離(step of transformation)，並且用Hash Map去記錄著 同時也用Hash Map記錄著每個字跟他的鄰居們(next word) 在用DFS去遍歷，從起點到終點，同時只選擇那些下一個字的距離是目前字的距離的少1 ``` class Solution{ public: /* * @param start: a string * @param end: a string * @param dict: a set of string * @return: a list of lists of string */ map> next_word_dict; vector> res; map distance; vector> findLadders(string &start, string &end, unordered_set &dict) { vector tem; tem.push_back(start); //将end添加进dict,防止结果为[] dict.insert(end); //bfs搜start--end的最短路径 bfs(start, end, dict); //dfs输出距离最短的路径 dfs(start, end, tem); return res; } vector next_word(string word,unordered_set &dict) { vector ans; for (int i = 0; i < word.size();i++) { string s = word; for (char j = 'a';j <= 'z';j++) { s[i] = j; if (s != word && dict.count(s)) { ans.push_back(s); } } } return ans; } void bfs(string &start, string &end,unordered_set &dict) { queue q; q.push(start); int step = 0; bool flag = false;//标记是否找到结果 distance[start] = 0; while (!q.empty()) { step++; int n = q.size(); for (int i = 0;i < n;i++) { string word = q.front(); q.pop(); for (string nextword : next_word(word,dict)) { next_word_dict[word].push_back(nextword); //当下一跳是end时，就可以结束搜索 if (nextword == end) { flag = true; } if (distance.count(nextword) == 0) { distance[nextword] = step; q.push(nextword); } } } if(flag){ break; } } } void dfs(string &start, string &end,vector &sol) { if (start == end) { res.push_back(sol); } vector tmp = next_word_dict[start]; //遍历start的下一跳 for (int i = 0; i < tmp.size(); i++) { if (distance[tmp[i]] != distance[start] + 1) { continue; } sol.push_back(tmp[i]); //遍历下一跳的下一跳 dfs(tmp[i], end, sol); sol.pop_back(); } } }; ``` ### 连通块问题 通过一个点找图中联通的所有点，不需要层级遍历。也可以用dfs，但是麻烦 **1179：朋友圈** 对没有visited的每个人做一次bfs，把它的朋友全都标记成visited **137：克隆图** 拆成三个步骤 1. bfs找到所有点 2. 克隆点，储存新老节点的映射关系 3. 克隆边 ### 拓扑排序 拓扑序是指一个满足有向图上，不存在一条边出节点在入节点后的线性序列，如果有向图中有环，就不存在拓扑序。可以通过拓扑排序算法来得到拓扑序，以及判断是否存在环。相关问题：要得到一个序列，且数据之间有指向性 入度in-degree：有多少点指向这个点 1. 统计每个点的入度（用hashmap） 2. 把入度为0的点放入队列中 3. 不断从队列中拿出一个点，去掉这个点所有边，相邻点的入度-1 4. 一旦发现新的入度为0的点，放入队列中 存在拓扑排序：所有点都被拿出来 拓扑排序唯一：队列中只能存在一个点 字典序最小：用priorityqueue 不需要visited，indegree起到相同的作用 #### 615. 课程表 转化为找是否存在拓扑排序。（注：测试集中有重复数据，不能用set要用multiset） #### 605. 序列重构 用seqs建图，找拓扑排序。判断拓扑排序是否唯一，且排序后的结果和org是否相同 ### 双向BFS 同时给出了起点和终点，可以从两头一起找，运算量是原先的根号 需要两个队列和两个set，当一个队列中的点在另一个的set中出现过则找到了目标点 ``` distance = 0 while forward_queue 和 back_queue 非空 distance++ for 所有 forward_queue 里的点 拓展出下一层节点加入forward_queue并在forward_set做标记 如果在backward_set出现则return distance distance++ for 所有 backward_queue 里的点 拓展出下一层节点加入backward_queue并在backward_set做标记 如果在forward_set出现则return distance ``` ## DFS 使用场景：二叉树，找所有方案，排列组合 时间复杂度通用公式：O(方案总数\*构造每个方案的时间) ### 遍历法 一个人拿着一个记事本走遍所有节点。没有return 回溯：找路径的时候如果传递的是引用，递归调用完需要回溯。传进来是什么样，函数return就要恢复成什么样 ``` path.push_back(root->left); dfs(root->left, path, result); path.pop_back(); path.push_back(root->right); dfs(root->right, path, result); path.pop_back(); ``` ### 分治法 分配小弟做子任务，自己进行结果汇总。有return ``` 左子树返回结果 = dfs(root->left); 右子树返回结果 = dfs(root->right); 整棵树的结果 = 合并左右子树 ``` **88. 最小公共节点** ``` class Solution { public: TreeNode * lowestCommonAncestor(TreeNode * root, TreeNode * A, TreeNode * B) { if(root == NULL) return NULL; if(root == A || root == B) { return root; } TreeNode* left = lowestCommonAncestor(root->left, A, B); TreeNode* right = lowestCommonAncestor(root->right, A, B); if(left != NULL && right != NULL) return root; if(left != NULL ) return left; if(right != NULL) return right; return NULL; } }; ``` 函数的作用：找到最小公共节点或者A或者B。return有三种可能：LCA，A或者B 如果root是A或者B，return root 左右都null：return null 左右都非null：return root 左右中一个为null：return 左/右 这样做的前提是保证树中一定有LCA，否则返回的可能是单独的A或者B节点 **578. 最低公共祖先III** 用两个flag判断是否是A或者B。如果已经在子树中找到了LCA,就直接return。否则，如果当前节点是 A且在子树中找到了B，或者当前节点是B且已经在子树中找到了A，就说明当前节点是LCA。 **474. 最低公共祖先II** 有指向父节点的指针，转换成找链表的公共节点 ### 二叉树非递归遍历 #### 中序遍历 最小的点：最左边 下一个点：右子树最左边的点或者路径中最近一个通过左子树包含当前点的点 一种方法：在stack中记录从根节点到当前节点的整条路径 另一种更简单的方法：在stack中只记录未访问过的点 ``` class BSTIterator { public: BSTIterator(TreeNode * root) { findMostLeft(root); } bool hasNext() { return !s.empty(); } TreeNode * next() { TreeNode *cur = s.top(); s.pop(); if (cur->right != nullptr) { findMostLeft(cur->right); } return cur; } void findMostLeft(TreeNode *root) { while (root != nullptr) { s.push(root); root = root->left; } } private: stack s; }; ``` 先把root到左下角的所有点push进stack。拿出一个点的时候，把他右节点到右节点左下角的所有点push进stack。 **902. BST中第k小的元素** 1\)直接一个in\_order\_traverse 2) follow up: 二叉树经常被修改，如何优化kth smallest 先traverse一遍，弄个哈希表将每个子树(root为key)有多少个node记下来 然后用quick Select思想，每次抛弃一部分 #### 后序遍历 1、如果根节点非空，将根节点加入到栈中。 2、如果栈不空，取栈顶元素（暂时不弹出）， a.如果（左子树已访问过或者左子树为空），且（右子树已访问过或右子树为空），则弹出栈顶节点，将其值加入数组， b.如果左子树不为空，且未访问过，则将左子节点加入栈中，并标左子树已访问过。 c.如果右子树不为空，且未访问过，则将右子节点加入栈中，并标右子树已访问过。 3、重复第二步，直到栈空。 ``` class Solution { public: vector postorderTraversal(TreeNode * root) { if (root == nullptr) return {}; stack s; s.push(root); TreeNode* prev = nullptr; vector result; while (!s.empty()) { TreeNode *cur = s.top(); if (prev == nullptr || prev->left == cur || prev->right == cur) { if (cur->left != nullptr) { s.push(cur->left); } else if (cur->right != nullptr) { s.push(cur->right); } } else if (prev == cur->left) { if (cur->right != nullptr) { s.push(cur->right); } } else { result.push_back(cur->val); s.pop(); } prev = cur; } return result; } }; ``` #### Morris算法 使用二叉树中的叶节点的right指针来保存后面将要访问的节点的信息，当这个right指针使用完成之后，再将它置为null，但是在访问过程中有些节点会访问两次，所以与递归的空间换时间的思路不同，Morris则是使用时间换空间的思想。（了解即可) ### 二叉搜索树 #### 二叉搜索树的增删查改 **增加** ``` public TreeNode insertNode(TreeNode root, TreeNode node) { if (root == null) { return node; } if (root.val > node.val) { root.left = insertNode(root.left, node); } else { root.right = insertNode(root.right, node); } return root; } ``` **删除** * 考虑待删除的节点为叶子节点，可以直接删除并修改父亲节点(Parent Node)的指针，需要区分待删节点是否为根节点 * 考虑待删除的节点为单支节点(只有一棵子树——左子树 or 右子树)，与删除链表节点操作类似，同样的需要区分待删节点是否为根节点 * 考虑待删节点有两棵子树，可以将待删节点与左子树中的最大节点进行交换，由于左子树中的最大节点一定为叶子节点，所以这时再删除待删的节点可以参考第一条 **95. 验证二叉查找树** 采用一个lower bound一个upper bound ``` class Solution { public: bool isValidBST(TreeNode * root) { return helper(root, LONG_MIN, LONG_MAX); } bool helper(TreeNode *root, long lower, long upper) { if (root == nullptr) return true; if (root->val <= lower || root->val >= upper) return false; return helper(root->right, root->val, upper) && helper(root->left, lower, root->val); } }; ``` **11. 二叉查找树中搜索区间** 中序遍历+剪枝，只有当前元素大于k1才去左边找，大于k2才去右边找 **701. 修建二叉搜索树** * 若根节点的值小于最小值，则递归调用右子树并返回右子树； * 若根节点的值大于最大值，则递归调用左子树并返回左子树； * 否则修剪左子树，右子树并返回根节点。 **448. 二叉查找树的中序后继** 首先要确定中序遍历的后继: * 如果该节点有右子节点, 那么后继是其右子节点的子树中最左端的节点 * 如果该节点没有右子节点, 那么后继是离它最近的祖先, 该节点在这个祖先的左子树内. 当向左移动时，需要更新successor, 相右移动时，无需更新successor 使用循环实现: * 查找该节点, 并在该过程中维护上述性质的祖先节点 * 查找到后, 如果该节点有右子节点, 则后继在其右子树内; 否则后继就是维护的那个祖先节点 ### 组合类DFS 组合的复杂度2^n **17. 全子集问题** 可以看成连通块问题，每个路径当作一个点 两种思路：多叉树（每次加一个点）和二叉树（每次加或不加） BFS做法： ``` vector> subsets(vector &nums) { if (nums.empty()) return {{}}; // 先排序 sort(nums.begin(), nums.end()); // 相当于队列 vector> result = {{}}; // 记录队头index int index = 0; // 相当于!q.empty() while (index < result.size()) { // 先取出subset vector subset = result[index++]; for (int i = 0; i < nums.size(); i++) { if (subset.size() > 0 && nums[i] <= subset.back()) continue; vector nsubset = subset; nsubset.push_back(nums[i]); result.push_back(nsubset); } } return result; } ``` dfs做法：递归搜索二叉树，每层加一个或者不加，到叶子节点结束 ``` class Solution { public: vector> subsets(vector &nums) { sort(nums.begin(),nums.end()); vector> result; vector subset; dfs(nums, result, 0, subset); return result; } void dfs(vector& nums, vector> &result, int index, vector& subset) { if (index == nums.size()) { result.push_back(subset); return; } subset.push_back(nums[index]); // 加 dfs(nums, result, index + 1, subset); subset.pop_back(); // 不加 dfs(nums, result, index + 1, subset); } }; ``` 另外一种做法：每次加一个点，把所有大于尾部元素的都加进去 ``` class Solution { public: vector> subsets(vector &nums) { sort(nums.begin(), nums.end()); vector> result = {}; vector subset; dfs(nums, result, subset, 0); return result; } void dfs(vector &nums, vector> &result, vector &subset, int index) { result.push_back(subset); for (int i = index; i < nums.size(); i++) { subset.push_back(nums[i]); dfs(nums, result, subset, i + 1); // 在i后面找 subset.pop_back(); // 回溯 } } }; ``` **18. 子集II** 有重复元素，只要在挑选下一个加入的元素的时候判断一下，重复的就不加进去 ``` for (int i = index; i < nums.size(); i++) { if (i > index && nums[i] == nums[i-1]) continue; subset.push_back(nums[i]); dfs(nums, result, subset, i + 1); subset.pop_back(); } ``` **135. 数字组合** 与 Subsets 比较 * Combination Sum 限制了组合中的数之和 * 加入一个新的参数来限制 * Subsets 无重复元素，Combination Sum 有重复元素 * 需要先去重 * Subsets 一个数只能选一次，Combination Sum 一个数可以选很多次 * 搜索时从 index 开始而不是从 index + 1 **425. 电话号码的字母组合** follow up: 如果有一个词典（Dictionary） 要求组成的单词都是词典里的 如何优化？ 用Trie或者建立一个包含单词所有前缀的hashmap，如果不在前缀map中则剪枝 wordSet = {“hello”, “world”} prefixSet = {“h”, “he”, “hel”, “hell”, “hello”, “w”, “wo”, “wor”, “worl”, “world”} **132. 单词搜索II** 建立perfix map 注意点： 1. 去重。先用一个set保存结果，再转换成vector返回 2. perfix dictionary用一个map，key是单词和其前缀，如果是单词value为true，否则为false **246. 二叉树的路径和II** 在递归的过程中记录从根节点到当前的path。 搜到每一个点的时候我们要查找是否存在以当前点为结束的路径的答案 ``` void search(TreeNode *root, int target, vector &path, vector> &result) { if (root == nullptr) return; path.push_back(root->val); int sum = 0; for (int i = path.size() - 1; i >= 0; i--) { sum += path[i]; if (sum == target) { vector tmp(path.begin() + i, path.end()); result.push_back(tmp); } } search(root->left, target, path, result); search(root->right, target, path, result); path.pop_back(); } ``` **472. 二叉树的路径和III** 嵌套dfs，先dfs找到每个node，再对每个node dfs，分左右上三个方向寻找。注意： 1. 要维护一个prev节点防止走回头路 2. 测试集中有负数，target<=0后不能return要继续找 ### 排列类DFS 排列和组合的区别是排列是有顺序的，而且只取叶子节点 排列的复杂度n! **15. 全排列** 需要一个map记录访问过的元素，回溯不仅要删除子集中的元素，还要删去map中的元素（恢复到和进入函数的时候一样） 复杂度O(N!\*N) **16. 带重复元素的排列** 只需要先排序，再加一个判断： ``` if (i > 0 && nums[i] == nums[i-1] && !visited[i - 1]) continue; // 当前元素和之前元素重复，但是之前元素没访问过（和当前元素处于同一层递归中） ``` #### 旅行商(TSP)问题 经过图上所有的点一次的最短路径 **暴力搜索** 建图（map(node, map(node, distance)) 先把所有点之间的距离设成无限大 dfs找到所有的可行路径，返回最小的一条 **剪枝(prunning)** 参数需要传递path 每次要加入一个新的点的时候，把当前path中最后一个点和前面的所有点交换一次，如果交换完的结果比当前的结果小，说明有更好的路径，当前路径可以被剪去 ``` bool hasBetter(vector &path, int next, unordered_map> &graph) { for (int i = 1; i < path.size() - 1; i++) { if (graph[path[i-1]][path[path.size()-1]] + graph[path[i]][next] <= graph[path[i-1]][path[i]] + graph[path[path.size()-1]][next]) return true; } return false; } ``` **状态压缩动态规划** 状态压缩：不关心顺序，只关心状态是0还是1 利用一个二进制足够长的整数，使用相应的二进制位的状态（0或1）来记录某个点是否被走过 状态表示方法f\[state]\[last]，state用二进制表示，last表示当前path的最后一位 转移方程f\[state]\[i] = min{f\[state-2^(i-1)]\[j] + graph\[j]\[i]} 遍历0到2^n - 1，返回min{f\[2^n - 1]}（所有的点都被走过，state全是1） 复杂度从O(n!\*n)减到O(2^n\*n) **随机化算法** 随机化一个初始方案，通过一个调整策略调整到局部最优值，再时间限制内重复上述过程直到快要超时 遗传算法、模拟退火 ### 非递归实现排列组合 #### 组合 **进制转换** 使用一个 正整数的二进制表示 的第 i 位是 1 还是 0 来代表集合的第 i 个数取或者不取。因为从 0 到 2^n - 1 总共 2^n 个整数，正好对应集合的 2^n 个子集 ``` class Solution { public: /** * @param nums: A set of numbers * @return: A list of lists */ vector> subsets(vector &nums) { vector> result; const int n = nums.size(); sort(nums.begin(), nums.end()); for (int i = 0; i < (1 << n); i++) { vector subset; for (int j = 0; j < n; j++) { if ((i & (1 << j)) != 0) { subset.push_back(nums[j]); } } result.push_back(std::move(subset)); } return result; } }; ``` **基于 BFS 的方法** ``` 第一层: [] 第二层: [1] [2] [3] 第三层: [1, 2] [1, 3], [2, 3] 第四层: [1, 2, 3] ``` 每一层的节点都是上一层的节点拓展而来 ``` class Solution { public: /* * @param nums: A set of numbers * @return: A list of lists */ vector> subsets(vector &nums) { vector> results; sort(nums.begin(), nums.end()); // BFS queue> que; que.push({}); while (!que.empty()) { vector subset = que.front(); que.pop(); results.push_back(subset); for (int i = 0; i < nums.size(); i++) { if (subset.size() == 0 || subset.back() < nums[i]) { vector nextSubset = subset; nextSubset.push_back(nums[i]); que.push(nextSubset); } } } return results; } }; ``` #### 排列 **190. 下一个排列** * 从右往左遍历数组 nums，直到找到一个位置 i ，满足 nums\[i] > nums\[i - 1] 或者 i 为 0 。 * i 不为 0 时，用j再次从右到左遍历 nums ，寻找第一个 nums\[j] > nums\[i - 1] 。而后交换 nums\[j] 和 nums\[i - 1] 。注意，满足要求的 j 一定存在！且交换后 nums\[i] 及右侧数组仍为降序数组。 * 将 nums\[i] 及右侧的数组翻转，使其升序。 **全排列** 使用下一个排列不断寻找新的排列 **197. 排列序号** 只需计算有多少个排列在当前排列A的前面即可。如何算呢?举个例子，\[3,7,4,9,1]，在它前面的必然是某位置i对应元素比原数组小，而i左侧和原数组一样。也即 \[3,7,4,1,X] ， \[3,7,1,X,X] ， \[3,1或4,X,X,X] ， \[1,X,X,X,X] 。 而第 i 个元素，比原数组小的情况有多少种，其实就是 A\[i] 右侧有多少元素比 A\[i] 小，乘上 A\[i] 右侧元素全排列数，即 A\[i] 右侧元素数量的阶乘。 i 从右往左看，比当前 A\[i] 小的右侧元素数量分别为 1,1,2,1，所以最终字典序在当前 A 之前的数量为 1×1!+1×2!+2×3!+1×4!=39 ，故当前 A 的字典序为 40。 ### DFS经典题 **33. N皇后** 入口函数、搜索函数、判断函数、打印函数 复杂度O(S\*N^2)，S为解的个数 优化：可以用一个哈希表保存被占有的格子，优化判断函数 **802. 数独** 暴力法：从上到下从左到右找每个空格，填入合法的数字再继续下一格 搜索顺序优化：优先搜索可能方案少的位置，每次找能填的数最少的格子 ## 数据结构 ### 哈希表 两种冲突解决方式：open hashing (seperate chaining)，close hashing (linear probling) 字符串的hash function: "abc" = (a\*31^2 + b \*31^1 + c\*31^0) % HASH\_SIZE **134. LRU Cache** deque+hashmap node储存prev，next，key，value hashmap储存key to node 每access一个key，把他的node移到最后面。新节点从尾部加入，老节点从头部移走 注意：move to tail之前要先移除当前节点 ``` class LRUCache { public: /* * @param capacity: An integer */ LRUCache(int capacity) { // do intialization if necessary dummy = new ListNode(); tail = new ListNode(); dummy->next = tail; tail->prev = dummy; _capacity = capacity; } ​ /* * @param key: An integer * @return: An integer */ int get(int key) { // write your code here if (dict.find(key) == dict.end()) return -1; ListNode *node = dict[key]; node->prev->next = node->next; node->next->prev = node->prev; moveToTail(node); return node->value; } ​ /* * @param key: An integer * @param value: An integer * @return: nothing */ void set(int key, int value) { // write your code here if (get(key) != -1) { dict[key]->value = value; return; } ​ if (dict.size() + 1 > _capacity) { ListNode *tmp = dummy->next; dummy->next = dummy->next->next; dummy->next->prev = dummy; dict.erase(tmp->key); delete tmp; } ​ ListNode *node = new ListNode(key, value); moveToTail(node); dict[key] = node; } ​ private: class ListNode { public: ListNode(int _key = -1, int _value = -1) : prev(nullptr), next(nullptr), key(_key), value(_value) {} ListNode *prev; ListNode *next; int value; int key; }; ​ void moveToTail(ListNode *node) { node->prev = tail->prev; tail->prev = node; node->prev->next = node; node->next = tail; } ​ ListNode *dummy; ListNode *tail; int _capacity; unordered_map dict; }; ``` 如果只用单链表，map里可以存prev节点 **657. insert delete get random o(1)** 用一个vector和一个map，vector储存元素，map储存{value，index} remove的时候和vector最后一个元素交换，再pop\_back follow up：有重复元素 用 HashMap 存储 number to a list of indices in numbers array. 也就是说，把某个数在数组中出现的所有的位置用 List 的形式存储下来 这样子的话，删除一个数的时候，就是从这个 list 里随便拿走一个数（比如最后一个数） 但是还需要解决的问题是，原来的算法中，删除一个数的时候，需要拿 number array 的最后个位置的数，来覆盖掉被删除的数。那这样原本在最后一个位置的数，他在 HashMap 里的记录就应该相应的变化。 但是，我们只能得到这个移动了的数是什么，而这个被移动过的数，可能出现在好多个位置上，去要从 HashMap 里得到的 indices 列表里，改掉那个 index=当前最后一个位置的下标。 所以这里的做法是，修改 number array，不只是存储 Number，同时存储，这个数在 HashMap 的 indices 列表中是第几个数。这样就能直接去改那个数的值了。否则还得 for 循环一次，就无法做到 O(1) **960. 数据流中第一个独特的数 II** 和lru一个思路，用map+linked list **124. 最长连续序列** 用一个hashset记录所有的数，每次拿出一个数，找到它的所有连续序列，从set中删除 **138. 子数组之和** 定义一个hash表，hash\[sum]=i表示sum这个值是第i个位置的前缀和 循环遍历这个整数数组，计算当前前缀和，如果sum曾在hash中出现，说明区间hash\[sum]+1,i的和为0，否则将sum存入hash ``` vector subarraySum(vector &nums) { // write your code here unordered_map perfix; ​ int sum = 0; for (int i = 0; i < nums.size(); i++) { sum += nums[i]; if (perfix.find(sum) != perfix.end()) return {perfix[sum]+1, i}; perfix[sum] = i; } return {0, nums.size()-1}; } ``` ### 堆 heap和priorityqueue的区别：priorityqueue remove操作是On 注意：priorityqueue默认是大根堆，小根堆要用greater（和sort相反） heapify up O(nlogn) heapify down O(logn) 初始选择最接近叶子的一个父结点，与其两个儿子中较小的一个比较，若大于儿子，则与儿子交换。 交换后再与新的儿子比较并交换，直至没有儿子。 构造一个堆：从 heap 的倒数第二层开始进行 siftdown 操作，复杂度On 堆排序：先构造堆，再从后往前heapify down 遍历堆的复杂度O(nlogn) **545. 前k大数II** Top k在线算法 用一个最大堆维护这些数字，当遇到add(number)这个操作时，就将元素加入到最大堆中，当遇到topk操作时就分K次取出最大堆顶元素，返回这些元素，然后将刚才加入的元素放回最大堆即可 **589. 最大栈** stack+hashset+heap 每次pop或popmax时不要真的删除元素，而是用一个hashset保存被删除的元素。 每次pop、popmax、top和topmax时先调用clearStack和clearHeap，把在set中的点删掉 有重复元素：用一个pair代替int，加上当前元素的id值（被push进栈的顺序，每次push+1） 时间复杂度：每个数之进入stack heap set各一次 push popmax topmax O(logN)，push pop O(1) **828. 字模式** 用两个hash map表示双向映射，如果没有找到映射则加入map中，如果找到了但是不符合映射return false 或者使用一个map一个set记录重复的str #### 外排序 外排序算法（External Sorting） 外排序算法是指在内存不够的情况下，如何对存储在一个或者多个大文件中的数据进行排序的算法。 * 将大文件切分为若干个个小文件，并分别使用内存排好序 * 使用K路归并算法（k-way merge）将若干个排好序的小文件合并到一个大文件中 K路归并算法使用的是数据结构堆（Heap）来完成的。我们将 K 个文件中的第一个元素加入到堆里，每次从堆中选出最小的元素，输出到目标结果文件中，然后如果这个元素来自第 x 个文件，则从第 x 个文件中继续读入一个新的数进来放到堆里，并重复上述操作，直到所有元素都被输出到目标结果文件中。 需要用一个三元tuple（元素，第几个文件，文件中的第几个元素） Follow up: 一个个从文件中读入数据，一个个输出到目标文件中操作很慢，如何优化？ 如果我们每个文件只读入1个元素并放入堆里的话，总共只用到了 1024 个元素，这很小，没有充分的利用好内存。另外，单个读入和单个输出的方式也不是磁盘的高效使用方式。因此我们可以为输入和输出都分别加入一个缓冲（Buffer）。假如一个元素有10个字节大小的话，1024 个元素一共 10K，1G的内存可以支持约 100K 组这样的数据，那么我们就为每个文件设置一个 100K 大小的 Buffer， 每次需要从某个文件中读数据，都将这个 Buffer 装满。当然 Buffer 中的数据都用完的时候，再批量的从文件中读入。输出同理，设置一个 Buffer 来避免单个输出带来的效率缓慢 **577. 合并K个排序间隔列表** 按区间start排序，如果下一个区间的start大于当前区间（result的最后一个）的end，则添加一个新的区间。如果start在当前区间内，当前区间的end更新为max(cur.end, next.end) ## 动态规划 **核心思想：**由大化小，为了长远的利益可以损失当前利益 可以将指数级别复杂度降低到多项式级别 **三种适用场景：** 1. 求最优值 2. 求方案数 3. 求可行性 **三种不适用场景：** 1. 求所有具体方案（用dfs） 2. 输入数据无序（背包问题不适用） 3. 暴力算法的复杂度已经是多项式级别 **递归四要素** 状态——递归的定义 转移方程——递归的拆解 初始化——递归的出口 答案——递归的调用 **时间复杂度**：状态总数\*决策数 动态规划当前状态只能依赖前一个状态，不能有循环依赖！ ### 滚动数组 如果状态依赖关系只在相邻的几层之间 则可以使用滚动数组进行优化 可以把空间复杂度降维。利用取模% 滚动数组只能优化第一个循环，不能优化多个维度 **数字三角形** ``` dp[i % 2][j] = min(dp[(i - 1) % 2][j], dp[(i - 1) % 2][j - 1]) + A[i][j] ``` **斐波那契数列** ``` dp[i % 3] = dp[(i - 1) % 3] + dp[(i - 2) % 3] ``` **骑士的最短路径** ``` dp[i][j] = min{dp[i - 1][(j - 2) % 3], dp[i + 1][(j - 2) % 3], dp[i - 2][(j - 1) % 3], dp[i + 2][(j - 1) % 3]} ``` **01背包** ``` dp[i][j] = max(dp[(i - 1) % 2][j], dp[(i - 1) % 2][j - A[i]] + A[i]) ``` ### 记忆化搜索 将函数的计算结果保存下来，下次通过同样的参数访问时，直接返回保存的结果 记忆化搜索的缺陷：StackOverflow，不适合解决O(n)的dp问题 **829. 字模式II** 1. 本题和字模式I不同,题干没有给出要配对的字符串,因此需要定义一个map类型dict来记录模板pattern中的字母对应配对的字符串,set类型used记录这个配对的字符串是否被枚举过。 2. 对输入的字符串str进行深度优先搜索，传入的参数包括：模板pattern、index\_p、字符串str、index\_s、dict、used； a. 当pattern搜索到末尾且str也搜索到末尾即能完全匹配，返回true，如果一个到末尾另一个没有返回false b. 如果当前模板的字母已经有匹配过字符串word: * 如果word和现应匹配的str不匹配，则返回false；（例如模板为：ABA，字符串为abc，则搜索到第三位时A已经匹配过a，但现在str中是c无法匹配；） * 如果word和现应匹配的str匹配，则递归调用dfs并返回结果，步进为：pattern往后1位，str往后word的长度位数； c. 如果当前模板的字母未匹配过字符串： * 遍历整个str，枚举字符串前缀word的作为匹配； * 若当前的word在set中则证明其已经在b.步骤中完成，可以剪枝； * 将word加入dict和used； * 递归调用dfs并返回结果，步进为：pattern往后1位，str往后word长度位数； * 将word从dict和used中删除； * 若所有的word都无法匹配，返回false **192. 通配符匹配** 如果碰到\*，分成两种情况：\*匹配空或者\*匹配任意数量的字符 用memo记录访问过的pattern str组合 复杂度O（nm） ``` class Solution { public: bool isMatch(string &s, string &p) { map, bool> memo; return helper(s, 0, p, 0, memo); } bool helper(string &s, int s_start, string &p, int p_start, map, bool> &memo) { if (s_start == s.length()) { for (int i = p_start; i < p.length(); i++) { if (p[i] != '*') return false; } return true; } if (p_start == p.length()) { return false; } if (memo.find(make_pair(s_start, p_start)) != memo.end()) { return memo[make_pair(s_start, p_start)]; } bool ret; if (p[p_start] != '*') { ret = (s[s_start] == p[p_start] || p[p_start] == '?') && helper(s, s_start+1, p, p_start+1, memo); } else { ret = helper(s, s_start, p, p_start+1, memo) || helper(s, s_start+1, p, p_start, memo); } memo[make_pair(s_start, p_start)] = ret; return ret; } }; ``` **154. 正则表达式匹配** 1. str匹配完后需要判断余下的pattern是否为空或者是X\*X\*的形式 2. 判断当前pattern的下一个是不是\*，如果是则分为匹配空或者匹配任意数量的字符，如果不是则判断str等于pattern或者pattern等于. ``` if (s_start == s.length()) { // 要满足X*X*的形式 if ((p.length() - p_start)%2 == 1) return false; for (int i = p_start + 1; i < p.length(); i+=2) { if (p[i] != '*') return false; } return true; } ... if (p_start + 1 < p.length() && p[p_start + 1] == '*') { // 匹配0个或者大于等于1个 ret = (s[s_start] == p[p_start] || p[p_start] == '.') && helper(s, s_start+1, p, p_start, memo) || helper(s, s_start, p, p_start+2, memo); } else { ret = (s[s_start] == p[p_start] || p[p_start] == '.') && helper(s, s_start+1, p, p_start+1, memo); } ``` **528. 单词拆分II** 直接使用 memo\[i] 记录从位置 i 开始的后缀 能够被 break 出来的所有方案 ``` class Solution { public: vector wordBreak(string &s, unordered_set &wordDict) { unordered_map> memo; return search(s, wordDict, memo); } vector search(const string &s, const unordered_set &wordDict, unordered_map> &memo) { if (s == "") return {}; if (memo.find(s) != memo.end()) return memo[s]; vector result; if (wordDict.find(s) != wordDict.end()) { result.push_back(s); } for (int i = 1; i < s.length(); i++) { string word = s.substr(0, i); if (wordDict.find(word) == wordDict.end()) continue; string substr = s.substr(i, s.length() - i); vector tmp = search(substr, wordDict, memo); for (string &str : tmp) { result.push_back(word + " " + str); } } memo[s] = result; return result; } }; ``` ### 坐标型 **109. 数字三角形** 状态：坐标 dp\[i]\[j]表示从ij走到最底层的最短路径 方程：从下往上倒过来推导，计算每个坐标到哪去 dp\[i]\[j] = min(dp\[i+1]\[j], dp\[i+1]\[j+1]) + triangle\[i]\[j] 初始化：终点（最后一层) 答案：起点 dp\[0]\[0] ### 接龙型 **76. 最长上升子序列** state: dp\[i] 表示以第 i 个数为龙尾的最长的龙有多长 function: dp\[i] = max{dp\[j] + 1}, j < i && nums\[j] < nums\[i] initialization: dp\[0..n-1] = 1 answer: max{dp\[0..n-1]} 找具体方案：倒推法，记录每个状态的最优值是从哪个前继状态来的 **398. 最长上升连续子序列 II** 一种做法：记忆化搜索 另一种：把二维矩阵打散成为一位数组，数组中每个元素记录二维矩阵中的坐标和高度。 然后把一位数组按照高度排序。 转移方程：f\[i] = max{f\[j] + 1} j < i && nums\[j] < nums\[i] ，且i和j两个点相邻} **603. 最大整除子集** 对数组排序，转换成接龙型动态规划 状态：dp\[i] 表示以i结尾子集最大元素数量 转移方程：Si % Sj = 0 **602. 俄罗斯套娃信封** 先对宽度排序，求高度的最长上升子序列，题目规定宽高均要严格大于，要排除宽度相等的情况 优化：用二分优化最长上升子序列，在dp数组中二分查找第一个大于等于当前数的位置，然后dp\[i]=k，即第i处的最长上升子序列长度为k。 ### 背包型 题目中通常有和与差的概念，数值会被放在状态中 不需要排序！ #### 01背包 **92. 背包问题** 第一种： 状态：dp\[i]\[j]表示前i个数能否凑出j的和 方程：dp\[i]\[j] = dp\[i-1]\[j] (前一个已经能凑出) or dp\[i-1]\[j-A\[i]] (前一个加上当前能不能凑出)。如果j\ O(n\*L) **512. 解码方法** 状态：dp\[i] 表示前i个有多少种解码方法 方程：dp\[i] = dp\[i-1] \* canDecode(最后一个) + dp\[i-2] \* canDecode(最后两个) 初始化：dp\[0] = 1 答案：dp\[n] 可以用滚动数组优化 **437. 书籍复印** 状态：dp\[i]\[j] 表示前i本书分给j个人的最少时间 方程：dp\[i]\[j] = min(max(dp\[prev]\[j-1], sum{prev...i-1})) 初始化：dp\[0]\[j] = 0, 其他 = INT\_MAX 答案：dp\[n]\[k] ## 其他 ### 前缀和 **41. 最大子数组** **贪心法：** 遍历整数数组： * sum累加当前的值； * 若当前 sum>maxAns，更新 maxAns=sum * 若当前 sum<0 ，表示当前的子数组和已经为负，累加到后面会使和更小，因此令 sum=0，相当于放弃当前的子数组，重新开始； **前缀和：** ``` int maxSubArray(vector nums) { //sum记录前i个数的和，maxSum记录全局最大值，minSum记录前i个数中0-k的最小值 int sum = 0, minSum = 0, maxSum = INT_MIN; for (int i = 0; i < nums.size(); i++) { sum += nums[i]; maxSum = max(maxSum, sum - minSum); minSum = min(minSum, sum); } return maxSum; } ``` **944. 最大子矩阵** 构造前缀和： ``` perfix[i][j] = perfix[i][j-1] + perfix[i-1][j] - perfix[i-1][j-1] + matrix[i-1][j-1]; ``` 对于左上角(x1, y1)，右下角(x2, y2)，矩阵和为 ``` perfix[x2][y2] - perfix[x1-1][y2] - perfix[x2][y1-1] + perfix[x1-1][y1-1] ``` 可以固定上下边界，水平方向上用一维数组求解