Leetcode hot100

• 1. 哈希表/集合
  • 1.1. 1.两数之和
  • 1.2. 49.字母异位词分组
  • 1.3. 128.最长连续序列
  • 1.4. 560.和为k的子数组
• 2. 普通栈
  • 2.1. 20.有效的括号
  • 2.2. 155.最小栈
  • 2.3. *394.字符串解码
  • 2.4. 32.最长有效括号
• 3. 堆
  • 3.1. 215.数组中的第K个最大元素
  • 3.2. 347.前K个高频元素
  • 3.3. 295.数据流的中位数
• 4. 双指针法
  • 4.1. 283.移动零
  • 4.2. 11.盛水最多的容器
  • 4.3. 15.三数之和
• 5. 单调栈
  • 5.1. 739.每日温度
  • 5.2. 84.柱状图中的最大矩形
  • 5.3. 42.接雨水
• 6. 单调队列
  • 6.1. 239.滑动窗口最大值
• 7. 滑动窗口
  • 7.1. 3.无重复字符的最长子串
  • 7.2. 438.找到字符串中所有字母异位词
  • 7.3. 76.最小覆盖子串
• 8. 前缀和
  • 8.1. 560.和为k的子数组
  • 8.2. 238.除自身以外数组的乘积
• 9. 动态规划
  • 9.1. 53.最大子数组和
  • 9.2. 45.跳跃游戏 ||
  • 9.3. 70.爬楼梯
  • 9.4. 118.杨辉三角
  • 9.5. 198.打家劫舍
  • 9.6. 279.完全平方数
  • 9.7. 322.零钱兑换
  • 9.8. 416.分割等和子集
  • 9.9. 139.单词拆分
  • 9.10. 300.最长递增子序列
  • 9.11. 152.乘积最大子数组
• 10. 多维动态规划
  • 10.1. 62.不同路径
  • 10.2. 64.最小路径和
  • 10.3. 5.最长回文子串
  • 10.4. 1143.最长公共子序列
  • 10.5. 72.编辑距离
• 11. 矩阵模拟
  • 11.1. 73.矩阵置零
  • 11.2. 54.螺旋矩阵
  • 11.3. 48.旋转图像
  • 11.4. 240.搜索二维矩阵II
• 12. 链表
  • 12.1. 160.相交链表
  • 12.2. 206.反转链表
  • 12.3. 234.回文链表
  • 12.4. 141.环形链表
  • 12.5. 142.环形链表II
  • 12.6. 21.合并两个有序链表
  • 12.7. 2.两数相加
  • 12.8. 19.删除链表的倒数第N个结点
  • 12.9. 24.两两交换链表中的节点
  • 12.10. 25.K个一组翻转链表
  • 12.11. 138.随机链表的复制
  • 12.12. 148.排序链表
  • 12.13. 23.合并K个升序链表
  • 12.14. 146.LRU缓存
• 13. 二叉树
  • 13.1. 94.二叉树的中序遍历
  • 13.2. 104.二叉树的最大深度
  • 13.3. 226.翻转二叉树
  • 13.4. 101.对称二叉树
  • 13.5. 543.二叉树的直径
  • 13.6. 102.二叉树的层序遍历
  • 13.7. 108.将有序数组转换为二叉搜索树
  • 13.8. 98.验证二叉搜索树
  • 13.9. 230.二叉搜索树中第K小的元素
  • 13.10. 199.二叉树的右视图
  • 13.11. 114.二叉树展开为链表
  • 13.12. 105.从前序与中序遍历序列构造二叉树
  • 13.13. 437.路径总和
  • 13.14. 236.二叉树的最近公共祖先
  • 13.15. 124.二叉树中的最大路径和
• 14. 图DFS/BFS遍历
  • 14.1. 200.岛屿数量
  • 14.2. 79.单词搜索
  • 14.3. 994.腐烂的橘子
  • 14.4. 207.课程表
  • 14.5. 208.实现前缀树
• 15. 回溯
  • 15.1. 46.全排列
  • 15.2. 78.子集
  • 15.3. 17.电话号码的字母组合
  • 15.4. 39.组合总和
  • 15.5. 22.括号生成
  • 15.6. 131.分割回文串
  • 15.7. 51.回溯
