leetcode hot 100(1)

leetcode hot 100(1)

哈希

• 1. 两数之和 - 力扣（LeetCode）:略
• 49. 字母异位词分组 - 力扣（LeetCode）：可以用map统计每个单词的字符情况，然后从小到大连接成一个字符串，作为key。比如hello的key就是e1h1l2o1。这样每个key对应一个列表，放key相同的列表
• 128. 最长连续序列 - 力扣（LeetCode）：先将数字记录到map，对每个数字进行遍历，如果一个数字num的前一个数字num-1在map中，就忽略该数字，因为如果从num为起点求最长序列。后面遇到num-1时，又要求一次。所以直接从没有前一个数字的num开始求最长序列。

双指针

• 283. 移动零 - 力扣（LeetCode）：i，j两个指针，i指向非零数字该放到的位置，j指向当前遍历到的数字。当nums[j]为0，就只移动j；如果nums[j]不为0，就swap(nums[i++],nums[j++])。
• 🥇11. 盛最多水的容器 - 力扣（LeetCode）: l、r双指针，计算以l、r为边界的容器的最大容量，记录最大值。当 height[l] < height[r] ，就移动l：l++。否则移动r：r++。
• 🥇 15. 三数之和 - 力扣（LeetCode）：先对数组排序, 然后i遍历数组，对每个i都有双指针l、r指向i+1和n-1。然后就是l、r移动监测和是否为0，如果是，则放入记录。然后继续移动l、r去重，尝试找到更多的组合，直至两个指针相碰。注意去重时的指针移动。
• 🥇42. 接雨水 - 力扣（LeetCode）：对于每根柱子height[i], 在i处能接的雨水等于max{min(leftmax,rightmax) - height[i], 0}。leftmax是i的左边包括i的最大height。同理，rightmax是i的右边包括i的最大height。 左右指针left、right，那边小就移动那个指针，持续更新leftmax和rightmax。

滑动窗口

• 🥇3. 无重复字符的最长子串 - 力扣（LeetCode）: 左右两个指针l、r。用map记录[l,r]区间的字符数字。移动r，如果r所指的字符已存在，就记录当前区间长度。然后再移动 l 直至 r 所指字符在区间[l,r]的个数为1。重复这个步骤，直至j遍历完字符串。
• 🥇438. 找到字符串中所有字母异位词 - 力扣（LeetCode）: 统计p的字符情况，记p的长度为len，然后l、r指针区间长度为len，如果[l,r]的字符情况和p一样，就记录结果。继续左移l、r指针。

子串

• 🥇和为 K 的子数组：前缀和

