LeetcodeHOT100刷题笔记

LeetcodeHOT100刷题笔记

0. 算法思想总结(⭐表示重要程度，⭐越多面试越容易考到)

  1. 两数之和
    • 使用HashMap存储数组元素，查询map中是否存在target-nums[i]
  2. 字母异位词分组
    • 转换为字符数组使用Arrays.sort()进行排序，排序后查询哈希表，放入HashMap<String,List<String>>中，键为排序后字符串，值为原始字符串的集合
  3. 最长连续序列 ⭐
    • 使用HashSet去重后，遍历HashSet
    • 当nums[i]-1不存在时，开始从nums[i]往后查询
    • 不断查询nums[i]+1,nums[i]+2...
  4. 移动零
    • 第一遍遍历： j初始为0，j 作为非零元素的插入位置，把所有 非零元素 依次填入 nums[j]
    • 第二遍遍历： 把 j 之后的元素全部填 0。
  5. 盛最多水的容器
    • left从左，right从右向中间移动，计算区间面积，每次计算后移动高度较小的指针，向中间靠拢
  6. 三数之和 ⭐
    • 先排序，三个指针：
      • i : 从0到nums.length-2遍历
      • left: 从i+1往后遍历
      • right：从nums.length-1往前遍历
    • 如果sum=0: left++,right–; 如果sum>0: right–; 如果sum<0: left++;
    • i 在遍历时，跳过相同的 nums[i]; left 和 right 指针移动时，也要跳过重复值。
  7. 接雨水
    • 水的面积=全部面积-柱子的面积
      • 全部面积 += 每一层的长度*1
  8. 无重复字符的最长字串 ⭐⭐⭐⭐
    • 用一个集合ArrayList维护当前的无重复子串,遍历字符串，如果当前字符已在list集合中重复，记录当前最大值，删除list中重复元素及以前的元素，添加当前元素
  9. 找到字符串中所有字母异位词
    • 滑动窗口 + 频率数组比较；维护两个长度为26的数组来比较窗口内的字符频率是否和 p 匹配，每次移除窗口左边的元素，添加新字符到窗口的右侧
  10. 和为K的子数组
    • 前缀和 + 哈希表
      • 哈希表：Key存储前缀和，Value存储这个前缀和出现的次数
      • 通过 prefixSum - k 计算是否有之前的前缀和能构成和 k 的子数组
      • preSum - k = (前面一个preSum索引,当前索引)的子数组之和
      • 加上之前的前缀和出现的次数即可
      • 注意：哈希表要添加： map.put(0,1)
  11. 滑动窗口最大值
    • 单调双端队列：使用双端队列(Deque)存储索引，在遍历数组时始终保持队列中元素对应的值单调递减，并在每次滑动窗口形成后，通过队头索引快速获取当前窗口的最大值，同时移除队头已滑出窗口范围的元素和队尾比当前元素小的元素
    • 如何更新队头的最大值？
      • 当新元素来的时候，从队尾往队头移动，把小于新元素的元素全部出队，然后从队尾入队
  12. 最小覆盖子串 ⭐⭐
    • 滑动窗口+哈希表
      • 一个哈希表记录t的字符出现的次数，另一个哈希表记录s当前窗口的字符出现的次数
      • 右指针right先往右移动，直到包含t所有的字符(借助valid记录窗口内满足条件的字符数)，记录当前最短子串的右边界
      • 左指针left收缩窗口，尝试寻找更短的子串，记录当前最短子串的左边界
  13. 最大子数组和
    • 局部最优 -> 推导全局最优 sum+=当前元素，如果sum>max，更新max；如果sum<0，将sum重置为0(因为前面的子数组对后续没有正向贡献)
  14. 合并区间 ⭐⭐⭐
    • 先根据start排序：
    • 初始化结果集合，加入第一个区间
    • 遍历剩余区间：
      • 如果当前区间和结果中的最后一个区间有重叠（即：上一个区间的 end >= 当前区间的 start）
        • → 合并两个区间（更新 end 为两者最大值）
      • 否则直接加入结果集合（无重叠）
  15. 轮转数组
    • 三次翻转法：
      • 先整体翻转数组；再翻转前 k 个元素；最后翻转后 n-k个元素；
    • 注意： k可能大于数组长度，所以要先对数组长度取模(k%=nums.length;)
  16. 除自身以外数组的乘积
    • 前缀积和后缀积：第一次从前往后遍历，构建结果数组每个位置前缀乘积，第二次从后往前遍历乘上后缀乘积
  17. 缺失的第一个正数 ⭐
    • 将[8,2,0,1,3,4]遍历转换为[1,2,3,4,0,8],通过原地交换的方式将正整数放到对应的位置上，然后从头遍历找到第一个不符合的正数
  18. 矩阵置零
    • 利用矩阵的第一行和第一列作为标记位来记录哪一行、哪一列需要被置 0 注意： 标记记录的过程中应该跳过第一行和第一列
  19. 螺旋矩阵 ⭐
    • 定义top, bottom, left, right四个边界变量控制遍历范围
    • 按照 右 → 下 → 左 → 上 的顺序依次遍历矩阵的元素
    • 注意：最后两个遍历(往左和往上)要判断是否还有行或列剩下
  20. 旋转图像
    • 旋转=转置+翻转
      • 先转置：将 matrix[i][j] 变成 matrix[j][i]。
      • 再水平翻转：让 matrix[j][i] 变成 matrix[j][n-1-i]。
  21. 搜索二维矩阵-ii
    • 从右上角出发，向下或向左移动，相等时返回true
  22. 相交链表
    • 双指针一块走，当 pA 走到尾巴 null，它就切换到 headB 重新开始。当 pB 走到尾巴 null，它就切换到 headA 重新开始。如果两个链表有交点，那么两个指针一定会在交点相遇。如果没有交点，最终两个指针都会走到 null
  23. 反转链表 ⭐
1
2
3
4
5
原链表:1→2→3→4
1: null←1 2→3→4
2: null←1←2 3→4
3: null←1←2←3 4
4: null←1←2←3←4
  1. 回文链表
    • 先用快慢指针找中点，把中点以后的链表反转，再比较反转后的一半链表和原链表的前一半
  2. 环形链表
    • 快慢指针找环：如果相遇了返回true
  3. 环形链表-ii ⭐
    • 当快慢指针相遇时：定义一个指针从相遇点开始走；另一个指针从链表头开始走，他们会在环的入口点相遇
  4. 合并两个有序链表 ⭐⭐⭐
    • 使用虚拟头结点，双指针遍历两个链表；谁的值小，就连接谁；遍历完一个，直接连接另一个
  5. 两数相加
    • 创建一个新链表记录两个链表之和，注意进位
  6. 删除链表的倒数第n个结点 ⭐⭐⭐⭐⭐
    • 创建一个dummy,快慢指针指向dummy；快指针先走n+1步，然后快慢指针一起移动直到快指针为null，此时慢指针的位置就是要删除结点的前一个结点位置
  7. 两两交换链表中的节点
    • 模拟即可
  8. k个一组翻转链表 ⭐⭐
    • 反转+找到K个结点一组即可，每次记录开始结点和终止结点
  9. 随机链表的复制
    • 使用 HashMap 存储旧节点与新节点的对应关系，并分两步完成链表复制
  10. 排序链表
    • 插入排序/归并排序
      • 使用快慢指针找到链表中点，将链表以中点拆分成左右链表递归排序，将两个链表合并成有序链表
  11. 合并k个升序链表
    • 使用最小堆(优先级队列)维护k个链表的当前最小节点，每次出队最小结点，入队最小结点的下一个结点，直到队列为空
  12. lru缓存
    • 定义双向链表维护缓存队列，定义哈希表维护当前队列的键和值，并提供快速查找结点
  13. 二叉树的中序遍历
    • 左根右递归
  14. 二叉树的最大深度
    • 当前节点为空返回0，递归计算左右子树的深度，取左右子树的较大值加1
  15. 翻转二叉树
    • 递归交换左右子树即可
  16. 对称二叉树 ⭐
    • 两个子树都为空则对称
    • 如果左右子树都不为空且值相等，同时左树的右子树和右树的左子树对称，同时左树的左子树和右树的右子树对称，则对称
  17. 二叉树的直径
    • 递归计算每个节点的左右子树的最大深度，当前节点的直径=左子树深度+右子树深度，更新最大直径
  18. 二叉树的层序遍历
    • 使用队列存储每层的结点，使用size记录当前层结点的个数，循环出队层中的结点，入队下一层左右子树的结点，直到队空为止
  19. 将有序数组转换为二叉搜索树
    • 以数组的中间元素作为root结点，左区间递归构造左子树root.left,右区间递归构造右子树root.right，直到数组区间索引left>right终止
  20. 验证二叉搜索树
    • 构建子树的大小边界，左右子树的值在边界外返回false，递归遍历左右子树
  21. 二叉搜索树中第k小的元素
    • 二叉搜索树用中序遍历即为一个升序的数组，直接计数到第k个遍历的结点时，返回当前元素即可
  22. 二叉树的右视图 ⭐
    • 使用队列进行层序遍历，找到每层最右边的结点即可
  23. 二叉树展开为链表
    • 创建一个新结点，使用新结点的右子树连接当前root结点，然后前序遍历递归连接root的左子树、root的右子树
  24. 从前序与中序遍历序列构造二叉树
    • 哈希表存储中序数组便于查找索引，前序数组第一个元素就是根节点，使用中序数组划分左右子树后进行递归构建左右子树
  25. 路径总和-iii
    • 使用哈希表存储前缀和出现次数，
    • backtracking(){终止条件{在哈希表找到(当前路径总和-目标值)的次数加到结果}，在哈希表添加当前路径总和，递归左右子树，回溯撤销哈希表添加的当前路径总和}
  26. 二叉树的最近公共祖先 ⭐
    • 先判断当前结点是否是p或q，再递归判断左右子树，分为左右子树都找到了结点，左右子树只有一个找到了，左右子树都没找到四种情况
  27. 二叉树中的最大路径和 ⭐
    • 用一个全局变量记录最大值，递归记录左右子树的最大贡献，更新最大值，返回当前结点能为父节点的最大路径值(只能选左右子树的其中一个贡献大的子树)
  28. 岛屿数量 ⭐
    • 若当前元素为’1’则计数加1，并递归的感染周围的元素为’2’，防止重复计数
  29. 腐烂的橘子
    • 先把当前状态转换替代成其他值，用时间标记当前腐烂的橘子，下一轮腐烂的橘子=当前time+1，直到没有新橘子被感染跳出循环
  30. 课程表
    • 判断一个有向图是否有环，不会….
  31. 实现trie前缀树
    • 面试会考吗？不会》….
  32. 全排列
    • 用一个boolean数组visited保存已经访问的元素，下次循环直接跳过；回溯三部曲：终止条件，for循环递归，回溯撤销
  33. 子集
    • 收集子集，for(){收集元素，递归到下一层元素，回溯撤销}
  34. 电话号码的字母组合
    • 通过回溯法依次遍历输入数字串 digits，从第一个数字开始，根据数字映射的字母表，逐个尝试每个字母，将其加入当前路径 path，然后递归处理下一个数字。当遍历到路径长度等于输入长度时，说明已生成一个完整组合，将其拼接成字符串加入结果列表 result，随后回退（撤销最后一个字符）继续尝试其它可能，直到穷尽所有组合。
  35. 组合总和 ⭐
    • 当前缀和等于target时，终止递归；for(){添加当前元素，递归进入下一层，回溯撤销}
  36. 括号生成
    • 当左右括号用完了终止递归加入结果(left==0&&right==0)
    • 当左括号数量大于0可以选择左括号
    • 当右括号剩余数量大于左括号剩余数量，可以选择右括号，然后添加递归回溯
  37. 单词搜索
    • 通过双重循环遍历二维字符数组的每个元素，找到与单词首字符相同的位置后，调用递归函数向上下左右四个方向查找下一个字符，每访问一个字符就将其暂时标记为已访问（用 # 替换），防止重复走回头路，递归如果找到完整单词则返回 true，未找到则恢复该位置原字符，继续尝试其他路径，直到所有可能都搜索完毕。
  38. 分割回文串
    • 通过从字符串的起始位置开始，用循环依次截取不同长度的子串，判断当前子串是否是回文串，如果是则将其加入路径列表，并递归继续处理剩余部分，直到遍历完整个字符串，将完整路径加入结果列表，递归返回时通过 removeLast() 撤销上一次添加的子串，继续尝试下一种截取方式。
  39. n皇后
    • 循环尝试在棋盘的每一行每一列放置皇后，遇到符合条件的位置就将皇后放下，并递归进入下一行继续放置，直到所有行都放置完毕时将当前棋盘状态转换成字符串列表加入结果集中，递归返回时通过将皇后位置回溯复原，继续尝试下一列的位置，最终遍历出所有可能的皇后摆放方案。
  40. 搜索插入位置
    • 二分查找
  41. 搜索二维矩阵
    • 二分查找：从右上角元素向下或向左移动
  42. 在排序数组中查找元素的第一个和最后一个位置
    • 二分查找先查找第一个位置，再查找结束位置
    • 查找左边位置时，当nums[mid] == target，right = mid - 1不断向左收缩
    • 查找右边位置时，当nums[mid] == target，left = mid + 1不断向右收缩
  43. 搜索旋转排序数组
    • 直接对数组进行二分，其中一定有一个子区间是有序的，另一个部分有序
    • 判断哪个区间是有序的，然后继续进行逻辑判断
  44. 寻找旋转排序数组的最小值 ⭐
    • 如果 nums[mid] > nums[right]，最小值一定在右边，left=mid+1
    • 如果 nums[mid] <= nums[right]，最小值在左边，right=mid
    • 退出循环时，left == right，正是最小值的位置
  45. 寻找两个正序数组的中位数
    • 暴力依次从前往后走 mid 步，此时是O(m+n)
  46. 有效的括号
    • 遇到左括号入栈，右括号如果能与栈顶左括号匹配则正确，不匹配返回false
  47. 最小栈
    • 用一个链表包含val和min两个成员变量，min用来保存最小值，入栈就是链表头结点头插一个新元素，出栈就是指向头结点下一个结点
  48. 字符串解码
    • 难，使用两个栈
  49. 每日温度
    • 使用一个单调递减的栈，栈用来存储索引
    • 如果当前温度小于等于栈顶温度则入栈
    • 当前温度大于栈顶元素，栈顶元素的天数更新并出栈
  50. 柱形图中最大的矩形
    • 双指针暴力，以当前柱子向左向右，找比自己高度大(大于等于)的柱子，计算当前面积并更新
  51. 数组中的第k个最大元素 ⭐⭐⭐
    • 使用小顶堆，堆顶元素始终是最小的元素，如果当前元素大于堆顶元素，堆顶元素出堆，当前元素入堆，最后堆顶元素就是第k个大的元素；换句话说就是用小顶堆把k-1个小的元素挤出去
  52. 前k个高频元素
    • 哈希表统计频率，用小根堆维护前k个高频元素
    • PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(k,(l1, l2) -> l1.getValue() - l2.getValue());
    • for (Map.Entry<Integer, Integer> entry : map.entrySet()) {}
  53. 数据流的中位数 ⭐
    • 利用两个堆（大根堆+小根堆），
    • 添加元素先添加到小顶堆，再把小顶堆的堆顶元素添加到大顶堆，
    • 如果小顶堆大小小于大顶堆大小(minHeap.size() < maxHeap.size())，把大顶堆的堆顶元素添加到小顶堆
  54. 买卖股票的最佳时机
    • 要想卖的时候利润最多，就要在之前最便宜的时候买入，因此维护之前的最小值即可。
  55. 跳跃游戏
    • 维护一个 farthest 变量，记录能跳到的最远距离
    • 如果当前索引超过了能跳到的最远距离，则跳不到终点
  56. 跳跃游戏-ii
    • 局部最优，找到下一个能跳的最远的位置，找最大的(下一个位置索引加上下一个位置最大跳跃距离)
    • 如果当前位置已经能到达终点，count++,跳出循环
  57. 划分字母区间
    • 使用哈希表保存每个字符的最后出现位置
    • 若发现某个字符的最后出现位置超出了当前片段范围，则更新 nextIndex
  58. 爬楼梯 ⭐
    • dp[i]： 爬到第i层楼梯，有dp[i]种方法
  59. 杨辉三角
    • dp[i][j] 代表第i行第j列元素的值
    • dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
  60. 打家劫舍
    • dp[i]：盗窃到第i间房间所获得的最高金额
    • dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])
  61. 完全平方数
    • 转换为完全背包问题
      • dp[i][j] 表示使用前 i 个完全平方数（1^2, 2^2, …, i^2）凑出 j 需要的最少个数。
      • 不选当前平方数 i^2：dp[i][j] = dp[i-1][j]（继承上一行）。
      • 选择当前平方数 i^2：dp[i][j] = dp[i][j - square] + 1（选 i^2 之后，继续凑 j - i^2）
  62. 零钱兑换
    • 转换为完全背包问题
    • dp[i][j]：用前 i 种硬币，凑成金额 j 所需的最少硬币数量
  63. 单词拆分
    • dp[i] 表示字符串 s 的前 i 个字符是否可以由字典中的单词拼接而成
    • dp[i]的值依赖于i之前某个 dp[j] == true，说明 s[0 ~ j-1]可以用字典单词拼接。 s.substring(j, i) 必须在 wordDict 里面，说明 j~i-1 这一段是一个合法单词
  64. 最长递增子序列
    • dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
    • 两次遍历：第一次遍历求每个以 nums[i] 结尾的最长递增子序列，第二次遍历i之前的元素，比较元素是否加入当前元素的后面作为结尾
  65. 乘积最大子数组 ⭐
    • 用max和min维护遍历到当前元素时的最大值和最小值
    • 如果当前元素是负数，那么会导致最大的变最小的，最小的变最大的。因此交换两个的值。
    • max = Math.max(max * nums[i], nums[i])
      • 对于每一个 nums[i]，最大乘积有两种选择：
      • 1️⃣ 继续累乘：max * nums[i] —— 把前面的乘积继续乘上这个 nums[i]，不切断子数组。
      • 2️⃣ 重新开始：nums[i] —— 从当前位置 i 开始一个新的乘积子数组。
  66. 分割等和子集
    • 转换为0-1背包问题
    • dp[i][j]：从前 i 个数里，能否选出一些数，使它们的和接近j
  67. 最长有效括号 ⭐
    • dp[i] 表示以下标 i 结尾的最长有效括号子串的长度，主要在于分情况讨论
    • 当 s[i] == '(' 时
    • 当 s[i] == ')' 时
      • 如果 s[i-1] == '('
      • 如果 s[i-1] == ')'
      • 如果 s[i - dp[i-1] - 1] == '('
  68. 不同路径
    • dp[i][j]代表到达第i行第j列的不同路径有多少个
  69. 最小路径和
    • dp[i][j]:走到第i行第j列时的最小总和
  70. 最长回文子串 ⭐⭐
    • 定义 dp[i][j] 表示字符串从索引 i 到 j 的子串是否是回文子串
    • 更长的子串，s[i] == s[j] 时，它是否回文取决于 s[i+1:j-1] 是否回文串
    • 外层循环 i 递减（从后往前遍历）,内层循环 j 递增（从左到右遍历）,因为 dp[i][j] 依赖于 dp[i+1][j-1]
  71. 最长公共子序列 ⭐⭐⭐
    • dp[i][j]: text1前i个字符串和text2前j个字符串的最长公共子序列长度
    • 如果i和j的字符相同，dp[i][j] = dp[i - 1][j - 1] + 1
    • 如果i和j的字符不相同，dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
  72. 编辑距离 ⭐
    • dp[i][j] 表示 word1 的前 i 个字符转换成 word2 的前 j 个字符的最小操作数
    • 如果i和j的字符相同，dp[i][j] = dp[i - 1][j - 1]
    • 如果i和j的字符不相同
      • 替换操作：dp[i-1][j-1] + 1
      • 删除操作：dp[i-1][j] + 1
      • 插入操作：dp[i][j-1] + 1
  73. 只出现一次的数字
    • 使用异或运算符(^)，a^a=0,a^0=a
  74. 多数元素
    • res=当前元素，用一个计数器，当出现自己时，计数+1，不是自己计数-1，当计数器=0时，重新把res置为当前元素
  75. 颜色分类
    • 两个指针：一个指针指向0位置，依次存储0元素，一个指针指向数组结尾位置，依次存储2元素
  76. 下一个排列
    • 2, 6, 3, 5, 4, 1 --> 2, 6, 4, 1, 3, 5 分为以下几步：
      1. 从后往前找到3
      2. 从后往前找，找到第一个大于3的数：4
      3. swap(3,4)，此时：2, 6, 4, 5, 3, 1
      4. 最后反转5，3，1即可得到2, 6, 4, 1, 3, 5
  77. 寻找重复数
    • 快慢指针找环，相遇之后，将fast重新置为0，两个指针每次移动一步，再次相遇就是重复数所在位置
    • fast = nums[nums[fast]] // 快指针每次移动两步
    • slow = nums[slow] // 慢指针每次移动一步
  1. 合并两个有序数组 ⭐
    • 双指针从后往前合并，避免覆盖还没处理的数据
  2. 字符串相加 ⭐⭐
    • 从 num1 和 num2 的末尾开始，一位一位相加,记得进位
  3. 最小k个数 ⭐
    • 使用大顶堆（PriorityQueue）来筛选数组中最小的 k 个数
  4. 买卖股票的最佳时机-ii
    • 贪心：只要今天比昨天大，就卖出
  5. 最大数
    • 使用自定义排序规则：Arrays.sort(strNums,(a,b)->(b+a).compareTo(a+b));
  6. 最长公共前缀
    • 用第一个字符串的每个字符，依次与后面所有字符串的相应字符进行比较即可
  7. 重排链表 ⭐⭐⭐⭐⭐
    • 重排链表=找链表中点+反转链表+合并链表
  8. 复原ip地址
    • 回溯算法
  9. 排序数组
    • 快速排序：O(nlogn)
  10. 多线程交替打印ab
    • synchronized+wait()/notify()

1. 两数之和

  • 一句话总结：使用HashMap存储数组元素，查询map中是否存在target-nums[i]

1.1 题目描述

  • 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
  • 你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素
  • 你可以按任意顺序返回答案。

1.2 算法思想和代码实现

1.2.1 暴力枚举法

通过两层循环遍历数组的每一对元素，判断它们的和是否等于目标值 target。如果找到符合条件的两个数，你就将它们的下标保存在结果数组中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    result[0] = i;
                    result[1] = j;
                }
            }
        }
        return result;
    }
}