• 16. 二分查找
  • 16.1. 35.搜索插入位置
  • 16.2. 74.搜索二维矩阵
  • 16.3. 34.在排列数组中查找元素的第一个和最后一个位置
  • 16.4. *33.搜索旋转排序数组
  • 16.5. 153.寻找旋转排序数组中的最小值
  • 16.6. 4.寻找两个有序数组的中位数
• 17. 贪心算法
  • 17.1. 121.买卖股票的最佳时机
  • 17.2. 55.跳跃游戏
  • 17.3. 763.划分字母区间
• 18. 未分类
  • 18.1. 56.合并区间
  • 18.2. 189.轮转数组
  • 18.3. 41.缺失的第一个正数
  • 18.4. 169.多数元素
  • 18.5. 75.颜色分类
  • 18.6. 31.下一个排列
  • 18.7. 287.寻找重复数
• 19. 位运算
  • 19.1. 136.只出现一次的数字

1. 哈希表/集合

1.1. 1.两数之和

• 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

  • 一个hash表记录出现过的（整数，下标），遍历过程中看是否hash表中有key为target - n的项

1.2. 49.字母异位词分组

• 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

  • 遍历字符串数组中的每一个字符串，排序，排序结果作为key，原字符串作为值加入到hash表。返回的时候hash表同一个key的为一组返回

1.3. 128.最长连续序列

• 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

  • 把整数数组nums的元素加到set中，set会排序，然后重新遍历set的元素，每次都向后看能连在一起的是多长并更新最大值

1.4. 560.和为k的子数组

• 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。

  • 计算前缀和，[i - j]的子数组和为k相当于求pre[i] - pre[j - 1] = k，相当于pre[j - 1] = pre[i] - k的pre[j - 1]个数。求前缀和的过程中hash表记录pre[i]值的个数，并统计以i结尾的和为k的个数是hash[pre[i] - k]个

2. 普通栈

2.1. 20.有效的括号

