网络营销是什么模式,站长工具seo综合查询怎么看数据,免费网站的资源可以发公众号吗,wordpress能导出网站吗LeetCode 热题 100#xff1a;https://leetcode.cn/studyplan/top-100-liked/ 文章目录 一、哈希1. 两数之和49. 字母异位词分组128. 最长连续序列 二、双指针283. 移动零11. 盛水最多的容器15. 三数之和42. 接雨水#xff08;待完成#xff09; 三、滑动窗口3. 无重复字符的…LeetCode 热题 100https://leetcode.cn/studyplan/top-100-liked/ 文章目录 一、哈希1. 两数之和49. 字母异位词分组128. 最长连续序列 二、双指针283. 移动零11. 盛水最多的容器15. 三数之和42. 接雨水待完成 三、滑动窗口3. 无重复字符的最长子串438. 找到字符串中所有字母异位词 四、子串560. 和为 K 的子数组239. 滑动窗口最大值76. 最小覆盖子串补充209. 长度最小的子数组 五、普通数组53. 最大子数组和56. 合并区间189. 轮转数组238. 除自身以外数组的乘积41. 缺失的第一个正数待完成 六、矩阵73. 矩阵置零54. 螺旋矩阵48. 旋转图像240. 搜索二维矩阵 II 七、链表160. 相交链表206. 反转链表234. 回文链表141. 环形链表142. 环形链表 II21. 合并两个有序链表2. 两数相加19. 删除链表的倒数第 N 个结点24. 两两交换链表中的节点25. K 个一组翻转链表待完成138. 随机链表的复制148. 排序链表23. 合并 K 个升序链表146. LRU 缓存 一、哈希
1. 两数之和
思路设置一个 map 容器用于存储当前元素和索引。遍历时一边将数据存入 map一边比从map中查找满足加和等于 target 的另一个元素。
class Solution {/*** 输入nums [2,7,11,15], target 9* 输出[0,1]* 解释因为 nums[0] nums[1] 9 返回 [0, 1] 。*/public int[] twoSum(int[] nums, int target) {MapInteger, 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[] {};}
}49. 字母异位词分组
思路设置一个 map 容器key是排序后的字符组合value是字母异位词的集合。
class Solution {/*** 输入: strs [eat, tea, tan, ate, nat, bat]* 输出: [[bat],[nat,tan],[ate,eat,tea]]*/public ListListString groupAnagrams(String[] strs) {MapString, ListString map new HashMap();for (String str : strs) {char[] chars str.toCharArray();Arrays.sort(chars);String sortStr Arrays.toString(chars);// 如果存在key即new String(chars)那么返回对应的 value// 否则将执行先初始化 keynew String(chars)value: new ArrayList()然后在返回value。map.computeIfAbsent(new String(chars), s - new ArrayList()).add(str);}return new ArrayList(map.values());}
}128. 最长连续序列
思路因为题目要求O(n)的时间复杂度因此使用set对数组进行转存并利用滑动窗口一次遍历即可得出连续序列的最长长度。
class Solution {/*** 输入nums [100,4,200,1,3,2]* 输出4* 解释最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。*/public int longestConsecutive(int[] nums) {if (nums.length 0) {return 0;}SetInteger set new TreeSet();for (int num : nums) {set.add(num);}int co 0;for (Integer num : set) {nums[co] num;}return sliderWindow(nums);}private int sliderWindow(int[] nums) {int left 0;int len nums.length;int max 1;for (int right 1; right len; right) {if (nums[right] - nums[right - 1] ! 1) {left right;}max Math.max(right - left 1, max);}return max;}
}二、双指针
283. 移动零
class Solution {/*** 输入: nums [0,1,0,3,12]* 输出: [1,3,12,0,0]*/public void moveZeroes(int[] nums) {int j 0;for (int i 0; i nums.length; i) {if (nums[i] ! 0) {nums[j] nums[i];}}for (; j nums.length; j) {nums[j] 0;}}
}11. 盛水最多的容器
思路定义双指针分别指向数组的最左边和最右边每次往里移动较短的元素的指针。这里解释为什么要移动短的 根据木桶原理整个木桶盛水的最大体积取决于小的那一段木板。如果移动短的指针体积可能变大也可能不变还有可能变小。但如果移动长的指针体积一定会变小。因此在指针不断往里移动的同时移动指向较短元素的指针能得出盛水最大的容量。 class Solution {public int maxArea(int[] height) {int len height.length;int left 0;int right len - 1;int maxArea 0;// 面积 短板 * 底边// 向内移动短板水槽短板 min(h[i], h[j]) 可能变大下个水槽面积可能增大// 向内移动长板水槽短板 min(h[i], h[j]) 可能变小或不变下个水槽面积一定减小因为底边长变小while (left right) {maxArea Math.max(Math.min(height[left], height[right]) * (right - left), maxArea);if (height[left] height[right]) {left;} else {right--;}}return maxArea;}
}15. 三数之和
思路将数组排完序后进行遍历遍历时选取当前元素的后一个元素和数组的最后一个元素为双指针。注意对重复元素进行去重
class Solution {/*** 输入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] 。* 注意输出的顺序和三元组的顺序并不重要。*/public ListListInteger threeSum(int[] nums) {ListListInteger res new ArrayList();int len nums.length;Arrays.sort(nums);for (int i 0; i len; i) {if (nums[i] 0) {break;}if (i ! 0 nums[i] nums[i - 1]) { // 去除重复元素continue;}int left i 1;int right len - 1;while (left right) {int sum nums[i] nums[left] nums[right];if (sum 0) {res.add(Arrays.asList(nums[i], nums[left], nums[right]));while (left right nums[left] nums[left 1]) { // 去除重复元素left;}while (left right nums[right - 1] nums[right]) {right--;}left;right--;} else if (sum 0) {right--;} else {left;}}}return res;}
}42. 接雨水待完成 三、滑动窗口
3. 无重复字符的最长子串
思路定义一个 map 容器 key 存储字符value 存储当前字符索引。使用滑动窗口计算最长字串当窗口内存在重复字符时调整窗口的左边界调整为重复元素索引的下一位并且注意左边界不能向左移动。
class Solution {/*** 输入: s abcabcbb* 输出: 3 * 解释: 因为无重复字符的最长子串是 abc所以其长度为 3。*/public int lengthOfLongestSubstring(String s) {MapCharacter, Integer map new HashMap(); // key字符value当前字符索引int len s.length();int start 0;int max 0;for (int end 0; end len; end) {char ch s.charAt(end);if (map.containsKey(ch)) {start Math.max(map.get(ch) 1, start); // 处理 abba如果不用max比较当遍历到最后一个a时start将会指向第一个b即start-end范围是 bba}map.put(ch, end);max Math.max(end - start 1, max);}return max;}
}438. 找到字符串中所有字母异位词
思路使用数组统计字符串中26个字符的出现次数固定滑动窗口大小并使用 Arrays.equals(...) 方法一边遍历一边比较。
class Solution {/*** 输入: s cbaebabacd, p abc* 输出: [0,6]* 解释:* 起始索引等于 0 的子串是 cba, 它是 abc 的异位词。* 起始索引等于 6 的子串是 bac, 它是 abc 的异位词。*/public ListInteger findAnagrams(String s, String p) {ListInteger res new ArrayList();int sLen s.length();int pLen p.length();if (sLen pLen) {return res;}int[] sWin new int[26];int[] pWin new int[26];for (int i 0; i pLen; i) {sWin[s.charAt(i) - a];pWin[p.charAt(i) - a];}if (Arrays.equals(sWin, pWin)) {res.add(0);}for (int i pLen; i sLen; i) {sWin[s.charAt(i - pLen) - a]--;sWin[s.charAt(i) - a];if (Arrays.equals(sWin, pWin)) {res.add(i - pLen 1);}}return res;}
}四、子串
560. 和为 K 的子数组
思路首先计算前缀和利用前缀和的差值确定子数组的和是否等于K。 如下面数组求子数组和为 6pre[4] - pre[1] 6 就代表num[1:3] 加和等于 6。
ind01234567value41230624前缀和 pre04571010161822
注这里我们预留第一个位置为0代表索引为 0 的元素前缀和为 0。
class Solution {/*** 输入nums [1,2,3], k 3* 输出2*/public int subarraySum(int[] nums, int k) {int res 0;int len nums.length;int[] pre new int[len 1];// 计算前缀和for (int i 0; i len; i) {pre[i 1] pre[i] nums[i];}for (int left 0; left len; left) {for (int right left; right len; right) {if (pre[right 1] - pre[left] k) {res;}}}return res;}
}上面做法的时间复杂度为 O ( n 2 ) O(n^2) O(n2)因此用哈希表进行优化。
思路设置一个 map 容器用于存储前缀和以及前缀和的个数当计算前缀和的同时来查找是否存在 前缀和 - 目标和如果存在则说明存在子数组和等于 k。如上述例子中求子数组和为 6当遍历到索引 4 时前缀和为 10 map 中存在键 key“10-6”4 {key4,value1}说明当前元素存在前缀和为 4 的情况。
ind01234567value41230624累加的前缀和4571010161822
class Solution {/*** 输入nums [1,2,3], k 3* 输出2*/public int subarraySum(int[] nums, int k) {MapInteger, Integer map new HashMap(); // key前缀和value: 前缀和的个数int res 0;map.put(0, 1); // 前缀和为 0 的个数有一个int sum 0; // 记录前缀和for (int num : nums) {sum num;if (map.containsKey(sum - k)) {res map.get(sum - k);}map.put(sum, map.getOrDefault(sum, 0) 1);}return res;}
}239. 滑动窗口最大值
思路设置一个大顶堆固定窗口大小遍历时首先清除过期元素然后将元素入堆。 值得注意的是有些比较小的元素由于不在堆顶不会立即删除。但是在后面如果到了堆顶也会删除。
class Solution {/*** 输入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*/public int[] maxSlidingWindow(int[] nums, int k) {PriorityQueueElem heap new PriorityQueue((elem1, elem2) - elem2.value - elem1.value);// 初始化大顶堆int len nums.length;int[] res new int[len - k 1];for (int i 0; i k; i) {heap.add(new Elem(nums[i], i));}res[0] heap.element().value;int co 1;for (int i k; i len; i) {while (!heap.isEmpty() heap.element().index i - k) { // 处理不在窗口的元素// 有些比较小的元素由于不在堆顶不会立即删除。但是在后面如果到了堆顶也会删除// 如nums [5,6,-1,-2,3], k 3// 当窗口在[6,-1,-2]时5还在堆内但是当窗口在[-1,-2,3]时会在堆顶被删除heap.remove();}heap.add(new Elem(nums[i], i));res[co] heap.element().value;}return res;}class Elem {int value;int index;public Elem() {}public Elem(int value, int index) {this.value value;this.index index;}}
}76. 最小覆盖子串
思路分别设置两个数组用来存储字符的出现次数利用滑动窗口边一边右移一边检查模式串是否被覆盖。 class Solution {/*** 输入s ADOBECODEBANC, t ABC* 输出BANC* 解释最小覆盖子串 BANC 包含来自字符串 t 的 A、B 和 C。*/public String minWindow(String s, String t) {if (s.length() t.length()) {return ;}int[] sChars new int[128];int[] tChars new int[128];for (char ch : t.toCharArray()) {tChars[ch];}int left 0;int sLen s.length();int resLeft -1;int resRight sLen;for (int right 0; right sLen; right) {sChars[s.charAt(right)];while (left right isCovered(sChars, tChars)) {if (right - left resRight - resLeft) {resLeft left;resRight right;}sChars[s.charAt(left)]--;left;}}return resLeft -1 ? : s.substring(resLeft, resRight 1);}private boolean isCovered(int[] sChars, int[] tChars) {for (int i A; i Z; i) {if (sChars[i] tChars[i]) {return false;}}for (int i a; i z; i) {if (sChars[i] tChars[i]) {return false;}}return true;}
}上面代码在每次遍历的时候都需要检查子串是否被覆盖因此可以考虑设置两个变量 sNum 和 tNum。tNum 用于记录 t 中不同字符的数量 sNum 用于记录 s 指定字符达到覆盖 t 的程度数量。如当 s 的子串中如果 ‘a’ 的数量等于 t 中 ‘a’ 字符的数量时 sNum 1否则不变。
class Solution {/*** 输入s ADOBECODEBANC, t ABC* 输出BANC* 解释最小覆盖子串 BANC 包含来自字符串 t 的 A、B 和 C。*/public String minWindow(String s, String t) {int[] sChars new int[128];int[] tChars new int[128];int sNum 0; // 记录 s 中的指定字符数量达到覆盖 t 程度的数量int tNum 0; // 记录 t 中有多少不同字符for (char ch : t.toCharArray()) {if (tChars[ch] 0) {tNum;}}int len s.length();int resLeft -1;int resRight len;int left 0;for (int right 0; right len; right) {if (sChars[s.charAt(right)] tChars[s.charAt(right)]) {sNum; // s中的该字符数量达到覆盖 t 中该字符的程度}while (left right sNum tNum) {if (right - left resRight - resLeft) { // 更新结果左右边界resLeft left;resRight right;}if (sChars[s.charAt(left)]-- tChars[s.charAt(left)]) {sNum--;}left;}}return resLeft -1 ? : s.substring(resLeft, resRight 1);}
}补充209. 长度最小的子数组
最小覆盖子串题目类似209. 长度最小的子数组
class Solution {/*** 输入target 7, nums [2,3,1,2,4,3]* 输出2* 解释子数组 [4,3] 是长度最小且总和大于等于 target 的子数组。*/public int minSubArrayLen(int target, int[] nums) {int len nums.length;int sum 0;int left 0;int res len 1;for (int right 0; right len; right) {sum nums[right];while (left right sum target) {res Math.min(right - left 1, res);sum - nums[left];}}return res len 1 ? 0 : res;}
}五、普通数组
53. 最大子数组和
思路设置变量 curr 用于记录子数组和遍历数组时当子数组和大于零时累加当前元素否则令子数组和等于当前数组元素。
class Solution {/*** 输入nums [-2,1,-3,4,-1,2,1,-5,4]* 输出6* 解释连续子数组 [4,-1,2,1] 的和最大为 6 。*/public int maxSubArray(int[] nums) {int curr 0;int max nums[0];for (int i 0; i nums.length; i) {if (curr 0) {curr nums[i];} else {curr nums[i];}max Math.max(curr, max);}return max;}
}56. 合并区间
思路定义内部类用于记录区间的左右端点对二维数组按照左端点递增左端点相同时右端点递增的规则排序。将数组第一个元素加入集合后进行遍历若发现当前 数组元素左端点和集合最后一个元素的左端点相同 或者 集合最后一个元素的右端点大于数组的左端点则将集合的最后一个元素的右端点进行取大处理否则将数组元素加入集合。
class Solution {/*** 输入intervals [[1,3],[2,6],[8,10],[15,18]]* 输出[[1,6],[8,10],[15,18]]* 解释区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].*/public int[][] merge(int[][] intervals) {int len intervals.length;ListRange list new ArrayList();Arrays.sort(intervals,(range1, range2) - range1[0] ! range2[0] ? range1[0] - range2[0] : range1[1] - range2[1]);list.add(new Range(intervals[0][0], intervals[0][1]));for (int i 1; i len; i) {Range range list.get(list.size() - 1);if (range.begin intervals[i][0] || range.end intervals[i][0]) {range.end Math.max(intervals[i][1], range.end); // Max比较大小是为了处理这种情况 [[1,4],[2,3]]} else {list.add(new Range(intervals[i][0], intervals[i][1]));}}int size list.size();int[][] res new int[size][2];for (int i 0; i size; i) {res[i][0] list.get(i).begin;res[i][1] list.get(i).end;}return res;}class Range {int begin;int end;public Range() {}public Range(int begin, int end) {this.begin begin;this.end end;}}
}189. 轮转数组
思路先将数组全部翻转然后对前 k 个元素和其余的元素分别做翻转。
class Solution {/*** 输入: 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]*/public void rotate(int[] nums, int k) {int len nums.length;k % len;reverseArr(nums, 0, len - 1);reverseArr(nums, 0, k - 1);reverseArr(nums, k, len - 1);}private void reverseArr(int[] nums, int begin, int end) {while (begin end) {int temp nums[begin];nums[begin] nums[end];nums[end] temp;begin;end--;}}
}238. 除自身以外数组的乘积
思路将数组元素累乘以后逐个相除可能会存在除零异常。因此考虑分别求当前元素的左侧累乘积和右侧累乘积最后再将两侧数组做累乘。
class Solution {/*** 输入: nums [1,2,3,4]* 输出: [24,12,8,6]*/public int[] productExceptSelf(int[] nums) {int len nums.length;int[] left new int[len];int[] right new int[len];int[] res new int[len];left[0] 1;right[len - 1] 1;// nums: [1, 2, 3, 4]// left: [1, 1, 2, 6]// right: [24,12,4, 1]for (int i 1; i len; i) {left[i] nums[i - 1] * left[i - 1];}for (int i len - 2; i 0; i--) {right[i] nums[i 1] * right[i 1];}for (int i 0; i len; i) {res[i] left[i] * right[i];}return res;}
}41. 缺失的第一个正数待完成 六、矩阵
73. 矩阵置零
思路设置矩阵行列大小的两个数组用于对矩阵元素为零的行列进行标记。再次遍历矩阵然后将标记过的行和列进行置零。 class Solution {public void setZeroes(int[][] matrix) {int m matrix.length;int n matrix[0].length;int[] rows new int[m];int[] columns new int[n];for (int i 0; i m; i) {for (int j 0; j n; j) {if (matrix[i][j] 0) {rows[i] 1;columns[j] 1;}}}for (int i 0; i m; i) {for (int j 0; j n; j) {if (rows[i] 1 || columns[j] 1) {matrix[i][j] 0;}}}}
}54. 螺旋矩阵
思路初始化矩阵的上下左右四个边界按照 “从左向右、从上向下、从右向左、从下向上” 四个方向循环打印每次都需要更新边界并判断结束条件。 class Solution {public ListInteger spiralOrder(int[][] matrix) {ListInteger res new ArrayList();int left 0;int right matrix[0].length - 1;int up 0;int down matrix.length - 1;while (true) {for (int i left; i right; i) {res.add(matrix[up][i]);}if (up down) {break;}for (int i up; i down; i) {res.add(matrix[i][right]);}if (left --right) {break;}for (int i right; i left; i--) {res.add(matrix[down][i]);}if (up --down) {break;}for (int i down; i up; i--) {res.add(matrix[i][left]);}if (left right) {break;}}return res;}
}48. 旋转图像
思路先将矩阵转置然后将左右对称的两列互换元素即可达到顺时针旋转 90 度的效果。 class Solution {public 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;}}}
}240. 搜索二维矩阵 II
思路利用 “每行的所有元素从左到右升序排列每列的所有元素从上到下升序排列” 这个特点从右上角开始向左下角的方向查找当元素大于目标元素这一列下面的元素都大于目标元素当元素小于目标元素这一行前面的元素都小于目标元素。 class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m matrix.length;int n matrix[0].length;int x 0; // 右上角int y n - 1;while (x m y 0) {if (matrix[x][y] target) { // 当前元素大于target这一列下面的元素都大于targety--;} else if (matrix[x][y] target) { // 当前元素小于target这一行前面的元素都小于targetx;} else {return true;}}return false;}
}也可以从左下角开始查找代码如下
class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m matrix.length;int n matrix[0].length;int x m - 1; // 左下角int y 0;while (x 0 y n) {if (matrix[x][y] target) { // 当前元素大于target这一行后面的元素都大于targetx--;} else if (matrix[x][y] target) { // 当前元素小于target这一列上面的元素都小于targety;} else {return true;}}return false;}
}七、链表
160. 相交链表
思路利用乘法交换律设两个链表相交前分别有 A B 个节点相交部分有 C 个节点那么 ACBBCA。设置两个指针分别指向两个链表的头部同时向后移动。当其中一个指针移动到结尾时则转向指向另一个链表的头部另一个指针步骤同上最终两个指针会在相交处会面。
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode pa headA;ListNode pb headB;while (pa ! pb) {pa pa null ? headB : pa.next;pb pb null ? headA : pb.next;}return pa;}
}注如果两个链表不相交也适合以上规律最终两个指针都会指向空也会跳出循环。 206. 反转链表
思路链表头插法。 /*** 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 reverseList(ListNode head) {ListNode pre new ListNode();ListNode p;p head;pre.next null;while(p ! null){ListNode temp p.next;p.next pre.next;pre.next p;p temp;}return pre.next;}
}234. 回文链表
思路本地的实现很多这里采用栈进行辅助判断回文。 /*** 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 boolean isPalindrome(ListNode head) {DequeListNode stack new LinkedList();ListNode p head;while (p ! null) {stack.push(p);p p.next;}while (head ! null) {p stack.pop();if (p.val ! head.val) {return false;}head head.next;}return true;}
}141. 环形链表
思路1使用 hash 表进行辅助判断是否存在环。 /*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public boolean hasCycle(ListNode head) {SetListNode set new HashSet();ListNode p head;while (p ! null) {if (set.contains(p)) {return true;}set.add(p);p p.next;}return false;}
}思路2使用快慢指针slow 每次向前走一步fast 每次向前走两步。 ① 当存在环时fast 由于走得快会发生扣圈的情况且最终与 slow 相遇。 ② 当不存在环时fast 可能在某次循环后发生当前位置为空或下一位置为空的两种情况当然由于走的快最终会返回 false。 总之循环的结束条件要么出现环 slow fast要么 fast 先一步为空。下面列举两种实现方式
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public boolean hasCycle(ListNode head) {ListNode slow head;ListNode fast head;while (true) {if (fast null || fast.next null) {return false;}slow slow.next;fast fast.next.next;if (slow fast) {return true;}}}
}// 推荐
public class Solution {public boolean hasCycle(ListNode head) {if (head null) {return false;}ListNode slow head;ListNode fast head;while (fast.next ! null fast.next.next ! null) {slow slow.next;fast fast.next.next;if (slow fast) {return true;}}return false;}
}142. 环形链表 II
思路1使用 hash 表。 /*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {SetListNode set new HashSet();ListNode p head;while (p ! null) {if (set.contains(p)) {return p;}set.add(p);p p.next;}return null;}
}思路2使用快慢指针思路如下
设 fast 每次走两个节点 slow 每次走一个节点。环外有 a 个结点环内有 b 个结点。第一次相遇时fast 走了 f 步slow 走了 s 步。 ① f 2s ② f s nb 表示 f 比 s 多走了 n*b 步即 n 圈。这样表示的原因在于扣圈。 化简得f 2nb, s nbn 代表扣圈的次数可能等于1,2,3,…设刚开始 slow 指针从开始到环的入口要走 k 步k a tbt 代表在环中循环的次数可能等于0,1,2,3,…。因此当发生第一次相遇时再走 a 步即可重新回到入环的起点。
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {if (head null) {return null;}ListNode slow head;ListNode fast head;while (fast.next ! null fast.next.next ! null) {slow slow.next;fast fast.next.next;if (slow fast) {fast head; // 令 fast 指针指向链表头部break;}}if (fast.next null || fast.next.next null) {return null;}while (slow ! fast) {slow slow.next;fast fast.next;}return fast;}
}21. 合并两个有序链表
思路设置两个指针分别指向链表头部逐个比较向后迭代即可。 /*** 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 mergeTwoLists(ListNode list1, ListNode list2) {ListNode p1 list1;ListNode p2 list2;ListNode pre new ListNode();ListNode p pre;while (p1 ! null p2 ! null) {if (p1.val p2.val) {p.next p1;p p1;p1 p1.next;} else {p.next p2;p p2;p2 p2.next;}}if (p1 ! null) {p.next p1;}if (p2 ! null) {p.next p2;}return pre.next;}
}2. 两数相加
思路设置两个指针和进位标志逐个向后相加迭代即可。 输入l1 [2,4,3], l2 [5,6,4] 输出[7,0,8] 解释342 465 807
/*** 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 addTwoNumbers(ListNode l1, ListNode l2) {ListNode pre new ListNode();ListNode p pre;ListNode p1 l1;ListNode p2 l2;int sign 0;int sum;while (p1 ! null || p2 ! null) {if (p1 ! null p2 ! null) {sum p1.val p2.val sign;p1 p1.next;p2 p2.next;} else if (p1 ! null) {sum p1.val sign;p1 p1.next;} else {sum p2.val sign;p2 p2.next;}p.next new ListNode(sum % 10);p p.next;sign sum / 10;}if (sign ! 0) {p.next new ListNode(sign);}return pre.next;}
}19. 删除链表的倒数第 N 个结点
思路让前面的指针先移动 n 步之后前后指针共同移动直到前面的指针到尾部为止。 /*** 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 removeNthFromEnd(ListNode head, int n) {ListNode pre new ListNode();pre.next head;ListNode p pre;ListNode q pre;int co 0;while (p.next ! null) {if (co n) {q q.next;}p p.next;}q.next q.next.next;return pre.next;}
}24. 两两交换链表中的节点
思路链表节点两两交换位置逐个向后迭代。 /*** 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 swapPairs(ListNode head) {ListNode pre new ListNode(0);pre.next head;ListNode p head;ListNode q pre;while (p ! null p.next ! null) {ListNode temp p.next.next;q.next p.next;q.next.next p;p.next null;q p;p temp;}if (p ! null) {q.next p;}return pre.next;}
}25. K 个一组翻转链表待完成 138. 随机链表的复制
思路题意是让我们把下面的随机链表做整体复制这里我们设置一个 map 容器用于对应原始节点和复制的节点存储以后再处理 next 指针和 random 指针。 /*
class Node {int val;Node next;Node random;public Node(int val) {this.val val;this.next null;this.random null;}
}
*/
class Solution {public Node copyRandomList(Node head) {if (head null) {return null;}MapNode, Node map new HashMap();Node p head;while (p ! null) {Node copyNode new Node(p.val);map.put(p, copyNode);p p.next;}p head;while (p ! null) {Node copyNode map.get(p);if (p.random ! null) {copyNode.random map.get(p.random);}if (p.next ! null) {copyNode.next map.get(p.next);}p p.next;}return map.get(head);}
}148. 排序链表
思路这里我们采用堆结构辅助链表排序将大顶堆构造好以后一边出堆一边利用头插法对链表结构进行重塑。 /*** 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 sortList(ListNode head) {PriorityQueueListNode queue new PriorityQueue((a, b) - b.val-a.val); // 大顶堆while(head ! null){queue.offer(head); // 从堆底插入head head.next;}ListNode pre new ListNode(0);while(!queue.isEmpty()){ListNode p queue.poll(); // 出队列并调整堆p.next pre.next; // 头插法倒序pre.next p;}return pre.next;}
}23. 合并 K 个升序链表
思路K 个有序链表重复调用两个有序链表的算法。
/*** 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 {/*** 输入lists [[1,4,5],[1,3,4],[2,6]]* 输出[1,1,2,3,4,4,5,6]*/public ListNode mergeKLists(ListNode[] lists) {int len lists.length;ListNode pre null; for (int i 0; i len; i) {pre mergeTwoLists(pre, lists[i]);}return pre;}private ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode p1 list1;ListNode p2 list2;ListNode pre new ListNode();ListNode p pre;while (p1 ! null p2 ! null) {if (p1.val p2.val) {p.next p1;p p1;p1 p1.next;} else {p.next p2;p p2;p2 p2.next;}}if (p1 ! null) {p.next p1;}if (p2 ! null) {p.next p2;}return pre.next;}
}146. LRU 缓存
输入 [LRUCache, put, put, get, put, get, put, get, get, get] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 输出 [null, null, null, 1, null, -1, null, -1, 3, 4] 解释 LRUCache lRUCache new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {11} lRUCache.put(2, 2); // 缓存是 {11, 22} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废缓存是 {11, 33} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废缓存是 {44, 33} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4 思路参考灵神的思路想象有一摞书。 get时将一本书(key) 抽出来放在最上面。 put放入一本新书如果已经有这本书(key)把他抽出来放在最上面并替换它的 value。如果没有这本书(key)就放在最上面。如果超出了 capacity 本书就把最下面的书移除。
题目要求 get 和 put 都是 O(1) 的时间复杂度因此考虑双向链表实现。
class LRUCache {class Node {int key, value;Node prev, next;public Node(int key, int value) {this.key key;this.value value;}}MapInteger, Node map;Node dummy;int capacity;public LRUCache(int capacity) {map new HashMap();dummy new Node(0, 0); // 头结点this.capacity capacity;dummy.next dummy;dummy.prev dummy;}public int get(int key) {Node node getNode(key);return node ! null ? node.value : -1;}public void put(int key, int value) {Node node getNode(key);if (node ! null) {node.value value; // 如果存在则在getRoot方法里面已经放到了头部return;}node new Node(key, value);map.put(key, node);pushFirst(node); // 放在链表头部if (map.size() capacity) {map.remove(dummy.prev.key);remove(dummy.prev);}}private Node getNode(int key) {if (!map.containsKey(key)) {return null;}Node node map.get(key);remove(node); // 删除旧节点pushFirst(node); // 将新节点加到链表头部return node;}private void pushFirst(Node node) {node.next dummy.next;node.prev dummy;dummy.next.prev node;dummy.next node;}private void remove(Node node) {node.prev.next node.next;node.next.prev node.prev;}
}
/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj new LRUCache(capacity);* int param_1 obj.get(key);* obj.put(key,value);*/