1.2.2 哈希表实现

使用 哈希表（HashMap） 来实现 O(n) 的时间复杂度

1
2
3
4
5
6
7
8
9
10
public static int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        if (map.containsKey(target - nums[i])) {
            return new int[]{map.get(target - nums[i]), i};
        }
        map.put(nums[i], i);
    }
    return new int[0];
}

2. 字母异位词分组

  • 一句话总结：转换为字符数组使用Arrays.sort()进行排序，排序后查询哈希表，放入HashMap<String,List<String>>中，键为排序后字符串，值为原始字符串的集合

2.1 题目描述

  • 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
  • 字母异位词： 是由重新排列源单词的所有字母得到的一个新单词。
1
2
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

2.2 算法思想和代码实现

2.2.1 方法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public static List<List<String>> groupAnagrams(String[] strs) {
    List<List<String>> ans = new ArrayList<>();

    // 将第一个元素放入第一个分组
    List<String> firstGroup = new ArrayList<>();
    firstGroup.add(strs[0]);
    ans.add(firstGroup);

    // 遍历剩余的字符串
    for (int i = 1; i < strs.length; i++) {
        boolean found = false; // 标记是否找到匹配的分组

        for (List<String> group : ans) {
            if (isSameWords(strs[i], group.get(0))) { // 和已有分组的第一个元素比较
                group.add(strs[i]);
                found = true;
                break; // 找到匹配的分组后跳出
            }
        }

        // 如果没有找到匹配的分组，则创建新的分组
        if (!found) {
            List<String> newList = new ArrayList<>();
            newList.add(strs[i]);
            ans.add(newList);
        }
    }
    return ans;
}

// 判断两个字符串是否是异位词
public static boolean isSameWords(String str1, String str2) {
    if (str1.length() != str2.length()) {
        return false;
    }
    char[] ch1 = str1.toCharArray();
    char[] ch2 = str2.toCharArray();
    Arrays.sort(ch1);
    Arrays.sort(ch2);

    return Arrays.equals(ch1, ch2);
}

2.2.2 方法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
      public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<>();
        // 为空判断
        if (strs == null || strs.length == 0)
            return res;

        Map<String, List<String>> map = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            // 转换为字符数组并对其排序
            char[] chars = strs[i].toCharArray();
            Arrays.sort(chars);
            String sortedChars = new String(chars);

            // 在哈希表中查询是否存在，存在则添加到集合中，不存在创建一个新的键值对，值为集合列表
            if (map.containsKey(sortedChars)) {
                map.get(sortedChars).add(strs[i]);
            } else {
                map.put(sortedChars, new ArrayList<>());
                map.get(sortedChars).add(strs[i]);
            }
        }

        // 将哈希表中的值添加到结果集合中
        for (Map.Entry<String, List<String>> entry : map.entrySet()) {
            res.add(entry.getValue());
        }

//        //返回遍历map的所有值
//        return new ArrayList<>(map.values());

        return res;
    }

3. 最长连续序列

  • 一句话总结：使用HashSet去重后，遍历HashSet,当nums[i]-1不存在时开始从nums[i]往后查询，不断查询nums[i]+1,nums[i]+2...

3.1 题目描述

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

1
2
3
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

3.2 算法思想和代码实现

3.2.1 HashSet 去重 + 排序 + 遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public static int longestConsecutive(int[] nums) {
    if(nums.length == 0) return 0;
    int res = 0;
    int max=0;

    //使用HashSet去重
    Set<Integer> set = new HashSet<>();
    for(int num:nums){
        set.add(num);
    }
    int[] nums1=  set.stream().mapToInt(i -> i).toArray();

    //对数组元素排序
    Arrays.sort(nums1);

    //遍历数组，对符合的最长序列进行计数
    for(int i=1;i<nums1.length;i++){
        if(nums1[i]==nums1[i-1]+1){
            max++;
            if(max>res)
                res = max;
        }else{
            max=0;
        }
    }

    return res+1;
}

3.2.2 使用 哈希表（HashSet）+ 贪心

  1. 先用 HashSet 存储所有数字，去重并提供 O(1) 时间复杂度的查询。
  2. 遍历数组中的每个数字 num：
    • 如果 num-1 不在 set 中，说明它是一个连续序列的起点，开始寻找最长的连续序列。
    • 依次检查 num+1, num+2，直到找不到为止，更新最长序列的长度。
  3. 遍历完数组后，返回最长的连续序列长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static int longestConsecutive(int[] nums) {

    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        set.add(num); // 添加到 HashSet 去重
    }

    int maxLen = 0;

    for (int num : set) {
        // 只有当 num-1 不在集合中时，才从 num 开始找
        if (!set.contains(num - 1)) {
            int currNum = num;
            int currLen = 1;

            // 不断查找 num+1，num+2...
            while (set.contains(currNum + 1)) {
                currNum++;
                currLen++;
            }

            maxLen = Math.max(maxLen, currLen);
        }
    }

    return maxLen;
}

4. 移动零

一句话总结：

  • 第一遍遍历： j初始为0，j 作为非零元素的插入位置，把所有 非零元素 依次填入 nums[j]
  • 第二遍遍历： 把 j 之后的元素全部填 0

4.1 题目描述

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

  • 请注意：必须在不复制数组的情况下原地对数组进行操作。
1
2
3
4
5
6
7
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:
输入: nums = [0]
输出: [0]

4.2 算法思想和代码实现

4.2.1 双指针

  1. 维护一个指针 j，表示当前应当放置非零元素的位置（即 左侧应保持所有的非零元素）
  2. 遍历整个数组：
    • 遇到 非零元素：让 j 右移一位，并将该非零元素与 j 位置的元素交换。
    • 遇到 零元素：继续遍历，不执行任何操作（即 j 不变）。
  3. 最终所有 0 会被推到数组末尾，而所有非零元素保持相对顺序不变。
1
2
3
4
5
6
7
8
9
10
public static void moveZeroes(int[] nums) {
    for (int i = 0, j = -1; i < nums.length; i++) {
        if (nums[i] != 0) {
            j++;  // j 指向当前应存放非零元素的位置
            int tmp = nums[i]; // 交换 nums[i] 和 nums[j]
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }
}

4.2.2 双指针(方法2)

第一遍遍历： j 作为非零元素的插入位置，把所有 非零元素 依次填入 nums[j] 。
第二遍遍历： 把 j 之后的元素全部填 0。

1
2
3
4
5
6
7
8
9
10
11
12
public static void moveZeroes(int[] nums) {
    int j = 0; // j 记录非零元素该存放的位置
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != 0) {
            nums[j++] = nums[i]; // 把非零元素依次放入左侧
        }
    }
    // 将剩余的部分填充 0
    while (j < nums.length) {
        nums[j++] = 0;
    }
}

5. 盛最多水的容器

  • 一句话总结： left从左，right从右向中间移动，计算区间面积，每次计算后移动高度较小的指针，向中间靠拢

5.1 题目描述

  • 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
  • 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
  • 返回容器可以储存的最大水量。
1
2
3
输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

5.2 算法思想和代码实现

双指针法

  1. 双指针初始化：
    • 用 left 指向数组的起始位置（左端）。
    • 用 right 指向数组的末尾（右端）。
    • 计算当前双指针围成的水容量 currentWater = (right - left) * Math.min(height[left], height[right])，并更新 maxWater。
  2. 双指针移动策略：
    • 移动高度较小的指针，向中间靠拢：
    • 如果 height[left] < height[right]，则 left++，因为移动较矮的边可能会遇到更高的边，使得最小高度变大，从而可能获得更大面积。
    • 否则 right–，类似地希望遇到更高的柱子增加容积。
  3. 终止条件：
    • 当 left >= right 时，搜索结束，返回 maxWater。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int maxArea = 0;

    while (left < right) {
        int currentArea = (right - left) * Math.min(height[left], height[right]);

        maxArea = Math.max(maxArea, currentArea);

        if (height[left] < height[right])
            left++;
        else right--;
    }

    return maxArea;
}

6. 三数之和

一句话总结：

  • 先排序，三个指针：
    • i : 从0到nums.length-2遍历
    • left: 从i+1往后遍历
    • right：从nums.length-1往前遍历
  • 如果sum=0: left++,right–; 如果sum>0: right–; 如果sum<0: left++;
  • i 在遍历时，跳过相同的 nums[i]; left 和 right 指针移动时，也要跳过重复值

6.1 题目描述

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

注意：答案中不可以包含重复的三元组。

1
2
3
4
5
6
7
8
输入：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] 。
注意，输出的顺序和三元组的顺序并不重要。

6.2 算法思想和代码实现

双指针法+排序

  1. 对 nums 进行排序：这样可以方便地跳过重复元素，并且利用双指针寻找目标值。
  2. 遍历 nums 作为第一个元素：
    • 设 nums[i] 作为三元组中的 第一个数。
    • 采用 双指针 方法，在 nums[i] 右侧找到 两个数 使得 nums[i] + nums[left] + nums[right] = 0。
  3. 使用左右双指针 (left 和 right)：
    • 初始 left = i + 1，right = nums.length - 1。
    • 如果 sum > 0，说明 right 选得过大，右指针 right–。
    • 如果 sum < 0，说明 left 选得过小，左指针 left++。
    • 如果 sum == 0，找到一组解，存入结果集。
  4. 避免重复解：
    • i 在遍历时，跳过相同的 nums[i] 。
    • left 和 right 指针移动时，也要跳过重复值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public static List<List<Integer>> threeSum2(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums); // 先排序

    for (int i = 0; i < nums.length - 2; i++) {
        // 跳过重复的 `nums[i]`
        if (i > 0 && nums[i] == nums[i - 1]) continue;

        int left = i + 1, right = nums.length - 1;

        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];

            if (sum == 0) {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                // 跳过重复的 `left` 和 `right`
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;

                left++;
                right--;
            } else if (sum < 0) {
                left++; // 和太小，移动左指针
            } else {
                right--; // 和太大，移动右指针
            }
        }
    }

    return result;
}

7. 接雨水

  • 一句话描述：

7.1 题目描述

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

1
2
3
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

7.2 算法思想和代码实现

双指针

  • 左右指针从两端往中间移动，记录左右最大高度
  • 当左低右高时，左位置接水量由左最大高度决定
  • 当左高右低时，右位置接水量由右最大高度决定
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int trap(int[] height) {
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0;
    int sumOfWater = 0;

    while (left < right) {
        // 更新左右最大高度
        leftMax = Math.max(leftMax, height[left]);
        rightMax = Math.max(rightMax, height[right]);

        if (height[left] < height[right]) {
            // 左低右高，左位置接水量由左最大高度决定
            sumOfWater += leftMax - height[left];
            left++;
        } else {
            // 左高右低，右位置接水量由右最大高度决定
            sumOfWater += rightMax - height[right];
            right--;
        }
    }
    
    return sumOfWater;
}

全部面积-柱子的面积=水的面积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int trap(int[] height) {
      int sumHeight = 0;
      int maxHeight = 0;
      for (int i = 0; i < height.length; i++) {
          sumHeight += height[i];
          maxHeight = Math.max(maxHeight, height[i]);
      }

      int sumAll = 0;
      int l = 0, r = height.length - 1;
      for (int i = 1; i <= maxHeight; i++) {
          while (l < r && height[l] < i) l++;
          while (l < r && height[r] < i) r--;
          sumAll += r - l + 1;
      }
      return sumAll - sumHeight;
  }

8. 无重复字符的最长字串

  • 一句话总结： 用一个集合ArrayList维护当前的无重复子串,遍历字符串，如果当前字符已在list集合中重复，记录当前最大值，删除list中重复元素及以前的元素，添加当前元素

8.1 题目描述

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

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

8.2 算法思想和代码实现

滑动窗口（基于列表维护的窗口）

该算法用于求解无重复字符的最长子串长度，使用了滑动窗口的思想，通过一个 List<Character> 维护当前的无重复子串。

  1. 初始化
    • 维护 maxSubstringLength 记录最长无重复子串的长度。
    • 用 List<Character> 作为滑动窗口，初始时加入 s[0]。
  2. 遍历字符串
    • 若 s[i] 已在窗口中，说明出现重复：
    • 更新 maxSubstringLength。
    • 删除窗口内重复字符及其之前的字符，确保窗口无重复。
    • 将 s[i] 加入窗口，继续扩展子串。
  3. 遍历结束后，检查 chars 长度是否比 maxSubstringLength 更大，取最大值返回。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public int lengthOfLongestSubstring(String s) {
       if (s == null || s.length() == 0)
           return 0;
       if (s.length() == 1)
           return 1;

       List<Character> list = new ArrayList<>();
       int max = 0;

       for (int i = 0; i < s.length(); i++) {
           char c = s.charAt(i);

           // 当前字符已存在，记录最大值，删除list中重复元素及以前的元素
           if (list.contains(c)) {
               max = Math.max(max, list.size());
               
               while (list.get(0) != c) {
                   list.remove(0);
               }
               list.remove(0);
           }

           // 无论重复不重复，list最后加上当前元素
           list.add(c);
       }
       max = Math.max(max, list.size());
       return max;
   }

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

  • 一句话总结： 滑动窗口 + 频率数组比较；维护两个长度为26的数组来比较窗口内的字符频率是否和 p 匹配，每次移除窗口左边的元素，添加新字符到窗口的右侧

9.1 题目描述

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

1
2
3
4
5
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

9.2 算法思想和代码实现

9.2.1 方法1

  1. 首先对 p 字符串进行排序，并将其存储在 ch2 中。
  2. 遍历字符串 s 的每个子字符串，长度与 p 相同。
  3. 每次取出子字符串并对其进行排序，与 ch2 比较是否相同，如果相同，则说明该子字符串是 p 的异位词，记录其起始位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static List<Integer> findAnagrams(String s, String p) {
    List<Integer> result=new ArrayList<>();
    //排除特殊情况：s<p的长度等
    if(s==null||p==null||s.length()<p.length()||s.length()==0||p.length()==0)
        return result;

    char[] ch1=s.toCharArray();
    char[] ch2=p.toCharArray();

    Arrays.sort(ch2); //对字符数组p进行排序

    for(int i=0;i<ch1.length-ch2.length+1;i++){
        //创建一个新的数组存储
        char[] ch3=new char[ch2.length];
        for(int j=0;j<ch2.length;j++){
            ch3[j]=ch1[i+j];
        }
        Arrays.sort(ch3);
        if(Arrays.equals(ch2,ch3)){//证明二者是异位词
            result.add(i);
        }
    }
    return result;
}

9.2.2 滑动窗口 + 频率数组比较

  1. 使用两个长度为 26 的频率数组，charP 存储 p 的字符频率，charS 存储当前滑动窗口中字符的频率。
  2. 滑动窗口从左到右逐字符遍历 s：
    • 每次将窗口右边界的字符加入 charS。
    • 如果窗口的大小超过 p 的长度，则移除窗口左边界的字符。
  3. 每次窗口调整后，比较 charP 和 charS，如果相等，则说明当前窗口是 p 的异位词。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public List<Integer> findAnagrams(String s, String p) {
    // 如果主串 s 的长度小于模式串 p，直接返回空列表（不可能有异位词）
    if (s.length() < p.length())
        return new ArrayList<>();

    List<Integer> list = new ArrayList<>();

    // 用两个数组统计字符出现次数，长度为26代表26个小写字母
    int[] charS = new int[26]; // 用于滑动窗口中当前子串的字符计数
    int[] charP = new int[26]; // 用于模式串 p 的字符计数

    // 统计模式串 p 中每个字符出现的次数
    for (int i = 0; i < p.length(); i++) {
        int index = p.charAt(i) - 'a';
        charP[index]++;
    }

    // 初始化滑动窗口，统计 s 的前 p.length() 个字符的频率
    for (int i = 0; i < p.length(); i++) {
        int index = s.charAt(i) - 'a';
        charS[index]++;
    }

    // 滑动窗口开始滑动，从索引 p.length() 开始，直到 s 的结尾
    for (int i = p.length(); i < s.length(); i++) {
        // 如果当前窗口的字符频率和目标频率相同，则记录起始索引
        if (Arrays.equals(charS, charP)) {
            list.add(i - p.length());
        }
        // 将窗口左边的字符移除
        int index = s.charAt(i - p.length()) - 'a';
        charS[index]--;
        // 加入窗口右边的新字符
        int curI = s.charAt(i) - 'a';
        charS[curI]++;
    }

    // 检查最后一个窗口是否匹配
    if (Arrays.equals(charS, charP)) {
        list.add(s.length() - p.length());
    }

    return list;
}

10. 和为K的子数组

  • 一句话总结：
  • 前缀和 + 哈希表
    • 哈希表：Key存储前缀和，Value存储这个前缀和出现的次数
    • 通过 prefixSum - k 计算是否有之前的前缀和能构成和 k 的子数组
    • 加上之前的前缀和出现的次数即可

10.1 题目描述

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

1
2
3
4
5
输入：nums = [1,1,1], k = 2
输出：2

输入：nums = [1,2,3], k = 3
输出：2

10.2 算法思想和代码实现

10.2.1 暴力遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static int subarraySum(int[] nums, int k) {
    int result = 0;
    if(nums==null||nums.length==0){
        return 0;
    }

    for(int i=0;i<nums.length-1;i++){
        int sum=nums[i];
        if(sum==k){
            result++;
        }

        for(int j=i+1;j<nums.length;j++){
            sum+=nums[j];
            if(sum==k){
                result++;
            }
        }
    }

    if(nums[nums.length-1]==k)
        result++;

    return result;
}

10.2.2 前缀和 + 哈希表（O(n)）|| 前缀和 - 前面的某个前缀和 = 这段区间的和

  • 前缀和：利用 prefixSum[j] - prefixSum[i] = k 的性质，我们可以快速判断子数组 [i+1, j] 是否符合要求。
  • 哈希表：用 HashMap 存储前缀和的出现次数，避免重复计算，达到 O(n) 的时间复杂度。
  1. 维护前缀和，计算 prefixSum = sum(0…j)。
  2. 通过 prefixSum - k 计算是否有之前的前缀和能构成和 k 的子数组。
  3. 使用 HashMap 记录 prefixSum 出现的次数，以便快速查找是否存在满足条件的子数组。
  • 但是答案中为什么是查找 pre - k? pre - k 又代表了什么？
  • 这里要做个公式转换：
    • preSum[j] - preSum[i] = k => preSum[j] - k = preSum[i]
    • 当前下标为 j，要寻找另一个下标i，他的前缀和与j的前缀和差值为k！！
  • 所以map中应该存储的就是下标为i时，其前缀和。
  • 这样就好理解为什么在map中寻找的是 preSum[j] - k。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static int subarraySum(int[] nums, int k) {
       int count = 0;
       int prefixSum = 0;
       HashMap<Integer, Integer> map = new HashMap<>();
       map.put(0, 1); // 处理从索引0开始的子数组

       for (int num : nums) {
           prefixSum += num;  // 计算前缀和
           
           // 检查是否存在 prefixSum - k
           if (map.containsKey(prefixSum - k)) {
               count += map.get(prefixSum - k); // 统计满足条件的子数组个数
           }
           
           // 记录当前前缀和出现的次数
           map.put(prefixSum, map.getOrDefault(prefixSum, 0) + 1);
       }
       
       return count;
   }

11. 滑动窗口最大值

  • 一句话描述： 单调双端队列：使用双端队列(Deque)存储索引，在遍历数组时始终保持队列中元素对应的值单调递减，并在每次滑动窗口形成后，通过队头索引快速获取当前窗口的最大值，同时移除队头已滑出窗口范围的元素和队尾比当前元素小的元素

11.1 题目描述

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：
输入：nums = [1], k = 1
输出：[1]

11.2 算法思想和代码实现

单调双端队列

  • 队头存放的是最大值
  • 每次从队尾入队
  • 如何更新队头的最大值？
    • 当新元素来的时候，从队尾往队头移动，把小于新元素的元素全部出队，然后从队尾入队
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static int[] maxSlidingWindow2(int[] nums, int k) {
    int n = nums.length;
    int[] result = new int[n - k + 1];
    Deque<Integer> deque = new LinkedList<>();

    for (int i = 0; i < n; i++) {
        // 移除超出窗口范围的元素
        if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }

        // 维持队列单调递减，移除队尾小于当前元素的索引
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }

        // 添加当前元素索引
        deque.offerLast(i);

        // 记录窗口最大值
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFirst()];
        }
    }

    return result;
}

12. 最小覆盖子串

  • 一句话总结：
  • 滑动窗口+哈希表
    • 一个哈希表记录t的字符出现的次数，另一个哈希表记录s当前窗口的字符出现的次数
    • 右指针right先往右移动，直到包含t所有的字符(借助valid记录窗口内满足条件的字符数)，记录当前最短子串的右边界
    • 左指针left收缩窗口，尝试寻找更短的子串，记录当前最短子串的左边界

12.1 题目描述

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

注意：

  • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串，我们保证它是唯一的答案。
1
2
3
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

12.2 算法思想和代码实现

滑动窗口+哈希表

我们维护一个窗口 [left, right]，在窗口中寻找包含 t 所有字符的最小子串。

  1. 使用 need 哈希表 记录 t 中所有字符及其出现的次数。
  2. 使用 window 哈希表 记录当前窗口内的字符出现次数。
  3. 右指针 right 扩展窗口，直到窗口包含 t 中所有字符。
  4. 左指针 left 收缩窗口，尝试寻找更短的子串，同时保证窗口仍然有效。
  5. 记录当前最短子串的 start 和 length，最终返回结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public static String minWindow(String s, String t) {
    if (s.length() < t.length()) return "";

    // 记录 t 中的字符及其数量
    HashMap<Character, Integer> need = new HashMap<>();
    HashMap<Character, Integer> window = new HashMap<>();

    for (char c : t.toCharArray()) {
        need.put(c, need.getOrDefault(c, 0) + 1);
    }

    int left = 0, right = 0;  // 滑动窗口左右指针
    int valid = 0;  // 记录窗口内满足条件的字符数
    int start = 0, minLen = Integer.MAX_VALUE;  // 记录最小子串的位置和长度

    while (right < s.length()) {
        char c = s.charAt(right); // 右侧字符进入窗口
        right++; // 右指针扩展窗口

        // 如果是 t 需要的字符，则更新窗口数据
        if (need.containsKey(c)) {
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (window.get(c).equals(need.get(c))) {
                valid++;  // 该字符的数量达标
            }
        }

        // 当窗口包含 t 的所有字符时，尝试收缩窗口
        while (valid == need.size()) {
            // 记录最小子串
            if (right - left < minLen) {
                start = left;
                minLen = right - left;
            }

            char d = s.charAt(left); // 左侧字符即将移出窗口
            left++; // 左指针收缩窗口

            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d))) {
                    valid--;  // 该字符不再满足要求
                }
                window.put(d, window.get(d) - 1);
            }
        }
    }

    return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}