• 给定一个只包括 ’(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。有效字符串需满足：1.左括号必须用相同类型的右括号闭合。2.左括号必须以正确的顺序闭合。3.每个右括号都有一个对应的相同类型的左括号。

  • 遍历字符串s，进行：1.如果是左括号类型则入栈 2.如果是右括号类型，则弹出栈顶，判断栈顶的左括号是否与当前遍历到的右括号匹配。

2.2. 155.最小栈

• 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。实现 MinStack 类:1.MinStack() 初始化堆栈对象。 2.void push(int val) 将元素val推入堆栈。3.void pop() 删除堆栈顶部的元素。4.int top() 获取堆栈顶部的元素。5.int getMin() 获取堆栈中的最小元素。

  • 数据结构：创建两个栈，一个栈放原数据，一个栈放当前的栈中最小值

  • 算法：1. 初始化函数：向最小栈放入INT_MIN 2. put函数：数据栈放数据，最小栈放min(当前数据，最小栈栈顶）3.getMin函数：最小栈栈顶

2.3. *394.字符串解码

• 给定一个经过编码的字符串，返回它解码后的字符串。编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

  • 准备一个string类型的栈，从后往前遍历s字符串，当遍历到除’[‘之外的都把其字符串形式加入栈，如果遇到’[‘则执行以下操作：从栈往前找到’]‘之前的字符串拼接成一个新的字符串ss，然后再往前找数字，每往前遍历一位都加上该数字*10得到要重复的个数，然后将ss重复这个个数得到新的字符串再加入到栈中。由于是从后往前遍历的，最后将栈中的字符串全部弹出并拼接起来就是结果。

2.4. 32.最长有效括号

• 给你一个只包含 ’(’ 和 ’)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

  • 本题主要难点我认为在于如何确定最长一段合法的有效括号的起始，用传统的左括号入栈，右括号匹配最近的出栈显然不能做到找到最长起始。不过很明显第一个无法匹配的右括号是最长的尾，最长的始我们可以人为标记：一开始入栈下标-1，每次匹配完一个最长的之后把那个右边界当作新的-1用。

3. 堆

3.1. 215.数组中的第K个最大元素

• 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

  • 创建一个最小堆，让它的容量控制在k个。对nums数组每个元素，如果堆数量没有超过k个则继续往里面加，超过k个则如果比堆的根节点还大，那么先弹出堆尾再加入该元素，否则舍弃。于是该堆永远维护前k大的元素，取最小堆的堆的根节点就是得到第k大的元素。

3.2. 347.前K个高频元素

• 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

  • 数据结构：一个hash表记录元素和出现的频率，一个最小堆维护频率前k大 算法：类似数组中的第k大元素，维护k个长度的最小堆。

3.3. 295.数据流的中位数

• 中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。实现 MedianFinder 类:1.MedianFinder() 初始化 MedianFinder 对象。2.void addNum(int num) 将数据流中的整数 num 添加到数据结构中。3.double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

  • 数据结构：维护两个堆，l是最大堆，r是最小堆。维护其元素关系：元素总数为偶数，则l = r，取中位数则为l和r堆顶取平均数。如果元素总数为奇数，则l = r + 1，取中位数为l的堆顶。

  • 算法：addNum(int num)函数实现，如果当前l = r，则如果num小于l堆顶则直接加入到l中，如果大于l堆顶则从r中弹出一个元素加到l中，num再加入r。如果l = r + 1同理，想办法加到r里面，并且维护有序性。

4. 双指针法

4.1. 283.移动零

• 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

  • 保持左指针指向所有非零末尾，右指针指向当前正在处理的，所以右指针不断向右移动，当指向非零的则和左指针元素交换并让左指针+1

4.2. 11.盛水最多的容器

• 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。

  • 初始左右指针分别指向数组头和数组尾，每次左指针向右移动一个或者右指针向左移动一个，更新最大值。每次移动长度左右指针中长度小的一定能保证水量不减。

4.3. 15.三数之和

• 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

  • 先排序以便解决重复，先固定第一个维度i，该维度下初始化l，r分别为i + 1和n - 1。在维度i下每次计算nums[i]+nums[l]+nums[r]并与0判断，小于0则l右移，否则r左移。判重方法即根据有序每次检查nums[k] == nums[k - 1]

5. 单调栈

5.1. 739.每日温度

• 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

  • 单调栈呈下降，每次遍历新的元素，弹出当前栈中比自己温度高的元素并给弹出的元素记录结果。最后给栈里没有一直弹出的元素记录结果（利用右边界减去当前元素的下标得到结果）。

5.2. 84.柱状图中的最大矩形

• 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

  • 思路：右边比它小的元素可以直接通过上升单调栈在弹出时确定，左边比它小的元素可以通过上升单调栈相邻的位置确定。所以在一次构造单调栈的过程中可以同时得到左右第一个比它小的元素，两个元素形成的范围再乘以自身高度就是可以围成的最大矩形面积。

  • 算法：构造上升单调栈，遍历每一个元素，如果比栈顶要小，逐个弹出栈顶元素，并在弹出栈顶时计算当前栈顶元素形成的的最大面积：当前元素即右边第一个比它小的元素，它在单调栈中相邻的元素即左边第一个比它小的元素。注意在原数组最前面和最最后加一个0能保证计算所有的矩形面积，不需要考虑边界问题。

5.3. 42.接雨水

• 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

  • 思路：类似于柱状图中的最大矩阵问题，这个是找两边比它大的，有一点不同的是该题要右边是比它大于等于的，保证相同高度只算一次（另外的为0），要不然会重复计算（看leetcode该题目的示例图T型）。另外一个不同就是，当前柱子前面没有比它高的柱子时，无法盛雨水，直接break。且最后留在递减单调栈的那部分也无法盛雨水，可以忽视。

  • 算法：构造下降单调栈，遍历每一个元素，如果大于等于栈顶则逐个弹出栈顶元素，并弹出时计算这部门的面积：左边比它高的柱子和右边大于等于它的柱子取最小值减去自身的高度乘以宽度（如果右边相同高度，则这部门面积为0）。累加计算出来的面积即可。

6. 单调队列

6.1. 239.滑动窗口最大值

• 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。

  • 维护这么一个单调递增的队列：首先创建窗口，每次加入一个新的元素都将比它小的元素全部弹出，直到队列中全是比它大的元素。在后续移动窗口的过程中，重复每次加入一个新的元素都将比它小的元素全部弹出，并且如果当前元素就是队列头元素，则弹出队列头元素，并更新此时的最大值。

7. 滑动窗口

7.1. 3.无重复字符的最长子串

• 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

  • 初始化l,r指针指向字符串s第一个字符，用一个hash表记录当前l-r的字符串每个字符出现的个数。每次r不断右移，当r位置的字符出现个数>1，就不断右移l，直到r位置字符个数 = 1，更新最大值

7.2. 438.找到字符串中所有字母异位词

• 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

  • 定义两个26长度的数组存储s和p当前每个字符出现的次数，首先统计出p的字符出现次数数组，然后l,r利用滑动窗口来遍历s当前窗口并计算字符次数数组，并定义一个check函数检查两个数组是否相等。l左移条件：s上窗口的长度 > p的长度。

7.3. 76.最小覆盖子串

• 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

  • 两个map记录s和t中出现的字符的个数，利用滑动窗口的方法，当r处的字符个数小于l时不断左移l，直到满足。这里要用一个cnt记录当前有多少个字符满足覆盖，统计答案时只有字符满足的个数等于t长度。

8. 前缀和

8.1. 560.和为k的子数组

• 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。

  • 计算前缀和，[i - j]的子数组和为k相当于求pre[i] - pre[j - 1] = k，相当于pre[j - 1] = pre[i] - k的pre[j - 1]个数。求前缀和的过程中hash表记录pre[i]值的个数，并统计以i结尾的和为k的个数是hash[pre[i] - k]个

8.2. 238.除自身以外数组的乘积

• 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

  • 计算前缀和和后缀和，然后两次遍历，当前元素乘以前一个元素的前缀和一遍，当前元素乘以后面一个元素的后缀和一遍。

9. 动态规划

9.1. 53.最大子数组和

• 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。

  • 动态规划转移方程：dp[i] = dp[i - 1] > 0 ? dp[i - 1] + nums[i] : nums[i]

9.2. 45.跳跃游戏 ||

• 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:1. 0 <= j <= nums[i] 2. i + j < n 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

  • dp[i]代表达到i的最小的次数，for j: 0 -> i - 1 dp[i] = min(dp[i], dp[j] + 1)

9.3. 70.爬楼梯

• 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

  • dp[i] = dp[i - 1] + dp[i - 2]

9.4. 118.杨辉三角

• 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。

  • for j : 1 -> i - 1 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]

9.5. 198.打家劫舍

• 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

  • dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])