• 🥇滑动窗口最大值：

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {int n = nums.size();int cur = 0;vector<int> res(n - k + 1);deque<int> dq;for (int i = 0; i < n; ++i) {// dq.back() < i && nums[dq.back()] < nums[i], 此时：// dq.back()要么在(i-k, i]范围内，但是这个范围中最大值肯定不是nums[dq.back()]，因为nums[i]>nums[dq.back()]// dq.back()要么在(i-k, i]不在范围内，更可以删除（如果nums[dq.back()] >= nums[i]，就给下个for循环删除）while (!dq.empty() && nums[dq.back()] < nums[i]) {  dq.pop_back();}dq.push_back(i);if (i >= k - 1) {   // 从第k个数才开始记录while (dq.front() <= i - k) {   // 将超出(i-k, i]范围的数字删除dq.pop_front();}res[cur++] = nums[dq.front()];}}return res;}
};

• 🥇最小覆盖子串：先记录t的字符串情况，左右指针 l、r。向右移动r指针，直至[l,r]区间字符能覆盖t。然后向左移动l指针，直至不能覆盖t。记录区间。反复此步骤，直至r指针到尾

class Solution {
public:string minWindow(string s, string t) {int matchChar = 0;  // 目前已匹配的字符数int res_left = -1;  // 目前匹配的最小区间的左区间int res_len = s.size() + 1; // 目前匹配的最小区间的长度int left = 0, right = 0;    // 滑动窗口map<char, int> tmap;map<char, int> smap;for (char c : t) {tmap[c]++;}while (right < s.size()) {while (right < s.size() && matchChar < t.size()) {  // 一直匹配，直至s[left, right]能完全覆盖，或者right右区间超出范围int cnt = tmap[s[right]];if (cnt > 0) {  // 只记录t有的字符if (smap[s[right]] < cnt) { // 对于重复的字符c，当区间中c的数量已超t中c的数量，就不再增加匹配字符数++matchChar;} ++smap[s[right]];   // 记录区间中的字符对应的数量}++right;}while (matchChar == t.size()) { // 缩小，直至区间不能完全覆盖t（通过匹配字符数来判断）int cnt = tmap[s[left]];if (cnt > 0) {if (--smap[s[left]] < cnt) {--matchChar;}}++left;}if (right - left + 1 < res_len) {   // 记录最小区间[left - 1, right)res_len = right - left + 1;res_left = left - 1;}}if (res_left == -1) {return "";} else {return s.substr(res_left, res_len);}}
};

普通数组

• 53. 最大子数组和 - 力扣（LeetCode）：dp[i]代表以nums[i]最大数组和。dp[i] = max(dp[i - 1], 0) + nums[i]。直接原地修改即可。
• 56. 合并区间 - 力扣（LeetCode）：贪心算法，先按照每个区间的左边界从小到大（尽可能合并多的区间）。记录左边界l、右边界r。对接下来的区间进行判断，如果左边界在l、r之间，就合并区间，如果右边界大于r就更新r。如果左边界大于r，就记录当前l、r为一个合并区间。并且更新l、r为当前区间的左右边界。
• 189. 轮转数组 - 力扣（LeetCode）：向右轮转 k 个位置。记得对k取余。先对后k个元素reverse，再对剩余元素reverse，之后对整改数组reverse。
• 238. 除自身以外数组的乘积 - 力扣（LeetCode）：最简单的用两个数组记录每个数字的左右乘积。或者可以用一个数组记录每个数字的左乘积，然后从右到左遍历，计算答案。剩下一个数组。
• 41. 缺失的第一个正数 - 力扣（LeetCode）：要求不能使用额外空间，那就只能使用原数组记录。假设数组长度为n，则可以记录1-n这n个数字的存在情况。流程：遍历数组，如果当前数字与数组下标不匹配，且当前数字小于等于n，大于等于1，就与以当前数字为小标的数组元素交换。swap(nums[i], nums[nums[i]]) 直至 nums[i] 或者 nums[nums[i]]匹配为止 或者 nums[i] == nums[nums[i]] 。后面遍历数组查看哪个数字缺少。

矩阵

• 73. 矩阵置零 - 力扣（LeetCode）：用第0行和第0列进行记录，用两个变量记录第0行和第0列是否需要置0.
• 54. 螺旋矩阵 - 力扣（LeetCode）：略。
• 48. 旋转图像 - 力扣（LeetCode）：将图像（矩阵）顺时针旋转 90 度。观察前后。一般是行或者列互换，然后对角线或者反对角线互换。具体略。
• 240. 搜索二维矩阵 II - 力扣（LeetCode）：从矩阵的右上角开始搜索，就能利用矩阵的有序特性。

链表

• 相交链表：找出相交点，可以先计算长度，让较长的链表先走，然后再一起走
• 反转链表：没什么好说的。迭代和递归都要懂
• 环形链表：快慢指针一起跑就好了，能碰到就代表有环
• 环形链表 II：不止要判断是否有环，而且要给出环的入口。先判断有环，有环后再让一个指针从头开始，然后快慢指针一步步走，碰到的就是环的入口（难的是数学证明）
• 合并两个有序链表：没什么好说的
• 两数相加：将和存到list1就好了，记录进位，到最后，如果还有进位还是1，就新增
• 删除链表的倒数第 N 个结点：注意边界情况，则链表长度是否大于等于N。a先走到第n个点，b开始指向链表头，a、b开始一起一步步走，b到链表尾，a就是结果。l = n + m，倒数第n，就是正数第l-n(m)，a先走n，b再下场，这样一起走，a后面刚好走l-n到链表尾，b刚好到第l-n个点
• 两两交换链表中的节点：就是有点恶心，本身不难。迭代很恶心，递归简单一点。
• K 个一组翻转链表：其实就是上一题的进阶，用递归简单点，先判断当前节点开头的链表是否有k个，不够直接返回，够的话先记下这k个节点的开头s和结尾e，翻转这个区间，然后对e->next递归调用，得到结果i，然后链接s->next=i,返回e
• 随机链表的复制：随机链表其实就是比普通链表多了一个random节点，然后这个random节点随机指向链表中的一个节点。可以用一个map保存旧节点映射到新节点的，第一次就按普通链表复制，第二次遍历旧链表，查看random链接情况，根据map，按照映射关系链接新节点的random
• 排序链表：n^{2要么用插入、要么冒泡。nlogn：自底向上的归并。n}2：自顶向下的归并（先快慢指针划分链表，然后递归对两个链表排序）
• 合并 K 个升序链表：就是合并两个升序链表的升级，两两合并就好。但是一般是选择当前最短的两个链表合并，这个可以通过堆来完成。
• LRU 缓存：经典题目，值得背诵。首先要记得是map+双链表完成的。越接近链表头部，就是最近用的。map存的是key到链表节点的映射，链表存的是key和value
  • put操作：
    • key已存在时，通过key获取到节点node，更新value，然后将node移动到链表头
    • key未存在时，且未满时，新建节点node，将node插入到链表尾，并且更新map（添加key到node的映射）
    • key未存在时，且已满时，同上上面的情况一样（新建节点node，将node插入到链表尾，并且更新map（添加key到node的映射）），只是要将将链表尾节点从链表删除，更新map（删除链表尾节点中的key到链表尾节点的映射）
  • get操作：
    • 通过key获取到节点node，获取value，然后将node移动到链表头
  • 链表设计：强烈建议一个head一个tail作为头尾，并实现以下函数：
    • removeNode(node) : 移除节点node
    • removeTail(): 移除尾部节点（不是tail，而是tail->prev）
    • addToHead(node): 往链表头部插入节点node
    • moveToHead(node): 将node从原来位置删除，并插入到链表头

请你设计并实现一个满足 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) 的平均时间复杂度运行。

二叉树

• 二叉树的中序遍历、前序遍历、后序遍历：

递归不解释，迭代：

主要用栈模拟递归过程，注意就是节点访问(visit)和出栈的时机

前序：visit：入栈前先visit，出栈：当一直往左走，无路可走时，出栈一个节点，取其右孩子（注意，栈中的节点都是已经访问过的）

中序：visit：出栈之后再visit，出栈：当一直往左走，无路可走时，出栈一个节点，取其右孩子（注意，栈中的节点都是没有访问过的，并且他们的左孩子都已入栈）

后序：这个有点特殊，需要用一个prev节点记录上一次visit的节点，这样当root->right == prev，证明root可以出栈，也可以访问了。

• 二叉树的最大深度: 三种做法：bfs统计层数，后序遍历迭代法，dfs递归
• 翻转二叉树：先反转左右子树，然后递归遍历左右子树
• 对称二叉树：将根节点的左右子树作为两棵树进行递归对比
• 二叉树的直径：经过当前节点的最大直径，就是左右子树的深度之和，这样在递归求深度的过程中，记录每个节点的左右子树的深度之和，这样就能得出答案。
• 二叉树的层序遍历：略
• 将有序数组转换为二叉搜索树：划分数组，将中间节点作为当前的根节点，左右两边数组作为左右子树，继续递归
• 验证二叉搜索树：给对每个节点给定一个值的范围，超出这个范围，则代表不是bst，然后递归对左右子树进行这个操作
• 二叉搜索树中第K小的元素：中序遍历，用一个标记变量标记当前是走到第几个节点
• 二叉树的右视图：层次遍历，每层从左到右遍历，每次取最后一个元素
• 二叉树展开为链表：递归前序遍历，用一个指针的指针prev记录前一个访问的节点，对每个节点root，prev->right = root； root->left = nullptr; 左右子树递归
• 从前序与中序遍历序列构造二叉树：略
• 路径总和 III：前缀合求，但是注意什么时候加，什么时候减。
• 二叉树的最近公共祖先：递归，略。
• 二叉树中的最大路径和:递归。辅助函数：求从root开始的最大路径和rootPathSum。先递归求左右子树的，则从当前root开始的最大路径和为prootsum = root->val + max(rightsum, leftsum)，记录最大的路径和为 max( prootsum , root->val + rightsum + leftsum).注意空节点返回0，左右和先和0比较
• 51. N 皇后 - 力扣（LeetCode）：就用一个大小为n的数组，记录每一行中，皇后放在那一列。注意对角线检测。