13. 最大子数组和

  • 一句话总结： 局部最优 -> 推导全局最优 sum+=当前元素，如果sum>max，更新max；如果sum<0，将sum重置为0(因为前面的子数组对后续没有正向贡献)

13.1 题目描述

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

子数组是数组中的一个连续部分。

1
2
3
4
5
6
7
8
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：
输入：nums = [1]
输出：1

13.2 算法思想和代码实现

如果 sum 大于 max，说明找到了一个更大的子数组和，将 max 更新为 sum。如果 sum 小于等于 0，说明当前子数组对后续的和没有正向贡献，将 sum 重置为 0，从下一个元素开始重新考虑新的子数组。

  1. 遍历数组 nums，更新 sum：
  2. 将 nums[i] 加入当前 sum，表示扩展当前子数组。
  3. 如果 sum > max，更新 max，记录新的最大和。
  4. 如果 sum 变成负数（sum <= 0），说明当前子数组对后续部分无贡献，需要重新开始新的子数组（即 sum = 0）。
1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxSubArray(int[] nums) {
    int sum = 0, max = Integer.MIN_VALUE;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];

        //如果 sum > max，更新 max，记录新的最大和。
        max = Math.max(max, sum);

        //如果 sum 变成负数（sum <= 0），说明当前子数组对后续部分无贡献，需要重新开始新的子数组（即 sum = 0）。
        sum = Math.max(sum, 0);
    }
    return max;
}

14. 合并区间

  • 一句话总结：
  • 先根据start排序：
    • 上一个end小于下一个start：直接加入结果集，continue;
    • 上一个end 大于等于下一个start: 有重复进行合并

14.1 题目描述

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

1
2
3
4
5
6
7
8
9
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

14.2 算法思想和代码实现

排序+遍历合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int[][] merge(int[][] intervals) {
      Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
      List<int[]> list = new ArrayList<>();
      list.add(intervals[0]);

      for (int i = 1; i < intervals.length; i++) {
          if (list.getLast()[1] >= intervals[i][0]) {
              int first = list.getLast()[0];
              int last = Math.max(list.getLast()[1], intervals[i][1]);
              list.removeLast();
              list.add(new int[]{first, last});
          } else {
              list.add(intervals[i]);
          }
      }

      return list.toArray(new int[list.size()][2]);
  }

15. 轮转数组

  • 一句话总结：
  • 三次翻转法：
    • 先整体翻转数组；再翻转前 k 个元素；最后翻转后 n-k个元素；
  • 注意： k可能大于数组长度，所以要先对数组长度取模(k%=nums.length;)

15.1 题目描述

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

1
2
3
4
5
6
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

15.2 算法思想和代码实现

三次翻转法 时间复杂度 O(n)，空间复杂度 O(1)

  1. 先整体翻转数组，得到 [7, 6, 5, 4, 3, 2, 1]
  2. 再翻转前 k=3 个元素，变成 [5, 6, 7, 4, 3, 2, 1]
  3. 最后翻转后 n-k=4 个元素，得到 [5, 6, 7, 1, 2, 3, 4]

三次翻转的过程可以理解为：

  • 整体翻转 → 把右边 k 个元素移动到前面，但顺序错了
  • 前 k 个元素翻转 → 让被移动到前面的元素恢复正确的顺序
  • 后 n-k 个元素翻转 → 让剩余元素恢复正确的顺序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void rotate2(int[] nums, int k) {
    int n = nums.length;
    k = k % n; // 避免 k 超过数组长度

    reverse(nums, 0, n - 1);    // 翻转整个数组
    reverse(nums, 0, k - 1);    // 翻转前 k 个元素
    reverse(nums, k, n - 1);    // 翻转剩下的元素
}

public static void reverse(int[] nums, int left, int right) {
    while (left < right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
        left++;
        right--;
    }
}

16. 除自身以外数组的乘积

  • 一句话描述：前缀积和后缀积：第一次从前往后遍历，构建结果数组每个位置前缀乘积，第二次从后往前遍历乘上后缀乘积

16.1 题目描述

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

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

1
2
输入: nums = [1,2,3,4]
输出: [24,12,8,6]

16.2 算法思想和代码实现

前缀积和后缀积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int[] productExceptSelf(int[] nums) {
    int[] res = new int[nums.length];
    int pre = 1, suf = 1;
    
    for (int i = 0; i < nums.length; i++) {
        res[i] = pre;
        pre *= nums[i];
    }
    for (int i = nums.length - 1; i >= 0; i--) {
        res[i] *= suf;
        suf *= nums[i];
    }
    
    return res;
}

17. 缺失的第一个正数

  • 一句话总结： 将[8,2,0,1,3,4]遍历转换为[1,2,3,4,0,8],通过原地交换的方式将正整数放到对应的位置上，然后从头遍历找到第一个不符合的正数

17.1 题目描述

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

1
2
3
4
5
6
7
8
9
示例 1：
输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

示例 2：
输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

17.2 算法思想和代码实现

原地哈希

  • 由于缺失的最小正整数一定在 [1, N+1] 之间（其中 N 是 nums.length），我们可以利用数组本身作为哈希表，将每个元素放到正确的位置（即 nums[i] == i + 1）。
  • 然后再遍历数组，找到第一个 nums[i] != i + 1 的索引 i，即 i + 1 为缺失的最小正整数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        // 将每个数放到正确的位置上，即 nums[i] = i + 1
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0 && nums[i] < n && nums[nums[i] - 1] != nums[i]) {
                swap(nums, nums[i] - 1, i);
                i--;  // 退一步，重新检查交换过来的那个值
            }
        }
        // 找到第一个 nums[i] != i + 1 的位置，返回 i + 1
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1)
                return i + 1;
        }
        // 若数组是 [1,2,3,4] 这样完整的，则返回 n+1
        return n + 1;
    }

    public void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

18. 矩阵置零

  • 一句话总结： 利用矩阵的第一行和第一列作为标记位来记录哪一行、哪一列需要被置 0 注意： 标记记录的过程中应该跳过第一行和第一列

18.1 题目描述

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

1
2
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

18.2 算法思想和代码实现

18.2.1 方法1

  1. 第一遍遍历：使用 HashSet 记录包含 0 的行索引 setRow 和列索引 setColumn。
  2. 第二遍遍历：将所有 setColumn 中的列全部置 0。
  3. 第三遍遍历：将所有 setRow 中的行全部置 0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static void setZeroes(int[][] matrix) {
    int m = matrix.length;
    int n = matrix[0].length;
    //创建两个哈希表用来存储为0的行和列值
    HashSet<Integer> setRow = new HashSet<Integer>();
    HashSet<Integer> setColumn = new HashSet<Integer>();

    //遍历矩阵，找到为0的元素的行和列
    for(int i = 0;i<m;i++)
        for(int j = 0;j<n;j++){
            if(matrix[i][j]==0){
                setRow.add(i);
                setColumn.add(j);
            }
        }

    //将有0的列都置为0
    for(int i = 0;i<m;i++)
        for(Integer j:setColumn)
            matrix[i][j]=0;

    //将有0的行都置为0
    for(int j=0;j<n;j++)
        for(Integer i:setRow)
            matrix[i][j]=0;
}

18.2.2 方法2（O(1) 空间复杂度）

我们可以 利用矩阵的第一行和第一列作为标记位 来记录哪一行、哪一列需要被置 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
public static void setZeroes(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    boolean firstRowZero = false, firstColZero = false;

    // 1. 检查第一列是否有 0
    for (int i = 0; i < m; i++) {
        if (matrix[i][0] == 0) {
            firstColZero = true;
            break;
        }
    }

    // 2. 检查第一行是否有 0
    for (int j = 0; j < n; j++) {
        if (matrix[0][j] == 0) {
            firstRowZero = true;
            break;
        }
    }

    // 3. 使用第一行和第一列记录需要置 0 的行和列
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = 0;  // 记录该行需要清零
                matrix[0][j] = 0;  // 记录该列需要清零
            }
        }
    }

    // 4. 置 0（根据第一行和第一列的标记）
    for (int i = 1; i < m; i++) {
        if (matrix[i][0] == 0) {
            for (int j = 1; j < n; j++) {
                matrix[i][j] = 0;
            }
        }
    }
    for (int j = 1; j < n; j++) {
        if (matrix[0][j] == 0) {
            for (int i = 1; i < m; i++) {
                matrix[i][j] = 0;
            }
        }
    }

    // 5. 处理第一列
    if (firstColZero) {
        for (int i = 0; i < m; i++) {
            matrix[i][0] = 0;
        }
    }

    // 6. 处理第一行
    if (firstRowZero) {
        for (int j = 0; j < n; j++) {
            matrix[0][j] = 0;
        }
    }
}

19. 螺旋矩阵

  • 一句话描述：
  • 定义top, bottom, left, right四个边界变量控制遍历范围
  • 按照 右 → 下 → 左 → 上 的顺序依次遍历矩阵的元素
  • 注意：最后两个遍历(往左和往上)要判断是否还有行或列剩下

19.1 题目描述

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

1
2
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

19.2 算法思想和代码实现

按照 右 → 下 → 左 → 上 的顺序依次遍历矩阵的元素。

我们可以使用 四个边界变量 控制遍历范围：

  • top：当前未遍历的上边界
  • bottom：当前未遍历的下边界
  • left：当前未遍历的左边界
  • right：当前未遍历的右边界
    在遍历过程中，每遍历完一圈，就收缩对应的边界，直到所有元素都被访问。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public static List<Integer> spiralOrder(int[][] matrix) {
     List<Integer> result = new ArrayList<>();

     int m = matrix.length, n = matrix[0].length;
     int top = 0, bottom = m - 1;
     int left = 0, right = n - 1;

     while (top <= bottom && left <= right) {
         // 从左到右
         for (int j = left; j <= right; j++) {
             result.add(matrix[top][j]);
         }
         top++; // 上边界收缩

         // 从上到下
         for (int i = top; i <= bottom; i++) {
             result.add(matrix[i][right]);
         }
         right--; // 右边界收缩

         // 判断是否还有行需要遍历
         if (top <= bottom) {
             // 从右到左
             for (int j = right; j >= left; j--) {
                 result.add(matrix[bottom][j]);
             }
             bottom--; // 下边界收缩
         }

         // 判断是否还有列需要遍历
         if (left <= right) {
             // 从下到上
             for (int i = bottom; i >= top; i--) {
                 result.add(matrix[i][left]);
             }
             left++; // 左边界收缩
         }
     }
     return result;
 }

20. 旋转图像

  • 一句话总结：
  • 旋转=转置+翻转
    1. 先转置：将 matrix[i][j] 变成 matrix[j][i]。
    2. 再水平翻转：让 matrix[j][i] 变成 matrix[j][n-1-i]。

20.1 题目描述

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

1
2
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

20.2 算法思想和代码实现

转置+翻转

  1. 转置矩阵（行变列，列变行）
  2. 翻转每一行（实现 90° 旋转）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
假设 matrix = [[1,2,3],[4,5,6],[7,8,9]]：

第一步：转置矩阵
转置后（行变列，列变行）：
1  4  7
2  5  8
3  6  9

第二步：翻转每一行
左右翻转后：
7  4  1
8  5  2
9  6  3
最终结果符合要求！

为什么旋转=转置+翻转？

旋转的最终的目标公式 matrix[i][j] → matrix[j][n-1-i]
拆解成两步：

  1. 先转置：将 matrix[i][j] 变成 matrix[j][i]。
  2. 再水平翻转：让 matrix[j][i] 变成 matrix[j][n-1-i]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void rotate(int[][] matrix) {
    int n = matrix.length;

    //先转置矩阵
    for (int i = 0; i < n; i++)
        for(int j = i+1; j < n; j++){
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }

    //在反转每一行(左右翻转)
    for(int i = 0; i < n; i++)
        for(int j=0;j<n/2;j++){
            int temp = matrix[i][j];
            matrix[i][j] = matrix[i][n-1-j];
            matrix[i][n-1-j] = temp;
        }
}

21. 搜索二维矩阵 II

  • 一句话总结： 从右上角出发，向下或向左移动，或返回true

21.1 题目描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

1
2
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

21.2 算法思想和代码实现

从右上角出发

就是要选择一个点，使得横向和纵向移动，martix能够有不同的变化

  • 左上角：往右往下移动，martix值都变大，无法区分，不可用
  • 右上角：往左martix变小，往下martix变大，可区分，可用
  • 左下角：往右martix变大，往上martix变小，可区分，可用
  • 右下角：往左往上移动，martix都变小，不可区分，不可用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static boolean searchMatrix(int[][] matrix, int target) {
    //从矩阵的右上角出发
    int i = 0, j = matrix[0].length - 1;
    while (i < matrix.length && j >= 0) {
        //如果相等返回true
        if (matrix[i][j] == target)
            return true;
            //如果大于target，往左移动
        else if (matrix[i][j] > target)
            j--;
            //如果小于target，往下移动
        else if (matrix[i][j] < target)
            i++;
    }
    return false;
}

22. 相交链表

  • 一句话总结： 双指针一块走，当 pA 走到尾巴 null，它就切换到 headB 重新开始。当 pB 走到尾巴 null，它就切换到 headA 重新开始。如果两个链表有交点，那么两个指针一定会在交点相遇。如果没有交点，最终两个指针都会走到 null

22.1 题目描述

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

题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。

22.2 算法思想和代码实现

22.2.1 暴力遍历(O(m*n))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    
    ListNode tempA = headA;
    while (tempA != null) {
        ListNode tempB = headB; // **每次遍历 headA 的一个节点，都要重新遍历 headB**
        while (tempB != null) {
            if (tempA == tempB) return tempA; // **找到相交点**
            tempB = tempB.next;
        }
        tempA = tempA.next;
    }

    return null; // **如果没有相交节点**
}

22.2.2 双指针法（O(m + n)）

双指针法通过两个指针分别遍历 headA 和 headB，当一个指针到达链表尾部时，切换到另一个链表的头部，这样可以在 一次遍历 中找到相交节点。

  • 思路：拼接链表分别得到 A + B 和 B + A。双指针遍历找到地址相同节点
  • 证明：假设 A = a + m, B = b + m (m 是相交之后的长度，相交之后剩下的长度一样)。
  • 那么双指针同时遍历 A + B 和 B + A 会在 a + m + b 和 b + m + a的位置（长度一致了！）找到相交节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode pA = headA, pB = headB;

    while (pA != pB) {
        if (pA == null)
            pA = headB;
        else
            pA = pA.next;

        if (pB == null)
            pB = headA;
        else
            pB = pB.next;
    }
    return pA;
}

23. 反转链表

  • 一句话描述：
1
2
3
4
5
原链表:1→2→3→4
1: null←1 2→3→4
2: null←1←2 3→4
3: null←1←2←3 4
4: null←1←2←3←4

23.1 题目描述

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

1
2
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

23.2 算法思想和代码实现

迭代反转 时间复杂度 O(n)

  • 使用 p 指针 记录前一个节点（初始为 null）。
  • 使用 curr 指针 遍历链表，并逐个反转指针方向。
1
2
3
4
5
6
7
8
9
10
11
12
13
public static ListNode reverseList(ListNode head) {
       ListNode p = null; // 反转后的链表头
       ListNode curr = head; // 当前遍历的节点

       while (curr != null) {
           ListNode nextTemp = curr.next; // 记录下一个节点
           curr.next = p; // 反转当前节点指针
           p = curr; //前进
           curr = nextTemp; // `curr` 前进
       }

       return p; // 反转后的头节点
   }

24. 回文链表

  • 一句话总结： 先用快慢指针找中点，把中点以后的链表反转，再比较反转后的一半链表和原链表的前一半

24.1 题目描述

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

1
2
输入：head = [1,2,2,1]
输出：true

24.2 算法思想和代码实现

24.2.1 利用额外空间存储链表元素，然后双指针比较是否为回文

  1. 遍历链表，将所有节点值存入 ArrayList。
  2. 使用双指针，一个从 list 末尾 开始，一个从链表 头部 开始，逐个比较值是否相等。
  3. 若所有对应元素相等，则链表是 回文链表，否则返回 false。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static boolean isPalindrome(ListNode head) {
    ListNode p = head;
    //创建一个集合保存链表元素
    List<Integer> list =new ArrayList<>();

    while(p!=null){
        list.add(p.val);
        p=p.next;
    }

    p=head;

    //集合元素从后往前与链表元素从前往后进行比较
    for(int i=list.size()-1;i>=list.size()/2;i--){
        if(list.get(i)!=p.val) return false;
        p=p.next;
    }

    return true;
}

24.2.2 快慢指针找中点 + 反转链表（O(n),O(1)）

  1. 使用快慢指针 找到链表的 中点。
  2. 反转后半部分链表。
  3. 从头和反转后的部分进行对比，判断是否为回文。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public static boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) return true;

    // 1. 使用快慢指针找到链表的中点
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // 2. 反转后半部分链表
    ListNode secondHalf = reverseList(slow);

    // 3. 进行回文判断
    ListNode p1 = head, p2 = secondHalf;
    while (p2 != null) {  // 只需要比较后半部分
        if (p1.val != p2.val) return false;
        p1 = p1.next;
        p2 = p2.next;
    }

    // 4. 可选：恢复链表
    reverseList(secondHalf);

    return true;
}

// 反转链表
private static ListNode reverseList(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

25. 环形链表

  • 一句话总结： 快慢指针找环：如果相遇了返回true

25.1 题目描述

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

25.2 算法思想和代码实现

为什么快慢指针一定会相遇

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static boolean hasCycle(ListNode head) {
    if(head==null || head.next==null) return false;

    //定义快慢指针
    ListNode slow =head;
    ListNode fast = head;
    
    while(fast!=null && fast.next!=null){
        //慢的一次走一步
        slow = slow.next;
        //快的一次走两步
        fast = fast.next.next;
        //如果他们能相遇，就一定是有环的
        if(slow==fast) return true;
    }

    return false;
}

26. 环形链表 II

  • 一句话总结： 当快慢指针相遇时：定义一个指针从相遇点开始走；另一个指针从链表头开始走，他们会在环的入口点相遇

26.1 题目描述

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

26.2 算法思想和代码实现

为什么快慢指针一定会相遇

定义一个指针从相遇点开始走；另一个指针从链表头开始走，他们会在环的入口点相遇

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static ListNode detectCycle(ListNode head) {
    //快慢指针判断是否有环
    ListNode slow =head;
    ListNode fast = head;
    
    while(fast!=null&&fast.next!=null){
        slow = slow.next;
        fast = fast.next.next;
        
        //如果有环
        if(slow==fast){
            //定义两个指针，一个从相遇点slow出发，另一个从head头出发
            ListNode meet =slow;
            ListNode p = head;
            
            //当二者相遇时，此结点就是环起点
            while(p!=meet){
                p = p.next;
                meet = meet.next;
            }
            return meet;
        }
    }

    return null;
}

27. 合并两个有序链表

  • 一句话描述： 使用虚拟头结点，双指针遍历两个链表；谁的值小，就连接谁；遍历完一个，直接连接另一个

27.1 题目描述

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

1
2
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

27.2 算法思想和代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;
    while (list1 != null && list2 != null) {
        if (list1.val < list2.val) {
            cur.next = list1;
            cur = cur.next;
            list1 = list1.next;
        } else {
            cur.next = list2;
            cur = cur.next;
            list2 = list2.next;
        }
    }

    if (list1 != null) {
        cur.next = list1;
    }
    if (list2 != null) {
        cur.next = list2;
    }

    return dummy.next;
}

28. 两数相加

  • 一句话总结： 创建一个新链表记录两个链表之和，注意进位

28.1 题目描述

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

1
2
3
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

28.2 算法思想和代码实现

创建一个新的链表存储最终的结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    // 创建一个新的链表用来保存最终结果
    ListNode l3 = new ListNode(0);
    ListNode head = l3; // 记录结果链表的头部
    int carry = 0;

    // 遍历两个链表，直到两个链表都遍历完
    while (l1 != null || l2 != null) {
        int x = 0, y = 0; 
        
        if (l1 != null) {
            x = l1.val;
        }
        if (l2 != null) {
            y = l2.val;
        }

        // 计算当前位的和与进位
        int sum = x + y + carry;
        carry = sum / 10; 

        // 取当前位的数字，创建新节点
        ListNode newNode = new ListNode(sum % 10);
        l3.next = newNode; 
        l3 = l3.next; 

        // 继续遍历 l1 和 l2
        if (l1 != null) {
            l1 = l1.next;
        }
        if (l2 != null) {
            l2 = l2.next;
        }
    }

    // 如果最后还有进位，创建一个新的节点
    if (carry > 0) {
        ListNode newNode = new ListNode(carry);
        l3.next = newNode;
    }

    return head.next; // 返回头节点
}

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

  • 一句话总结： 创建一个dummy,快慢指针指向dummy；快指针先走n+1步，然后快慢指针一起移动直到快指针为null，此时慢指针的位置就是要删除结点的前一个结点位置

29.1 题目描述

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

1
2
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

29.2 算法思想和代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public ListNode removeNthFromEnd(ListNode head, int n) {
    // 创建虚拟头结点，避免删除头节点时判断麻烦
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    ListNode fast = dummy;
    ListNode slow = dummy;

    // fast先走n+1步，保持间距
    for (int i = 0; i <= n; i++) {
        fast = fast.next;
    }

    // fast 和 slow 同时移动，直到 fast 到达链表末尾
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }

    // 删除倒数第n个节点
    slow.next = slow.next.next;

    // 返回新的头结点
    return dummy.next;
}

30. 两两交换链表中的节点

  • 一句话描述： 模拟即可

30.1 题目描述

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

1
2
输入：head = [1,2,3,4]
输出：[2,1,4,3]

30.2 算法思想和代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ListNode swapPairs(ListNode head) {
     // 创建虚拟头节点，方便处理头节点交换的问题
     ListNode dummy = new ListNode(0);
     dummy.next = head;
     ListNode cur = dummy; // cur用来遍历链表
     
     while(cur.next != null && cur.next.next != null) {
         // node1是第一个结点，node2是第二个结点
         ListNode node1 = cur.next;
         ListNode node2 = cur.next.next;

         // 交换节点
         cur.next = node2;
         node1.next = node2.next;
         node2.next = node1;

         // cur 移动到下一对节点前的位置
         cur = node1;
     }
     
     return dummy.next;
 }