9.6. 279.完全平方数

• 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

  • for j: 1 -> (i - j * j >= 0) dp[i] = min(dp[i], dp[i - j * j] + 1)

9.7. 322.零钱兑换

• 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。

  • 完全背包最值问题，对于非排序问题在nums维度和target维度没有区别，因为是完全背包问题，所以正序遍历target。dp[i]代表达到面值target的最小的方法数，最值问题所以表达式为for i : 0 -> target : dp[i] = min(dp[i], dp[i - c] + 1)

9.8. 416.分割等和子集

• 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

  • 0/1背包存在问题，问题转化为是否存在几个nums（不重复选取），使得和为总和的一半。因为是0/1背包问题，所以倒序遍历target，并且一开始初始化的值应该均为false。dp[i]代表达到target为i是否存在几个num。存在问题的表达式：for i: target -> 1 dp[i] = dp[i] || dp[i - num]

9.9. 139.单词拆分

• 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

  • 完全背包存在问题，外层循环字符串长度（target，完全背包所以正序），内层循环单词（nums），for w : words 满足可以匹配该段w则dp[i] = dp[i] || dp[i - w]

9.10. 300.最长递增子序列

• 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

  • for j : 0 -> i 如果nums[i] > nums[j] dp[i] = max(dp[i], dp[j] + 1)

9.11. 152.乘积最大子数组

• 给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。子数组 是数组的连续子序列。

  • dp[i][1] 表示：以 nums[i] 结尾的连续子序列的乘积的最大值，dp[i][0] 表示：以 nums[i] 结尾的连续子序列的乘积的最小值。 nums[i] >= 0 则 dp[i][0] = min(nums[i], dp[i - 1][0] * nums[i]) ，dp[i][1] = max(nums[i], dp[i - 1][1] * nums[1])。 nums[i] < 0 则相反

10. 多维动态规划

10.1. 62.不同路径

• 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？

  • dp[i][j] = dp[i-1][j] + dp[i][j-1]

10.2. 64.最小路径和

• 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。

  • dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

10.3. 5.最长回文子串

