# codeTop100 **Repository Path**: wenttao/code-top100 ## Basic Information - **Project Name**: codeTop100 - **Description**: 手撕算法准备，热门面试算法（idea版本滴） - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 1 - **Forks**: 0 - **Created**: 2025-06-27 - **Last Updated**: 2025-07-05 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 算法代码合集 **简介：** - 这是一个包含多种常见算法实现的Java代码合集。 - 题目来源于`codeTop`（[CodeTop 面试题目总结](https://codetop.cc/home)）的前100道热门面试题，适用于学习和练习算法，用于应对中大厂互联网开发求职面试时的手撕算法环节！ - `readme.md`文件，是将题目按照专题进行分类，这里面的代码是**力扣核心代码模式**版的，可以直接在力扣上进行提交。项目的代码对应为核心模式的扩展版本，在idea编辑器进行编写的，含测试数据构建（类似acm模式）。 - 算法具体思路和不同解法，都在项目中进行描述了，该文件不再过多赘述。 > 计划：先把前100更新完成，后续会加更前200题！ ## 数组或者排序或二分查找 ### 215. 数组中的第K个最大元素 > 题目链接：[215. 数组中的第K个最大元素](https://leetcode.cn/problems/kth-largest-element-in-an-array/) **Code** ```java class Solution { public int findKthLargest(int[] nums, int k) { int n = nums.length; return q_sort(nums, 0, n - 1, k - 1); } public int q_sort(int[] nums, int l , int r, int k){ if(l >= r) return nums[k]; int x = nums[l + r >> 1]; int i = l - 1, j = r + 1; while(i < j){ do i ++; while(nums[i] > x); do j --; while(nums[j] < x); if(i < j){ int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } } if(k <= j) return q_sort(nums, l, j, k); else return q_sort(nums, j + 1, r, k); } } ``` ### 手撕快速排序 **Code** ```java package com.lwt.codetop.arrayOrSort; // 手撕快速排序 public class QuickSort { private static int[] nums; public static void main(String[] args) { // 构建测试用例 nums = new int[]{5, 3, 2, 4, 1}; int n = nums.length; // 快排 quick_sort(nums, 0, n - 1); for (int x : nums) { System.out.print(x + " "); } } /** * 递归实现快速排序：分化左右两边 左边小于x x 右边大于x; 递归排序左右两边 * @param nums */ private static void quick_sort(int[] nums, int l, int r) { if(l >= r) return; int x = nums[l + r >> 1]; int i = l - 1, j = r + 1; while(i < j){ do i ++; while(nums[i] < x); do j --; while (nums[j] > x); if(i < j){ int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } } quick_sort(nums, l, j); quick_sort(nums, j + 1, r); } } ``` ### 33. 搜索旋转排序数组 > 题目链接：[33. 搜索旋转排序数组](https://leetcode.cn/problems/search-in-rotated-sorted-array/) **Code** ```java class Solution { public int search(int[] nums, int target) { int n = nums.length; //第一次二分： 找出两段划分的分界点 int l = 0, r = n - 1; while(l < r){ int mid = l + r + 1 >> 1; if(nums[mid] >= nums[0]) l = mid; else r = mid - 1; } if(l > r) return -1; // 判断tar位于哪一段 if(target >= nums[0]){ l = 0; }else{ l = r + 1; r = n - 1; } //第二次二分：找出tar的位置 while (l < r){ int mid = l + r >> 1; if(nums[mid] >= target) r = mid; else l = mid + 1; } if(l <= r && nums[l] == target) return l; return -1; } } ``` ### 88. 合并两个有序数组 > 题目链接：[88. 合并两个有序数组](https://leetcode.cn/problems/merge-sorted-array/) **Code** ```java class Solution { public void merge(int[] a, int n, int[] b, int m) { //解法二：双指针（归并排序） int i = 0, j = 0, cnt = 0; int[] tmp = new int[n + m]; while(i < n && j < m){ if(a[i] <= b[j]) tmp[cnt ++] = a[i ++]; else tmp[cnt ++] = b[j ++]; } // 比完了还有剩余 while(i < n) tmp[cnt ++] = a[i ++]; while(j < m) tmp[cnt ++] = b[j ++]; for(int k = 0; k < m + n; k ++) a[k] = tmp[k]; } } ``` ### 54. 螺旋矩阵 > 题目链接：[54. 螺旋矩阵](https://leetcode.cn/problems/spiral-matrix/) **Code** ```java class Solution { public List spiralOrder(int[][] g) { List res = new ArrayList<>(); int n = g.length, m = g[0].length; boolean[][] st = new boolean[n + 10][m + 10]; // 定义方向 int[] dx = {0, 1, 0, -1}; int[] dy = {1, 0, -1, 0}; int d = 0; // 用于方向控制 int k = 0; int x = 0, y = 0; while(k < n * m){ st[x][y] = true; res.add(g[x][y]); int a = x + dx[d], b = y + dy[d];// 这里用d一直控制方向 if(a < 0 || a >= n || b < 0 || b >= m || st[a][b]){ d = (d + 1) % 4; a = x + dx[d]; b = y + dy[d]; } // 更新位置移动 x = a; y = b; k += 1; } return res; } } ``` ### 4. 寻找两个正序数组的中位数 > 题目链接：[4. 寻找两个正序数组的中位数](https://leetcode.cn/problems/median-of-two-sorted-arrays/) **治法求解中位数（时间复杂度 O(log(n+m))）** 我们将问题直接转化成求两个数组中第k小的元素。 首先我们给出 `getKthSmallest` 函数的参数含义：表示从 `nums1[i:nums1.size() - 1]` 和 `nums2[j:nums2.size() - 1]` 这两个切片中找到第k小的数字。假设 `nums1` 和 `nums2` 的切片元素个数分别为 `len1` 和 `len2`，为了方便讨论，我们定义为 `len1 < len2`。 考虑一般的情况，我们在这两个切片中各取 `k/2` 个元素，令 `si = i + k/2`, `sj = j + k/2`，得到切片 `nums1[i : si - 1]（k/2个数）` 和 `nums2[j : sj - 1]`。 - 如果 `nums1[si - 1] < nums2[sj - 1]`，说明 `nums1[i : si - 1]` 中的元素都是小于第k小的元素的，我们可以舍去这部分元素，在剩下的区间内去找第 `k - k/2` 小的元素。 - 如果 `nums1[si - 1] >= nums2[sj - 1]`，说明 `nums2[j : sj - 1]` 中的元素都是小于第k小的元素的，我们可以舍去这部分元素，在剩下的区间内去找第 `k - k/2` 小的元素。 - ![img](https://cdn.nlark.com/yuque/0/2025/png/21561442/1751509420125-84b13b1d-07b5-4dde-bf54-a9f477723a2a.png) 考虑特殊情况，当 `nums1[i : nums1.size() - 1]` 切片中的元素小于 `k/2` 个了，那么我们就将这个切片中的所有元素取出来，在 `nums2` 中仍然取 `k/2` 个元素。这是因为k是一个有效值（即 `len1 + len2 >= k`），不可能出现 `len1 < k/2` 的同时 `len2 < k/2`；另一方面因为我们确保了 `len1 < len2`，所以也不可能出现 `len1 >= k/2` 的时候 `len2 < k/2`，即 `len2 >= k/2` 恒成立。 **Code** ```java class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int total = nums1.length + nums2.length; if(total % 2 == 0) { int left = f(nums1, 0, nums2, 0, total / 2); int right = f(nums1, 0, nums2, 0, total / 2 + 1); return (left + right) / 2.0; }else { return f(nums1, 0, nums2, 0, total / 2 + 1); } } private static int f(int[] nums1, int i, int[] nums2, int j, int k) { // 为了方便我们默认第一个数组的元素是少的 if(nums1.length - i > nums2.length - j) return f(nums2, j, nums1, i, k); // 边界特判 // 当第一个数组用完了(第一个数组是空的，我们要找的就是第二个数组的第k个数，即B[j + k - 1]，k是从1开始的) if(nums1.length == i) return nums2[j + k - 1]; // 当取第一个元素/递归出口 if(k == 1) return Math.min(nums1[i], nums2[j]); int si = Math.min(nums1.length, i + k / 2); // A[k/2]的后一个位置 注意；由于A[]的元素可能少，为了防止越界要进行特判 int sj = j + k / 2; // B[k/2]的后一个位置 // 分治 if(nums1[si - 1] > nums2[sj - 1]){ return f(nums1, i, nums2, sj, k - (sj - j)); }else { return f(nums1, si, nums2, j, k - (si - i)); } } } ``` **两个代码细节：** - 边界特判的顺序不能颠倒 - **`if (i == nums1.length)`**：当`nums1`的剩余元素为空时（即索引`i`已超出`nums1`的范围），直接从`nums2`中取第`k`小的元素。 - #### `if (k == 1)`：当要找的是第 1 小的元素时（即`k=1`），直接比较两个数组当前索引处的最小值。 - 总结：**必须先处理数组为空的情况，再处理`k=1`的情况**，以避免无效的数组访问。 - 例如，`nums1 = []`，`nums2 = [2]`，`k = 1`。，如何顺序互换，就会报错，因为`nums1`是空的 - 在f函数中，`nums1.length`不能换为全局的静态变量`n, m`：因为当nums1较长的时候，我们是要进行交换然后再重新进行递归的，而这个交换并没有重新更新`n和m`，从而到时栈溢出！ ### 704. 二分查找 > 题目链接：[704. 二分查找](https://leetcode.cn/problems/binary-search/) **Code** ```java class Solution { public int search(int[] nums, int target) { int n = nums.length; int l = 0, r = n - 1; while(l < r) { int mid = l + r >> 1; if(nums[mid] >= target) r = mid; else l = mid + 1; } if (nums[l] == target) return l; return -1; } } ``` ### 31. 下一个排列 > 题目链接：[31. 下一个排列](https://leetcode.cn/problems/next-permutation/) （下一个排列：限制：常数空间，原地修改）--->**思维题：背过即可** - 由于所有排列的位数是一样的，那么意味着字典序越小数值也就越小 - 也就是说，要找到某一个排列的下一个大于它的最小排列，我们要**尽可能的保证高位的数不变，然后变低位**，这样才是比我们当前字典序大的最小的那一个 - 因此，我们可以考虑**从后往前**进行一个遍历 - - 为此，我们要找到的是（从右往左看的话就是第一个非升序的数的位置）**第一个非降序的位置（也就是说该位置可以变大一些），那么它可以变大成什么呢？--->定位** - 我们要找到该位置后面，**比他大的最小的那个数（确保字典序最小）**，然后进行交换——>找数，交换 - 为了确保最后的序列的字典序最小，我们应该**将该位置后面的所有数进行升序排序**——>排序位置后序列 - 自此，得到的就是比当前排列字典序大的最小的排列了 【举例子】2 3 5 4 1 1. 找到第一个非降序的位置--->3（从右往左遍历，即第一个非严格升序的位置） 2. 找到它后面比它大的最小的数--->4，然后进行交换--->2 4 5 3 1 3. 为了使得交换的整个序列字典序最小，我们将它后面的数进行升序排序--->2 4 1 3 5 - 时间复杂度：O（n) - 空间复杂度：O（1） **Code** ```java class Solution { public void nextPermutation(int[] nums) { int n = nums.length; // 找到第一个非降序的位置 int k = n - 1; while(k > 0 && nums[k - 1] >= nums[k]) k-= 1; if(k == 0){ // 说明当前序列是最大字典序了，要进行反转 reverse(nums, 0, n - 1); }else{ // 找到该位置后面比它大的最小的数，然后进交换 // 该数的实际位置是K-1 int t = k; while(t < n && nums[t] > nums[k - 1]) t += 1; swap(nums, k - 1, t - 1); // 将该位置后面的所有数进行逆序排序（因为之前就是非严格降序的了，反转即可） reverse(nums, k, n - 1); } } public static void reverse(int[] nums, int i, int j){ while(i < j){ swap(nums, i, j); i += 1; j -= 1; } } public static void swap(int[] nums, int i, int j){ int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } } ``` ### 69. x 的平方根 > 题目链接：[69. x 的平方根 ](https://leetcode.cn/problems/sqrtx/) **Code** ```java class Solution { public int search(int[] nums, int target) { int n = nums.length; int l = 0, r = n - 1; while(l < r) { int mid = l + r >> 1; if(nums[mid] >= target) r = mid; else l = mid + 1; } if (nums[l] == target) return l; return -1; } } ``` ### ## 二叉树 ### 102. 二叉树的层序遍历 > 题目链接：[102. 二叉树的层序遍历](https://leetcode.cn/problems/binary-tree-level-order-traversal/) **Code** ```java class Solution { public List> levelOrder(TreeNode root) { List> res = new ArrayList<>(); if(root == null){ return res; } Queue q = new LinkedList<>(); q.add(root); while(!q.isEmpty()){ List ceng = new ArrayList<>(); int len = q.size(); for(int i = 0; i < len; i ++){ TreeNode t = q.poll(); ceng.add(t.val); if(t.left != null) q.add(t.left); if(t.right != null) q.add(t.right); } res.add(ceng); } return res; } } ``` ### 236. 二叉树的最近公共祖先 > 题目链接：[236. 二叉树的最近公共祖先](https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/) **Code** ```java class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { return dfs(root, p, q); } public static TreeNode dfs(TreeNode root, TreeNode p, TreeNode q) { // if(root == null || root == p || root == q) return root; // 判断左右子树是否包含p q // 采用的是后序遍历的方式，也就是说自底向上的，那么找到的祖先就是最近的 TreeNode left = dfs(root.left, p, q); TreeNode right = dfs(root.right, p, q); if(left == null) return right; // 如果左子树不包含p q，说明可能在右子树 if(right == null) return left;// 如果右子树不包含p q，说明可能在左子树 return root; // 左右两边都不为空，即p q左右各一个，则此时根节点即为最近公共祖先 } } ``` ### 103. 二叉树的锯齿形层序遍历 > 题目链接：[103. 二叉树的锯齿形层序遍历](https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/) ```java class Solution { public List> zigzagLevelOrder(TreeNode root) { return bfs(root); } private static List> bfs(TreeNode root) { List> res = new ArrayList<>(); if(root == null) return res; // 特判 int depth = 1; Queue q = new LinkedList<>(); q.add(root); while (!q.isEmpty()){ int n = q.size(); List ceng = new ArrayList<>(); for (int i = 0; i < n; i++) { TreeNode node = q.poll(); ceng.add(node.val); if(node.left != null) q.add(node.left); if(node.right != null) q.add(node.right); } if(depth % 2 == 0) Collections.reverse(ceng); // 逆序 res.add(new ArrayList<>(ceng)); depth += 1; } return res; } } ``` ### 124. 二叉树中的最大路径和 > 题目链接：[124. 二叉树中的最大路径和](https://leetcode.cn/problems/binary-tree-maximum-path-sum/) ```java class Solution { int res = -0x3f3f3f3f; // 不要用static public int maxPathSum(TreeNode root) { dfs(root); return res; } /** * 后续遍历：递归获取树的最大（一边的最大高度/和）--> left、right * 更新res * @param root * @return */ private int dfs(TreeNode root){ if (root == null) return 0; int left = Math.max(0, dfs(root.left)); int right = Math.max(0, dfs(root.right)); // 更新答案 res = Math.max(res, left + right + root.val); // 返回最大和（高度） return Math.max(left, right) + root.val; } } ``` ## 动态规划（DP） ### 53. 最大子数组和 > 题目链接：[53. 最大子数组和](https://leetcode.cn/problems/maximum-subarray/) **Code** ```java class Solution { public int maxSubArray(int[] nums) { int res = nums[0]; int n = nums.length; int[] f = new int[n + 10]; f[0] = nums[0]; for(int i = 1; i < n; i ++){ f[i] = Math.max(nums[i], nums[i] + f[i - 1]); res = Math.max(res, f[i]); } return res; } } ``` ### 5. 最长回文子串 > 题目链接：[5. 最长回文子串](https://leetcode.cn/problems/longest-palindromic-substring/) **Code** - DP解法 ```java class Solution { public String longestPalindrome(String s) { int n = s.length(); s = " " + s; boolean[][] f = new boolean[n + 10][n + 10]; String res = ""; // 区间dp for (int len = 1; len <= n; len++) { for (int i = 1; i + len - 1 <= n; i++) {// 枚举区间左端点 int j = i + len - 1; if (len == 1) { f[i][j] = true; } else { // len >= 2 if (s.charAt(i) == s.charAt(j) && (len == 2 || f[i + 1][j - 1] == true)) { f[i][j] = true; } } // 更新答案，求最长回文串 if (f[i][j] == true && len > res.length()) { res = s.substring(i, j + 1); // [i, j) } } } return res; } } ``` - 中心扩散（双指针）解法 ```java class Solution { public String longestPalindrome(String s) { int n = s.length(); s = " " + s; boolean[][] f = new boolean[n + 10][n + 10]; String res = ""; // 中心=扩散法则 for (int i = 1; i <= n; i++) { // 回文串是偶数的情况 int l = i, r = i + 1; while (l >= 1 && r <= n && s.charAt(l) == s.charAt(r)) { l -= 1; r += 1; } // 更新答案 if (r - l - 1 > res.length()) res = s.substring(l + 1, r); // 回文串是奇数的情况 l = i - 1; r = i + 1; while (l >= 1 && r <= n && s.charAt(l) == s.charAt(r)) { l -= 1; r += 1; } // 更新答案 if (r - l - 1 > res.length()) res = s.substring(l + 1, r); } return res; } } ``` ### 121. 买卖股票的最佳时机 > 题目链接：[121. 买卖股票的最佳时机](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/) 解法一：状态dp ```java class Solution { public int maxProfit(int[] prices) { int n = prices.length; int[][] f = new int[n][2]; f[0][1] = -prices[0]; f[0][0] = 0; for(int i = 1; i < n; i ++){ f[i][0] = Math.max(f[i - 1][0], f[i - 1][1] + prices[i]); f[i][1] = Math.max(f[i - 1][1], -prices[i]); } return f[n - 1][0]; } } ``` 解法二：贪心 + 前缀最小值 ```java class Solution { public int maxProfit(int[] prices) { int preMin = prices[0]; int res = 0; for (int x : prices) { res = Math.max(res, x - preMin); preMin = Math.min(preMin, x); } return res; } } ``` ### 300. 最长递增子序列 > 题目链接：[300. 最长递增子序列](https://leetcode.cn/problems/longest-increasing-subsequence/) **Code** ```java class Solution { public int lengthOfLIS(int[] a) { int n = a.length; int[] f = new int[n + 10]; int res = 0; for(int i = 0; i < n; i ++){ f[i] = 1; for(int j = 0; j < i; j ++){ if(a[i] > a[j]) f[i] = Math.max(f[j] + 1, f[i]); } res = Math.max(f[i], res); } return res; } } ``` ### 42. 接雨水 > 题目链接：[42. 接雨水](https://leetcode.cn/problems/trapping-rain-water/) 思路一：递推 ```java class Solution { public int trap(int[] height) { int n = height.length; int[] left = new int[n + 10]; int[] right = new int[n + 10]; int res = 0; // 预处理每根柱子左右两边最高的柱子高度 for(int i = 1; i < n; i ++){ left[i] = Math.max(left[i - 1], height[i - 1]); } for(int i = n - 2; i >= 0; i --){ right[i] = Math.max(right[i + 1], height[i + 1]); } // 求雨水面积 for(int i = 0; i < n; i ++){ int minH = Math.min(left[i], right[i]); if(minH > height[i]) res += (minH - height[i]); } return res; } } ``` 思路二：单调栈（TODO） ### 72. 编辑距离 > 题目链接：[72. 编辑距离](https://leetcode.cn/problems/edit-distance/) ```java class Solution: def minDistance(self, a: str, b: str) -> int: n, m = len(a), len(b) a = " " + a b = " " + b f = [[inf] * (m + 10) for _ in range(n + 10)] # 初始化 for i in range(0, n + 1): f[i][0] = i for j in range(0, m + 1): f[0][j] = j # dp for i in range(1, n + 1): for j in range(1, m + 1): # 插入/删除a[i]，使得两串相等 f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1 # 替换 if a[i] == b[j]: f[i][j] = min(f[i][j], f[i - 1][j - 1]) else: f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1) return f[n][m] ``` ## 链表 ### 146. LRU缓存机制 > 题目链接：[146. LRU 缓存](https://leetcode.cn/problems/lru-cache/) **Code** ```java // 定义双链表结构 class Node{ int key; int value; Node left; Node right; public Node(){} public Node(int key, int value){ this.key = key; this.value = value; } } class LRUCache { private int capacity; private Node L; private Node R; private Map h = new HashMap<>(); public LRUCache(int capacity) { this.capacity = capacity; L = new Node(0, 0); R = new Node(0, 0); L.right = R; R.left = L; } /** 从缓存中获取元素：若不存在直接返回-1 存在：removeNode addToHead 返回结果 */ public int get(int key) { Node p = h.get(key); if(p == null) return -1; removeNode(p); addToHead(p); return p.value; } /** 向缓存中插入元素：若元素存在，则覆盖，removeNode addTohead 不存在：判断是否满了 满了 LRU 获取末尾节点，然后删除(remove和删除h) 不管满不满 都要新建节点，然后插入操作 addTohead */ public void put(int key, int value) { Node p = h.get(key); if(p != null){ p.value = value; removeNode(p); addToHead(p); }else{ if(h.size() == capacity){ Node tail = R.left; removeNode(tail); h.remove(tail.key); } Node newNode = new Node(key, value); h.put(key, newNode); addToHead(newNode); } } public void removeNode(Node p){ p.left.right = p.right; p.right.left = p.left; } public void addToHead(Node p){ p.right = L.right; p.left = L; L.right.left = p; L.right = p; } } ``` ### 206. 反转链表 > 题目链接：[206. 反转链表](https://leetcode.cn/problems/reverse-linked-list/) **Code** ```java class Solution { public ListNode reverseList(ListNode head) { if(head == null) return head; ListNode a = head, b = a.next; while(b != null){ ListNode c = b.next; b.next = a; a = b; b = c; } head.next = null; return a; } } ``` ### 25. K 个一组翻转链表 > 题目链接：[25. K 个一组翻转链表](https://leetcode.cn/problems/reverse-nodes-in-k-group/) 扩展： - 原题是k个一组翻转，最后剩下的不足k个的话就不反转 - 扩展：即使不足k个也要进行翻转 **Code** ```java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseKGroup(ListNode head, int k) { if(head == null) return head; ListNode dummy = new ListNode(0); dummy.next = head; ListNode p = dummy; // 定义k个一组翻转的前驱 while(true){ // 1. 判断前驱后面是否足够k个一组 ListNode q = p; for(int i = 0; i < k; i ++){ if(q == null) break; q = q.next; } if(q == null) break; // 不足k个 // 2. 组内翻转，即翻转k-1次 ListNode a = p.next, b = a.next; for(int i = 0; i < k - 1; i ++){ ListNode c = b.next; b.next = a; a = b; b = c; } // 3. 改变前后指针指向 ListNode t = p.next; p.next = a; t.next = b; // 为下次做准备 p = t; } return dummy.next; } } ``` **扩展版：**不足k个一组的也要进行翻转 ```java class Solution { public ListNode reverseKGroup(ListNode head, int k) { if(head == null) return head; ListNode dummy = new ListNode(0); dummy.next = head; ListNode p = dummy; // 定义k个一组翻转的前驱 Boolean flag = false; // 标记是否够k个 while(true){ // 1. 判断前驱后面是否足够k个一组 ListNode q = p; for(int i = 0; i < k; i ++){ if(q == null) break; q = q.next; } if(q == null){ // 不足k个也要进行翻转 flag = true; break; } // 2. 组内翻转，即翻转k-1次 ListNode a = p.next, b = a.next; for(int i = 0; i < k - 1; i ++){ ListNode c = b.next; b.next = a; a = b; b = c; } // 3. 改变前后指针指向 ListNode t = p.next; p.next = a; t.next = b; // 为下次做准备 p = t; } // 判断是否不足k个（原始/剩下）,不足，再进行翻转剩下的 if(flag == true && p.next != null){// 不足 且有元素 ListNode a = p.next, b = a.next; while(b != null){ ListNode c = b.next; b.next = a; a = b; b = c; } // 改变指针指向 ListNode t = p.next; p.next = a; t.next = null; // 最后要置空 } return dummy.next; } } ``` ### 21. 合并两个有序链表 > 题目链接：[21. 合并两个有序链表](https://leetcode.cn/problems/merge-two-sorted-lists/) ```java class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode dummy = new ListNode(0); ListNode cur = dummy; // 1. 归并 while(list1 != null && list2 != null){ if(list1.val <= list2.val){ cur.next = list1; list1 = list1.next; }else{ cur.next = list2; list2 = list2.next; } cur = cur.next; } // 2. 扫尾 if(list1 != null) cur.next = list1; if(list2 != null) cur.next = list2; return dummy.next; } } ``` ### 92. 反转链表 II > 题目链接：[92. 反转链表 II](https://leetcode.cn/problems/reverse-linked-list-ii/) **Code** ```java class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { if(head == null) return null; ListNode dummy = new ListNode(0); dummy.next = head; // 1. 找到起点的前驱p ListNode p = dummy; for(int i = 0; i < m - 1; i ++) p = p.next; // 2. 反转区域[n,m] ListNode a = p.next, b = a.next; for(int i = 0; i < n - m; i ++){ ListNode c = b.next; b.next = a; a = b; b = c; } // 3. 改变链表指向 p.next.next = b; p.next = a; return dummy.next; } } ``` ### 141. 环形链表 > 题目链接：[141. 环形链表](https://leetcode.cn/problems/linked-list-cycle/) **Code** ```java // 环形链表 public class Solution { public boolean hasCycle(ListNode head) { if(head == null) return false; // 快慢指针，快走二，慢走一，相遇则表明存在环 ListNode fast = head, slow = head; while(fast.next != null && fast.next.next != null){ fast = fast.next.next; slow = slow.next; if(fast == slow) return true; } return false; } } ``` ### 23. 合并 K 个升序链表 > 题目链接：[23. 合并 K 个升序链表](https://leetcode.cn/problems/merge-k-sorted-lists/) **Code** ```java class Solution { public ListNode mergeKLists(ListNode[] lists) { PriorityQueue q = new PriorityQueue((x,y) -> (x.val - y.val)); // k个有序链表的头指针节点加入小根堆 for(int i = 0; i < lists.length; i ++){ if(lists[i] != null) q.add(lists[i]); } // 归并k个链表 ListNode dummy = new ListNode(-1); ListNode cur = dummy; while(!q.isEmpty()){ // 拿到最小值，加入新链表 ListNode t = q.poll(); cur.next = new ListNode(t.val); // 归并链表头指针移动, 将下一个节点放入堆中 if(t.next != null) q.add(t.next); // 链表指针移动 cur = cur.next; } return dummy.next; } } ``` ### 143.重排链表 > 题目链接：[143. 重排链表](https://leetcode.cn/problems/reorder-list/) ```java class Solution { public void reorderList(ListNode head) { if(head == null) return ; // 1. 获取中间节点 ListNode t = getMid(head); // 2. 翻转后半部分链表 ListNode hou = reverse(t); // 3. 交替拼接两段链表 merge(head, hou); } /** * 获取链表的中间节点 * @param head * @return */ private static ListNode getMid(ListNode head) { ListNode fast = head, slow = head; while (fast.next != null && fast.next.next != null){ fast = fast.next.next; slow = slow.next; } return slow; } /** * 翻转链表 * @param head * @return */ private static ListNode reverse(ListNode head) { ListNode a = head, b = a.next; while(b != null){ ListNode c = b.next; b.next = a; a = b; b = c; } head.next = null; return a; } private static void merge(ListNode list1, ListNode list2) { while(list1 != null && list2 != null){ ListNode n1 = list1.next, n2 = list2.next; list1.next = list2; list2.next = n1; list1 = n1; list2 = n2; } } } ``` ### 160. 相交链表 > 题目链接：[160. 相交链表](https://leetcode.cn/problems/intersection-of-two-linked-lists/) ```java public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { // 思路：背过，a + b + c的路径长度相等 ListNode p = headA, q = headB; while(p != q){ if(p == null) p = headB; else p = p.next; if(q == null) q = headA; else q = q.next; } return p; } } ``` ### 142. 环形链表 II > 题目链接：[142. 环形链表 II](https://leetcode.cn/problems/linked-list-cycle-ii/) ```java public class Solution { public ListNode detectCycle(ListNode head) { if(head == null) return head; ListNode fast = head, slow = head; while (fast.next != null && fast.next.next != null){ fast = fast.next.next; slow = slow.next; if(fast == slow){ fast = head; while (fast != slow){ fast =fast.next; slow = slow.next; } return fast; } } return null; } } ``` ### 19. 删除链表的倒数第 N 个结点 > 题目链接：[19. 删除链表的倒数第 N 个结点](https://leetcode.cn/problems/remove-nth-node-from-end-of-list/) ```java class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(-1); dummy.next = head; // 统计链表长度 ListNode p = dummy; int len = 0; while(p != null){ p = p.next; len += 1; } // 找到倒数第n个节点的前驱 p = dummy; for (int i = 0; i < len - n - 1; i++) { p = p.next; } // 删除 p.next = p.next.next; return dummy.next; } } ``` ### 148. 排序链表 > 题目链接：[148. 排序链表](https://leetcode.cn/problems/sort-list/) ```java class Solution { public ListNode sortList(ListNode head) { // 注意特判：为空||单个元素就不用排序了 if (head == null || head.next == null) return head; // 1. 获取链表的中间节点，并划分链表 ListNode t = getMid(head); ListNode hou = t.next; t.next = null; // 2. 递归排序 ListNode left = sortList(head); // 这里是head ListNode right = sortList(hou); // 3. 合并两个有序链表 return merge(left, right); } private static ListNode merge(ListNode list1, ListNode list2) { ListNode dummy = new ListNode(-1); ListNode cur = dummy; while (list1 != null && list2 != null) { if (list1.val <= list2.val) { cur.next = list1; list1 = list1.next; } else { cur.next = list2; list2 = list2.next; } cur = cur.next; } // 扫尾 if (list1 != null) cur.next = list1; if (list2 != null) cur.next = list2; return dummy.next; } private static ListNode getMid(ListNode head) { ListNode fast = head, slow = head; while (fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next; } return slow; } } ``` ### 2. 两数相加 > 题目链接：[2. 两数相加](https://leetcode.cn/problems/add-two-numbers/) ```java class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(-1); ListNode cur = dummy; int s = 0, t = 0; // s模拟对位和 t代表进位 while(l1 != null || l2 != null){ s += t; if(l1 != null){ s += l1.val; l1 = l1.next; } if(l2 != null){ s += l2.val; l2 = l2.next; } cur.next = new ListNode(s % 10); cur = cur.next; t = s / 10; s = 0; // 为下一次准备 } if(t != 0) cur.next = new ListNode(t); return dummy.next; } } ``` ## 双指针 ### 3. 无重复字符的最长子串 > 题目链接：[3. 无重复字符的最长子串](https://leetcode.cn/problems/longest-substring-without-repeating-characters/) **Code** ```java class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(); int res = 0; Map cnt = new HashMap<>(); for(int i = 0, j = 0; i < n; i ++){ char c = s.charAt(i); cnt.put(c, cnt.getOrDefault(c, 0) + 1); while(j < i && cnt.get(c) > 1){ char left = s.charAt(j); cnt.put(left, cnt.get(left) - 1); j += 1; } res = Math.max(res, i - j + 1); } return res; } } ``` ### 15. 三数之和 > 题目链接：[15. 三数之和](https://leetcode.cn/problems/3sum/) **Code** ```java class Solution { public List> threeSum(int[] nums) { List> res = new ArrayList<>(); int n = nums.length; Arrays.sort(nums); for(int i = 0; i < n; i ++){// 枚举a // 对a去重 if(i > 0 && nums[i] == nums[i - 1]) continue; // 双指针枚举b,c，找到方案并去重 int l = i + 1, r = n - 1; while(l < r){ // 三数之和 ---》 且我们之前排序了 有序性 int s = nums[i] + nums[l] + nums[r]; if(s > 0) { r -= 1; } else if (s < 0){ l += 1; } else{ // 找到答案 res.add(Arrays.asList(nums[i], nums[l], nums[r])); //对b c进行去重 while (l < r && nums[l] == nums[l + 1]) l += 1; while (l < r && nums[r] == nums[r - 1]) r -= 1; // 指针移动，为一下次准备 l += 1; r -= 1; } } } return res; } } ``` ### 415. 字符串相加 > 题目链接：[415. 字符串相加](https://leetcode.cn/problems/add-strings/) ```java class Solution { public String addStrings(String num1, String num2) { String res = ""; int n = num1.length(), m = num2.length(); int i = n - 1, j = m - 1; int s = 0, t = 0; while(i >= 0 || j >= 0){ s += t; if(i >= 0) s += num1.charAt(i) - '0'; // 必须if判断的，因为字符可能不等长 if(j >= 0) s += num2.charAt(j) - '0'; i -= 1; j -= 1; // 答案拼接 res = s % 10 + res; // 进位 t = s / 10; // 为下一次对位和准备 s = 0; } if(t != 0) res = "1" + res; return res; } } ``` ### 165. 比较版本号 > 题目链接：[165. 比较版本号](https://leetcode.cn/problems/compare-version-numbers/) ```java class Solution { public int compareVersion(String v1, String v2) { int n = v1.length(), m = v2.length(); int i = 0, j = 0; while (i < n || j < m) { // 找出对位上的数字 int a = i, b = j; while(a < n && v1.charAt(a) != '.') { a += 1; } while(b < m && v2.charAt(b) != '.') { b += 1; } int x = 0, y = 0; // 注意特判 if(a == i) x = 0; else x = Integer.parseInt(v1.substring(i, a)); if(b == j) y = 0; else y = Integer.parseInt(v2.substring(j, b)); if(x < y) return -1; if(x > y) return 1; // 指针移动 i = a + 1; j = b + 1; } return 0; } } ``` ## 图论 ### 200. 岛屿数量 > 题目链接：[200. 岛屿数量](https://leetcode.cn/problems/number-of-islands/) **Code** ```java class Solution { char[][] g; int n, m; int[] dx = {-1, 1, 0, 0}; int[] dy = {0, 0, -1, 1}; public int numIslands(char[][] grid) { g = grid; n = grid.length; m = grid[0].length; int res = 0; for(int i = 0; i < n; i ++){ for(int j = 0; j < m; j ++){ if(g[i][j] == '1'){ dfs(i, j); res ++; } } } return res; } public void dfs(int x, int y){ g[x][y] = '0'; for(int i = 0; i < 4; i ++){ int a = x + dx[i], b = y + dy[i]; if(a < 0 || a >= n || b < 0 || b >= m || g[a][b] != '1') continue; dfs(a, b); } } } ``` ## 栈 ### 20. 有效的括号 > 题目链接：[20. 有效的括号](https://leetcode.cn/problems/valid-parentheses/) **Code** ```java class Solution { public boolean isValid(String s) { char[] charArray = s.toCharArray(); Stack stk = new Stack<>(); HashMap mp = new HashMap<>(); mp.put(')', '('); mp.put(']', '['); mp.put('}', '{'); for (char x : charArray) { if(x == '(' || x == '[' || x == '{') stk.add(x); else { if(stk.isEmpty() || stk.peek() != mp.get(x)) return false; stk.pop(); } } return stk.isEmpty(); } } ``` ### 232. 用栈实现队列 > 题目链接：[232. 用栈实现队列](https://leetcode.cn/problems/implement-queue-using-stacks/) **Code** ```java class MyQueue { Stack stk; Stack w; public MyQueue() { stk = new Stack<>(); w = new Stack<>(); } public void push(int x) { stk.add(x); } public int pop() { while (stk.size() > 1) { w.add(stk.pop()); } int val = stk.pop(); while (!w.isEmpty()) { stk.add(w.pop()); } return val; } public int peek() { while (stk.size() > 1) { w.add(stk.pop()); } int val = stk.peek(); while (!w.isEmpty()) { stk.add(w.pop()); } return val; } public boolean empty() { return stk.isEmpty(); } } ``` ### 32. 最长有效括号 > 题目链接：[32. 最长有效括号](https://leetcode.cn/problems/longest-valid-parentheses/) 注意：背过 思路：栈 一个合法括号序列的性质： 1. 任意前缀中左括号的数量 >= 右括号的数量 2. 左右括号数量相等 具体做法： 对于一个串，要找出合法的括号字串，就要找出对应的起始边界 - 右边界：可以通过性质1来确定，通过扫描找出所有第一次右括号数量 > 左括号数量的位置，即第一个不合法的位置 - - （然后，在该位置进行分段，也就是说，之前的任何合法序列是不可能横跨这条线的！） - 接着在重新计数、重新划界 - 也就是说我们找合法序列的时候，只要在划分的每一段里边`[....)`寻找即可。 - 左边界：对于上述划分好的段除了边界外，都满足`(括号数量 >= )括号数量`也就是说任何一个右括号必然能够找到与它对应匹配的左括号，然后我们再去考虑这一段内的最大括号匹配长度是多少？即对于每一个右括号而言，怎么去找到离它最远的是的序列合法匹配的最远的左括号的位置呢？-----> 可以用栈来进行实现，段内用栈来进行维护，执行一个括号匹配的流程，最后根据栈内左括号剩余的数量来确定左边界 - - 栈为空，则开始位置即为左边界 - 非空（1个）：则左边界为起点位置 + 1 - 对于段内每一次合法匹配，更新求取最大长度答案即可 ![img](https://cdn.nlark.com/yuque/0/2025/png/21561442/1751717473760-55bb08a3-b8e3-4787-a0f0-10f3795bfe3a.png) - 时间复杂度：`O（n）` **Code** ```java class Solution { public int longestValidParentheses(String s) { int n = s.length(); int res = 0; Stack stk = new Stack<>(); int start = -1; // 起点 for (int i = 0; i < n; i++) { // 遇到左括号 if(s.charAt(i) == '(') { stk.add(i); }else { // 遇到右括号 if(stk.size() > 0){ // 非空则出栈，然后判断是带内匹配还是某段完整匹配，更新答案 stk.pop(); if(stk.size() > 0){ // 段内匹配（栈内还有元素） res = Math.max(res, i - stk.peek()); }else { // 某段匹配（栈内元素为0） res = Math.max(res, i - start); } }else { // 遇到第一个右括号数量 > 左括号数量 的位置-->分段 start = i; } } } return res; } } ``` ## 回溯 ### 全排列 > 题目链接：[46. 全排列](https://leetcode.cn/problems/permutations/) ```java class Solution { int N = 25; int n; List> res = new ArrayList<>(); List path = new ArrayList<>(); boolean[] st = new boolean[N]; public List> permute(int[] nums) { n = nums.length; for(int i = 0; i < n; i ++) nums[i] += 10; dfs(nums, 0); return res; } public void dfs(int[] nums, int u){ if(u == n){ res.add(new ArrayList(path)); return ; } // 枚举每一种可能 for(int i = 0; i < n; i ++){ if(!st[nums[i]]){ st[nums[i]] = true; path.add(nums[i] - 10); dfs(nums, u + 1); st[nums[i]] = false; path.remove(path.size() - 1); } } } } ``` ### 93. 复原 IP 地址 > 题目链接：[93. 复原 IP 地址](https://leetcode.cn/problems/restore-ip-addresses/) ```java class Solution { public List restoreIpAddresses(String s) { List res = new ArrayList<>(); int n = s.length(); if (n < 4) return res; dfs(0, 0, "", 0, s, res); return res; } private void dfs(int u, int start, String curs, int cnt, String s, List res) { if (u == s.length()) { if (cnt == 4) { res.add(curs.substring(0, curs.length() - 1)); } return; } // 不选 if (u < s.length() - 1) { dfs(u + 1, start, curs, cnt, s, res); } // 选 String t = s.substring(start, u + 1); if (t.length() > 12) return; if (Long.parseLong(t) > 255) return; if (cnt > 4) return; if (t.length() > 1 && t.charAt(0) == '0') return; dfs(u + 1, u + 1, curs + t + ".", cnt + 1, s, res); } } ``` ### 22. 括号生成 > 题目链接：[22. 括号生成](https://leetcode.cn/problems/generate-parentheses/) ```java class Solution { public List generateParenthesis(int n) { List res = new ArrayList<>(); dfs(0, 0, 0, n, "", res); return res; } public static void dfs(int u, int left, int right, int n, String curs, List res) { if(u == 2 * n){ if(left == right){ res.add(curs); } return; } // 优先加左括号 if(left < n) dfs(u + 1, left + 1, right, n, curs + '(', res); // 可以加右括号 if(left > right) dfs(u + 1, left, right + 1, n, curs + ')', res); } } ``` ## 差分 ### 56. 合并区间 > 题目链接：[56. 合并区间](https://leetcode.cn/problems/merge-intervals/) ```java class Solution { private static int N = (100000 + 10) * 2; public int[][] merge(int[][] intervals) { int[] b = new int[N]; // 1. 区间扩展 与差分操作 for (int[] num : intervals) { int l = num[0] * 2, r = num[1] * 2; insert(b, l, r, 1); } // 2. 求原数组 for(int i = 1; i < N; i ++) b[i] += b[i - 1]; // 3. 区间合并 List resList = new ArrayList<>(); int start = -1; for (int i = 0; i < N; i++) { if(b[i] > 0 && start == -1) start = i; // 起点 else if(b[i] == 0 && start != -1){ // 找到一个区间的结尾 resList.add(new int[]{start / 2, i / 2}); start = -1; // 为下一次做准备 } } int[][] res = resList.toArray(new int[0][]); for (int[] re : res) { System.out.println(re[0]+"---"+re[1]); } return res; } private static void insert(int[]b, int l, int r, int c){ b[l] += c; b[r + 1] -= c; } } ``` ## 队列 ### 239. 滑动窗口最大值 > 题目链接：[239. 滑动窗口最大值](https://leetcode.cn/problems/sliding-window-maximum/) 单调栈/单调队列的本质就是一个双端队列。 背过 思路：**单调队列**----用一个双端队列来维护长度为k的滑动窗口，维护窗口内的最大值 - 对于窗口内的k个数，要求最大值，暴力的做法就是进行遍历求最大值 - 我们可以用单调队列来求最大值，如何维护这个单调序列呢？（把所有不可能是答案的数都删掉（右边的数>=左边的数，那么我们就把左边的数删掉），结果发现剩余的序列是一个单调序列，求最值的时候，直接返回队头即可，时间复杂度：O（1）） - - 每次插入一个新数的时候，判断它是否比队尾还要大（严格单调 >= 队尾） - - - 要是比队尾还要大的的话，一直将队尾删掉（序列还是满足 <= 队头），然后插入队尾 - - 对于元素的淘汰，除了上述外，还有可能是过期被淘汰了（超出窗口k的范围） ```java class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; Deque q = new LinkedList<>(); int[] res = new int[n - k + 1]; int idx = 0; for (int i = 0; i < n; i++) {// i这里是窗口的右端点 // 移除过期元素（说明队头元素已经划出窗口了，弹出队头以元素） if(!q.isEmpty() && i - k + 1 > q.peekFirst()) q.pollFirst(); // 维护单调队列（当前元素 >= 队尾元素，则不断弹出，然后在加入，维护一个单调递增的序列） while (!q.isEmpty() && nums[i] >= nums[q.peekLast()]) q.pollLast(); // 当前元素入队(加入队尾) q.addLast(i); // 当窗口大小达到k时，记录最大值 if(i >= k - 1) res[idx ++] = nums[q.peekFirst()]; } return res; } } ``` ##