31. K个一组翻转链表

  • 一句话总结： 反转+找到K个结点一组即可，每次记录开始结点和终止结点

31.1 题目描述

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

1
2
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

31.2 算法思想和代码实现

  1. 找到 k 个节点，如果数量不足 k，直接返回 head。
  2. 翻转 k 个节点，并将翻转后的部分连接到新链表。
  3. 更新指针，继续处理下一个 k 组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
   public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode cur = dummy;

    while (true) {
        ListNode start = cur.next;
        ListNode end = cur;

        // 判断剩余长度是否 >= k
        for (int i = 0; i < k && end != null; i++) {
            end = end.next;
        }
        if (end == null) break;  // 不足k个，结束循环

        ListNode next = end.next;
        end.next = null;  // 截断k组
        cur.next = reverse(start);  // 翻转k组
        start.next = next;  // 接回链表
        cur = start;  // cur 移动到下一组前
    }

    return dummy.next;
}

//反转链表
public ListNode reverse(ListNode head) {
    ListNode cur = null;
    while (head != null) {
        ListNode nextNode = head.next;
        head.next = cur;
        cur = head;
        head = nextNode;
    }
    return cur;
}

32. 随机链表的复制

  • 一句话总结： 使用 HashMap 存储旧节点与新节点的对应关系，并分两步完成链表复制

32.1 题目描述

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random –> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random –> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。

1
2
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

32.2 算法思想和代码实现

使用 HashMap 存储旧节点与新节点的对应关系，并分两步完成链表复制：

  1. 复制 next 指针并建立映射关系
    • 遍历原链表，创建新链表的 next 结构，同时在 HashMap 中存储每个旧节点对应的新节点。
    • 这样可以保证新链表的 next 结构和原链表一致。
  2. 复制 random 指针
    • 再次遍历链表，通过 HashMap 查询旧链表的 random 指向的节点，并将其映射到新链表的 random 指针。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public Node copyRandomList(Node head) {
     if (head == null) return null; // 若链表为空，则直接返回 null

     // 创建 HashMap，用于保存旧节点与新节点的对应关系
     Map<Node, Node> map = new HashMap<>();

     // 1. 通过 next 指针创建出新链表，并建立旧节点到新节点的映射关系
     Node newHead = new Node(head.val); // 复制头节点
     Node newNode = newHead, oldNode = head.next; // newNode 指向新链表，oldNode 遍历旧链表
     map.put(head, newHead); // 记录头节点映射关系
     map.put(null, null); // 处理 random 指向 null 的情况

     while (oldNode != null) { // 遍历旧链表，复制所有节点
         Node tempNode = new Node(oldNode.val); // 创建新节点
         newNode.next = tempNode; // 连接新节点
         newNode = newNode.next; // 移动新链表指针
         map.put(oldNode, newNode); // 记录映射关系
         oldNode = oldNode.next; // 继续遍历旧链表
     }

     // 2. 复制 random 指针
     oldNode = head;
     newNode = newHead;
     while (oldNode != null) {
         newNode.random = map.get(oldNode.random); // 通过 map 获取对应的新节点并赋值
         newNode = newNode.next; // 移动到下一个新节点
         oldNode = oldNode.next; // 移动到下一个旧节点
     }

     return newHead; // 返回新链表的头节点
 }

33. 排序链表

  • 一句话总结：
  • 归并排序
    • 使用快慢指针找到链表中点，将链表以中点拆分成左右链表递归排序，将两个链表合并成有序链表

33.1 题目描述

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

1
2
输入：head = [4,2,1,3]
输出：[1,2,3,4]

33.2 算法思想和代码实现

  • 归并排序: 分治法，将链表递归拆分，然后合并排序
  1. 递归终止条件
    • 当链表为空（head == null）或只有一个节点（head.next == null），直接返回 head。
  2. 找到链表中点（快慢指针法）
    • 使用 slow 和 fast 指针，让 fast 先走一步，保证 slow 取左中位数，防止死循环。
  3. 拆分链表
    • mid.next = null 断开链表，分为左右两部分递归排序。
  4. 合并有序链表
    • 使用双指针合并两个有序链表（归并排序的核心）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public ListNode sortList(ListNode head) {
    if (head == null || head.next == null)
        return head;

    //将链表从中间分割成两个链表
    ListNode mid = getMiddle(head);
    ListNode rightHead = mid.next;
    mid.next = null; //断开前一个链表

    //递归排序分割后的两块链表
    ListNode left = sortList(head);
    ListNode right = sortList(rightHead);

    //将链表归并
    return merge(left, right);
}


//找到链表中间结点
public ListNode getMiddle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

//归并两个链表
public ListNode merge(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;

    //依次比较两个链表的结点的大小，小的加上去
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            cur.next = l1;
            l1 = l1.next;
        } else {
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }

    //看哪个链表有剩余的，加上去
    if (l1 != null) cur.next = l1;
    if (l2 != null) cur.next = l2;

    return dummy.next;
}

34. 合并K个升序链表

  • 一句话总结： 使用最小堆(优先级队列)维护k个链表的当前最小节点，每次出队最小结点，入队最小结点的下一个结点，直到队列为空

34.1 题目描述

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

1
2
3
4
5
6
7
8
9
10
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

34.2 算法思想和代码实现

  • 使用最小堆（优先队列）来维护 k 个链表的当前最小节点，每次取出最小值并推进链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public ListNode mergeKLists(ListNode[] lists) {
       if (lists == null || lists.length == 0)
           return null;

       int k = lists.length;
       ListNode dummy = new ListNode(0);
       ListNode cur = dummy;

       PriorityQueue<ListNode> pq = new PriorityQueue<>(k, new Comparator<ListNode>() {
           @Override
           public int compare(ListNode o1, ListNode o2) { //重写比较器
               return o1.val - o2.val;
           }
       });

       //先把k个链表的头结点放进优先级队列中
       for (ListNode head : lists) {
           if (head != null) {
               pq.offer(head);
           }
       }

       //将最小的结点弹出来并连接到有序链表后，将弹出来的结点的下一个结点入队
       while (!pq.isEmpty()) {
           ListNode minNode = pq.poll();
           cur.next = minNode;
           cur = cur.next;

           if (minNode.next != null)
               pq.offer(minNode.next);
       }

       return dummy.next;
   }

35. LRU缓存

  • 一句话描述： 定义双向链表维护缓存队列，定义哈希表维护当前队列的键和值，并提供快速查找结点

35.1 题目描述

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

35.2 算法思想和代码实现

双向链表 + HashMap

  • 双向链表维护缓存队列
  • 哈希表：通过key快速查找Node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
public class LRUCache {
    //哈希表保存结点的键和值
    HashMap<Integer, Node> map = new HashMap<>();
    int capacity;
    //创建一个虚头结点和尾结点
    Node head, tail;

    //使用双向链表模拟缓存队列
    class Node {
        int key, value;
        Node next, prev;

        Node() {
        }

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    //构造方法初始化
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();

        head = new Node(-1, -1);
        tail = new Node(-1, -1);

        head.next = tail;
        tail.prev = head;
    }

    //使用缓存中的key，更新缓存队列
    public int get(int key) {
        //如果不存在，返回-1
        if (!map.containsKey(key))
            return -1;

        //存在，将缓存中的当前结点移动到队头的后面，并删除当前位置的当前结点
        Node cur = map.get(key);
        removeNode(cur);
        moveToHead(cur);

        return cur.value;
    }

    //添加缓存中的结点
    public void put(int key, int value) {
        //已经存在了当前的key，删除原本的结点和哈希表中的key
        if (map.containsKey(key)) {
            Node olddNode = map.get(key);
            removeNode(olddNode);
            map.remove(key);
        }

        //在哈希表和缓存队列中添加当前结点
        Node newNode = new Node(key, value);
        map.put(key, newNode);
        moveToHead(newNode);

        //如果哈希表中的结点大于容量，删除队尾的缓存结点和哈希表中的队尾结点元素
        if (map.size() > capacity) {
            Node lastNode = tail.prev;
            if (lastNode != head) {
                removeNode(lastNode);
                map.remove(lastNode.key);
            }
        }
    }

    //删除当前结点
    public void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    //将当前结点添加到头结点的后面
    public void moveToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
}

36. 二叉树的中序遍历

  • 一句话总结： 左根右递归

36.1 题目描述

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

1
2
输入：root = [1,null,2,3]
输出：[1,3,2]

36.2 算法思想和代码实现

递归：左根右

1
2
3
4
5
6
7
8
9
10
List<Integer> list = new ArrayList<>();

public List<Integer> inorderTraversal(TreeNode root) {
    if (root == null)
        return list;
    inorderTraversal(root.left);
    list.add(root.val);
    inorderTraversal(root.right);
    return list;
}

37. 二叉树的最大深度

  • 一句话总结： 当前节点为空返回0，递归计算左右子树的深度，取左右子树的较大值加1

37.1 题目描述

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

1
2
输入：root = [3,9,20,null,null,15,7]
输出：3

37.2 算法思想和代码实现

递归计算

1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxDepth(TreeNode root) {
    // 如果当前节点为空，则返回深度 0
    if (root == null) return 0;

    // 递归计算左子树的最大深度
    int left = maxDepth(root.left);

    // 递归计算右子树的最大深度
    int right = maxDepth(root.right);

    // 当前节点的深度为左右子树深度的较大值 + 1
    return Math.max(left, right) + 1;
}

38. 翻转二叉树

  • 一句话描述： 递归交换左右子树即可

38.1 题目描述

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

1
2
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

38.2 算法思想和代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public TreeNode invertTree(TreeNode root) {
    // 如果当前节点为空，则直接返回 null
    if (root == null) return null;

    // 暂存当前节点的左子节点
    TreeNode left = root.left;

    // 递归反转右子树，并赋值给当前节点的左子节点
    root.left = invertTree(root.right);
    // 递归反转左子树，并赋值给当前节点的右子节点
    root.right = invertTree(left);
    
    return root;
}

39. 对称二叉树

  • 一句话总结：
  • 两个子树都为空则对称
  • 如果左右子树都不为空且值相等，同时左树的右子树和右树的左子树对称，同时左树的左子树和右树的右子树对称，则对称

39.1 题目描述

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

1
2
输入：root = [1,2,2,3,4,4,3]
输出：true

39.2 算法思想和代码实现

  1. 怎么判断一棵树是不是对称二叉树？
    答案：如果所给根节点，为空，那么是对称。如果不为空的话，当他的左子树与右子树对称时，他对称
  2. 那么怎么知道左子树与右子树对不对称呢？在这我直接叫为左树和右树
    答案：如果左树的左孩子与右树的右孩子对称，左树的右孩子与右树的左孩子对称，那么这个左树和右树就对称。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean isSymmetric(TreeNode root) {
       return fun(root.left, root.right);
   }

   public boolean fun(TreeNode left, TreeNode right) {
       // 如果两个子树都为空，则对称
       if (left == null && right == null)
           return true;

       // 如果左右子树都不为空且值相等，
       // 同时左树的右子树和右树的左子树对称，
       // 同时左树的左子树和右树的右子树对称，则对称
       if (left != null && right != null && left.val == right.val && fun(left.left, right.right)
               && fun(left.right, right.left))
           return true;

       // 其他情况不对称
       return false;
   }

40. 二叉树的直径

  • 一句话描述： 递归计算每个节点的左右子树的最大深度，当前节点的直径=左子树深度+右子树深度，更新最大直径

40.1 题目描述

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

1
2
3
输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

40.2 算法思想和代码实现

  • 递归思想：计算每个节点的左右子树深度，并更新最大直径。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int max = 0;

  public int diameterOfBinaryTree(TreeNode root) {
      maxDepth(root);
      return max;
  }

  public int maxDepth(TreeNode root) {
      if (root == null)
          return 0;

      // 递归计算左右子树的最大深度
      int left = maxDepth(root.left);
      int right = maxDepth(root.right);

      // 用左子树深度 + 右子树深度更新最大直径
      max = Math.max(max, left + right);

      // 返回当前节点的最大深度 = 左右子树最大深度 + 1（算上当前节点）
      return Math.max(left, right) + 1;
  }

41. 二叉树的层序遍历

  • 一句话描述： 使用队列存储每层的结点，使用size记录当前层结点的个数，循环出队层中的结点，入队下一层左右子树的结点，直到队空为止

41.1 题目描述

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

1
2
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

41.2 算法思想和代码实现

使用队列（Queue） 作为辅助数据结构，按照层的顺序依次处理每个节点。

  1. 先将 根节点入队，然后进入循环：
    • 记录当前层的节点个数 size。
    • 遍历当前层的 size 个节点：
      • 弹出队列头部节点，并将其值存入当前层的列表中。
      • 将该节点的左右子节点入队（若存在）。
  2. 遍历完整层后，将当前层的列表加入最终结果。
  3. 继续处理下一层，直至队列为空，即所有节点都被遍历完。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public List<List<Integer>> levelOrder(TreeNode root) {
     if (root == null)
         return new ArrayList<>(); 

     // 创建队列用于层序遍历
     Deque<TreeNode> queue = new LinkedList<>();
     // 用于存储最终的层序遍历结果
     List<List<Integer>> res = new ArrayList<>(); 

     queue.offer(root); // 先将根节点入队

     while (!queue.isEmpty()) {
         int size = queue.size(); // 记录当前层的节点数
         List<Integer> list = new ArrayList<>(); // 用于存储当前层的节点值
         
         while (size > 0) {
             TreeNode node = queue.poll(); // 取出队列元素

             if (node.left != null)
                 queue.offer(node.left); // 左子节点入队
             if (node.right != null)
                 queue.offer(node.right); // 右子节点入队

             list.add(node.val); 
             size--;
         }

         res.add(list); 
     }
     return res;
 }

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

  • 一句话描述： 以数组的中间元素作为root结点，左区间递归构造左子树root.left,右区间递归构造右子树root.right，直到数组区间索引left>right终止

42.1 题目描述

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

1
2
3
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

42.2 算法思想和代码实现

  • 将有序数组从中间分割，分为左区间和右区间
  • 左区间用来构造左子树
  • 右区间用来构造右子树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public TreeNode sortedArrayToBST(int[] nums) {
    return sortTree(nums, 0, nums.length - 1);
}

public TreeNode sortTree(int[] nums, int left, int right) {
    if (left > right) return null;
    int mid = left + (right - left) / 2;
    
    //构造当前结点
    TreeNode root = new TreeNode(nums[mid]);

    //递归构造左子树和右子树
    root.left = sortTree(nums, left, mid - 1);
    root.right = sortTree(nums, mid + 1, right);

    return root;
}

43. 验证二叉搜索树

  • 一句话描述： 构建子树的大小边界，左右子树的值在边界外返回false，递归遍历左右子树

43.1 题目描述

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。
1
2
输入：root = [2,1,3]
输出：true

43.2 算法思想和代码实现

43.2.1 中序遍历+集合有序

  • 中序遍历的结果如果是一个升序的，则返回true
  • 用一个集合保存中序遍历结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//创建一个集合保存二叉树元素
List<Integer> list =new ArrayList<>();

public boolean isValidBST(TreeNode root) {
    inorderTraversal(root);
    //中序遍历如果是一个升序的结果，则返回true
    for (int i = 0; i < list.size()-1; i++) {
        if(list.get(i)>=list.get(i+1))
            return false;
    }

    return true;
}

//中序遍历
public void inorderTraversal(TreeNode root) {
    if(root == null) return;
    inorderTraversal(root.left);
    list.add(root.val);
    inorderTraversal(root.right);
}

43.2.2 递归检查

  • 每个节点 root.val 必须在某个范围内，即：
    • 左子树的所有节点值必须 小于 root.val
    • 右子树的所有节点值必须 大于 root.val
  • 递归过程中，维护 当前允许的最大值 max 和最小值 min，如果 root.val 超出范围，则不是 BST。
1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean isValidBST(TreeNode node, long min, long max) {
        if (node == null) return true;

        // 检查当前节点是否在允许范围内
        if (node.val <= min || node.val >= max) return false;

        // 递归检查左右子树
        return isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max);
    }

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

  • 一句话描述： 二叉搜索树用中序遍历即为一个升序的数组，直接计数到第k个遍历的结点时，返回当前元素即可

44.1 题目描述

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

1
2
输入：root = [3,1,4,null,2], k = 1
输出：1

44.2 算法思想和代码实现

  • 二叉搜索树的中序遍历是一个升序的数据
  • 中序遍历，到第k个遍历的元素后，返回当前结点元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private int count = 0; // 记录当前访问的节点数量
private int result = 0; // 记录最终结果

public int kthSmallest(TreeNode root, int k) {
    inorder(root, k);
    return result;
}

private void inorder(TreeNode node, int k) {
    if (node == null) return;

    inorder(node.left, k); // 递归左子树

    count++; // 访问当前节点
    if (count == k) {
        result = node.val;
        return;
    }

    inorder(node.right, k); // 递归右子树
}

45. 二叉树的右视图

  • 一句话描述： 使用队列进行层序遍历，找到每层最右边的结点即可

45.1 题目描述

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

1
2
输入：root = [1,2,3,null,5,null,4]
输出：[1,3,4]

45.2 算法思想和代码实现

  • 思想：找到层序遍历的每层最后一个结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public List<Integer> rightSideView(TreeNode root) {
    if(root==null) return new ArrayList<>();
    
    List<Integer> res = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    //层序遍历
    while(!queue.isEmpty()){
        int size = queue.size();

        while(size>0){
            TreeNode node = queue.poll();

            if(node.left!=null)
                queue.offer(node.left);
            if(node.right!=null)
                queue.offer(node.right);

            size--;
            
            //返回每层的最后一个结果，也就是最右边的结点
            if(size==0) res.add(node.val);
        }

    }
    return res;
}

46. 二叉树展开为链表

  • 一句话描述： 创建一个新结点，使用新结点的右子树连接当前root结点，然后前序遍历递归连接root的左子树、root的右子树

46.1 题目描述

给你二叉树的根结点 root ，请你将它展开为一个单链表：

  • 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。
1
2
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

46.2 算法思想和代码实现

  • 以 先序遍历（根-左-右） 的方式展开二叉树。
  • 使用 cur 变量记录上一个访问的节点，并将 cur.right 指向当前节点 root，从而形成链表结构。
  • cur 变量始终存储着已经展开的最后一个节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// cur 记录上一个访问的节点
TreeNode cur = null;

public void flatten(TreeNode root) {

    if (root == null) return;

    // 先保存左、右子树（因为后面会修改 root.left 和 root.right）
    TreeNode left = root.left;
    TreeNode right = root.right;

    // 如果 cur 不为空，说明已经处理过前一个节点
    if (cur != null) {
        cur.left = null;  // 断开左子树
        cur.right = root; // 让上一个节点的右子树指向当前节点
    }

    // 更新 cur 为当前节点
    cur = root;

    // 递归处理左右子树
    flatten(left);
    flatten(right);
}

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

  • 一句话描述： 哈希表存储中序数组便于查找索引，前序数组第一个元素就是根节点，使用中序数组划分左右子树后进行递归构建左右子树

47.1 题目描述

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

1
2
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

47.2 算法思想和代码实现

递归 + 哈希表优化查找

  • 先序遍历的第一个元素一定是当前子树的根节点
  • 利用中序遍历划分左右子树
    • 中序遍历查找根节点的位置 rootIndex，从而确定 左子树的大小 (leftSize = rootIndex - inLeft)
    • 左子树的范围在 [inLeft, rootIndex - 1]，右子树的范围在 [rootIndex + 1, inRight]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
HashMap<Integer, Integer> map = new HashMap<>();

   public TreeNode buildTree(int[] preorder, int[] inorder) {
       //将中序遍历数组的元素作为key,索引作为value存储在哈希表中
       for (int i = 0; i < inorder.length; i++) {
           map.put(inorder[i], i);
       }

       return buildTree(preorder, 0, preorder.length - 1, 0, inorder.length - 1);
   }

   public TreeNode buildTree(int[] preorder, int preLeft, int preRight, int inLeft, int inRight) {
       //递归终止条件
       if (preLeft > preRight || inLeft > inRight) return null;

       //前序遍历第一个结点一定是根结点，记录此根结点在中序遍历的位置，计算左子树大小
       TreeNode root = new TreeNode(preorder[preLeft]);
       int rootIndex = map.get(preorder[preLeft]);
       int leftSize = rootIndex - inLeft;

       //递归构造左右子树
       TreeNode left = buildTree(preorder, preLeft + 1, preLeft + leftSize, inLeft, rootIndex - 1);
       TreeNode right = buildTree(preorder, preLeft + leftSize + 1, preRight, rootIndex + 1, inRight);

       root.left = left;
       root.right = right;
       return root;
   }

48. 路径总和 III

  • 一句话描述： 使用哈希表存储前缀和出现次数，backtracking(){终止条件{在哈希表找到(当前路径总和-目标值)的次数加到结果}，在哈希表添加当前路径总和，递归左右子树，回溯撤销哈希表添加的当前路径总和}

48.1 题目描述

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

1
2
3
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

48.2 算法思想和代码实现