• 给你一个字符串 s，找到 s 中最长的回文 子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

  • 第一层循环For len 2 -> n 第二层循环 j dp[j][j + len - 1] = dp[j + 1][j + len - 2] && (s[j] == s[j + len - 1])

10.4. 1143.最长公共子序列

• 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

  • dp[i][j]=dp[i−1][j−1]+1, 当 text1[i−1]==text2[j−1];

  • dp[i][j]=max(dp[i−1][j],dp[i][j−1]), 当 text1[i−1]!=text2[j−1]

10.5. 72.编辑距离

• 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作：1.插入一个字符2.删除一个字符3.替换一个字符

  • 若A和B最后一个字母相同：dp[i][j] = dp[i - 1][j - 1]

  • 若A和B最后一个字母不同：dp[i][j] = min(dp[i - 1][j - 1] , dp[i - 1][j], dp[i][j - 1]) + 1

11. 矩阵模拟

11.1. 73.矩阵置零

• 给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

  • 两个bool数组，一个长度m记录当前行是否需要置零，一个长度n记录当前列是否需要置零。第一遍遍历，如果i,j处为0，则行数组i置为true，列数组j置为true。第二遍遍历，i,j置零0的条件是行数组i行或列数组j行为true

11.2. 54.螺旋矩阵

• 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

  • 四个遍历is,ie代表行遍历的头尾，js,je代表列遍历的头尾。按照顺序每次遍历完相应这四个变量中有一个要减1，注意终止条件。

11.3. 48.旋转图像

• 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。你必须在原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

  • 四个角matrix[n - 1 - j][i]，matrix[n - 1 - i][n - 1 - j]，matrix[j][n - 1 - i]，matrix[i][j]

11.4. 240.搜索二维矩阵II

• 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：1.每行的元素从左到右升序排列。2.每列的元素从上到下升序排列。

  • 右上角和左下角的元素，沿行的方向和沿列的方向有一个递增，有一个递减。从这里开始遍历，如果比target小了就沿递增方向移动，如果比target大了就沿递减方向移动，直到一个方向越界

12. 链表

12.1. 160.相交链表

• 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

  • 相交的起始结点记为c，因为c到a链表尾等于c到b链表尾，记为l，所以两个结点都先走完自己链表再走对方链表的长度直到第一次相遇在c所走的长度都是a + b - l

12.2. 206.反转链表

• 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

  • 希望你能把代码背过：1.赋值next结点2.cur指向pre3.更新cur和pre

12.3. 234.回文链表

• 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

  • 遍历一遍得到长度，反转前len/2的链表，取两个新链表的头开始遍历并判断是否相等。注意链表奇数和偶数的区别（区别在后半部分链表遍历的头节点）

12.4. 141.环形链表

• 给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。如果链表中存在环 ，则返回 true 。 否则，返回 false 。

  • 快慢指针，一个一次走两步，一个一次走一步，看快指针最后是空还是跟满指针走到一起

12.5. 142.环形链表II

• 给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。如果链表中有某个节点，可以通过连续跟踪 指针再次到达，则链表中存在环。不允许修改 链表。

  • 快指针b和慢指针a，b一次走两步，a一次走一步，最后a和b相遇，此时a走了A步，b走了B步。B-A = l为环的长度。于是先让b走l步，再让a和b一起走最后相遇的结点就是要求的结点。

12.6. 21.合并两个有序链表

• 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

  • 归并的那一步

12.7. 2.两数相加

• 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

  • 注意进位

12.8. 19.删除链表的倒数第N个结点

• 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

  • 快慢指针，快指针先走n步，然后再一起走，直到快指针为空，返回慢指针。

12.9. 24.两两交换链表中的节点

• 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

  • 背递归解法：1.终止条件: !head || !head->next 2.返回的是新的头节点，即head->next 3. 子递归的头节点是head->next->next 4. 反转head和它的下一个节点的指向 5. head是新头节点的下一个节点，应该指向子递归的新头节点，即head->next = swapPairs(next.next);

12.10. 25.K个一组翻转链表

• 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

  • 单独写一个反转链表函数，每隔k个一组分开（写法:while(n >= k) n-=k），调用该函数，然后再把新的头尾合起来

12.11. 138.随机链表的复制

• 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

  • hash表一一对应，两遍遍历即可

12.12. 148.排序链表