48.2.1 递归遍历所有的子树

  1. 递归遍历
    • 以当前节点为起点计算符合条件的路径数（调用 dfs）。
    • 分别递归左子树和右子树，继续以子树的根作为起点计算符合条件的路径数（调用 pathSum）。
  2. 深度优先搜索（DFS）计算路径数
    • dfs(root, target): 计算以 root 为起点的路径总数：
      • 若当前节点值 root.val 等于 target，则计数 count++。
      • 递归计算 root.left 和 root.right，更新路径数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int pathSum(TreeNode root, long targetSum) {
       if (root == null)
           return 0;

       //依次将当前根结点作为一个树，左子树作为一个树，右子树作为一个树进行递归
       return dfs(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
   }

   
   public int dfs(TreeNode root, long target) {
       if (root == null)
           return 0;
       int count = 0;
       
       //如果当前结点等于Target则为一个路径
       if (root.val == target)
           count++;

       //递归左子树和右子树，将target减去当前结点的值
       count += dfs(root.left, target - root.val) + dfs(root.right, target - root.val);
       return count;
   }

48.2.2 前缀和+回溯

  1. 使用哈希表存储前缀和出现次数
    • 设 prefixSum 记录从根到当前节点的路径和：
      • 若 prefixSum[j] - prefixSum[i] = targetSum，则说明从 i+1 到 j 的路径和为 targetSum。
    • 只需要查询 prefixSum[j] - targetSum 是否出现过。
  2. 深度优先遍历 + 回溯
    • 使用 HashMap<Long, Integer> 记录遍历过程中所有的 prefixSum 及其出现次数。
    • 在递归进入子节点时，更新前缀和哈希表；
    • 递归完成后，回溯删除当前节点贡献的前缀和，避免影响其他路径计算。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public int pathSum(TreeNode root, int targetSum) {
        HashMap<Long, Integer> prefixSumCount = new HashMap<>();
        // 初始化前缀和为 0 的路径数量为 1（空路径）
        prefixSumCount.put(0L, 1);
        return dfs(root, 0, targetSum, prefixSumCount);
    }

    private int dfs(TreeNode node, long currSum, int targetSum, HashMap<Long, Integer> prefixSumCount) {
        if (node == null) return 0;

        // 更新当前前缀和
        currSum += node.val;

        // 检查是否存在从某个祖先节点到当前节点的路径和等于 targetSum
        int count = prefixSumCount.getOrDefault(currSum - targetSum, 0);

        // 记录当前前缀和出现次数
        prefixSumCount.put(currSum, prefixSumCount.getOrDefault(currSum, 0) + 1);

        // 递归进入左右子树
        count += dfs(node.left, currSum, targetSum, prefixSumCount);
        count += dfs(node.right, currSum, targetSum, prefixSumCount);

        // 回溯：撤销当前节点对前缀和的影响
        prefixSumCount.put(currSum, prefixSumCount.get(currSum) - 1);

        return count;
    }

49. 二叉树的最近公共祖先

  • 一句话描述： 先判断当前结点是否是p或q，再递归判断左右子树，分为左右子树都找到了结点，左右子树只有一个找到了，左右子树都没找到四种情况

49.1 题目描述

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

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

1
2
3
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

49.2 算法思想和代码实现

  1. 终止条件：
    • 如果 root 为空，说明已经递归到了叶子节点的空子树，返回 null。
    • 如果 root 等于 p 或 q，说明找到了其中一个目标节点，直接返回 root（可能是最近公共祖先）。
  2. 递归查找：
    • 在左子树中递归查找 p 和 q 的最近公共祖先 (left)。
    • 在右子树中递归查找 p 和 q 的最近公共祖先 (right)。
  3. 回溯过程：
    • 如果 left 和 right 都不为空，说明 p 和 q 分别位于 root 的左右子树，root 就是它们的最近公共祖先。
    • 如果 left 为空，说明 p 和 q 都在 root 的右子树，返回 right。
    • 如果 right 为空，说明 p 和 q 都在 root 的左子树，返回 left。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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);

       //左右子树都找到了，说明是root
       if (left != null && right != null)
           return root;
       //左子树找到了右子树没找到，返回左子树
       if (left != null && right == null)
           return left;
       //左子树没找到右子树找到了，返回右子树
       return right;
   }

50. 二叉树中的最大路径和

  • 一句话总结： 用一个全局变量记录最大值，递归记录左右子树的最大贡献，更新最大值，返回当前结点能为父节点的最大路径值(只能选左右子树的其中一个贡献大的子树)

50.1 题目描述

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。

1
2
3
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

50.2 算法思想和代码实现

  1. 递归遍历整棵树：

    • 计算左右子树的最大贡献值（如果贡献值小于 0，则丢弃）。
    • 计算当前节点作为路径顶点时的最大路径和，并更新全局 maxPathSum。
    • 计算当前节点能提供的最大贡献值，并返回给上一层递归。

  2. 分情况讨论：

    • 路径断裂：返回当前子树的最大贡献值（只能选左右子树之一）。
    • 路径不断裂：更新全局最大路径和（包含左右子树和当前节点）。

1、那么，首先我们可以假设走到了某个节点，现在要面临的问题是路径的最大值问题，显然对于这种问题，每遍历到一个节点，我们都要求出包含该节点在内的此时的最大路径，并且在之后的遍历中更新这个最大值。对于该节点来说，它的最大路径currpath就等于左右子树的最大路径加上本身的值，也就是currpath = left+right+node,val，但是有一个前提，我们要求的是最大路径，所以若是left或者right小于等于0了，那么我们就没有必要把这些值加上了，因为加上一个负数，会使得最大路径变小。这里的最大路径中的最其实就是一个限定条件，也就是我们常说的贪心算法，只取最大，最好，其余的直接丢弃。

2、好了，1中的主体我们已经明确了，但是还存在一个问题，那就是left和right具体应该怎么求，也就是left和right的递归形式。显然我们要把node.left和node.right再次传输到递归函数中，重复上述的操作。但如果到达了叶子节点，是不是需要往上一层返回了呢？那么返回值又是多少呢？
我们要明确left和right的基本含义，它们表示的是最大贡献，那么一个节点的最大贡献就等于node.val+max(left,right)，这个节点本身选上，然后从它的左右子树中选择最大的那个加上。
对于叶子节点也是这样，但是叶子节点的左右子树都为空，所以加上0，哎，注意看，此时是不是边界条件也出来了，但节点为空时，返回0 。 好了，至此循环的主体，返回值，边界条件都定义好了，那么整个递归的代码是不是就水到渠成了。这样一看递归也没什么了不起的！！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int maxSum = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
    dfs(root);
    return maxSum;
}

private int dfs(TreeNode node) {
    if (node == null)
        return 0;

    int left = Math.max(0, dfs(node.left)); // 左子树最大贡献
    int right = Math.max(0, dfs(node.right)); // 右子树最大贡献

    // 以当前节点为最高点的路径和
    maxSum = Math.max(maxSum, left + right + node.val);

    // 返回当前节点能为父节点贡献的最大路径值
    return Math.max(left, right) + node.val;
}

51. 岛屿数量

  • 一句话总结： 若当前元素为’1’则计数加1，并感染周围的元素为’2’，防止重复计数

51.1 题目描述

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

1
2
3
4
5
6
7
输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

51.2 算法思想和代码实现

  • 遍历岛这个二维数组，如果当前数为1，则进入感染函数并将岛个数+1
  • 感染函数：其实就是一个递归标注的过程，它会将所有相连的1都标注成2。
    • 为什么要标注？这样就避免了遍历过程中的重复计数的情况，一个岛所有的1都变成了2后，遍历的时候就不会重复遍历了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public int numIslands(char[][] grid) {
    int count = 0;

    //遍历所有元素，找到所有的岛，并感染岛的上下左右
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                count++;
                infect(grid, i, j);
            }
        }
    }
    return count;
}

//将当前的岛的元素全部感染成2，上下左右的元素置为2
public void infect(char[][] grid, int i, int j) {
    if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != '1')
        return;

    grid[i][j] = '2';

    //感染上下左右的元素
    infect(grid, i - 1, j);
    infect(grid, i + 1, j);
    infect(grid, i, j - 1);
    infect(grid, i, j + 1);
}

52. 腐烂的橘子

  • 一句话描述： 先把当前状态转换替代成其他值，用时间标记当前腐烂的橘子，下一轮腐烂的橘子=当前time+1，直到没有新橘子被感染跳出循环

52.1 题目描述

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

  • 值 0 代表空单元格；
  • 值 1 代表新鲜橘子；
  • 值 2 代表腐烂的橘子。
    每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
    返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
1
2
输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4

52.2 算法思想和代码实现

  1. 状态转换：
    • 空位 0 被标记为 -2; 新鲜橘子 1 被标记为 -1; 腐烂橘子 2 被标记为 0
  2. BFS 模拟腐烂过程：
    • 遍历整个网格，找到所有腐烂橘子（初始 0 值）。
    • 在 while 循环中，每分钟所有当前腐烂的橘子尝试感染其四个方向的新鲜橘子
    • 被感染的橘子被赋值为 time + 1，即表示它在 time+1 分钟后变烂。
  3. 终止条件：
    • 如果在某一轮遍历中没有橘子被感染，说明腐烂过程结束，跳出循环。
  4. 检查是否仍有未腐烂的橘子：
    • 遍历网格，如果仍然存在 -1（新鲜橘子），则返回 -1，表示无法全部腐烂。
    • 否则，返回 time，即腐烂传播所需的总时间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public static int orangesRotting(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int time = 0; // 记录腐烂传播所需的分钟数

        // -2 表示空位，-1 表示新鲜橘子，0 表示腐烂橘子
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] -= 2;
            }
        }

        // 模拟腐烂过程
        while (true) {
            boolean finished = true;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == time) {
                        // 当前腐烂的橘子，尝试感染四个方向的新鲜橘子
                        if (i - 1 >= 0 && grid[i - 1][j] == -1) {
                            grid[i - 1][j] = time + 1;
                            finished = false;
                        }
                        if (j - 1 >= 0 && grid[i][j - 1] == -1) {
                            grid[i][j - 1] = time + 1;
                            finished = false;
                        }
                        if (i + 1 < m && grid[i + 1][j] == -1) {
                            grid[i + 1][j] = time + 1;
                            finished = false;
                        }
                        if (j + 1 < n && grid[i][j + 1] == -1) {
                            grid[i][j + 1] = time + 1;
                            finished = false;
                        }
                    }
                }
            }
            if (finished)
                break; // 如果没有橘子被感染，结束循环
            else
                time++;
        }

        // 遍历网格，如果仍然存在未腐烂的橘子，返回 -1
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == -1)
                    return -1;

        return time;
    }

53. 课程表

  • 一句话描述： 判断一个有向图是否有环，不会….

53.1 题目描述

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

1
2
3
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

53.2 算法思想和代码实现

拓扑排序，用于判断一个有向图是否存在环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static boolean canFinish(int numCourses, int[][] prerequisites) {
    int len = prerequisites.length;
    if (len == 0) return true;

    int[] pointer = new int[numCourses];// 每个课程被指向的次数
    for (int[] p : prerequisites) ++pointer[p[1]];
    boolean[] removed = new boolean[len];// 标记prerequisites中的元素是否被移除
    int remove = 0;// 移除的元素数量
    while (remove < len) {
        int currRemove = 0;// 本轮移除的元素数量
        for (int i = 0; i < len; i++) {
            if (removed[i]) continue;// 被移除的元素跳过
            int[] p = prerequisites[i];
            if (pointer[p[0]] == 0) {// 如果被安全课程指向
                --pointer[p[1]];// 被指向次数减1
                removed[i] = true;
                ++currRemove;
            }
        }
        if (currRemove == 0) return false;// 如果一轮跑下来一个元素都没移除，则没必要进行下一轮
        remove += currRemove;
    }
    return true;
}

54. 实现Trie(前缀树)

  • 一句话描述： 面试会考吗？不会》….

54.1 题目描述

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：
Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入
["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

54.2 算法思想和代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class TrieNode {
    TrieNode[] children;
    boolean isEnd;
    
    public TrieNode() {
        children = new TrieNode[26]; // 假设只包含小写字母 a-z
        isEnd = false;
    }
}

public class Trie {
    private TrieNode root;
    
    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }
    
    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEnd;
    }
    
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }
    
    private TrieNode searchPrefix(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }
}

55. 全排列

  • 一句话描述： 用一个boolean数组visited保存已经访问的元素，下次循环直接跳过；回溯三部曲：终止条件，for循环递归，回溯撤销

55.1 题目描述

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

1
2
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

55.2 算法思想和代码实现

  • 用visited保存已经访问过的元素，下次循环直接跳过
  • 终止条件：排列的长度等于数组长度
  • 循环+递归：跳过已经访问过的元素，没有访问的元素加入排列结果
  • 回溯：撤销当前选择的元素，并将visited改为true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class Solution055 {
    List<List<Integer>> result = new ArrayList<>();// 存储最终的全排列结果
    List<Integer> path = new ArrayList<>();// 存储当前排列的路径
    boolean[] visited;// 记录某个元素是否被使用
    
    public List<List<Integer>> permute(int[] nums) {
        if (nums == null || nums.length == 0)
            return result;

        // 初始化 visited 数组，长度等于输入数组长度，初始值默认为 false
        visited = new boolean[nums.length];
        
        permuteHelper(nums);
        return result;
    }

    // 递归回溯函数
    public void permuteHelper(int[] nums) {
        // 终止条件：当前排列的长度等于输入数组长度
        if (path.size() == nums.length) {
            // 返回当前路径
            result.add(new ArrayList<>(path));
            return;
        }

        // 遍历所有元素，尝试加入排列
        for (int i = 0; i < nums.length; i++) {
            // 如果当前元素已被使用，则跳过
            if (visited[i])
                continue;

            // 选择当前元素
            path.add(nums[i]);
            visited[i] = true;

            // 递归进入下一层
            permuteHelper(nums);

            // 撤销选择，进行回溯
            path.removeLast();
            visited[i] = false;
        }
    }
}

56. 子集

  • 一句话描述： 收集子集，for(){收集元素，递归到下一层元素，回溯撤销}

56.1 题目描述

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

1
2
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

56.2 算法思想和代码实现

1
2
3
4
5
6
7
                        []
           /            |            \
        [1]            [2]           [3]
       /   \           /            /
   [1,2]  [1,3]     [2,3]        
    /                    
[1,2,3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
List<List<Integer>> result = new ArrayList<List<Integer>>();//保存最终结果
List<Integer> path=new ArrayList<>();//保存当前路径下的结果

public List<List<Integer>> subsets(int[] nums) {
    subsetsHelper(nums, 0);
    return result;
}

public void subsetsHelper(int[] nums,int start){
    //返回当前每一种情况的子集
    result.add(new ArrayList<>(path));
    
    //遍历完整个数组之后结束
    if(start>nums.length){
        return;
    }

    for(int i=start;i<nums.length;i++){
        path.add(nums[i]);
        subsetsHelper(nums,i+1);
        path.removeLast();//撤销，回溯
    }
}

57. 电话号码的字母组合

  • 一句话总结：
  • 通过回溯法依次遍历输入数字串 digits，从第一个数字开始，根据数字映射的字母表，逐个尝试每个字母，将其加入当前路径 path，然后递归处理下一个数字。当遍历到路径长度等于输入长度时，说明已生成一个完整组合，将其拼接成字符串加入结果列表 result，随后回退（撤销最后一个字符）继续尝试其它可能，直到穷尽所有组合。

57.1 题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

1
2
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

57.2 算法思想和代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
List<String> result = new ArrayList<>();    // 用于存储最终的组合结果
List<Character> path = new ArrayList<>();    // 用于存储当前递归路径上的字符

// 用于映射数字到对应的字母字符
String[] mapString = {
        " ", " ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};

public List<String> letterCombinations(String digits) {
    // 如果输入为空，则直接返回空列表
    if (digits == null || digits.length() == 0)
        return result;

    // 进行回溯搜索
    letterCombinationsHelper(digits, 0);
    return result;
}

public void letterCombinationsHelper(String digits, int index) {
    // 递归终止条件：当索引等于字符串长度时，表示已经生成了一个完整的组合
    if (index == digits.length()) {
        
        // 将 path 中的字符拼接成字符串并加入结果列表
        StringBuilder sb = new StringBuilder();
        for (char c : path) {
            sb.append(c);
        }
        result.add(sb.toString());
        return;
    }

    // 取出当前索引对应的数字，并找到其对应的字母字符串
    String str = mapString[digits.charAt(index) - '0'];

    // 遍历该数字对应的所有字母
    for (int i = 0; i < str.length(); i++) {
        // 选择当前字母，加入路径
        path.add(str.charAt(i));
        // 递归处理下一个数字
        letterCombinationsHelper(digits, index + 1);
        // 撤销选择（回溯）
        path.removeLast();
    }
}

58. 组合总和

  • 一句话描述： 当前缀和等于target时，终止递归；for(){添加当前元素，递归进入下一层，回溯撤销}

58.1 题目描述

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

1
2
3
4
5
6
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

58.2 算法思想和代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
List<List<Integer>> res = new ArrayList<>();
   List<Integer> path = new ArrayList<>();

   public List<List<Integer>> combinationSum(int[] candidates, int target) {
       //先对整数数组进行排序
     //  Arrays.sort(candidates);

       combinationSumHelper(candidates, target, 0, 0);
       return res;
   }

   public void combinationSumHelper(int[] candidates, int target, int start, int sum) {
       if (sum == target) {
           res.add(new ArrayList<>(path));
           return;
       }

       for (int i = start; i < candidates.length; i++) {
           // 如果 sum + candidates[i] > target 就终止遍历
           if (sum + candidates[i] > target) break;

           path.add(candidates[i]);
           combinationSumHelper(candidates, target, i, sum + candidates[i]);
           path.removeLast();
       }

   }

59. 括号生成

  • 一句话描述：
  • 当左右括号用完了终止递归加入结果(left==0&&right==0)
  • 当左括号数量大于0可以选择左括号
  • 当右括号剩余数量大于左括号剩余数量，可以选择右括号，然后添加递归回溯

59.1 题目描述

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

1
2
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

59.2 算法思想和代码实现

  • 只有剩余的左括号数量大于 0 时，才可以选择左括号
  • 只有右括号剩余数量大于左括号时，才可以选择右括号
  • 递归终止条件：如果左右括号都用完了，加入结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
List<String> res = new ArrayList<>();
List<Character> path = new ArrayList<>();

public List<String> generateParenthesis(int n) {
    generateParenthesisHelper(n, n);
    return res;
}

public void generateParenthesisHelper(int left, int right) {
    // 递归终止条件：如果左右括号都用完了，加入结果
    if (left == 0 && right == 0) {
        StringBuilder sb = new StringBuilder();
        for (char c : path) {
            sb.append(c);
        }
        res.add(sb.toString());
        return;
    }

    // 只有剩余的左括号数量大于 0 时，才可以选择左括号
    if (left > 0) {
        path.add('(');
        generateParenthesisHelper(left - 1, right);
        path.removeLast();
    }

    // 只有右括号剩余数量大于左括号时，才可以选择右括号
    if (right > left) {
        path.add(')');
        generateParenthesisHelper(left, right - 1);
        path.removeLast();
    }
}

60. 单词搜索

  • 一句话描述： 通过双重循环遍历二维字符数组的每个元素，找到与单词首字符相同的位置后，调用递归函数向上下左右四个方向查找下一个字符，每访问一个字符就将其暂时标记为已访问（用 # 替换），防止重复走回头路，递归如果找到完整单词则返回 true，未找到则恢复该位置原字符，继续尝试其他路径，直到所有可能都搜索完毕。

60.1 题目描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

1
2
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

60.2 算法思想和代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public boolean exist(char[][] board, String word) {
      for (int i = 0; i < board.length; i++) {
          for (int j = 0; j < board[0].length; j++) {
              if (isExist(board, word, i, j, 0)) {
                  return true;
              }
          }
      }
      return false;
  }

  public boolean isExist(char[][] board, String word, int row, int col, int num) {
      // 递归终止条件：找到完整单词
      if (num == word.length()) return true;

      // 边界检查：是否超出范围
      if (row < 0 || col < 0 || row >= board.length || col >= board[0].length) return false;

      // 检查当前字符是否匹配
      if (board[row][col] != word.charAt(num)) return false;

      board[row][col] = '#'; // 标记已访问，防止重复使用

      // 尝试向四个方向寻找下一个字符
      boolean found = isExist(board, word, row + 1, col, num + 1) ||
              isExist(board, word, row - 1, col, num + 1) ||
              isExist(board, word, row, col + 1, num + 1) ||
              isExist(board, word, row, col - 1, num + 1);

      // 恢复原来的字符
      board[row][col] = word.charAt(num);

      return found;
  }

61. 分割回文串

  • 一句话描述： 通过从字符串的起始位置开始，用循环依次截取不同长度的子串，判断当前子串是否是回文串，如果是则将其加入路径列表，并递归继续处理剩余部分，直到遍历完整个字符串，将完整路径加入结果列表，递归返回时通过 removeLast() 撤销上一次添加的子串，继续尝试下一种截取方式。

61.1 题目描述

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

1
2
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

61.2 算法思想和代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
List<List<String>> res = new ArrayList<>();
 List<String> path = new ArrayList<>(); // 存储每个回文子串

 public List<List<String>> partition(String s) {
     partitionHelper(s, 0);
     return res;
 }

 public void partitionHelper(String s, int start) {
     if (start == s.length()) {
         res.add(new ArrayList<>(path));
         return;
     }

     for (int i = start; i < s.length(); i++) {
         String sub = s.substring(start, i + 1); // 取出子串【start,i+1),左闭区间，右开区间

         if (isPalindrome(sub)) {
             path.add(sub); // 记录回文子串
             partitionHelper(s, i + 1); // 递归
             path.removeLast(); // 回溯，移除最后加入的子串
         }
     }
 }

 // 回文判断
 public boolean isPalindrome(String s) {
     int left = 0, right = s.length() - 1;
     while (left < right) {
         if (s.charAt(left) != s.charAt(right)) {
             return false;
         }
         left++;
         right--;
     }
     return true;
 }

62. N皇后

  • 一句话描述： 循环尝试在棋盘的每一行每一列放置皇后，遇到符合条件的位置就将皇后放下，并递归进入下一行继续放置，直到所有行都放置完毕时将当前棋盘状态转换成字符串列表加入结果集中，递归返回时通过将皇后位置回溯复原，继续尝试下一列的位置，最终遍历出所有可能的皇后摆放方案。

62.1 题目描述

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

1
2
3
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

62.2 算法思想和代码实现

  1. 递归搜索
    • 按行进行搜索，每行尝试放置一个皇后。
    • 当所有行都放置完皇后时，将当前棋盘加入 ans 结果集。
  2. 合法性检查
    • 在尝试放置皇后前，检查当前列、左上方 45° 对角线、右上方 135° 对角线是否已有皇后。
    • 只有满足条件的位置才能放置皇后。
  3. 回溯
    • 先尝试在当前行的某一列放置皇后。
    • 递归处理下一行。
    • 如果递归失败（即后续行无法放置皇后），撤销当前放置（回溯），尝试当前行的下一列。
  4. 终止条件
    • 当 row == n（即所有行都放置完皇后）时，表示找到了一种合法解法，存入 ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
List<List<String>> ans = new ArrayList<>(); // 存储所有可能的 N 皇后解法

public List<List<String>> solveNQueens(int n) {
    char[][] chess = new char[n][n]; // 创建 n × n 的棋盘
    // 初始化棋盘，所有位置填充为 '.'（表示空位）
    for (char[] c : chess)
        Arrays.fill(c, '.');
    dfs(0, n, chess); // 递归回溯从第 0 行开始
    return ans;
}

private void dfs(int row, int n, char[][] chess) {
    // 终止条件：所有行都已经放置了皇后
    if (row == n) {
        List<String> list = new ArrayList<>();
        for (char[] c : chess)  // 将当前棋盘的每一行转换为字符串
            list.add(String.copyValueOf(c));
        ans.add(list);  // 将这一种可行解加入结果集
        return;
    }

    // 在当前行的每一列尝试放置皇后
    for (int col = 0; col < n; col++) {
        if (isValid(row, col, n, chess)) { // 检查当前位置是否可以放置皇后
            chess[row][col] = 'Q';  // 放置皇后
            dfs(row + 1, n, chess);  // 递归放置下一行的皇后
            chess[row][col] = '.';  // 回溯：撤销放置，尝试下一列
        }
    }
}

private boolean isValid(int row, int col, int n, char[][] chess) {
    // 1. 检查当前列是否已有皇后
    for (int i = 0; i < row; i++)
        if (chess[i][col] == 'Q')
            return false;

    // 2. 检查左上方 45° 斜线是否已有皇后
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
        if (chess[i][j] == 'Q')
            return false;

    // 3. 检查右上方 135° 斜线是否已有皇后
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
        if (chess[i][j] == 'Q')
            return false;

    // 如果当前位置符合规则，则返回 true
    return true;
}

63. 搜索插入位置

  • 一句话描述： 二分查找

63.1 题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

1
2
输入: nums = [1,3,5,6], target = 5
输出: 2

63.2 算法思想和代码实现

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int searchInsert(int[] nums, int target) {
    int left = 0, right = nums.length - 1;

    while (left <= right) {
        int mid = (left + right) / 2;

        if (nums[mid] == target)
            return mid;
        else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    // 当目标值不存在于数组中时，返回插入位置，即左指针的位置
    return left;
}

64. 搜索二维矩阵

  • 一句话描述： 二分查找：从右上角元素向下或向左移动

64.1 题目描述

给你一个满足下述两条属性的 m x n 整数矩阵：

  • 每行中的整数从左到右按非严格递增顺序排列。
  • 每行的第一个整数大于前一行的最后一个整数。
    给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
1
2
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

64.2 算法思想和代码实现

二分查找：从右上角元素向下或向左移动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static boolean searchMatrix(int[][] matrix, int target) {
    //i和j分别记录右上角的元素
    int i = 0, j = matrix[0].length - 1;

    while (i < matrix.length && j >= 0) {
        if (matrix[i][j] == target)
            return true;
        else if (matrix[i][j] > target)
            j--;
        else if (matrix[i][j] < target)
            i++;
    }

    return false;
}

65. 在排序数组中查找元素的第一个和最后一个位置

  • 一句话描述：
  • 二分查找先查找第一个位置，再查找结束位置
  • 查找左边位置时，当nums[mid] == target，right = mid - 1不断向左收缩
  • 查找右边位置时，当nums[mid] == target，left = mid + 1不断向右收缩

65.1 题目描述

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

1
2
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

65.2 算法思想和代码实现

分两次查找，第一次二分查找开始位置，第二次二分查找结束位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public static int[] searchRange(int[] nums, int target) {
    int first = findFirstPosition(nums, target);
    if (first == -1) {
        return new int[]{-1, -1};
    }
    int last = findLastPosition(nums, target);

    return new int[]{first, last};
}

//二分查找第一个位置
private static int findFirstPosition(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;  // 不断收缩右边界，直到找到最左的target
        }
    }
    
    if (left < nums.length && nums[left] == target) {
        return left;
    }
    return -1;
}

//二分查找最后一个位置
private static int findLastPosition(int[] nums, int target) {
    int left = 0, right = nums.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;  // 不断收缩左边界，直到找到最右的target
        }
    }
    
    if (right >= 0 && nums[right] == target) {
        return right;
    }
    return -1;
}