• 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

  • 模拟归并排序

12.13. 23.合并K个升序链表

• 给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

  • 写个合并两个升序数组的函数，然后把这个k个两两合并。如果想要到O(k*logk^n)复杂度可以使用最小堆优化

12.14. 146.LRU缓存

• 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。实现 LRUCache 类：1.LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 2.int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1。 3.void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

  • 数据结构：hash表key->node（O(1)的get），int当前容量和最大容量，双向链表头节点和尾节点

  • 算法：get(key)：hash表直接获取，并将该节点移动到双向链表头 put(key value)：如果hash表存在key，直接替换并移动到双向链表最前面。如果不存在则判断是否超过最大容量，超过则先删除尾节点，添加新的节点到hash表和双向链表头部。 前面提到的移动到双向链表头部是先删除，再加到头部

13. 二叉树

13.1. 94.二叉树的中序遍历

• 给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

  • 递归和非递归

13.2. 104.二叉树的最大深度

• 给定一个二叉树 root ，返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

  • 递归 max(process(root->left), process(root->right)) + 1

13.3. 226.翻转二叉树

• 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

  • 递归，递归翻转左返回左根节点，递归翻转右返回右根节点，最后翻转左右根节点

13.4. 101.对称二叉树

• 给你一个二叉树的根节点 root ， 检查它是否轴对称。

  • 递归，process(左根节点，右根节点) 主函数 return process(root, root)

13.5. 543.二叉树的直径

• 给你一棵二叉树的根节点，返回该树的 直径 。二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。两节点之间路径的 长度 由它们之间边数表示。

  • 递归，在递归求深度函数中，ans = max(ans, depth(root->left), depth(root->right) + 1)。注意最后的结果是ans - 1

13.6. 102.二叉树的层序遍历

• 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

  • BFS，队列，弹出元素然后加入其左右孩子

13.7. 108.将有序数组转换为二叉搜索树

• 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

  • 递归，取m = (l + r)/2，left = process(l, m - 1)，right = process(m + 1, r)，然后m元素作为新的根节点

13.8. 98.验证二叉搜索树

• 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。有效 二叉搜索树定义如下：1.节点的左子树只包含 小于 当前节点的数。2.节点的右子树只包含 大于 当前节点的数。3.所有左子树和右子树自身必须也是二叉搜索树。

  • 递归，process(root->left, lower, root->val) && process(root->right, root->val, upper)

13.9. 230.二叉搜索树中第K小的元素

• 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

  • 中序遍历，n = k时记录结果

13.10. 199.二叉树的右视图

• 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

  • 层序遍历，并且从每一层记录数量，然后遍历这一层时得到最后一个元素

13.11. 114.二叉树展开为链表

• 给你二叉树的根结点 root ，请你将它展开为一个单链表：1.展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。2.展开后的单链表应该与二叉树 先序遍历 顺序相同。

  • 先序遍历，先记录一开始的左右节点，然后接在原来的链表上，再递归遍历左右节点

13.12. 105.从前序与中序遍历序列构造二叉树

• 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

  • 根据前序第一个元素得到根节点，根据中序遍历找到根节点所在位置，从而确定左子树的节点范围和右子树的节点范围，继续递归遍历左子树和右子树。

13.13. 437.路径总和

• 给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

  • dfs(root, target)函数表示以root根为起始点的和为target的路径数量，返回值为dfs(root->left, target - root->val) + dfs(root->right, target - root->val)。则要求的pathSum(root, target)为dfs(root.target) + pathSum(root->left, target - root->val) + pathSum(root->right, target - root->val)

13.14. 236.二叉树的最近公共祖先

• 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

  • process(root, p, q)想清楚该函数的含义：1. 如果 p 和 q 都存在，则返回它们的公共祖先；2.如果只存在一个，则返回存在的一个；3.如果 p 和 q 都不存在，则返回 NULL

  • 算法（process(root, p, q)内)：1.root为空返回空 2. root为p或者root为q向上返回root本身3.递归遍历左右子树得到l,r，如果l和r都不为空说明p,q分别位于左右子树，返回root。如果l，r中有一个为空说明p，q位于一个子树上则返回不为空的那个

13.15. 124.二叉树中的最大路径和

• 二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。路径和 是路径中各节点值的总和。给你一个二叉树的根节点 root ，返回其 最大路径和 。

  • 和二叉树的直径同一道题？递归，在递归求深度函数中，ans = max(ans, depth(root->left), depth(root->right) + 1)。

14. 图DFS/BFS遍历

14.1. 200.岛屿数量

• 给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

  • 图DFS，每次dfs遍历都向四个方向扩散，用一个vis数组记录是否遍历过，一次dfs遍历到的所有1就算一次岛屿。图dfs最简单的写法

14.2. 79.单词搜索

• 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

  • 图DFS，每次dfs遍历都向四个方向扩散，用一个vis数组记录是否遍历过，终止条件是四个方向均无下一个单词，遍历完整个单词则为true

14.3. 994.腐烂的橘子

• 在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：1.值 0 代表空单元格；2.值 1 代表新鲜橘子；3.值 2 代表腐烂的橘子。每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

  • 图BFS，用一个队列表示每一时刻新腐烂的橘子，每一轮都把当前队列的橘子弹出，并将其四周未腐烂的橘子加入队列，同时自己变为已腐烂过状态（以后不会重复加入，也避免使用vis数组）

14.4. 207.课程表

• 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

  • 拓扑排序+BFS：一个队列记录当前入度为0的课程号，用邻接表（一般是map，key为原节点，value为目的节点的集合，不过这里长度确定可以使用节点集合的数组）记录边的关系，一个数组记录每个节点的入度数。每次学习完一个课程后都从邻接表中找到与之相邻的课程让其入度数组减1，如果减到零则加入到队列中

14.5. 208.实现前缀树

• Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。请你实现 Trie 类：1.Trie() 初始化前缀树对象。2.void insert(String word) 向前缀树中插入字符串 word 。3.boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。4.boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

  • 数据结构：自定义Node结构体，成员变量有bool isEnd代表是否是单词结束，有变量Node*[26]向下的孩子节点

  • 算法：1.insert(word)：向下依次创建（如果不存在），在叶子节点让isEnd = true 2.search(word)：向下依次遍历，保证最后叶子节点isEnd = true 3.startsWith(prefix) ：向下依次遍历，不需要保证叶子节点isEnd= true

15. 回溯

15.1. 46.全排列

• 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

  • vis数组法：1. 不排序 2. dfs函数里面for 0 -> n，且!vis的 3. 放入结果条件是tmp数组的length

  • swap法（mysql greedy search）：1. 不排序 2. dfs函数里面for idx -> n，不需要vis ，操作是交换 3. 放入结果的条件是idx = n

15.2. 78.子集

• 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

  • 1. 不含重复元素，所以不排序 2. dfs函数里面 for idx -> n 3. 放入结果的条件是每进入dfs函数都要放入结果

15.3. 17.电话号码的字母组合

• 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

  • 树搜索，string数组可以表示映射关系，每次dfs函数里遍历数组对应string的每个字符向下搜索即可

15.4. 39.组合总和

• 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。对于给定的输入，保证和为 target 的不同组合数少于 150 个。

  • 1. 不含重复元素，不用排序 2. dfs函数里面for idx -> n（因为结果不能重复），且子递归是dfs(idx)而不是dfs(idx + 1)（因为可以重复选取元素）。3. 放入结果的条件是sum = target

15.5. 22.括号生成

• 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

  • 1.dfs函数里面dfs(新的左括号)，if (l > r) dfs(新的右括号) 2. 放入结果的条件是l = r，终止条件是l + r = 2n)

15.6. 131.分割回文串

• 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。回文串 是正着读和反着读都一样的字符串。

  • 1.dfs函数里的for idx -> n 2. 向下递归的条件是 s[idx - i] 是回文序列 3. 放入结果的条件是idx = n

15.7. 51.回溯

• 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ’.’ 分别代表了皇后和空位。

  • dfs 1. 两个维度，行维度写在dfs上，dfs(row)，列维度在dfs里面for循环中for 0 -> col。2. 向下dfs的条件是放在row, col位置满足N皇后不能互相进攻，写一个单独的函数判断（因为dfs遍历所有row维度不会重复，只要判断col维度在它前面的和斜着是否有互相攻击的） 3. 放入结果的条件是row = n

16. 二分查找

16.1. 35.搜索插入位置

• 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。

  • 红蓝染色，l区域：m < target， 返回r