66. 搜索旋转排序数组

  • 一句话描述：
  • 直接对数组进行二分，其中一定有一个子区间是有序的，另一个部分有序
  • 判断哪个区间是有序的，然后继续进行逻辑判断

66.1 题目描述

整数数组 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) 的算法解决此问题。

66.2 算法思想和代码实现

  • 直接对数组进行二分，其中一定有一个子区间是有序的，另一个部分有序
    1. 如果target在这个有序区间内：直接二分
    2. 如果target在另一个区间内：二分后仍得到一个有序和部分有序区间，不断往复。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public static int search(int[] nums, int target) {
     int left = 0, right = nums.length - 1; 

     while (left <= right) { 
         int mid = left + (right - left) / 2;

         // 如果中间元素就是目标值，则返回索引
         if (nums[mid] == target) { 
             return mid;
         }

         // 判断左半部分是否是有序的
         if (nums[left] <= nums[mid]) {
             // 如果目标值在左半部分范围内，则缩小右边界
             if (target >= nums[left] && target < nums[mid]) {
                 right = mid - 1;
             } else { // 否则搜索右半部分
                 left = mid + 1;
             }
         }

         // 如果右半部分是有序的
         else if (nums[left] > nums[mid]) {
             // 如果目标值在右半部分范围内，则缩小左边界
             if (target <= nums[right] && target > nums[mid]) {
                 left = mid + 1;
             } else { // 否则搜索左半部分
                 right = mid - 1;
             }
         }
     }
     return -1; // 未找到目标值，返回 -1
 }

67. 寻找旋转排序数组的最小值

  • 一句话描述：
    • 如果 nums[mid] > nums[right]，最小值一定在右边，left=mid+1
    • 如果 nums[mid] <= nums[right]，最小值在左边，right=mid
    • 退出循环时，left == right，正是最小值的位置

67.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
2
3
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

67.2 算法思想和代码实现

  • 如果 nums[mid] > nums[right]，最小值一定在右边，left=mid+1
  • 如果 nums[mid] <= nums[right]，最小值在左边，right=mid
  • 退出循环时，left == right，正是最小值的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int findMin(int[] nums) {
    int left = 0, right = nums.length - 1;

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] > nums[right]) {
            // 最小值在右半边
            left = mid + 1;
        } else {
            // 最小值在左半边（包含 mid）
            right = mid;
        }
    }

    return nums[left]; // 或 nums[right]，此时 left == right
}

68. 寻找两个正序数组的中位数

  • 一句话描述： 难，，直接暴力吧

68.1 题目描述

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

1
2
3
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

68.2 算法思想和代码实现

  • 将两个数组划分为左右两部分，确保：
    • 左半部分的所有元素 ≤ 右半部分的所有元素。
    • 这样，左半部分的最大值是中位数（如果总数是奇数）。
    • 如果总数是偶数，中位数是左半部分的最大值和右半部分的最小值的平均值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;

        // 保证 nums1 是较短的数组
        if (m > n) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int left = 0, right = m, halfLen = (m + n + 1) / 2;
        while (left <= right) {
            int i = (left + right) / 2;
            int j = halfLen - i;

            if (i < m && nums1[i] < nums2[j - 1]) {
                left = i + 1; // i 过小，需要右移
            } else if (i > 0 && nums1[i - 1] > nums2[j]) {
                right = i - 1; // i 过大，需要左移
            } else { // i 是合适的切割位置
                int maxLeft;
                if (i == 0) {
                    maxLeft = nums2[j - 1];
                } else if (j == 0) {
                    maxLeft = nums1[i - 1];
                } else {
                    maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
                }

                if ((m + n) % 2 == 1) {
                    return maxLeft; // 奇数长度直接返回中位数
                }

                int minRight;
                if (i == m) {
                    minRight = nums2[j];
                } else if (j == n) {
                    minRight = nums1[i];
                } else {
                    minRight = Math.min(nums1[i], nums2[j]);
                }

                return (maxLeft + minRight) / 2.0; // 偶数长度返回均值
            }
        }
        return 0;
    }

69. 有效的括号

  • 一句话描述： 遇到左括号入栈，右括号如果能与栈顶左括号匹配则正确，不匹配返回false

69.1 题目描述

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

69.2 算法思想和代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public boolean isValid(String s) {
    Stack<Character> stack = new Stack<Character>();
    
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        
        //如果字符是左括号，则入栈
        if (c == '(' || c == '{' || c == '[')
            stack.push(c);

        //如果字符是右括号
        if (c == ')' || c == '}' || c == ']') {
            //为空返回false
            if (stack.isEmpty())
                return false;

            //如果此时字符和栈顶元素相同，则弹出栈顶元素，否则返回false
            if (stack.peek() == '(' && c == ')' || stack.peek() == '{' && c == '}' || stack.peek() == '[' && c == ']') {
                stack.pop();
            } else return false;
        }
    }
    
    return stack.isEmpty();
}

70. 最小栈

  • 一句话描述： 用一个链表包含val和min两个成员变量，min用来保存最小值，入栈就是链表头结点头插一个新元素，出栈就是指向头结点下一个结点

70.1 题目描述

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

70.2 算法思想和代码实现

  • 使用链表实现一个栈的操作
  • 链表的头部始终指向栈顶元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class MinStack {
    // 头节点，始终指向栈顶
    Node head;
    
    public MinStack() {
        head = null; // 栈初始化为空
    }

    public void push(int val) {
        // 如果栈为空，则新节点的 min 值就是 val 本身
        if (head == null) {
            head = new Node(val, val);
            return;
        }

        // 如果栈非空，新节点的 min 取当前值与前一个 min 的较小值
        head = new Node(val, Math.min(val, head.min), head);
    }
    
    public void pop() {
        head = head.next; // 直接指向下一个节点，删除当前栈顶
    }
    
    public int top() {
        return head.val;
    }

    public int getMin() {
        return head.min;
    }
    
    //创建一个链表内部类
    class Node {
        int val;
        int min;
        Node next;

        // 构造方法（用于创建栈底节点）
        public Node(int val, int min) {
            this.val = val;
            this.min = min;
            this.next = null;
        }

        // 构造方法（用于创建普通节点，包含 next 指针）
        public Node(int val, int min, Node next) {
            this.val = val;
            this.min = min;
            this.next = next;
        }
    }
}

71. 字符串解码

  • 一句话描述： 难，使用两个栈

71.1 题目描述

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

1
2
输入：s = "3[a]2[bc]"
输出："aaabcbc"

71.2 算法思想和代码实现

使用两个栈：

  • 一个存放重复次数（countStack）
  • 一个存放之前的部分字符串（resStack）
  1. 当遇到 [ 时，意味着开始一个新的子串，需要把当前的 StringBuilder 存入栈，新的部分重新开始。
  2. 当遇到 ] 时，意味着这个子串已经结束，要取出 count 并重复添加到上一级字符串中。
  3. 当遇到数字字符时，计算对应的数字，因为数字取值在300以内，不一定是单个字符，可能为多个字符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public static String decodeString(String s) {
    Stack<Integer> countStack = new Stack<>(); //存放次数
    Stack<StringBuilder> resStack = new Stack<>(); //存放括号中的字符串
    StringBuilder currentStr = new StringBuilder();
    int k = 0;

    for (char c : s.toCharArray()) {
        if (Character.isDigit(c)) {
            // 计算完整的数字
            k = k * 10 + (c - '0');
        } else if (c == '[') {
            
            // 将当前的字符串和次数入栈
            countStack.push(k);
            resStack.push(currentStr);
            
            // 开始新的字符串
            currentStr = new StringBuilder();
            k = 0;
        } else if (c == ']') {
            
            // 结束当前字符串，取出对应的次数
            StringBuilder decodedStr = resStack.pop();
            
            int repeatTimes = countStack.pop();
            for (int i = 0; i < repeatTimes; i++) {
                decodedStr.append(currentStr);
            }
            
            currentStr = decodedStr;  // 继续拼接上层字符串
        } else {
            currentStr.append(c);
        }
    }
    return currentStr.toString();
}

72. 每日温度

  • 一句话描述：
  • 使用一个单调递减的栈，栈用来存储索引
  • 如果当前温度小于等于栈顶温度则入栈
  • 当前温度大于栈顶元素，栈顶元素的天数更新并出栈

72.1 题目描述

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

1
2
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

72.2 算法思想和代码实现

  1. 初始化一个单调递减栈 stack，存储温度的索引。
  2. 遍历 temperatures 数组：
    • 当栈不为空，且当前温度大于栈顶索引对应的温度时：
      • 说明找到了栈顶元素的下一个更高温度，计算间隔天数并更新 res。
      • 继续弹出栈顶，直到栈为空或栈顶温度大于当前温度。
      • 将当前索引 i 入栈。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int[] dailyTemperatures(int[] temperatures) {
     int[] res = new int[temperatures.length]; //res数组存储最终结果
     Deque<Integer> stack = new ArrayDeque<>(); //定义一个单调栈

     for (int i = 0; i < temperatures.length; i++) {
         //只有栈为空或者当前温度比栈顶温度小的时候，入栈
         if (stack.isEmpty() || temperatures[i] <= temperatures[stack.peek()]) {
             stack.push(i);
         }

         //如果当前温度比栈顶温度大
         if (temperatures[i] > temperatures[stack.peek()]) {
             while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
                 res[stack.peek()] = i - stack.peek();
                 stack.pop();
             }
             stack.push(i);
         }
     }

     return res;
 }

73. 柱形图中最大的矩形

  • 一句话描述： 双指针暴力，以当前柱子向左向右，找比自己高度大(大于等于)的柱子，计算当前面积并更新

73.1 题目描述

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

1
2
3
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

73.2 算法思想和代码实现

  • 双指针暴力
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int largestRectangleArea(int[] heights) {
    int maxArea = 0;
    int n = heights.length;

    for (int i = 0; i < n; i++) {
        int height = heights[i];
        int left = i, right = i;

        // 向左扩展
        while (left > 0 && heights[left - 1] >= height) {
            left--;
        }

        // 向右扩展
        while (right < n - 1 && heights[right + 1] >= height) {
            right++;
        }

        int width = right - left + 1;
        int area = height * width;
        maxArea = Math.max(maxArea, area);
    }

    return maxArea;
}

利用单调递增栈快速找到每个柱子的左右边界，计算出以该柱子为高的最大矩形面积

  • 对于每根柱子，如何快速找到其左右边界？
    通常，我们关心 以某个柱子 heights[i] 为高的最大矩形：
    • 这个矩形的 宽度 由该柱子 左侧第一个小于该柱子的柱子 和 右侧第一个小于该柱子的柱子 决定。
    • 这个矩形的 面积 = 高度 × 宽度。
      如何快速找到左右边界?
    • 用单调递增栈（从小到大存柱子的索引）来维护递增序列：
    • 当当前柱子 heights[i] 大于等于栈顶柱子，说明矩形还可以扩展，入栈。
    • 当当前柱子 heights[i] 小于栈顶柱子，说明矩形不能继续扩展了，栈顶柱子对应的最大矩形的宽度边界已经确定，可以计算面积。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public static int largestRectangleArea(int[] heights) {
      // 使用单调栈（存储柱子的索引）来计算最大矩形面积
      Deque<Integer> stack = new ArrayDeque<>();
      int area = 0;

      // 遍历数组，并在最后额外处理一次栈中剩余的元素
      for (int i = 0; i <= heights.length; i++) {
          int h;
          // 当遍历到最后一个位置时，假设一个高度为 0 的柱子，以便清空栈
          if (i == heights.length) {
              h = 0;
          } else {
              h = heights[i];
          }

          // 维护单调递增栈（栈中存放的是索引）
          // 如果当前柱子的高度 h 小于栈顶索引对应的柱子高度，则说明栈顶柱子的右边界确定
          while (!stack.isEmpty() && h < heights[stack.peek()]) {
              int height = heights[stack.pop()]; // 弹出栈顶元素，表示以该柱子为高的矩形结束
              int width;

              // 如果栈为空，说明当前弹出的柱子是所有柱子中最矮的，其宽度是 `i`
              if (stack.isEmpty()) {
                  width = i;
              } else {
                  //宽度 = 右边界 i - 左边界 stack.peek() - 1
                  // 否则，矩形的宽度是 `i - stack.peek() - 1`
                  // 其中 `stack.peek()` 是左边第一个比它小的柱子
                  width = i - stack.peek() - 1;
              }
              
              area = Math.max(area, width * height);
          }

          // 将当前柱子索引入栈，确保栈内索引对应的高度是递增的
          stack.push(i);
      }
      return area;
  }

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

  • 一句话描述： 使用小顶堆，堆顶元素始终是最小的元素，如果当前元素大于堆顶元素，堆顶元素出堆，当前元素入堆，最后堆顶元素就是第k个大的元素；换句话说就是用小顶堆把k-1个小的元素挤出去

74.1 题目描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

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

1
2
输入: [3,2,1,5,6,4], k = 2
输出: 5

74.2 算法思想和代码实现

  • 采用小顶堆维护前 k 大元素
    • 由于 Java 的 PriorityQueue 默认是小顶堆，所以堆顶元素（peek()）始终是堆中最小的元素。
    • 这样，我们可以用大小为 k 的最小堆，确保堆中存储的是数组中前 k 大的元素。
    • 最后栈顶元素就是数组第k个大的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static int findKthLargest(int[] nums, int k) {
       // 使用小顶堆，用于维护前 k 大的元素
       PriorityQueue<Integer> pq = new PriorityQueue<>();

       // 先将前 k 个元素加入堆中，建立一个大小为 k 的最小堆
       for (int i = 0; i < k; i++) {
           pq.offer(nums[i]);
       }

       // 遍历数组剩余元素，确保堆中始终保留 k 个最大的元素
       for (int i = k; i < nums.length; i++) {
           if (nums[i] > pq.peek()) { // 只有当前元素比堆顶元素大时，才进行替换
               pq.poll(); // 最小的元素弹出堆顶
               pq.offer(nums[i]); // 插入新元素，保证堆中始终有 k 个最大的元素
           }
       }

       // 堆顶元素就是整个数组中第 k 大的元素
       return pq.peek();
   }

75. 前K个高频元素

  • 一句话描述：
  • 哈希表统计频率，用小根堆维护前k个高频元素
  • PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(k,(l1, l2) -> l1.getValue() - l2.getValue());
  • for (Map.Entry<Integer, Integer> entry : map.entrySet()) {}

75.1 题目描述

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

1
2
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

75.2 算法思想和代码实现

小根堆 + 哈希表

  • 利用哈希表统计频率
  • 然后用小根堆维护前 K 个高频元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public static int[] topKFrequent(int[] nums, int k) {
    HashMap<Integer, Integer> map = new HashMap<>();

    // 统计频率
    for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }

    // 使用最小堆，按频率排序
    PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(k,(l1, l2) -> l1.getValue() - l2.getValue());

    // 维护一个大小为 k 的小根堆
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
        if (pq.size() < k) {
            pq.offer(entry);
        } else if (entry.getValue() > pq.peek().getValue()) {
            pq.poll();
            pq.offer(entry);
        }
    }

    // 取出堆中的 k 个元素
    int[] res = new int[k];
    for (int i = k - 1; i >= 0; i--) {
        res[i] = pq.poll().getKey();
    }

    return res;
}

76. 数据流的中位数

  • 一句话描述：
  • 利用两个堆（大根堆+小根堆），
  • 添加元素先添加到小顶堆，再把小顶堆的堆顶元素添加到大顶堆，
  • 如果小顶堆大小小于大顶堆大小(minHeap.size() < maxHeap.size())，把大顶堆的堆顶元素添加到小顶堆

76.1 题目描述

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

  • 例如 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
2
3
4
5
6
7
8
9
10
11
12
13
输入
["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

76.2 算法思想和代码实现

利用两个堆（大根堆+小根堆）维护数据流的中位数

  • 采用两个堆
    • 大根堆 maxHeap（存较小的一半）：堆顶是较小的一半数据中的 最大值。
    • 小根堆 minHeap（存较大的一半）：堆顶是较大的一半数据中的 最小值。
  • 保证大根堆 maxHeap 的元素个数 不小于 小根堆 minHeap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class MedianFinder {
      PriorityQueue<Integer> minHeap;
      PriorityQueue<Integer> maxHeap;

      public MedianFinder() {
          minHeap = new PriorityQueue<>();
          // 使用自定义比较器，降序排列
          maxHeap = new PriorityQueue<>((a, b) -> b - a);
      }

      public void addNum(int num) {
          // 先将新元素添加到大根堆
          maxHeap.offer(num);
          // 把大根堆的最大值移动到小根堆，保证 minHeap 存储较大的一半数据
          minHeap.offer(maxHeap.poll());

          // 如果小根堆的大小大于大根堆，则需要调整，保持 maxHeap >= minHeap
          if (minHeap.size() > maxHeap.size()) {
              maxHeap.offer(minHeap.poll());
          }
      }

      public double findMedian() {
          // 若两个堆大小相等，说明总元素个数是偶数，取两个堆顶元素的平均值
          if (minHeap.size() == maxHeap.size()) {
              return (minHeap.peek() + maxHeap.peek()) / 2.0;
          }
          // 若大根堆元素较多，说明总数是奇数，中位数是大根堆的堆顶元素
          else {
              return maxHeap.peek();
          }
      }
  }

77. 买卖股票的最佳时机

  • 一句话描述； 要想卖的时候利润最多，就要在之前最便宜的时候买入，因此维护之前的最小值即可。

77.1 题目描述

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

1
2
3
4
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

77.2 算法思想和代码实现

要想卖的时候利润最多，就要在之前最便宜的时候买入，因此维护之前的最小值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//要想卖的时候利润最多，就要在之前最便宜的时候买入，因此维护之前的最小值即可。
public static int maxProfit(int[] prices) {
    int maxProfit = 0;
    int minPrice = Integer.MAX_VALUE;

    for (int i = 0; i < prices.length; i++) {
        //维护之前的最小值
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        }
        
        //如果当前卖出的利润最多，则更新最大利润
        if (prices[i] - minPrice > maxProfit) {
            maxProfit = prices[i] - minPrice;
        }
    }

    return maxProfit;
}

78. 跳跃游戏

  • 一句话描述：
  • 维护一个 farthest 变量，记录能跳到的最远距离
  • 如果当前索引超过了能跳到的最远距离，则跳不到终点

78.1 题目描述

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

1
2
3
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

78.2 算法思想和代码实现

使用 贪心算法 维护一个 farthest 变量，记录能跳到的最远距离

  • 如果遍历到 i 时 farthest 不能再往前推进，则返回 false