16.2. 74.搜索二维矩阵

• 给你一个满足下述两条属性的 m x n 整数矩阵：1.每行中的整数从左到右按非严格递增顺序排列。2.每行的第一个整数大于前一行的最后一个整数。给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

  • 红蓝染色，先找所在的行（l区域 <= target)，返回l，再找所在的列

16.3. 34.在排列数组中查找元素的第一个和最后一个位置

• 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

  • 红蓝染色，最后一个位置：r区域 m > target，返回l；第一个位置：r区域 m >= target，返回r

16.4. *33.搜索旋转排序数组

• 整数数组 nums 按升序排列，数组中的值 互不相同 。在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

  • 先找旋转点，利用二分的二段性，l区域 nums[m] > nums[0]，l和r区域就是旋转分隔点，之后通过target与nums[0]的关系判断应该是在第一段还是第二段中，然后在这一小段中利用二分查找target

16.5. 153.寻找旋转排序数组中的最小值

• 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

  • 即Leetcode33搜索旋转排列数组的第一步，利用二分的二段性，l区域 nums[m] > nums[0]，如果r = n则说明旋转后跟原来一样，则最小值是nums[0]，否则为nums[r]

16.6. 4.寻找两个有序数组的中位数

• 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log (m+n)) 。

17. 贪心算法

17.1. 121.买卖股票的最佳时机

• 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

  • 数组遍历一遍，同时记录遍历到当前出现过的最小元素和最小元素买入，当前价格卖出能获得的最大利润（先计算理论再求当前最小值）

17.2. 55.跳跃游戏

• 给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

  • 遍历一遍数组，用变量step记录当前能走到的最远的位置，遍历到i位置，如果i < step则false。每到一个位置更新step = max(step, i + nums[i])，最后判断是否step >= n - 1。

17.3. 763.划分字母区间

• 给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。返回一个表示每个字符串片段的长度的列表。

  • 用一个map（或者长度26的数组）统计每个字母最后一次出现的数组位置，后续遍历的过程中，当前片段的结束位置end = max(end, map[c])，直到到end位置换下一个片段即可

18. 未分类

18.1. 56.合并区间

• 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

  • 先对intervals数组以左端点排序，然后遍历排序后的intervals数组，每次取intervals[i - 1]为pre，intervals[i]为cur，如果cur左端点大于pre右端点则合并操作：右端点取pre和cur右端点较大的值，如果不需要合并则将pre加到合并后的数组中

18.2. 189.轮转数组

• 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

  • 定义一个反转数组函数，先全部反转，再反转（0，k%n - 1)，再反转(k%n, n - 1)

18.3. 41.缺失的第一个正数

• 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

  • 假设数组长度为n，那么缺失的第一个正数只可能是[1, n + 1]。遍历一遍数组，将所有负数变为n + 1（对后面统计不会有影响），然后再遍历一遍，找到小于等于n的数，就将对应下标-1的数变为负数，最后遍历一遍找第一个正数并返回下标+1

18.4. 169.多数元素

• 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

  • 排序，取中间元素

18.5. 75.颜色分类

• 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

  • 定义一个left，right指针，维持left左边是0，right右边是2。For i 0 -> n - 1 如果是0则交换i和left，并且让left右移，此时i继续往后遍历（因为被交换过来到i位置的数一定是1，不需要动）。但是如果是2则交换i和right位置并让right左移，同时要让i退回去（这里交换过来的数不能保证是1）

18.6. 31.下一个排列

• 整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。给你一个整数数组 nums ，找出 nums 的下一个排列。

  • 思路：(1)如何使得下一个元素变大：将前面的小元素与后面的大元素交换(2)如何使得找尽可能小的下一个元素：从后往前找第一个升序的元素对（才有的换），让它与从后往前第一个比自己大的元素交换（代价最小的换），然后将其后面的元素（降序排列的）升序排序（即倒置即可）

18.7. 287.寻找重复数

• 给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

  • 数组下标->数字，建立一个链表。如果没有重复数，因为有下标0，所以是个单向链表。但如果有了环，链表就会出现环。所以等价于环形链表题目，通过快慢指针解决

19. 位运算

19.1. 136.只出现一次的数字

• 给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

  • 位运算，相同为0不同为1，所以所有出现两次的数异或起来变为0，0异或一个数还是它本身