1
2
3
4
5
6
7
8
9
10
11
public static boolean canJump(int[] nums) {
    int farthest = 0; // 维护能跳到的最远距离

    for (int i = 0; i < nums.length; i++) {
        if (i > farthest) return false; // 如果当前索引超过了能跳到的最远距离，则跳不到终点
        farthest = Math.max(farthest, i + nums[i]); // 更新最远能到达的位置
        if (farthest >= nums.length - 1) return true; // 如果最远可以到达终点，则直接返回 true
    }

    return false;
}

79. 跳跃游戏 II

  • 一句话描述：
  • 局部最优，找到下一个能跳的最远的位置，找最大的(下一个位置索引加上下一个位置最大跳跃距离)
  • 如果当前位置已经能到达终点，count++,跳出循环

79.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
2
3
4
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

79.2 算法思想和代码实现

维护当前跳跃的覆盖范围，更新最远可达位置
记录下一次能到达的最远位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int jump(int[] nums) {
    int count = 0;
    for (int i = 0; i < nums.length - 1; ) {
        //如果当前位置已经能到达终点，count++,跳出循环
        if (nums[i] + i >= nums.length - 1) {
            count++;
            break;
        }

        //局部最优，找到下一个能跳的最远的位置，找最大的(下一个位置索引加上下一个位置最大跳跃距离)
        int nextNum = 0, nextJump = i;
        for (int j = i + 1; j <= i + nums[i]; j++) {
            if (j + nums[j] >= nextNum) {
                nextJump = j;
                nextNum = j + nums[j];
            }
        }
        i = nextJump;
        count++;
    }
    return count;
}

80. 划分字母区间

  • 一句话描述：
  • 使用哈希表保存每个字符的最后出现位置
  • 若发现某个字符的最后出现位置超出了当前片段范围，则更新 nextIndex

80.1 题目描述

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 “ababcc” 能够被分为 [“abab”, “cc”]，但类似 [“aba”, “bcc”] 或 [“ab”, “ab”, “cc”] 的划分是非法的。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

1
2
3
4
5
6
输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

80.2 算法思想和代码实现

  1. 使用哈希表保存每个字符的最后出现位置
  2. 划分字符串：
    • 遍历字符串，每次确定当前字符所在的片段范围（从 i 到 nextIndex）。
    • 继续遍历该范围内的字符，若发现某个字符的最后出现位置超出了当前片段范围，则更新 nextIndex，以保证这个片段包含所有出现过的字符。
    • 计算该片段的长度，并添加到结果列表中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public List<Integer> partitionLabels(String s) {
    List<Integer> res = new ArrayList<>();
    Map<Character, Integer> map = new HashMap<>();
    
    // 记录每个字符的最后出现位置
    for (int i = 0; i < s.length(); i++) {
        map.put(s.charAt(i), i);
    }

    int nextIndex = 0, start = 0;
    for (int i = 0; i < s.length(); i++) {
        nextIndex = Math.max(nextIndex, map.get(s.charAt(i)));
        
        if (i == nextIndex) {
            res.add(nextIndex - start + 1);
            start = i + 1;
        }
    }

    return res;
}

81. 爬楼梯

  • 一句话描述： dp[i]： 爬到第i层楼梯，有dp[i]种方法

81.1 题目描述

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

1
2
3
4
5
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

81.2 算法思想和代码实现

  1. 确定dp数组以及下标的含义
    • dp[i]： 爬到第i层楼梯，有dp[i]种方法
  2. 确定递推公式
    • dp[i] = dp[i - 1] + dp[i - 2]
  3. dp数组如何初始化
    • dp[1]=1;dp[2]=2;
  4. 确定遍历顺序
    • 从前往后遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int climbStairs(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;

    //确定递推公式
    int[] dp = new int[n + 1];

    //初始化
    dp[1] = 1;
    dp[2] = 2;

    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

82. 杨辉三角

  • 一句话描述：
  • dp[i][j] 代表第i行第j列元素的值
  • dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]

82.1 题目描述

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

1
2
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

82.2 算法思想和代码实现

  1. 确定dp数组
    • dp[i][j] 代表第i行第j列元素的值
  2. 初始化dp数组
    • dp[0][0]=1;dp[i][0]=1;dp[i][i]=1;
  3. 递推公式
    • dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
  4. 遍历顺序
    • 从前往后，从上到下遍历二维数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> res = new ArrayList<>();
    int[][] dp = new int[numRows][numRows];

    // 初始化第一行
    dp[0][0] = 1;
    List<Integer> first = new ArrayList<>();
    first.add(1);
    res.add(first);

    for (int i = 1; i < numRows; i++) {
        List<Integer> temp = new ArrayList<>();
        dp[i][0] = 1;
        temp.add(dp[i][0]);

        for (int j = 1; j < i; j++) {
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; //递推公式
            temp.add(dp[i][j]);
        }

        dp[i][i] = 1;  // 右边界元素也是1
        temp.add(dp[i][i]);

        res.add(temp);
    }
    return res;
}

83. 打家劫舍

  • 一句话描述：
  • dp[i]：盗窃到第i间房间所获得的最高金额
  • dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])

83.1 题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

1
2
3
4
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

83.2 算法思想和代码实现

  1. dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]
  2. 递推公式：
    • 决定dp[i]的因素就是第i房间偷还是不偷。
    • 如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i]
    • 如果不偷第i房间，那么dp[i] = dp[i - 1]，即考 虑i-1房
    • dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
  3. 初始化：dp[1] = max(nums[0], nums[1]);dp[0] 一定是 nums[0]
  4. 从前到后遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int rob(int[] nums) {
       if(nums.length == 1) return nums[0];
       
       //dp数组：考虑是否偷dp[i]所得的最大值
       int[] dp = new int[nums.length];

       //是否偷dp[0]所得的最大值，这里肯定是要偷的，才能得到最大值
       dp[0]=nums[0];
       dp[1]=Math.max(nums[0],nums[1]); //dp[1]的最大值取决于nums[0]和nums[1]哪个大，偷哪个

       for(int i=2;i<nums.length;i++){
           dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]); //递推公式
       }

       return dp[nums.length-1];
   }

84. 完全平方数

  • 一句话描述：
  • 转换为完全背包问题
    • dp[i][j] 表示使用前 i 个完全平方数（1^2, 2^2, …, i^2）凑出 j 需要的最少个数。
    • 不选当前平方数 i^2：dp[i][j] = dp[i-1][j]（继承上一行）。
    • 选择当前平方数 i^2：dp[i][j] = dp[i][j - square] + 1（选 i^2 之后，继续凑 j - i^2）

84.1 题目描述

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

1
2
3
输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

84.2 算法思想和代码实现

转换为完全背包问题

  1. 状态定义
    • dp[i][j] 表示使用前 i 个完全平方数（1^2, 2^2, …, i^2）凑出 j 需要的最少个数。
  2. 初始化
    • dp[0][0] = 0（凑出 0 需要 0 个数）。
    • 其他 dp[i][j] 设为 Integer.MAX_VALUE，表示默认无法凑出。
  3. 状态转移
    • 不选当前平方数 i^2：dp[i][j] = dp[i-1][j]（继承上一行）。
    • 选择当前平方数 i^2：dp[i][j] = dp[i][j - square] + 1（选 i^2 之后，继续凑 j - i^2）。
  4. 遍历方式
    • 外层循环 遍历所有可能的平方数 i^2。
    • 内层循环 遍历目标值 j，尝试用 i^2 进行凑数。
  5. 结果
    最终 dp[maxSqrt][n] 即为凑出 n 所需的最少完全平方数个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static int numSquares(int n) {
    int maxSqrt = (int) Math.sqrt(n);
    int[][] dp = new int[maxSqrt + 1][n + 1];

    // 初始化dp数组
    for (int i = 0; i <= maxSqrt; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i][j] = Integer.MAX_VALUE; // 设为默认最大值
        }
    }

    dp[0][0] = 0; // 凑成 0 需要 0 个数
    
    // 遍历平方数
    for (int i = 1; i <= maxSqrt; i++) {
        int square = i * i;
        for (int j = 0; j <= n; j++) {
            if (j < square) {
                dp[i][j] = dp[i - 1][j]; // 不能选当前平方数，则继承上一行
            } else {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - square] + 1); // 选或者不选
            }
        }
    }

    return dp[maxSqrt][n];
}

85. 零钱兑换

  • 一句话描述：
  • 转换为完全背包问题
  • dp[i][j]：用前 i 种硬币，凑成金额 j 所需的最少硬币数量

85.1 题目描述

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

1
2
3
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

85.2 算法思想和代码实现

转换为完全背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public int coinChange(int[] coins, int amount) {
    int n = coins.length;
    // dp[i][j]：用前 i 种硬币，凑成金额 j 所需的最少硬币数量
    int[][] dp = new int[n + 1][amount + 1];

    // 初始化：
    // 金额为0时，不需要任何硬币
    // 其余金额初始化为一个大数，表示暂时无法凑成
    for (int i = 0; i <= n; i++) {
        for (int j = 1; j <= amount; j++) {
            dp[i][j] = Integer.MAX_VALUE - 1; 
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= amount; j++) { 
            if (j < coins[i - 1]) {
                // 当前硬币面值大于目标金额，无法选，继承上一行的方案
                dp[i][j] = dp[i - 1][j];
            } else {
                // 可以选择当前硬币（无限次）
                // 两种方案取较小值：
                // 1️⃣ 不选当前硬币：dp[i-1][j]
                // 2️⃣ 选当前硬币一次：dp[i][j - coins[i-1]] + 1
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1);
            }
        }
    }

    if (dp[n][amount] == Integer.MAX_VALUE - 1)
        return -1;
    return dp[n][amount];
}

86. 单词拆分

  • 一句话总结：
  • dp[i] 表示字符串 s 的前 i 个字符是否可以由字典中的单词拼接而成
  • dp[i]的值依赖于i之前某个 dp[j] == true，说明 s[0 ~ j-1]可以用字典单词拼接。 s.substring(j, i) 必须在 wordDict 里面，说明 j~i-1 这一段是一个合法单词

86.1 题目描述

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

1
2
3
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

86.2 算法思想和代码实现

  1. 状态定义：
    • dp[i] 表示字符串 s 的前 i 个字符是否可以由字典中的单词拼接而成。
  2. 状态转移方程：
    • dp[i] = true 当且仅当 存在某个 j，满足：
      • dp[j] == true（表示 s[0:j] 可以被拆分）
      • s[j:i] 存在于 wordDict 中（表示 s[j:i] 是一个有效单词）
  3. 初始化：
    • dp[0] = true，表示空字符串可以被拆分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> set = new HashSet<>(wordDict);
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true; // 空字符串可以组成

    for (int i = 1; i <= s.length(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && set.contains(s.substring(j, i))) {
                dp[i] = true;
                break; 
            }
        }
    }
    return dp[s.length()];
}

87. 最长递增子序列

  • 一句话描述：
  • dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
  • 两次遍历：第一次遍历求每个以 nums[i] 结尾的最长递增子序列，第二次遍历i之前的元素，比较元素是否加入当前元素的后面作为结尾

87.1 题目描述

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

1
2
3
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

87.2 算法思想和代码实现

  1. 状态定义：
    • 设 dp[i] 表示 以 nums[i] 结尾的最长递增子序列的长度。
  2. 状态转移方程：
    • 遍历 j（0 ≤ j < i），检查所有可能的前一个元素：
      • 如果 nums[i] > nums[j]，即 nums[i] 可以接在 nums[j] 之后形成更长的递增子序列：
        • dp[i]=max(dp[i],dp[j]+1)
    • 遍历完成后，更新 res 记录 全局最长递增子序列的长度。
  3. 初始化：
    • 每个元素 单独作为子序列时，长度至少是 1，所以 dp[i] 初始为 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static int lengthOfLIS(int[] nums) {
    // dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
    int[] dp = new int[nums.length];
    int res = 1; 

    // 初始化 dp 数组，每个元素单独作为子序列时长度为 1
    for (int i = 0; i < nums.length; i++) {
        dp[i] = 1;
    }

    // 遍历数组，计算每个以 nums[i] 结尾的最长递增子序列
    for (int i = 1; i < nums.length; i++) {
        // 遍历 i 之前的元素 nums[j]，找到比 nums[i] 小的元素
        for (int j = 0; j < i; j++) {
            // 如果 nums[i] > nums[j]，说明可以接在 nums[j] 之后形成递增子序列
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }

        res = Math.max(res, dp[i]);
    }

    return res;
}

88. 乘积最大子数组

  • 一句话描述：
  • 用max和min维护遍历到当前元素时的最大值和最小值
  • 如果当前元素是负数，那么会导致最大的变最小的，最小的变最大的。因此交换两个的值。
  • max = Math.max(max * nums[i], nums[i])
    • 对于每一个 nums[i]，最大乘积有两种选择：
      • 1️⃣ 继续累乘：max * nums[i] —— 把前面的乘积继续乘上这个 nums[i]，不切断子数组。
      • 2️⃣ 重新开始：nums[i] —— 从当前位置 i 开始一个新的乘积子数组。

88.1 题目描述

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

测试用例的答案是一个 32-位 整数。

1
2
3
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

88.2 算法思想和代码实现

对于每个元素 nums[i]，有三种可能的情况：

  1. 当前元素为正数：imax 可能增大，imin 可能减小。分别更新 imax 和 imin。
  2. 当前元素为负数：负数会导致最大乘积变成最小乘积，最小乘积变成最大乘积。此时，应该交换 imax 和 imin，然后根据当前元素更新这两个值。
  3. 当前元素为零：乘积会重置为零，可以跳过对最大和最小值的更新。
  • 更新 max 为 max(imax, max)，记录当前的最大乘积。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int maxProduct(int[] nums) {
    int max = Integer.MIN_VALUE, imax = 1, imin = 1; //一个保存最大的，一个保存最小的。
    for (int i = 0; i < nums.length; i++) {
        //如果数组的数是负数，那么会导致最大的变最小的，最小的变最大的。因此交换两个的值。
        if (nums[i] < 0) {
            int tmp = imax;
            imax = imin;
            imin = tmp;
        }

        imax = Math.max(imax * nums[i], nums[i]);
        imin = Math.min(imin * nums[i], nums[i]);

        max = Math.max(max, imax);
    }
    return max;
}

89. 分割等和子集

  • 一句话描述：
  • 转换为0-1背包问题
  • dp[i][j]：从前 i 个数里，能否选出一些数，使它们的和接近j

89.1 题目描述

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

1
2
3
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

89.2 算法思想和代码实现

89.2.1 转换为0-1背包问题

  1. 如果当前背包容量小于当前物品容量，那就放不进，那就只能取同列上一行的价值(相同的背包，上一个物品时的最优价值)
  2. 在当前背包容量大于当前物品容量时
    • 放入该物品得到一个价值，因为还有剩余容量(剩余容量等于当前背包容量减去当前放入物品容量)，然后到上一行去找这个剩余容量的价值(肯定是最优价值)
    • 然后把新放入物品价值加上剩余容量价值的和与上一行同列的价值进行比较，价值较大者为最优解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//转换为最小背包问题
  public static boolean canPartition(int[] nums) {
      int sum = 0;
      // 计算数组的总和,如果总和为奇数，无法分割成两个和相等的子集,目标是凑够总和/2
      for (int num : nums) {
          sum += num;
      }
      if (sum % 2 != 0) {
          return false;
      }
      int target = sum / 2;

      //dp[i][j]代表放入i时，大小为j的容量的最优解; 初始化：默认初始化为0
      int[][] dp = new int[nums.length + 1][target + 1];

      for (int i = 1; i <= nums.length; i++)
          for (int j = 1; j <= target; j++) {
              if (j < nums[i - 1]) {
                  dp[i][j] = dp[i - 1][j];
              } else {
                  dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i - 1]] + nums[i - 1]);
              }
          }

      return dp[nums.length][target] == target;
  }

89.2.2 方法2

  1. 状态定义

    • dp[i][j] 表示在前 i 个元素中，是否可以选出若干个数，使其和为 j。

  2. 状态转移方程

    • 对于每个元素 nums[i-1]，可以选择“选它”或者“不选它”：
      • 不选 nums[i-1]：dp[i][j] = dp[i-1][j]
      • 选 nums[i-1]（前提 j >= nums[i-1]）：dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i-1]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public static boolean canPartition(int[] nums) {
       int sum = 0;
       // 计算数组的总和,如果总和为奇数，无法分割成两个和相等的子集,目标是凑够总和/2
       for (int num : nums) {
           sum += num;
       }
       if (sum % 2 != 0) {
           return false;
       }
       int target = sum / 2;

       // dp[i][j] 表示是否可以从前 i 个数中选出若干个数，使其和为 j
       boolean[][] dp = new boolean[nums.length + 1][target + 1];

       // 初始化：当 j=0 时，即不选任何数，总和可以为 0
       dp[0][0] = true;

       for (int i = 1; i <= nums.length; i++) {
           for (int j = 0; j <= target; j++) {
               // 继承上一个状态：不选当前数时，是否能凑出 j
               dp[i][j] = dp[i - 1][j];

               // 选当前数：如果 j >= nums[i-1]，则可以尝试选它
               if (j >= nums[i - 1]) {
                   dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
               }

               // 如果已经找到一个子集使其和为 target，提前返回 true
               if (dp[i][target]) return true;
           }
       }
       return false;
   }

90. 最长有效括号

  • 一句话描述：
  • dp[i] 表示以下标 i 结尾的最长有效括号子串的长度，主要在于分情况讨论
  • 当 s[i] == '(' 时
  • 当 s[i] == ')' 时
    • 如果 s[i-1] == '('
    • 如果 s[i-1] == ')'
      • 如果 s[i - dp[i-1] - 1] == '('

90.1 题目描述

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

1
2
3
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

90.2 算法思想和代码实现

定义 dp[i] 表示以下标 i 结尾的最长有效括号子串的长度。状态转移方程如下：

  1. 当 s[i] == '(' 时，dp[i] = 0，因为以左括号结尾不可能是有效括号序列。
  2. 当 s[i] == ')' 时，需要考虑：
    • 如果 s[i-1] == '('，那么 dp[i] = dp[i-2] + 2（前面已有的有效括号子串加上这对新匹配的括号）。
    • 如果 s[i-1] == ')'，那么需要检查 i - dp[i-1] - 1 位置的字符是否是 ‘(‘：
      • 如果 s[i - dp[i-1] - 1] == '('，那么 dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]（前一个有效括号子串加上新匹配的括号，再加上更前面的有效子串）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public static int longestValidParentheses(String s) {
    if (s == null || s.length() < 2) {
        return 0;
    }

    int n = s.length();
    // dp[i] 表示以 s[i] 结尾的最长有效括号子串长度
    int[] dp = new int[n]; 
    int maxLen = 0; // 记录最长有效括号子串的长度

    for (int i = 1; i < n; i++) {
        if (s.charAt(i) == '(') {
            dp[i] = 0;
        }

        // 只有当前字符是 ')' 时才有可能形成有效括号
        if (s.charAt(i) == ')') { 

            // 情况1：前一个字符是 '('，可以直接与它配对形成 "()"
            if (s.charAt(i - 1) == '(') {
                if (i >= 2) { // 如果 i >= 2，则需要加上 dp[i - 2]，表示连接前面的有效括号子串
                    dp[i] = dp[i - 2] + 2;
                } else { // 如果 i < 2，说明 "()" 是当前能形成的唯一有效子串
                    dp[i] = 2;
                }
            }

            // 情况2：前一个字符是 ')'，需要看 i-dp[i-1]-1 是否是 '('，才能形成有效括号
            else {
                // 只有 i - dp[i - 1] - 1 在有效范围内且 s[i - dp[i - 1] - 1] == '('，才能形成匹配
                if (i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + 2;

                    // 如果 i - dp[i - 1] - 1 前面还有有效括号子串，则需要加上它的长度
                    if (i - dp[i - 1] - 1 - 1 >= 0) {
                        dp[i] += dp[i - dp[i - 1] - 1 - 1];
                    }
                }
            }

            // 记录最大值
            maxLen = Math.max(maxLen, dp[i]);
        }
    }

    return maxLen;
}

91. 不同路径

  • 一句话描述： dp[i][j]代表到达第i行第j列的不同路径有多少个

91.1 题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

1
2
输入：m = 3, n = 7
输出：28

91.2 算法思想和代码实现

  • dp[i][j]代表到达第i行第j列的不同路径有多少个
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int uniquePaths(int m, int n) {
    //dp[i][j]代表到达第i行第j列的不同路径有多少个
    int[][] dp =new int[m][n];

    //初始化dp
    dp[0][0]=1;
    for(int i=1;i<m;i++)
        dp[i][0]=1;
    for(int i=1;i<n;i++)
        dp[0][i]=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];
}

92. 最小路径和

  • 一句话描述： dp[i][j]:走到第i行第j列时的最小总和

92.1 题目描述

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

1
2
3
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

92.2 算法思想和代码实现

  • 本单元格的最小路径和依赖于上一行同列和上一列同行的路径和的最小值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        //dp[i][j]:走到第i行第j列时的最小总和
        int[][] dp = new int[m][n];

        //初始化
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }

        //dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }

        return dp[m - 1][n - 1];
    }

93. 最长回文子串

  • 一句话总结：
  • 定义 dp[i][j] 表示字符串从索引 i 到 j 的子串是否是回文子串
  • 更长的子串，s[i] == s[j] 时，它是否回文取决于 s[i+1:j-1] 是否回文串
  • 外层循环 i 递减（从后往前遍历）,内层循环 j 递增（从左到右遍历）,因为 dp[i][j] 依赖于 dp[i+1][j-1]

93.1 题目描述

给你一个字符串 s，找到 s 中最长的 回文 子串。

1
2
3
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

93.2 算法思想和代码实现

与回文子串题目一样，只不过这里求了最长的(回文子串)

  • 定义 dp[i][j] 表示字符串 s 从索引 i 到 j 的子串是否是回文子串
  • 当s[i]和s[j]不相同时，一定是false
  • 当s[i]和s[j]相同时，分以下三种情况：
    • 单个字符一定是回文串，所以 dp[i][i] = true
    • 相邻字符相等时也是回文串，即 dp[i][i+1] = (s[i] == s[i+1])
    • 更长的子串，s[i] == s[j] 时，它是否回文取决于 s[i+1:j-1] 是否回文，即 dp[i][j] = dp[i+1][j-1]。
  • 外层循环 i 递减（从后往前遍历）
    • 因为 dp[i][j] 依赖于 dp[i+1][j-1]，所以要先计算 dp[i+1][j-1] 再计算 dp[i][j]。
  • 内层循环 j 递增（从左到右遍历）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public static String longestPalindrome(String s) {
       int maxLen = 0;
       int left = 0, right = 0;
       //dp[i][j]:从i到j的子串是不是回文的
       boolean[][] dp = new boolean[s.length()][s.length()];

       //i必须要从后往前遍历
       for (int i = s.length() - 1; i >= 0; i--) {
           //j从i开始往后遍历
           for (int j = i; j < s.length(); j++) {
               if (s.charAt(i) == s.charAt(j)) {
                   if (j == i || j == i + 1) {
                       dp[i][j] = true;
                   } else {
                       if (dp[i + 1][j - 1]) {
                           dp[i][j] = true;
                       }
                   }
               }

               if (dp[i][j]) {
                   if (j - i > maxLen) {
                       maxLen = j - i;
                       left = i;
                       right = j;
                   }
               }
           }
       }

       return s.substring(left, right + 1);
   }

94. 最长公共子序列

  • 一句话描述：
  • dp[i][j]: text1前i个字符串和text2前j个字符串的最长公共子序列长度
  • 如果i和j的字符相同，dp[i][j] = dp[i - 1][j - 1] + 1
  • 如果i和j的字符不相同，dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

94.1 题目描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

  • 例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
    两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
1
2
3
输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

94.2 算法思想和代码实现

  • dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
  • 如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;
  • 如果text1[i - 1] 与 text2[j - 1]不相同，那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的。
    • 即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int longestCommonSubsequence(String text1, String text2) {
    //dp[i][j]:text1在0~i子串和text2在0~j子串中的最长公共子序列长度
    int[][] dp = new int[text1.length() + 1][text2.length() + 1];

    //从前往后，从上到下遍历
    for (int i = 1; i <= text1.length(); i++) {
        for (int j = 1; j <= text2.length(); j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[text1.length()][text2.length()];
}

95. 编辑距离

  • 一句话描述:
  • dp[i][j] 表示 word1 的前 i 个字符转换成 word2 的前 j 个字符的最小操作数
  • 如果i和j的字符相同，dp[i][j] = dp[i - 1][j - 1]
  • 如果i和j的字符不相同
    • 替换操作：dp[i-1][j-1] + 1
    • 删除操作：dp[i-1][j] + 1
    • 插入操作：dp[i][j-1] + 1

95.1 题目描述

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符
1
2
3
4
5
6
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

95.2 算法思想和代码实现

  • dp[i][j] 表示 word1 的前 i 个字符转换成 word2 的前 j 个字符的最小操作数
  • 初始化：
    • dp[i][0] = i：word1 变成空串，需要 i 次删除操作。
    • dp[0][j] = j：空串变成 word2，需要 j 次插入操作。
  • 状态转移方程：
    • 若 word1[i-1] == word2[j-1]，则 dp[i][j] = dp[i-1][j-1]（当前字符相同，无需操作）。
    • 否则，取三种操作的最小值：
      • 替换操作：dp[i-1][j-1] + 1
      • 删除操作：dp[i-1][j] + 1
      • 插入操作：dp[i][j-1] + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public static int minDistance(String word1, String word2) {
        // dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最小操作数
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];

        // 初始化 dp 数组
        // 当 word2 为空时，word1 需要删除 i 个字符才能变成 word2
        for (int i = 0; i <= word1.length(); i++)
            dp[i][0] = i;
        // 当 word1 为空时，word2 需要插入 i 个字符才能变成 word1
        for (int i = 0; i <= word2.length(); i++)
            dp[0][i] = i;

        // 从左到右，从上到下遍历
        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                // 如果当前字符相等，则不需要额外操作，继承前一个状态
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 三种操作：
                    // 1. 替换（dp[i - 1][j - 1] + 1）
                    // 2. 删除 word1 的字符（dp[i - 1][j] + 1）
                    // 3. 插入 word2 的字符（dp[i][j - 1] + 1）
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }

96. 只出现一次的数字

  • 一句话描述： 使用异或运算符(^)，a^a=0,a^0=a

96.1 题目描述

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

1
2
输入：nums = [2,2,1]
输出：1

96.2 算法思想和代码实现

96.2.1 排序后遍历(O(nlogn))

先排序，在遍历找到出现一次的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
public static int singleNumber(int[] nums) {
    Arrays.sort(nums);

    if(nums.length==1)
        return nums[0];

    for (int i = 1; i < nums.length; i+=2) {
        if(nums[i]!=nums[i-1])
            return nums[i-1];
    }

    return nums[nums.length-1];
}

96.2.2 位运算：异或

异或：位运算时，相同为0，不同为1

  • a ^ a = 0（相同的数异或后变成 0）
  • a ^ 0 = a（任何数与 0 异或还是它本身）
  • 异或运算满足交换律和结合律，因此所有成对的数字都会变成 0，最终只剩下那个唯一的数。
1
2
3
4
5
6
7
8
9
public static int singleNumber(int[] nums) {
    int result = 0;

    for (int num : nums) {
        result ^= num;
    }

    return result;
}

97. 多数元素

  • 一句话描述： res=当前元素，用一个计数器，当出现自己时，计数+1，不是自己计数-1，当计数器=0时，重新把res置为当前元素

97.1 题目描述

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

1
2
输入：nums = [3,2,3]
输出：3

97.2 算法思想和代码实现

97.2.1 先排序+取中位数

1
2
3
4
public static int majorityElement(int[] nums) {
       Arrays.sort(nums);
       return nums[nums.length / 2];
   }

97.2.2 摩尔投票法

核心就是对拼消耗。
玩一个诸侯争霸的游戏，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。
那就大混战呗，最差所有人都联合起来对付你（对应你每次选择作为计数器的数都是众数），或者其他国家也会相互攻击（会选择其他数作为计数器的数），但是只要你们不要内斗，最后肯定你赢。
最后能剩下的必定是自己人。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int majorityElement2(int[] nums) {
       int x = nums[0];
       int count = 1;
       for (int i = 1; i < nums.length; ++i) {
           if (count == 0) {
               x = nums[i];
           }
           if (nums[i] == x) {
               count++;
           } else {
               count--;
           }
       }
       return x;
   }

98. 颜色分类

  • 一句话描述：
  • 两个指针：一个指针指向0位置，依次存储0元素，一个指针指向数组结尾位置，依次存储2元素

98.1 题目描述

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

1
2
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

98.2 算法思想和代码实现

0，1，2 排序。一次遍历，如果是0，则移动到表头，如果是2，则移动到表尾，不用考虑1。0和2处理完，1还会有错吗？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void sortColors(int[] nums) {
     //x,y记录0和2的位置
     int x = 0, y = nums.length - 1;
     
     for (int i = 0; i < nums.length; i++) {
         //如果当前元素是0，把它放到数组开头位置
         if (nums[i] == 0 && i > x) {
             nums[i] = nums[x];
             nums[x] = 0;
             x++;
             i--;
         }
         
         //如果当前元素是2，把它放到数组结尾位置
         if (nums[i] == 2 && i < y) {
             nums[i] = nums[y];
             nums[y] = 2;
             y--;
             i--;
         }
     }
 }

99. 下一个排列

  • 一句话描述：
  • 2, 6, 3, 5, 4, 1 --> 2, 6, 4, 1, 3, 5 分为以下几步：
    1. 从后往前找到3
    2. 从后往前找，找到第一个大于3的数：4
    3. swap(3,4)，此时：2, 6, 4, 5, 3, 1
    4. 最后反转5，3，1即可得到2, 6, 4, 1, 3, 5

99.1 题目描述

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

  • 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

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

  • 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
  • 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
  • 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
    给你一个整数数组 nums ，找出 nums 的下一个排列。
    必须 原地 修改，只允许使用额外常数空间。
1
2
输入：nums = [1,2,3]
输出：[1,3,2]

99.2 算法思想和代码实现

  1. 从后往前找出数值下降的位置 i
  2. 交换 nums[i] 和 i之后比nums[i]大的最小数
  3. 让i+1位及其之后的排列最小即 递增（其实已经是递减的了，直接反转就行）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public static void nextPermutation(int[] nums) {
    int start = -1;

    //从后往前遍历，找到第一个非递减的元素，该元素就是排列的起点start
    for (int i = nums.length - 2; i >= 0; i--) {
        if (nums[i] < nums[i + 1]) {
            start = i;
            break;
        }
    }

    // 如果整个数组是降序排列，则直接反转它变成最小排列
    if (start == -1) {
        reverse(nums, 0, nums.length - 1);
        return;
    }

    //找到比start大的最小的元素,并与start交换
    for (int i = nums.length - 1; i > start; i--) {
        if (nums[i] > nums[start]) {
            swap(nums, i, start);
            break;
        }
    }

    //反转从start+1到最后的数组元素
    reverse(nums, start + 1, nums.length - 1);
}

//交换
public static void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

//反转
public static void reverse(int[] nums, int start, int end) {
    while (start < end) {
        swap(nums, start, end);
        start++;
        end--;
    }
}

100. 寻找重复数

  • 一句话描述：
  • 快慢指针找环，相遇之后，将fast重新置为0，两个指针每次移动一步，再次相遇就是重复数所在位置
  • fast = nums[nums[fast]] // 快指针每次移动两步
  • slow = nums[slow] // 慢指针每次移动一步

100.1 题目描述

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

1
2
输入：nums = [1,3,4,2,2]
输出：2

100.2 算法思想和代码实现

  1. 数组大小为 n+1，其中的数字范围是 [1, n]，因此必然有一个数字重复

  2. 快慢指针判圈

  • 定义两个指针：

    • 慢指针 (slow) 每次移动一步。
    • 快指针 (fast) 每次移动两步。

  • 为什么存在环？

    • 由于 nums[i] 指向数组中的索引，这实际上形成了一个 链表 结构。
    • 由于存在 重复元素，意味着至少有两个索引指向 同一位置，从而形成 环。
  1. 找到环的入口（即重复数）
    • 当 slow == fast 时，说明快慢指针相遇，表明存在环。
    • 让 fast 指针回到 起点 (0)，然后 两个指针都每次移动一步。
    • 他们再次相遇的地方，就是 环的入口（即重复的数字）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int findDuplicate(int[] nums) {
    int fast = 0, slow = 0;

    // 使用快慢指针寻找相遇点
    while (true) {
        fast = nums[nums[fast]]; // 快指针每次移动两步
        slow = nums[slow]; // 慢指针每次移动一步

        // 当快慢指针相遇时，说明存在环
        if (slow == fast) {
            fast = 0; // 重新将快指针置于起点

            // 通过第二次相遇点确定重复的数字
            while (nums[slow] != nums[fast]) {
                fast = nums[fast]; // 快指针每次移动一步
                slow = nums[slow]; // 慢指针每次移动一步
            }
            
            return nums[slow]; // 返回找到的重复数字
        }
    }
}

END

101. 使用最小花费爬楼梯

使用最小花费爬楼梯

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int minCostClimbingStairs(int[] cost) {
    //dp[i]代表爬到第i个台阶所花费的最小费用
    int[] dp=new int[cost.length+1];

    //初始化dp
    dp[0]=0;
    dp[1]=0;

    for(int i=2;i<=cost.length;i++){
        dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]); //状态转移方程
    }

    return dp[cost.length];
}

102. 不同路径II

不同路径II

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
       int m = obstacleGrid.length;
       int n = obstacleGrid[0].length;

       //dp[i][j]：到达第i行第j列的不同路径个数
       int[][] dp = new int[m][n];

       //初始化
       if (obstacleGrid[0][0] == 1)
           return 0;
       dp[0][0] = 1;
       for (int i = 1; i < m; i++) {
           if (obstacleGrid[i][0] == 0)
               dp[i][0] = dp[i - 1][0];
           else
               dp[i][0] = 0;
       }
       for (int i = 1; i < n; i++) {
           if (obstacleGrid[0][i] == 0)
               dp[0][i] = dp[0][i - 1];
           else
               dp[0][i] = 0;
       }

       //状态转移方程
       for (int i = 1; i < m; i++) {
           for (int j = 1; j < n; j++) {
               if (obstacleGrid[i][j] == 0) {
                   dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
               } else {
                   dp[i][j] = 0;
               }
           }
       }

       return dp[m - 1][n - 1];
   }

103. 整数拆分

整数拆分

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int integerBreak(int n) {
    //dp[i]代表i可以拆分的最大乘积
    int[] dp = new int[n+1];

    //初始化
    dp[0] = 0;
    dp[1] = 0;
    dp[2]=1;

    //dp[i] = Math.max(dp[i],j*(i-j),j*dp[i-j]);
    for(int i = 3; i <= n; i++)
        for(int j=1;j<=i/2;j++){
            dp[i]=Math.max(Math.max(j*(i-j),j*dp[i-j]),dp[i]);
        }

    return dp[n];
}

104. 不同的二叉搜索树

不同的二叉搜索树

结题思路：假设n个节点存在二叉排序树的个数是G(n)，1为根节点，2为根节点，...，n为根节点，当1为根节点时，其左子树节点个数为0，右子树节点个数为n-1，同理当2为根节点时，其左子树节点个数为1，右子树节点为n-2，所以可得G(n) = G(0)G(n-1)+G(1)(n-2)+...+G(n-1)*G(0)

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int numTrees(int n) {
    //dp[i]：由i个结点组成的二叉树的种类
    int[] dp =new int[n+1];

    //初始化
    dp[0]=1;
    dp[1]=1;

    //dp[i]=dp[0]*dp[i-1]+dp[1]*dp[i-2]+...+dp[i]*dp[0]
    for(int i=2;i<=n;i++)
        for(int j=0;j<i;j++){
            dp[i]+=dp[j]*dp[i-j-1];
        }

    return dp[n];
}

105. 最后一块石头的重量 II

最后一块石头的重量 II

转换为0-1背包问题：

  • 尽量让石头分成重量相同的两堆（尽可能相同），相撞之后剩下的石头就是最小的。
  • 一堆的石头重量是sum，那么我们就尽可能拼成 重量为 sum / 2 的石头堆。 这样剩下的石头堆也是 尽可能接近 sum/2 的重量。 那么此时问题就是有一堆石头，每个石头都有自己的重量，是否可以 装满 最大重量为 sum / 2的背包。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//转换为01背包问题
public static int lastStoneWeightII(int[] stones) {
    int sum = 0;
    for (int i = 0; i < stones.length; i++)
        sum += stones[i];
    int target = sum / 2;

    int[][] dp = new int[stones.length + 1][target + 1];
    for (int i = 1; i <= stones.length; i++)
        for (int j = 1; j <= target; j++) {
            if (j < stones[i - 1]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);
            }
        }

    return sum - 2 * dp[stones.length][target];
}

106. 回文子串

回文子串
该题目与最长回文子串类似(最长回文子串)

  • dp定义：布尔类型的dp[i][j]：表示区间范围[i,j]的子串是否是回文子串，如果是dp[i][j]为true，否则为false
  • 状态转移方程：
    • 当s[i]与s[j]不相等，dp[i][j]一定是false。
    • 当s[i]与s[j]相等时，有如下三种情况
      • 情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
      • 情况二：下标i 与 j相差为1，例如aa，也是回文子串
      • 情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int countSubstrings(String s) {
    int count = 0;
    //dp[i][j]:从i到j的子串是不是回文的
    boolean[][] dp = new boolean[s.length()][s.length()];

    for (int i = s.length() - 1; i >= 0; i--) { // 逆序遍历i
        for (int j = i; j < s.length(); j++) {
            if (s.charAt(i) == s.charAt(j)) {
                if (j == i || j == i + 1) { // 单个字符 or 相邻字符
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i + 1][j - 1];
                }
            }
            if (dp[i][j]) {
                count++;
            }
        }
    }
    return count;
}

201. 合并两个有序数组

双指针从后往前合并，避免覆盖还没处理的数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void merge(int[] nums1, int m, int[] nums2, int n) {
    int p1 = m - 1;
    int p2 = n - 1;
    int p = m + n - 1;

    while (p1 >= 0 && p2 >= 0) {
        if (nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1--;
        } else {
            nums1[p] = nums2[p2];
            p2--;
        }
        p--;
    }

    // 如果 nums2 还有剩余元素，复制到 nums1
    while (p2 >= 0) {
        nums1[p] = nums2[p2];
        p2--;
        p--;
    }
}

202. 字符串相加

1️⃣ 从 num1 和 num2 的末尾开始，一位一位相加。
2️⃣ 用一个 carry 保存进位，初始为 0。
3️⃣ 每次把当前位的和 sum = digit1 + digit2 + carry 计算好，sum % 10 放入结果，sum / 10 更新 carry。
4️⃣ 最后别忘了：如果 carry != 0，还要加到结果前面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public String addStrings(String num1, String num2) {
    StringBuilder sb = new StringBuilder();
    int i = num1.length() - 1, j = num2.length() - 1, carry = 0;

    while (i >= 0 || j >= 0 || carry != 0) {
        int x = i >= 0 ? num1.charAt(i) - '0' : 0;
        int y = j >= 0 ? num2.charAt(j) - '0' : 0;
        int sum = x + y + carry;

        sb.append(sum % 10);
        carry = sum / 10;

        i--;
        j--;
    }

    return sb.reverse().toString();
}

203. 最小K个数

使用大顶堆（PriorityQueue）来筛选数组中最小的 k 个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int[] smallestK(int[] arr, int k) {
    if (k == 0)
        return new int[0];

    int[] res = new int[k];
    PriorityQueue<Integer> pq = new PriorityQueue<>(k, (l1, l2) -> l2 - l1);

    for (int num : arr) {
        if (pq.size() < k) {
            pq.offer(num);
        } else if (num < pq.peek()) {
            pq.poll();
            pq.offer(num);
        }
    }

    int i = 0;
    while (!pq.isEmpty()) {
        res[i++] = pq.poll();
    }

    return res;
}

204. 买卖股票的最佳时机 II

贪心：只要今天比昨天大，就卖出

1
2
3
4
5
6
7
8
9
public int maxProfit(int[] prices) {
    int res = 0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) {
            res += prices[i] - prices[i - 1];
        }
    }
    return res;
}

205. 最大数

使用自定义排序规则：Arrays.sort(strNums,(a,b)->(b+a).compareTo(a+b));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public String largestNumber(int[] nums) {
    String[] strNums = new String[nums.length];
    for (int i = 0; i < nums.length; i++) {
        strNums[i] = String.valueOf(nums[i]);
    }

    Arrays.sort(strNums, (a, b) -> (b + a).compareTo(a + b));
    if (strNums[0].equals("0"))
        return "0";

    StringBuilder sb = new StringBuilder();
    for (String str : strNums) {
        sb.append(str);
    }
    
    return sb.toString();
}

206. 最长公共前缀

用第一个字符串的每个字符，依次与后面所有字符串的相应字符进行比较即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public String longestCommonPrefix(String[] strs) {
    StringBuilder sb = new StringBuilder();

    for (int i = 0; i < strs[0].length(); i++) {
        char c = strs[0].charAt(i);
        for (int j = 1; j < strs.length; j++) {
            if (i >= strs[j].length() || c != strs[j].charAt(i)) {
                return sb.toString();
            }
        }
        sb.append(c);
    }
    
    return sb.toString();
}

207. 重排链表

重排链表=找链表中点+反转链表+合并链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public void reorderList(ListNode head) {
    if (head == null || head.next == null)
        return;

    // 找中点
    ListNode mid = findMid(head);
    ListNode l2 = reverse(mid.next);
    mid.next = null; // 切断前后链表

    ListNode l1 = head;
    ListNode cur = new ListNode(0);

    while (l1 != null && l2 != null) {
        cur.next = l1;
        l1 = l1.next;
        cur = cur.next;

        cur.next = l2;
        l2 = l2.next;
        cur = cur.next;
    }
    if (l1 != null)
        cur.next = l1; // 补上尾巴
}

public ListNode findMid(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

public ListNode reverse(ListNode head) {
    ListNode cur = null;
    while (head != null) {
        ListNode temp = head.next;
        head.next = cur;
        cur = head;
        head = temp;
    }
    return cur;
}

208. 复原 IP 地址

回溯算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
List<String> res = new ArrayList<>();
// 用于存储 "255" 这种IP段
List<String> path = new ArrayList<>();

public List<String> restoreIpAddresses(String s) {
    backtracking(s, 0);
    return res;
}

private void backtracking(String s, int start) {
    // 如果已经切了 4 段，并且刚好用完所有字符，说明找到一个合法的 IP
    if (path.size() == 4 && start == s.length()) {
        res.add(String.join(".", path));
        return;
    }

    // 从 start 开始，尝试截取 1~3 位的子串
    for (int i = start; i < s.length() && i - start < 3; i++) {
        // 防止出现 "01" "00" 这种非法格式
        if (i > start && s.charAt(start) == '0') return;

        // 截取 startIdx 到 i 的子串，转成整数
        int v = Integer.parseInt(s.substring(start, i + 1));
        
        if (v >= 0 && v <= 255) {
            path.add(s.substring(start, i + 1));
            backtracking(s, i + 1);
            path.removeLast();
        }
    }
}

209. 排序数组

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public static int[] sortArray(int[] nums) {
    quickSort(nums, 0, nums.length - 1);
    return nums;
}

public static void quickSort(int[] nums, int low, int high) {
    if (low >= high) return;

    int i = low, j = high;
    int pivot = nums[(low + high) / 2];  // 选取中间值作为基准

    while (i <= j) {
        while (nums[i] < pivot) i++;
        while (nums[j] > pivot) j--;
        if (i <= j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }
    // 递归左右两边
    quickSort(nums, low, j);
    quickSort(nums, i, high);
}

public static void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

210. 多线程交替打印ab

使用synchronized和wait()/notify()方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
private final Object lock = new Object();
      private boolean printA = true;

      public void printA() throws InterruptedException {
          synchronized (lock) {
              while (!printA) {
                  lock.wait();
              }
              System.out.print("a");
              printA = false;
              lock.notify();
          }
      }

      public void printB() throws InterruptedException {
          synchronized (lock) {
              while (printA) {
                  lock.wait();
              }
              System.out.print("b");
              printA = true;
              lock.notify();
          }
      }

      public static void main(String[] args) {
          Solution000 sl =new Solution000();

          Thread threadA = new Thread(() -> {
              try {
                  for (int i = 0; i < 10; i++) sl.printA();
              } catch (InterruptedException e) { e.printStackTrace(); }
          });

          Thread threadB = new Thread(() -> {
              try {
                  for (int i = 0; i < 10; i++) sl.printB();
              } catch (InterruptedException e) { e.printStackTrace(); }
          });

          threadA.start();
          threadB.start();
      }