淮南移动网站建设,phpcms网站模版下载,山东前十名建筑设计院,湖北网站推广系统LeetCode 热题 100 其他系列哈希1. 两数之和49. 字母异位词分组128. 最长连续序列 双指针27. 移除元素283. 移动零11. 盛最多水的容器剑指 Offer II 007. 数组中和为 0 的三个数42. 接雨水 滑动窗口438. 找到字符串中所有字母异位词3. 无重复字符的最长子串 字串560. 和为 K 的… LeetCode 热题 100 其他系列哈希1. 两数之和49. 字母异位词分组128. 最长连续序列 双指针27. 移除元素283. 移动零11. 盛最多水的容器剑指 Offer II 007. 数组中和为 0 的三个数42. 接雨水 滑动窗口438. 找到字符串中所有字母异位词3. 无重复字符的最长子串 字串560. 和为 K 的子数组剑指 Offer 59 - I. 滑动窗口的最大值 普通数组最大子数组和56. 合并区间189. 轮转数组238. 除自身以外数组的乘积 矩阵73. 矩阵置零54. 螺旋矩阵48. 旋转图像240. 搜索二维矩阵 II 链表160. 相交链表206. 反转链表234. 回文链表141. 环形链表基础模板题142. 环形链表 II21. 合并两个有序链表模板题2. 两数相加19. 删除链表的倒数第 N 个结点24. 两两交换链表中的节点25. K 个一组翻转链表138. 复制带随机指针的链表148. 排序链表23. 合并 K 个升序链表 二叉树94. 二叉树的中序遍历104. 二叉树的最大深度226. 翻转二叉树101. 对称二叉树543. 二叉树的直径102. 二叉树的层序遍历108. 将有序数组转换为二叉搜索树98. 验证二叉搜索树剑指 Offer 54. 二叉搜索树的第k大节点199. 二叉树的右视图114. 二叉树展开为链表105. 从前序与中序遍历序列构造二叉树LCR 050. 路径总和 III236. 二叉树的最近公共祖先 图论200. 岛屿数量994. 腐烂的橘子207. 课程表208. 实现 Trie (前缀树) 回溯17. 电话号码的字母组合77. 组合39. 组合总和剑指 Offer 34. 二叉树中和为某一值的路径46. 全排列47. 全排列 II78. 子集51. N 皇后22. 括号生成131. 分割回文串 二分查找35. 搜索插入位置74. 搜索二维矩阵34. 在排序数组中查找元素的第一个和最后一个位置JZ11 旋转数组的最小数字存在重复值153. 寻找旋转排序数组中的最小值不包含重复值33. 搜索旋转排序数组 栈20. 有效的括号155. 最小栈739. 每日温度42. 接雨水 堆数组中的第K个最大元素347. 前 K 个高频元素295. 数据流的中位数 贪心算法55. 跳跃游戏45. 跳跃游戏 II763. 划分字母区间 动态规划70. 爬楼梯118. 杨辉三角322. 零钱兑换279. 完全平方数139. 单词拆分300. 最长递增子序列和最大子数组152. 乘积最大子数组416. 分割等和子集打家劫舍系列198. 打家劫舍213. 打家劫舍 II337. 打家劫舍 III 多维动态规划62. 不同路径63. 不同路径 II64. 最小路径和5. 最长回文子串中心扩展法非动态规划解法解法一暴力 - 遍历所有字串解法二中心扩展法 1143. 最长公共子序列 技巧169. 多数元素136. 只出现一次的数字75. 颜色分类287. 寻找重复数 其他系列
【LeetCode刷题总结 - 剑指offer系列 - 持续更新】 【LeetCode刷题总结 - 面试经典 150 题 -持续更新】
哈希
1. 两数之和
【两数之和】 分析 空间换时间的思想将当前值 以及对应下标信息 存储在map中
核心代码
// 初始化存储 某个值 以及 在nums中的位置信息
HashMapInteger, Integer tempMap new HashMap();// 如果目标值 存在tempMap中则说明找到了结果
if(tempMap.containsKey(another)) {res[0] i;res[1] tempMap.get(another);return res;
}// 主流程把当前值 及 对应位置信息存入到map中
tempMap.put(nums[i], i);代码 class Solution {public int[] twoSum(int[] nums, int target) {// 初始化map 【值:下标】HashMapInteger, Integer tempMap new HashMap();int[] res new int[2];for(int i0; inums.length; i) {Integer another target - nums[i];// 如果目标值 存在tempMap中则说明找到了结果if(tempMap.containsKey(another)) {res[0] i;res[1] tempMap.get(another);return res;}// 将【值:下标】 存储在map中 (常规套路在写代码时进入for后 就可以先写这一步)tempMap.put(nums[i], i);}return res;}
}49. 字母异位词分组
【49. 字母异位词分组】 分析 由于互为字母异位词的两个字符串包含的字母相同因此对两个字符串分别进行排序之后得到的字符串一定是相同的故可以将排序之后的字符串作为哈希表的键。 代码 class Solution {public ListListString groupAnagrams(String[] strs) {MapString, ListString map new HashMapString, ListString();for (String str : strs) {char[] array str.toCharArray();// 字母异位词 排序后一定相同Arrays.sort(array);String key new String(array);ListString list map.getOrDefault(key, new ArrayListString());list.add(str);map.put(key, list);}return new ArrayListListString(map.values());}
}128. 最长连续序列
【128. 最长连续序列】 分析 参考题解【【超小白】哈希集合/哈希表/动态规划/并查集四种方法绝对够兄弟们喝一壶的】
首先遍历数组将数据存储到set中set有两个作用 作用1使用hashSet判断元素是否存在时间复杂度为O(1)作用2元素去重 遍历set计算元素连续累加的最大长度。若 cur-1存在则没必要计算原因 原因1如果num-1已经在数组中的话那么num-1肯定会进行相应的1遍历然后遍历到num原因2而且从num-1开始的1遍历必定比从num开始的1遍历得到的序列长度更长 代码 class Solution {public int longestConsecutive(int[] nums) {int res 0;SetInteger set new HashSet();for(int num: nums) {set.add(num);}// 遍历去重后的setfor(int num: set) {int cur num;/*** 若存在 cur-1那么我们是没必要计算的因为* 1. 如果num-1已经在数组中的话那么num-1肯定会进行相应的1遍历然后遍历到num* 2. 而且从num-1开始的1遍历必定比从num开始的1遍历得到的序列长度更长* 结论我们便可将在一个连续序列中的元素让其只在最小的元素才开始1遍历*/if(!set.contains(cur-1)) {// 计算累加连续最大长度while(set.contains(cur1)) {cur;}// 更新最大值res Math.max(res, cur - num 1);}}return res;}
}双指针
27. 移除元素
【27. 移除元素】 分析 新增一个指针left[0,left) 之间的元素就是!val的遍历数组判断每个元素是否等于val! val 则添加到nums[left]left
参考动画https://leetcode.cn/problems/remove-element/solution/xue-sheng-wu-de-nu-peng-you-du-neng-kan-nk7yy/ 代码 class Solution {public int removeElement(int[] nums, int val) {int left 0;// 遍历数组判断每个元素for(int right0; rightnums.length; right) {if(nums[right] ! val) {nums[left] nums[right];left;}}return left;}
}283. 移动零
【283. 移动零】 分析 跟上题类似只不过目标值变成了0 代码 class Solution {public void moveZeroes(int[] nums) {int len nums.length;int left 0;for(int i0; ilen; i) {if(nums[i] ! 0) {nums[left] nums[i];}}for(int ileft; ilen; i) {nums[i] 0;}}
}11. 盛最多水的容器
【11. 盛最多水的容器】 分析 借鉴题解https://leetcode.cn/problems/container-with-most-water/solution/container-with-most-water-shuang-zhi-zhen-fa-yi-do/
结论左右指针谁的高度越低谁就往中间移动
若向内移动短板水槽的短板min(h[i], h[j])可能变大因此下个水槽面积可能增大若向内移动长板水槽的短板min(h[i], h[j])不变或变小因此下个水槽面积一定变小
流程
初始化双指针leftright分列水槽的两端循环收窄直到双指针相遇则跳出 更新面积最大值max选定两板高度中的短板向中间收窄一格 返回值返回面积最大值即可 代码 class Solution {public int maxArea(int[] height) {int max Integer.MIN_VALUE;int left 0;int right height.length-1;while(left right) {int area (right - left) * Math.min(height[left], height[right]);max Math.max(max, area);// 谁低谁往中间移动if(height[left] height[right]) {left;} else {right--;}}return max;}
}剑指 Offer II 007. 数组中和为 0 的三个数
【剑指 Offer II 007. 数组中和为 0 的三个数】 分析 先排序通过枚举 i 确定第一个数另外两个指针 leftright 分别从左边 i 1 和右边 length - 1 往中间移动找到满足 nums[left] nums[right] -nums[i] 的所有组合去重因为是有序序列因此我们可以用如下方式去重重点看代码细细品味 代码 class Solution {/*** 【重要】因为数据是排好序的因此我们哪样处理才会去重* 细细品味其实每次去重都是保证 三元组中每一个元素这一次 与 下一次 数据不同每一个元素都是如此*/public ListListInteger threeSum(int[] nums) {ListListInteger res new ArrayList();Arrays.sort(nums);for(int i0; inums.length; i) {// 若当前值与上一个相同则没必要再重新搞一遍了否则会重复if(i 0 nums[i] nums[i-1]) {continue;}int target -nums[i];int left i1;int right nums.length-1;while(left right) {int sum nums[left] nums[right];if(sum target) {res.add(Arrays.asList(nums[i], nums[left], nums[right]));// 找下一个跟 当前tempL不同的值作为新的left因为数组是有序的因此这样可以保证去重int tempL nums[left];while(left right nums[left] tempL) {left;}// 找下一个跟 当前tempR不同的值作为新的right同理int tempR nums[right--];while(left right nums[right] tempR) {right--;}}if(sum target) {left;} else if ( sum target) {right--;}}}return res;}
}42. 接雨水
【42. 接雨水】 分析 参考视频【单调栈经典来袭LeetCode:42.接雨水】
建议先做上一题
找到较低点的前一个较大值 和 后一个较大值则可以算较低点 相对于 前、后两个较大点所接的雨水横向求解水平求解维护一个单调栈存储下标若当前值大于栈顶元素则栈顶元素就是 较低点栈顶第二个元素就是较低点的前一个较大点当前值就是较低点的下一个较大点 代码 class Solution {public int trap(int[] height) {// stack维护一个单调栈非递减存储下标StackInteger stack new Stack();// 记录接雨水的总数int sum 0;for(int i0; iheight.length; i) {int cur height[i];// 若栈顶元素 小于 当前值则弹出表示当前值是栈顶元素的后续第一个较大者while(!stack.isEmpty() height[stack.peek()] cur) {// nextHeight下个较大值(下标)int nextHeight i;// mid就是中间点(下标)int mid stack.pop();if(stack.isEmpty()) { // 若为空 则直接跳过不处理break;}// preHeight:前一个较大值(下标)int preHeight stack.peek();// 高度差int diffY Math.min(height[preHeight], height[nextHeight]) - height[mid];// 宽度差int diffX nextHeight - preHeight - 1;// 面积累计sum diffX * diffY;}stack.push(i);}return sum;}
}滑动窗口
438. 找到字符串中所有字母异位词
【438. 找到字符串中所有字母异位词】 分析 参考题解【固定滑动窗口求解LC438】 代码 class Solution {public ListInteger findAnagrams(String s, String p) {ListInteger res new ArrayList();int lenS s.length();int lenP p.length();if(lenS lenP) { // 若 s长度 p长度 则不存在解return new ArrayList();}// 用于维护滑动窗口过程中每个字母的数量int[] windowCount new int[26];// 用于统计字符p的每个字符的数量int[] pCount new int[26];// 初始统计for(int i0; ilenP; i) {windowCount[s.charAt(i) - a];pCount[p.charAt(i) - a];}// [left, right] 维护滑动窗口区间 区间内的windowCount若与pCount相同则满足解条件for(int left0, rightlenP-1; rightlenS; left, right) {if(Arrays.equals(windowCount, pCount)) {res.add(left);}// 左指针移动windowCount[s.charAt(left) - a]--;// 右指针移动if(right 1 lenS) {windowCount[s.charAt(right 1) - a];}}return res;}
}3. 无重复字符的最长子串
【无重复字符的最长子串】 分析 解题思路 该题是一道滑动窗口的问题。 滑动窗口的一般套路左区间手动改变有区间for循环累加
B站上视频链接 https://www.bilibili.com/video/BV1BV411i77g https://www.bilibili.com/video/BV1w5411E7EP
总结注意点
和第一道题【1. 两数之和】类似点在于都可以使用 一个map 来记录【值:下标】使用双指针 构建滑动窗口的 经典问题。套路左边界手动改变 右边界自动累加l和r滑动窗口的区间[l,r]表示的就是当前所维护的不重复的字串l Math.max(l, map.get(curChar) 1),这里取得是map.get(curChar) 1别忘了1了。如果不1的话那么字串可能是abca这种即第一个字符与后面那个字符重复 代码 class Solution {public int lengthOfLongestSubstring(String s) {// 判空处理if(null s || s.length() 0) {return 0;}// 初始化map 【值:下标】HashMapCharacter, Integer map new HashMap();// 定义滑动窗口最左侧指针int l 0;// 最大长度int maxLength 0;// r可以理解为 滑动窗口最右侧指针for(int r 0; r s.length(); r) {char curChar s.charAt(r);// 若map中之前存过这个值的下标则让left指针右移 if(map.containsKey(curChar)) {// 目的更新l 为 l、map(curChar)最右侧的下标// Math.max的好处我们不需要考虑这个值是否在滑动窗口内l Math.max(l, map.get(curChar) 1);}// 更新最大长度maxLength Math.max(maxLength, r - l 1);// 将【值:下标】 存储在map中 (常规套路在写代码时进入for后 就可以先写这一步)map.put(curChar, r);}return maxLength;}
}字串
560. 和为 K 的子数组
【560. 和为 K 的子数组】 分析 参考视频【560. 和为 K 的子数组 Subarray Sum Equals K【LeetCode 力扣官方题解】】 参考评论 代码 class Solution {public int subarraySum(int[] nums, int k) {/**【这题其实可以转换为第一题的AB。 谈谈我的理解】参考用户buzhengjing的评论//举个例子:int[] a {1, 2, 3, 4, 5, 6};//将每个元素累加,对应下面这个数组:int[] b {1, 3, 6, 10, 15, 21};//因为题干要求是连续子数组,所以任意的b[i]与b[j]的差值即为子数组的和.//所以就变成了找出b[i]与b[j]的差等于k,有多少种组合方式.//第一题是找两数之和abtarget这题是找两数之差a-btarget*/int count 0;int len nums.length;// 记录前缀和int[] dp new int[len];dp[0] nums[0];for(int i1; ilen; i) {dp[i] dp[i-1] nums[i];}// 记录前缀和 的个数 key前缀和 value 个数MapInteger, Integer map new HashMap();/*** 前缀和为0要赋值为1。* 例子nums [3,...], k 3和 nums [1, 1, 1,...], k 3 这两种情况 刚开始需要得到前缀和为0的个数如果给0 的话结果就会漏记算这种情况*/map.put(0, 1);// 遍历前缀和for(int i0; ilen; i) {int target dp[i] - k;count map.getOrDefault(target, 0); // 更新countmap.put(dp[i], map.getOrDefault(dp[i], 0) 1); // 累加前缀和的个数}return count;}
}剑指 Offer 59 - I. 滑动窗口的最大值
【剑指 Offer 59 - I. 滑动窗口的最大值】 分析 其实思路和上一题是一致的可以在上一题的基础上进行处理
没达到滑动窗口大小时大小为K不需要移除头部元素直接添加尾部元素调用push_back达到滑动窗口大小时存储当前队列最大值max_value达到滑动窗口大小后需要先移除头部元素pop_front再添加尾部元素push_back然后存储当前队列最大值max_value 代码 class Solution {// 存储实际的值QueueInteger queue;// 双端队列维护最大值单调递减DequeInteger deque;public void init() {queue new LinkedList();deque new LinkedList();}public int max_value() {if(deque.isEmpty()) {return -1;}// 返回队列头部元素递增序列 头部最大return deque.peekFirst();}public void push_back(int value) {queue.offer(value);// 移除掉队列中比自己小的值篮球队长模型while(!deque.isEmpty() deque.peekLast() value) {deque.pollLast();}// 最后添加到队尾deque.addLast(value);}public int pop_front() {if(queue.isEmpty()) {return -1;}// 若队头元素 就是 最大队列的头部则移除掉 最大队列头部if(queue.peek().equals(deque.peek())) {deque.poll();}// 最终调用队列的pollreturn queue.poll();}public int[] maxSlidingWindow(int[] nums, int k) {// 存储结果int[] res new int[nums.length - k 1];init();// 没达到滑动窗口大小时大小为K不需要移除最前面元素for(int i0; ik; i) {push_back(nums[i]);}int index 0;res[index] max_value(); for(int ik; inums.length; i) {pop_front();push_back(nums[i]);res[index] max_value();}return res;}
}简化版
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int len nums.length;int[] res new int[len - k 1];DequeInteger maxQueue new LinkedList();for(int i0; ik; i) {while(!maxQueue.isEmpty() nums[i] maxQueue.peekLast()) {maxQueue.removeLast();}maxQueue.offer(nums[i]);}int idx 0;res[idx] maxQueue.peek();for(int ik; ilen; i) {// 删除元素if(maxQueue.peek().equals(nums[i-k])) {maxQueue.poll();}// 添加新的元素while(!maxQueue.isEmpty() nums[i] maxQueue.peekLast()) {maxQueue.removeLast();}maxQueue.offer(nums[i]);// 储存最大值res[idx] maxQueue.peek();}return res;}
}普通数组
最大子数组和
【最大子数组和】 分析 技巧像这种最大、最小 的 子数组、子序列我们在定义动态数组时大多数这样定义dp[i] 以下标i 值为结尾的 子数组 或者 子序列
遍历nums填写dp数组dp[i]以nums[i]结尾若dp[i-1] 0则没必要加上dp[i-1]了因为加上去则会使dp[i]更小dp[i] nums[i]否则dp[i] nums[i] dp[i-1] 代码 class Solution {public int maxSubArray(int[] nums) {if(nums.length 0) {return 0;}// dp定义: 表示以 i下标值 结尾的子数组的和int[] dp new int[nums.length];dp[0] nums[0];int maxSubArrayValue dp[0];for(int i1; inums.length; i) {// 若dp[i-1] 为负数则以i结尾的子数组就没必要加上前面的了因为加上去只会让数组和更小if(dp[i-1] 0) {dp[i] nums[i];} else {dp[i] dp[i-1] nums[i];}// 若dp[i] 大于 最大值则更新最大值if(dp[i] maxSubArrayValue) {maxSubArrayValue dp[i];}}return maxSubArrayValue;}
}56. 合并区间
【56. 合并区间】 分析 参考文章【秒懂力扣区间题目重叠区间、合并区间、插入区间】
遍历intervals若interval与res的最后一个元素区间重合则合并最后一个区间否则 则直接加入到res中 代码 class Solution {public int[][] merge(int[][] intervals) {Listint[] res new ArrayList();// 升序排列Arrays.sort(intervals, (v1,v2) - v1[0] - v2[0]);// 遍历intervals更新resfor(int[] interval: intervals) {if(!res.isEmpty() interval[0] res.get(res.size()-1)[1]) { // 重叠了则更新res的最后一个元素// 拿到 res的最后一个元素int[] last res.get(res.size()-1);// 更新last[1]last[1] Math.max(last[1], interval[1]);} else { // 不重叠则直接更新res.add(interval);}}int[][] res1 new int[res.size()][2];for(int i0; ires.size(); i) {for(int j0; j2; j) {res1[i][j] res.get(i)[j];}}return res1;}
}189. 轮转数组
【189. 轮转数组】 分析 步骤一整体翻转[1,2,3,4,5,6,7] - [7,6,5,4,3,2,1]步骤二数组截断分成两段若k3则[7,6,5,4,3,2,1] - [7,6,5]、[4,3,2,1]步骤三分别对两段数组进行翻转[7,6,5]、[4,3,2,1] - [5,6,7]、[1,2,3,4]步骤四拼接两段[5,6,7]、[1,2,3,4] - [5,6,7,1,2,3,4] 代码 class Solution {/*** 因为我们实际上并没有分割数组所有操作都是在原数组上因此【步骤二】 和 【步骤四】是可以省略的*/public void rotate(int[] nums, int k) {// 注意该题的k有可能大于数组的长度因此我们要提前取余k k % nums.length;// 步骤一整体翻转[1,2,3,4,5,6,7] - [7,6,5,4,3,2,1]reverse(nums, 0, nums.length-1);// 步骤二数组截断分成两段若k3则[7,6,5,4,3,2,1] - [7,6,5]、[4,3,2,1]// 步骤三分别对两段数组进行翻转[7,6,5]、[4,3,2,1] - [5,6,7]、[1,2,3,4]reverse(nums, 0, k-1);reverse(nums, k, nums.length-1);// 步骤四拼接两段[5,6,7]、[1,2,3,4] - [5,6,7,1,2,3,4]}/*** 翻转数组中元素 [a,b,c,d] - [d,c,b,a]*/public void reverse(int[] nums, int left, int right) {while(left right) {swap(nums, left, right);left;right--;}}/*** 交换数组中 index1 和index2 的位置*/public void swap(int[] nums, int index1, int index2) {int temp nums[index1];nums[index1] nums[index2];nums[index2] temp;}
}238. 除自身以外数组的乘积
【238. 除自身以外数组的乘积】 分析 解题思路 B站上视频连接https://www.bilibili.com/video/BV1xV411f773
利用类似于动态规划的思想构建[0,i]的乘积数组即i及i之前的所有数的乘积利用类似于动态规划的思想构建[i,n-1]的乘积数组即i及i之后的所有数的乘积最终根据题意 res[i] cj1[i-1] * cj2[i1]求最终结果集 代码 public class Solution {public int[] multiply(int[] A) {int n A.length;// 用于存放 i及i之前的所有乘积包含i[0,i]int[] cj1 new int[n];// 用于存放 i及i之后的所有乘积包含i[i,n-1]int[] cj2 new int[n];// 用于存放那结果集int[] res new int[n];// 类似于动态规划的求法求cj1。[0,i]for(int i0; in; i) {// 若i为0则区A[0] 边界条件if(i 0)cj1[i] A[0];else // 动态规划cj1[i] cj1[i-1] * A[i];}// 类似于动态规划的求法求cj2。[i,n-1]。 同上for(int in-1; i0; i--) {if(i n-1)cj2[i] A[n-1];elsecj2[i] cj2[i1] * A[i];}// 最后根据题意求结果集for(int i0; in; i) {if(i 0)res[i] cj2[i1];else if(i n-1)res[i] cj1[i-1];elseres[i] cj1[i-1] * cj2[i1];}return res;}
}矩阵
73. 矩阵置零
【73. 矩阵置零】 分析 参考视频【【LeetCode 每日一题】73. 矩阵置零 | 手写图解版思路 代码讲解】 代码 class Solution {public void setZeroes(int[][] matrix) {int m matrix.length;int n matrix[0].length;boolean flag_row0 false;boolean flag_col0 false;// 遍历第一行是否存在0for(int i0; in; i) {if(matrix[0][i] 0) flag_row0 true;}// 遍历第一列是否存在0for(int i0; im; i) {if(matrix[i][0] 0) flag_col0 true;}// i、j 都从下标1 开始遍历否则会错误for(int i1; im; i) {for(int j1; jn; j) {if(matrix[i][j] 0) {// 若当前位置为0则将第一行、第一列对应的位置置0matrix[0][j] 0;matrix[i][0] 0;}}}// i、j 都从下标1 开始遍历否则会错误for(int i1; im; i) {for(int j1; jn; j) {if(matrix[0][j] 0 || matrix[i][0] 0) {matrix[i][j] 0;}}}if(flag_row0) {for(int i0; in; i) {matrix[0][i] 0;}}if(flag_col0) {for(int i0; im; i) {matrix[i][0] 0;}}}
}54. 螺旋矩阵
【54. 螺旋矩阵】 分析 参考bilibili视频【LeetCode力扣刷题 | 剑指Offer 29. 顺时针打印矩阵】 代码 class Solution {public ListInteger spiralOrder(int[][] matrix) {int left 0;int right matrix[0].length - 1;int top 0;int bottom matrix.length - 1;ListInteger res new ArrayList();while(true) {// 打印最上边的for(int ileft; iright; i) {res.add(matrix[top][i]);}top;if(top bottom) break;// 打印最右边的for(int itop; ibottom; i) {res.add(matrix[i][right]);}right--;if(right left) break;// 打印最下边的for(int iright; ileft; i--) {res.add(matrix[bottom][i]);}bottom--;if(bottom top) break;// 打印最左边的for(int ibottom; itop; i--) {res.add(matrix[i][left]);}left;if(left right) break;}return res;}
}48. 旋转图像
【48. 旋转图像】 分析 先沿左上 到 右下 的中心斜线反转再沿数轴中心反转
参考视频【【LeetCode 每日一题】48. 旋转图像 | 手写图解版思路 代码讲解】 代码 class Solution {public void rotate(int[][] matrix) {int n matrix.length;// 沿对角线反转for(int i0; in; i) {for(int j0; ji; j) { // 注意j的范围int temp matrix[i][j];matrix[i][j] matrix[j][i];matrix[j][i] temp;}}// 沿中心竖线反转for(int i0; in; i) {for(int j0; jn/2; j) { // 注意j的范围int temp matrix[i][j];matrix[i][j] matrix[i][n-j-1];matrix[i][n-j-1] temp;}}}
}240. 搜索二维矩阵 II
【240. 搜索二维矩阵 II】 分析 首先题中说明 每一行都按照从左到右递增的顺序排序 每一列都按照从上到下递增的顺序排序。 那么一看数据是有序的 那么我们肯定第一时间想到二分查找法。但在着整个二维数组中好像没法直接使用二分查找但是我们可以使用二分查找的思想。
二分查找思想 每一轮比较首先获取一个特殊值然后让目标值与该值进行比较每次比较都能排除一些数据进而缩小搜索的范围。
解决该题我们用的方法和二叉查找法类似也是每次都取一个特殊值与目标值比较每轮都排除一部分数据进而缩小数据的查找范围 B站上讲解视频 https://www.bilibili.com/video/BV12J411i7A6
https://www.bilibili.com/video/BV1Tt411F7YD?spm_id_from333.999.0.0 代码 class Solution {public boolean searchMatrix(int[][] array, int target) {// 套路模板 先判空if(array.length 0) return false;// row表示有几行,col表示有几列。int row array.length;int col array[0].length;// 我们取右上角的值int x 0; int y col - 1;// 不断排除一列或者一行不断缩小范围while(x row-1 y 0) {if(target array[x][y]) {// 排除头一行的数据x;}else if (target array[x][y]) {// 排除后一列的数据y--;}else {return true;}}// 若判处完所有数据仍没有找目标值 该值不存在return false;}
}链表
160. 相交链表
【160. 相交链表】 版本一 import java.util.*;
/**
* 暴力解法
*/
public class Solution {public ListNode getIntersectionNode(ListNode pHead1, ListNode pHead2) {HashSetListNode set new HashSet();// 首先遍历第一个链表的所有节点 并将节点存入带set中while(pHead1 ! null) {set.add(pHead1);pHead1 pHead1.next;}// 遍历第二个链表 如果出现节点包含在set中 则说明该节点是链表1和链表2的公共节点while(pHead2 ! null) {if(set.contains(pHead2)) {return pHead2;}pHead2 pHead2.next;}return null;}
}心得
暴力可以解决大多数问题set.contains(xxx) 判断set中是否存在xxx这个对象 版本二 public class Solution {public ListNode getIntersectionNode(ListNode pHead1, ListNode pHead2) {int size1 0; // 记录链表1的长度int size2 0; // 记录链表2的长度ListNode cur1 pHead1;ListNode cur2 pHead2;// 算出链表1 的长度while(cur1 ! null) {size1;cur1 cur1.next;}// 算出链表2 的长度while(cur2 ! null) {size2;cur2 cur2.next;}cur1 pHead1;cur2 pHead2;// 相当于链表1和链表2 在一个等长的链表上 依次后移如果两指针相同 则一定是第一个相交点while(cur1 ! cur2) {// 先走链表2 的长度 再遍历链表1if(size2 ! 0) {size2--;}else {cur1 cur1.next;}// 先走链表1 的长度 再遍历链表2if(size1 ! 0) {size1--;}else {cur2 cur2.next;}}return cur1;}
}心得
有时候解题可以换一种思路 版本三 public class Solution {public ListNode getIntersectionNode(ListNode pHead1, ListNode pHead2) {// p1 初始指向pHead1ListNode p1 pHead1;// p2 初始指向pJead2ListNode p2 pHead2;// 遍历 p1 和 p2while(p1 ! p2) {// 若p1走链表1走到头 则开始走链表2if(p1 null)p1 pHead2;else // 没走到头就后移p1 p1.next;// p2 同上if(p2 null)p2 pHead1;elsep2 p2.next;}// 最终p1肯定等于p2 因为他俩要么都是公共点要么都为nullreturn p1;}
}206. 反转链表
【206. 反转链表】 分析 双指针前指针-pre当前指针-cur局部翻转实现整体翻转 代码 public class Solution {public ListNode reverseList(ListNode head) {ListNode pre null; // 前一个节点ListNode cur head; // 当前节点 该引用初始指向head头结点while(cur ! null) {// 1、创建一个新引用指向当前节点的下个节点ListNode next cur.next;// 2、当前节点指向上个节点局部反转cur.next pre;// 3、cur和pre指针后移先移pre 后移cur顺序不能反pre cur;cur next;}return pre;}
}234. 回文链表
【234. 回文链表】 分析 大体上分三步
1、先将链表分为两段2、反转第二段链表3、比较两段链表各个节点是否相同 代码 class Solution {public boolean isPalindrome(ListNode head) {if(head null) return true;// 先将链表分为两段ListNode fast head;ListNode slow head;while(fast.next ! null fast.next.next ! null) {fast fast.next.next;slow slow.next;}ListNode newList slow.next;slow.next null;// 反转第二段链表ListNode prev null;ListNode cur newList;while(cur ! null) {ListNode nextNode cur.next;cur.next prev;prev cur;cur nextNode;}// 比较两段链表各个节点是否相同while(prev ! null) {if(prev.val ! head.val) {return false;}prev prev.next;head head.next;}return true;}
}141. 环形链表基础模板题
【141. 环形链表】 分析 可以参考我之前总结的这篇文章很详细【判断单链表是否有环以及入环节点】 代码 public class Solution {public boolean hasCycle(ListNode head) {if(head null) return false;if(head.next null) return false;ListNode slow head.next;ListNode fast head.next.next;while(slow ! fast) {if(fast null || fast.next null) {return false;}slow slow.next;fast fast.next.next;}return true;}
}142. 环形链表 II
【142. 环形链表 II】 分析 可以参考我之前总结的这篇文章很详细【判断单链表是否有环以及入环节点】 代码 public class Solution {public ListNode detectCycle(ListNode head) {if(head null) return null;if(head.next null) return null;ListNode slow head.next;ListNode fast head.next.next;while (slow ! fast) {if(fast null || fast.next null) {return null;}slow slow.next;fast fast.next.next;}slow head;while(slow ! fast) {slow slow.next;fast fast.next;}return fast;}
}21. 合并两个有序链表模板题
【21. 合并两个有序链表】 分析 双指针分别指向 list1 和 list2比较list1 和 list2 的指针指向的节点大小更小者最拼接到新链表末尾并且指针后移若某一个链表已经遍历完那么直接将另一个未遍历完的链表连接到新链表的尾部
直接看代码代码更清晰 代码 class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {// 新链表的虚拟头结点ListNode head new ListNode(0);ListNode cur head;// 从list1 和 list2 中取更小者拼接到新链表尾部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;} // 能走到这里只有有两种情况1、list1合并完了、list2没合并完 2、list1没合并完、list2合并完了// 合并list1剩余的元素if(list1 ! null) {cur.next list1;}// 合并list2剩余的元素if(list2 ! null) {cur.next list2;}return head.next; }
}2. 两数相加
【两数相加】 分析 详细流程可参考代码
总结注意点
常规链表的移动指针三个移动指针对应三个链表while(null ! head1 || null ! head2) 循环条件是 || 不是任意一个链表没走完就执行的逻辑int num1 nullhead1 ? 0 : head1.val 当前节点 为null取0否则取val构建进位变量 carry作用域一定要放到外面放里面就没法用了考虑最后一步最后节点遍历完后判断最后一步运算是否进位了进位则补1否则不处理 代码 /*** 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 head1 l1; // 移动指针1指向链表1ListNode head2 l2; // 移动指针2指向链表2// 构建结果链表ListNode resHead new ListNode();ListNode temp resHead;// 移动指针3指向链表3// 进位值 默认是0 作用域一定要是外面int carry 0;while(null ! head1 || null ! head2) {// 为空取0 否则取val核心思想int num1 nullhead1 ? 0 : head1.val;int num2 nullhead2 ? 0 : head2.val;int sum num1 num2 carry;// 求模取余 获取当前节点值int curVal sum % 10;// 整除获取进位值carry sum / 10;// 构建当前节点ListNode curNode new ListNode(curVal);// 尾插法temp.next curNode; temp curNode;// 节点后移只需要考虑不为null的链表即可因为为null的话我们默认取0, 不会有影响if(null ! head1) head1 head1.next;if(null ! head2) head2 head2.next;}// 最后节点遍历完后判断最后一步运算是否进位了进位则补1否则不处理if(carry 1) {ListNode lastNode new ListNode(1);temp.next lastNode;}return resHead.next;}
}19. 删除链表的倒数第 N 个结点
【19. 删除链表的倒数第 N 个结点】 分析 算出链表的长度 - size根据 n 和 size 算出待删除节点的前一个节点位置找到待删除节点的前一个节点调用cur.next cur.next.next 删除目标节点
为了避免处理边界节点我们可以在头结点前面加一个虚拟头结点dummyHead 代码 class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {int size 0;ListNode cur head;// 算出链表的长度while(cur ! null) {size;cur cur.next;}// 计算待删除节点 的 前一个位置int index size - n;// 虚拟头结点避免处理特殊的边界情况ListNode dummyHead new ListNode(0);dummyHead.next head;cur dummyHead;// 指针指向待删除节点的前一个节点for(int i0; iindex; i) {cur cur.next;}// 删除目标节点cur.next cur.next.next;return dummyHead.next;}
}24. 两两交换链表中的节点
【24. 两两交换链表中的节点】 分析 参考视频讲解【帮你把链表细节学清楚 | LeetCode24. 两两交换链表中的节点】 代码 class Solution {public ListNode swapPairs(ListNode head) {if(head null) return null;ListNode dummyNode new ListNode(0);dummyNode.next head;ListNode cur dummyNode;while(cur.next ! null cur.next.next ! null) {// 保存下一个节点ListNode temp1 cur.next;// 保存下下下个节点ListNode temp2 cur.next.next.next;// 处理指向关系cur.next temp1.next;cur.next.next temp1;temp1.next temp2;// cur后移两步cur cur.next.next;}return dummyNode.next;}
}25. K 个一组翻转链表
【25. K 个一组翻转链表】 分析 参考讲解视频【【LeetCode 25. K 个一组翻转链表】 每天一题刷起来C 年薪冲冲冲】
先将前 k 个节点组成的链表进行翻转递归处理剩余的链表 代码 class Solution {public ListNode reverseKGroup(ListNode head, int k) {// 特殊情况一【链表为null 或者 k1, 没必要反转】if(head null || k 1) {return head;}// end 指向当前节点ListNode end head;// 下面这一段代码主要用来判断 链表长度是否小于kfor(int i1; ik end ! null; i) {end end.next;}if(end null) { // 若end为null说明 剩下节点不足k个了不需要翻转return head;}// 走到此处 [head,end] 其实就是当前需要翻转的k个节点// 排除完特殊情况 下面就是正常情况了。 此时cur已经指向第k个节点了// 先保存下一节点k1地址 因为接下来要断开 cur与k1 节点的连接ListNode nextListHead end.next;// 断开k节点 与 k1节点的连接 因为接下来要单独反转当前组单链表了end.next null;// 反转当前组 单项链表ListNode newHead reverse(head); // 翻转之后之前的head其实就跑到尾部了// 递归处理剩余剩下的链表并拼接在之前的head后面此时的head指针指向的是尾部head.next reverseKGroup(nextListHead, k);// 返回反转后的新头节点return newHead;}/*** 翻转单链表*/private ListNode reverse(ListNode head) {ListNode cur head;ListNode prev null;while(cur ! null) {ListNode nextNode cur.next;cur.next prev;prev cur;cur nextNode;}return prev;}
}138. 复制带随机指针的链表
【138. 复制带随机指针的链表】 分析 第一次遍历原链表简单复制新的节点此时新老节点 仅仅是val相同遍历的过程中将新、老节点的映射关系存储在map中第二次遍历原链表复制链表中 next 、 random的指向关系依赖map中的映射关系 代码 class Solution {public Node copyRandomList(Node head) {if(head null) {return null;}MapNode, Node map new HashMap();Node cur head;// 1、 第一次遍历原链表 创建对应的新节点 并且对应关系存入到map集合中while(cur ! null) {// 1.1 创建新节点Node newNode new Node(cur.val);// 2.2 并将 以oldNode为keynewNode为value的方式存入到map中 oldNode:newNodemap.put(cur, newNode);cur cur.next;}// 2、第一次遍历原链表进行深拷贝cur head;while(cur ! null) {// 2.1 复制对应next节点map.get(cur).next map.get(cur.next);// 2.2 复制对应random节点map.get(cur).random map.get(cur.random);cur cur.next;}return map.get(head);}
}148. 排序链表
【148. 排序链表】 分析 最简单的做法就是将所有节点放到集合中然后对集合进行排序任意排序算法都可以这里可参考【八大排序算法】
了解排序算法的会发现归并排序处理链表是非常舒服的尤其是合并阶段
该题我使用的就是链表版的归并排序数组版的归并排序可以参考【归并排序】
归并排序主要分两个阶段
分治将待排序列二分一直向下划分直到只有一个元素为止只有一个元素相当于已排序合并将已排序的两个子序列合并为一个新的有序序列主要逻辑 动画排序过程
该题我拆分了三个小方法 【获取链表中心元素】 在【LeetCode刷题总结 - 剑指offer系列 - 持续更新】这篇文章中有总结过当存在偶数个节点时怎么获取中心左侧的元素怎么获取中心右侧的元素 该题中我们要获取的是中心左侧的元素因为后面我们要断开链表就需要靠左的元素执行 node.next null
/*** 返回中心节点* 若节点个数为偶数则返回中心左边的节点例如[1,2,3,4]最终返回2*/
public ListNode getMiddle(ListNode head) {ListNode slow head;ListNode fast head;while(fast.next ! null fast.next.next ! null) {slow slow.next;fast fast.next.next;}return slow;
}【合并两个有序的链表】
/*** 归并将两个有序的链表 合并为一个链表*/
public ListNode merge(ListNode left, ListNode right) {// 虚拟头节点ListNode head new ListNode(0);ListNode cur head;// 合并左链表、右链表都存在未合并的元素while(left ! null right ! null) {if(left.val right.val) {cur.next left;left left.next;} else {cur.next right;right right.next;}cur cur.next;}// 能走到这里只有有两种情况1、左边合并完了、右边没合并完 2、左边没合并完、右边合并完了// 合并左链表剩余的元素if(left ! null) {cur.next left;}// 合并右链表剩余的元素if(right ! null) {cur.next right;}return head.next;
}【归并排序整体框架】
public ListNode sort(ListNode head) {// 终止条件只有一个元素就不必再排序了if(head ! null head.next null) {return head;}// 获取中心节点ListNode middle getMiddle(head);// 从中心断开left为做链表right为右链表ListNode right middle.next;middle.next null;ListNode left head;// 递归划分处理左半段ListNode sortedLeft sort(left);// 递归划分处理右半段ListNode sortedRight sort(right);// 将划分后的排序合并排序的主要逻辑在这个方法里return merge(sortedLeft, sortedRight);
}代码 class Solution {public ListNode sortList(ListNode head) {if(head null) {return null;}return sort(head);}public ListNode sort(ListNode head) {// 终止条件只有一个元素就不必再排序了if(head ! null head.next null) {return head;}// 获取中心节点ListNode middle getMiddle(head);// 从中心断开left为做链表right为右链表ListNode right middle.next;middle.next null;ListNode left head;// 递归划分处理左半段ListNode sortedLeft sort(left);// 递归划分处理右半段ListNode sortedRight sort(right);// 将划分后的排序合并排序的主要逻辑在这个方法里return merge(sortedLeft, sortedRight);}/*** 归并将两个有序的链表 合并为一个链表*/public ListNode merge(ListNode left, ListNode right) {// 虚拟头节点ListNode head new ListNode(0);ListNode cur head;// 合并左链表、右链表都存在未合并的元素while(left ! null right ! null) {if(left.val right.val) {cur.next left;left left.next;} else {cur.next right;right right.next;}cur cur.next;}// 能走到这里只有有两种情况1、左边合并完了、右边没合并完 2、左边没合并完、右边合并完了// 合并左链表剩余的元素if(left ! null) {cur.next left;}// 合并右链表剩余的元素if(right ! null) {cur.next right;}return head.next;}/*** 返回中心节点* 若节点个数为偶数则返回中心左边的节点例如[1,2,3,4]最终返回2*/public ListNode getMiddle(ListNode head) {ListNode slow head;ListNode fast head;while(fast.next ! null fast.next.next ! null) {slow slow.next;fast fast.next.next;}return slow;}
}23. 合并 K 个升序链表
【23. 合并 K 个升序链表】 分析 还是归并排序的思路。 其实归并排序的本质就是将两个有序的序列合并为一个有序的序列。归并排序是先将长序列 分成无数个小的子序列其实就是为了得到有序的序列因为当子序列长度为1时就可以看做有序的序列了紧接着在二二合并
该题其实就是给了我们已经排序好的子序列然后让我们二二合并而为了提高效率我们可以参考归并排序使用分治的思想时间复杂度nlogk 代码 class Solution {public ListNode mergeKLists(ListNode[] lists) {if(lists null || lists.length0) {return null;}return partition(lists, 0, lists.length-1);}/*** 本质上还是归并排序的框架*/public ListNode partition(ListNode[] lists, int left, int right) {// 终止条件只有一个链表就没必要再合并了if(left right) {return lists[left];}int mid (left right) 1;// 递归处理左边ListNode sortedLeft partition(lists, left, mid);// 递归处理右边ListNode sortedRight partition(lists, mid1, right);// 归并return merge(sortedLeft, sortedRight);}/*** 归并将两个有序的链表 合并为一个链表*/public ListNode merge(ListNode left, ListNode right) {// 虚拟头节点ListNode head new ListNode(0);ListNode cur head;// 合并左链表、右链表都存在未合并的元素while(left ! null right ! null) {if(left.val right.val) {cur.next left;left left.next;} else {cur.next right;right right.next;}cur cur.next;}// 能走到这里只有有两种情况1、左边合并完了、右边没合并完 2、左边没合并完、右边合并完了// 合并左链表剩余的元素if(left ! null) {cur.next left;}// 合并右链表剩余的元素if(right ! null) {cur.next right;}return head.next;}}二叉树
94. 二叉树的中序遍历
【94. 二叉树的中序遍历】 代码 class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger res new ArrayList();dfs(root, res);return res;}public void dfs(TreeNode root, ListInteger res) {if(root null) return;dfs(root.left, res);res.add(root.val);dfs(root.right, res);}
}104. 二叉树的最大深度
【104. 二叉树的最大深度】 代码 class Solution {public int maxDepth(TreeNode root) {return getDepth(root);}public int getDepth(TreeNode root) {if(root null) return 0;int leftDepth getDepth(root.left);int rightDepth getDepth(root.right);return Math.max(leftDepth, rightDepth) 1;}
}226. 翻转二叉树
【226. 翻转二叉树】 代码 class Solution {public TreeNode invertTree(TreeNode root) {if(root null) return null;swap(root);invertTree(root.left);invertTree(root.right);return root;}public void swap(TreeNode root) {if(root null) return;TreeNode temp root.left;root.left root.right;root.right temp;}
}101. 对称二叉树
【101. 对称二叉树】 分析 这里是把根节点的左右子树当做两棵树然后比较这两棵树是否对称
比较两棵树是否相同的主要代码
boolean leftIsSame isSame(root1.left, root2.left);
boolean rightIsSame isSame(root1.right, root2.right);比较两棵树是否对称的主要代码
// 判断对称的外侧即 左树的左孩子 与 右树的右孩子
boolean outFlag symmetric(root1.left, root2.right);
// 判断对称的内侧即 左树的右孩子 与 右树的左孩子
boolean inFlag symmetric(root1.right, root2.left);代码 class Solution {public boolean isSymmetric(TreeNode root) {return symmetric(root.left, root.right);}public boolean symmetric(TreeNode root1, TreeNode root2) {if(root1 null root2 null) {return true;}if(root1 null || root2 null) {return false;}if(root1.val ! root2.val) {return false;}// 判断对称的外侧即 左树的左孩子 与 右树的右孩子boolean outFlag symmetric(root1.left, root2.right);// 判断对称的内侧即 左树的右孩子 与 右树的左孩子boolean inFlag symmetric(root1.right, root2.left);return outFlag inFlag;}
}543. 二叉树的直径
【543. 二叉树的直径】 分析 使用一个变量维护最大直径在求二叉树深度的基础上更新 最大直径直径求法左子树深度 右子树深度 1 代码 class Solution {int maxLength 0;public int diameterOfBinaryTree(TreeNode root) {getDepth(root);return maxLength - 1;}public int getDepth(TreeNode root) {if(root null) return 0;int lDepth getDepth(root.left);int rDepth getDepth(root.right);maxLength Math.max(maxLength, lDepth rDepth 1);return Math.max(lDepth, rDepth) 1;}
}102. 二叉树的层序遍历
【102. 二叉树的层序遍历】 分析 一样的模板套路 代码 class Solution {public ListListInteger levelOrder(TreeNode root) {if(root null) {return new ArrayList();}ListListInteger res new ArrayList();QueueTreeNode queue new LinkedList();queue.offer(root);while(!queue.isEmpty()) {int len queue.size();ListInteger list new ArrayList();for(int i0; ilen; i) {TreeNode node queue.poll();list.add(node.val);if(node.left ! null) {queue.offer(node.left);}if(node.right ! null) {queue.offer(node.right);}}res.add(list);}return res;}
}108. 将有序数组转换为二叉搜索树
【108. 将有序数组转换为二叉搜索树】 分析 当看到有序数组第一印象想到二分 当看到二叉树第一印象想到中序遍历但是这题是构造二叉树因此用不到中序遍历
每次都取数组中心元素作为根节点那么左、右子树的节点个数绝对值相差一定1左、右子树其实是规模更小的相同问题顺其自然想到递归分治的思想分别处理左、右子数组直到left right 为止 代码 class Solution {public TreeNode sortedArrayToBST(int[] nums) {return dfs(nums, 0, nums.length - 1);}public TreeNode dfs(int[] nums, int left, int right) {if(left right) {return null;}int mid (left right) 1;TreeNode root new TreeNode(nums[mid]);root.left dfs(nums, left, mid - 1);root.right dfs(nums, mid 1, right);return root;}
}98. 验证二叉搜索树
【98. 验证二叉搜索树】 分析 使用一个变量维护上一个节点的值中序遍历若当前节点前一个节点大则为false 代码 class Solution {long prev Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if(root null) return true;boolean leftFlag isValidBST(root.left);if(root.val prev) return false;prev root.val;boolean rightFlag isValidBST(root.right);return leftFlag rightFlag;}
}剑指 Offer 54. 二叉搜索树的第k大节点
【剑指 Offer 54. 二叉搜索树的第k大节点】 分析 对于二叉搜索树中序遍历最终是有序的 代码 class Solution {private ListInteger res new ArrayList();public int kthLargest(TreeNode root, int k) {dfs(root, k);return res.get(k-1);}public void dfs(TreeNode root, int k) {if(root null) {return;}// 若res的大小是k则不用再遍历了if(res.size() k) {return;}// 中序遍历搜索树最终是有序序列dfs(root.right, k);res.add(root.val);dfs(root.left, k);}
}199. 二叉树的右视图
【199. 二叉树的右视图】 分析 层次遍历取每一层的末尾节点 代码 class Solution {public ListInteger rightSideView(TreeNode root) {if(root null) {return new ArrayList();}QueueTreeNode queue new LinkedList();queue.offer(root);ListInteger res new ArrayList();while(!queue.isEmpty()) {int length queue.size();for(int i0; ilength; i) {TreeNode node queue.poll();if(node.left ! null) {queue.offer(node.left);}if(node.right ! null) {queue.offer(node.right);}if(i length-1) {res.add(node.val);}}}return res;}
}114. 二叉树展开为链表
【114. 二叉树展开为链表】 分析 参考视频【【LeetCode 每日一题】114. 二叉树展开为链表 | 手写图解版思路 代码讲解】 代码 class Solution {public void flatten(TreeNode root) {TreeNode cur root;// 遍历二叉树while(cur ! null) {// 若左子树不为空则特殊处理if(cur.left ! null) {// 1、 找到左子树中 最右侧的节点 pTreeNode p cur.left;while(p.right ! null) {p p.right;}// 2、改变指向关系p.right cur.right;cur.right cur.left;cur.left null;}// 指针到右孩子cur cur.right;}}
}105. 从前序与中序遍历序列构造二叉树
【105. 从前序与中序遍历序列构造二叉树】 分析 上面【分治算法-系列】的【剑指 Offer 07. 重建二叉树】 代码 class Solution {int[] preorder;int[] inorder;// 存储中序遍历 对应值的下标private HashMapInteger, Integer inorderMap new HashMap();public TreeNode buildTree(int[] preorder, int[] inorder) {this.preorder preorder;this.inorder inorder;for(int i0; iinorder.length; i) {inorderMap.put(inorder[i], i);}return build(0, preorder.length-1, 0, inorder.length-1);}public TreeNode build(int left1, int right1, int left2, int right2) {if(left1right1 || left2right2) {return null;}int rootVal preorder[left1];TreeNode root new TreeNode(rootVal);int idx inorderMap.get(rootVal);int leftTreeSize idx - left2; // 左子树大小int rightTreeSize right2 - idx; // 右子树大小// 构建左孩子root.left build(left11, left1leftTreeSize, left2, left2leftTreeSize-1);// 构建右孩子root.right build(left1leftTreeSize1, right1, idx1, right2);return root;}
}LCR 050. 路径总和 III
【LCR 050. 路径总和 III】 分析 与上面两题不同的几点
这次“路径”的定义不一定是从根节点到叶子节点因此我们要遍历整棵树的每个节点再以该节点为根调用dfs深度优先并且目标条件不再判断是否为叶子节点这次节点值 可以是负数、0、正数因此我们再找到某条路径后不能return还要再往深入走因为节点值可能为负数
解题步骤
遍历该树的每个节点以每个节点为根分别调用dfs深度搜索找到目标路径并累加到计数器 代码 import java.util.*;/** public class TreeNode {* int val 0;* TreeNode left null;* TreeNode right null;* public TreeNode(int val) {* this.val val;* }* }*/public class Solution {int count 0; // 计数器记录路径总数// 遍历该树的每个节点再调用dfs这一步主要是遍历的作用public int FindPath (TreeNode root, int sum) {// 套路if(root null) return count;// 执行当前节点的逻辑 这里是 dfs(root,sum);dfs(root,sum);// 递归遍历 该节点的左右子树FindPath(root.left, sum);FindPath(root.right, sum);// 最终返回计数器 countreturn count;}// 深度遍历 统计路径条数void dfs(TreeNode root, int sum) {// 套路模板 先判空if(root null) return;// 执行当前节点的正常逻辑这里是sum-val以及找寻目标 sum0sum - root.val;if(sum 0) // 这里与前面的题不同的是 不用判断 左右节点为null 因为路径定义不一定非是叶子节点count; // 这里为什么不return呢 因为节点可以为负数继续往深处走可能还满足// 递归深度搜索左右孩子dfs(root.left, sum);dfs(root.right, sum);}
}心得
一般先遍历每个节点再将每个节点看做树根操作的都可以使用两个递归配合操作。先遍历树 再对每个节点分别操作。
236. 二叉树的最近公共祖先
【236. 二叉树的最近公共祖先】 分析 上面已经总结过该题【剑指 Offer 68 - II. 二叉树的最近公共祖先】 代码 class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root null) {return null;}return dfs(root, p, q);}// 【后续遍历】的特点可以把最终返回的节点 通过递归一直往上推public TreeNode dfs(TreeNode root, TreeNode p, TreeNode q) {// 当前节点为null则肯定找不到直接返回nullif(root null) {return null;}// 找到了p 或者 q则向上返回if(root p || root q) {return root;}// 【左】TreeNode left dfs(root.left, p, q);// 【右】TreeNode right dfs(root.right, p, q);// 【中】if(left ! null right ! null) {// 若左、右子树都找到了则当前节点就是最近公共节点return root;} else if (left ! null right null) {// 左树找到了但右树没找到则返回left结果return left;} else if(right ! null left null) {// 右树找到了但左树没找到则返回right结果return right;} else {// 都没找到则向上返回nullreturn null;}}
}图论
200. 岛屿数量
【200. 岛屿数量】 分析 遍历所有网格遇到陆地点则以该点开始深度优先遍历遍历过的点要打上标记避免后序重复遍历 代码 class Solution {public int numIslands(char[][] grid) {int count 0;for(int i0; igrid.length; i) {for(int j0; jgrid[0].length; j) {// 遇到陆地if(grid[i][j] 1) {dfs(grid, i, j);count;}}}return count;}public void dfs(char[][] grid, int x, int y) {// 边界条件if(!inArea(grid, x, y)) {return;}// 不是岛屿不处理if(grid[x][y] ! 1) {return;}// 遍历过要加上标记grid[x][y] 2;dfs(grid, x-1, y); // 上dfs(grid, x1, y); // 下dfs(grid, x, y-1); // 左dfs(grid, x, y1); // 右}public boolean inArea(char[][] grid, int x, int y) {return x 0 x grid.length y 0 y grid[0].length;}
}994. 腐烂的橘子
【994. 腐烂的橘子】 分析 广度优先
参考题解【理清思路为什么用 BFS以及如何写 BFS 代码Java/Python】 代码 class Solution {public int orangesRotting(int[][] grid) {Queueint[] queue new LinkedList();int m grid.length;int n grid[0].length;int fresh 0;int time 0;// 遍历橘子for(int i0; im; i) {for(int j0; jn; j) {if(grid[i][j] 1) { // 新鲜橘子则freshfresh;} else if (grid[i][j] 2) { // 将腐烂的橘子加入队列中queue.offer(new int[]{i, j});}}}// 没有新鲜的直接返回0if(fresh 0) return 0;// 广度优先while(!queue.isEmpty() fresh 0) { // 必须满足新鲜的数量0 否则就没必要遍历了int len queue.size();time;for(int i0; ilen; i) {int[] badOrange queue.poll();int x badOrange[0];int y badOrange[1];// 上 只腐蚀新鲜的坏的在之前已经遍历过了if(x-1 0 grid[x-1][y] 1) {grid[x-1][y] 2; // 腐蚀fresh--;queue.offer(new int[]{x-1, y});}// 下if(x1 m grid[x1][y] 1) {grid[x1][y] 2;fresh--;queue.offer(new int[]{x1, y});}// 左if(y-1 0 grid[x][y-1] 1) {grid[x][y-1] 2;fresh--;queue.offer(new int[]{x, y-1});}// 右if(y1 n grid[x][y1] 1) {grid[x][y1] 2;fresh--;queue.offer(new int[]{x, y1});}}}return fresh 0 ? time : -1;}
}207. 课程表
【207. 课程表】 分析 参考视频【207. 课程表 Course Schedule 【LeetCode 力扣官方题解】】
参考题解【「图解」拓扑排序 | 课程表问题】 代码 class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {// 课号和对应的入度MapInteger, Integer inDegreeMap new HashMap();for(int i0; inumCourses; i) {inDegreeMap.put(i, 0);}// 依赖关系, 依赖当前课程的后序课程MapInteger, ListInteger outDegreeCourseMap new HashMap();for(int[] arr: prerequisites) {int prev arr[1];int cur arr[0];// 更新出度集合列表if(!outDegreeCourseMap.containsKey(prev)) {outDegreeCourseMap.put(prev, new ArrayList());}outDegreeCourseMap.get(prev).add(cur);// 更新入度inDegreeMap.put(cur, inDegreeMap.get(cur) 1);}// BFS将入度为0不需要前置课程的课程放入列表QueueInteger queue new LinkedList();for(int key: inDegreeMap.keySet()) {if(inDegreeMap.get(key) 0) {queue.offer(key);}}while(!queue.isEmpty()) {int cur queue.poll();if(!outDegreeCourseMap.containsKey(cur)) {continue;}ListInteger outDegreeCourse outDegreeCourseMap.get(cur);for(int course: outDegreeCourse) {inDegreeMap.put(course, inDegreeMap.get(course) - 1);// 入度为0说该课的前修改已经修完所以当前课可以修了if (inDegreeMap.get(course) 0) {queue.offer(course);}}}// 遍历入度, 如果还有课程的入度不为0, 返回faslefor (int key : inDegreeMap.keySet()) {if (inDegreeMap.get(key) ! 0) {return false;}}return true;}
}208. 实现 Trie (前缀树)
【208. 实现 Trie (前缀树)】 代码 class Trie {// 自定义Node节点数据结构private class Node {// 词典MapCharacter, Node dict new HashMap();// 是否为终止节点boolean isEnd false;}// 一棵树的根节点private Node root;public Trie() {// 初始化根节点root new Node();}public void insert(String word) {Node cur this.root;char[] charArr word.toCharArray();for(char ch: charArr) {MapCharacter, Node dict cur.dict;// 若当前词典不存在该字符对应的Node则为该字符创建Nodeif(!dict.containsKey(ch)) {dict.put(ch, new Node());}// 指针下移cur dict.get(ch);}// 将终止节点的打上终止标记cur.isEnd true;}public boolean search(String word) {Node endNode searchPrefix(word);// 若终止节点不为空 并且 endNode为true说明词典中存在目标单词return endNode ! null endNode.isEnd;}public boolean startsWith(String prefix) {Node endNode searchPrefix(prefix);// 若终止节点不为空说明有目标前缀return endNode ! null;}/*** 搜索目标前缀并返回最后终止节点*/public Node searchPrefix(String prefix) {// 从根节点出发Node cur this.root;char[] charArr prefix.toCharArray();// 遍历搜索字符for(char ch: charArr) {MapCharacter, Node dict cur.dict;// 若词典节点为null则说明没有直接返回nullif(dict.get(ch) null) {return null;}// 指针下移继续向下搜索cur dict.get(ch);}// 最终返回终止节点return cur;}
}
回溯
回溯章节建议跟随【代码随想录-回溯】课程学习 真心推荐卡尔讲的很不错 回溯模板 void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}常规回溯题 与 二叉树回溯题的差别 二叉树的回溯整体上确实是回溯的思想大体思路也差不多。但在处理细节上还是有些不同的例如【剑指 Offer 34. 二叉树中和为某一值的路径】与【39. 组合总和】相比
二叉树要从根节点处理每次递归中处理的是当前节点而常规回溯题一般不处理根节点每次递归中处理的都是孩子节点而且是多孩子因此在处理细节上是有差异的二叉树递归代码
public void backtracking(TreeNode root, int target, ListInteger path) {if(root null) {return;}// 处理当前节点target - root.val;path.add(root.val);if(target 0 root.left null root.right null) {res.add(new ArrayList(path));}// 处理左右孩子节点backtracking(root.left, target, path);backtracking(root.right, target, path);// 状态重置target root.val;path.remove(path.size() - 1);
}常规回溯递归代码
public void backtracking(ListInteger path, int startIndex, int[] candidates, int target) {// 终止条件if(target 0) {res.add(new ArrayList(path));return;}// for循环处理孩子节点for(int istartIndex; icandidates.length; i) {// 剪枝因为我们事先已经为数组排好序了越往后数字越大如果当前数字都已经减到负数了那后面的就没必要在判断了if(target - candidates[i] 0) {break;}target - candidates[i];path.add(candidates[i]);backtracking(path, i, candidates, target);// 状态重置target candidates[i];path.remove(path.size() - 1); }
}17. 电话号码的字母组合
【17. 电话号码的字母组合】 分析 套用上面的模板即可不细讲了
// 删除最后一个字符
sb.deleteCharAt(sb.length() - 1)代码 class Solution {private ListString res new ArrayList();StringBuilder path new StringBuilder();private String[] letters { ,*,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};public ListString letterCombinations(String digits) {if (digits.length() 0) {return new ArrayList();}StringBuilder path new StringBuilder();backtracking(0, digits);return res;}public void backtracking(int level, String digits) {// 不合法终止条件if(path.length() digits.length()) { // 此处也可以写成 level digits.length() 来做为终止条件res.add(path.toString()); // 添加到结果集return;}// 找到对应的候选集int index digits.charAt(level) - 0;char[] chars letters[index].toCharArray();// 因为每层的可选集都是独立的因此for循环都可以从0开始不会重复for(int i0; ichars.length; i) {path.append(chars[i]);backtracking(level 1, digits);path.deleteCharAt(path.length() - 1); // 状态重置}}
}77. 组合
【77. 组合】 分析 参考视频【带你学透回溯算法-组合问题对应力扣题目77.组合| 回溯法精讲】
可以将这题与上题对比来看 相同点
都是组合问题路径组合不能重复例如234 和 324就是重复的
不同点
上一题每层的可选集都不一样。例如输入“23”第一层的可选集是“a、b、c”第二层的可选集是“d、e、f”因此我们在遍历每层的可选集时都可以从下标0开始遍历因为是独立的数据集所以不会重复而该题每层的可选集都是一样都是[1,n]但是我们要保证路径元素不能重复所以在处理for循环时就要注意。下面是模拟回溯的多叉树状态从左往右、从上到下 可选集的返回都会缩小1。这时我们使用startIndex来记录下一层搜索的起始位置for循环的初始下标
回溯的过程的多叉树
核心代码如下 for(int istartIndex; in; i)从startIndex开始遍历保证组合路径不会重复 backtracking(temp, i 1, n, k)使用i1保证组合中的元素不会重复
// 从左往右看 因为i本身会自增且递归函数为backtracking(temp, i 1, n, k)参数2就是startIndex因此越往右可选范围越小
// 越往下也是一样调用backtracking(temp, i 1, n, k)越往下可选集范围越小
for(int istartIndex; in; i) {temp.add(i);backtracking(temp, i 1, n, k); // 核心temp.remove(temp.size() - 1);
}代码 class Solution {ListListInteger res new ArrayList();ListInteger path new ArrayList();public ListListInteger combine(int n, int k) {backtracking(1, n, k);return res;}public void backtracking(int startIndex, int n, int k) {// 终止条件if(path.size() k) {res.add(new ArrayList(path));return;}// 遍历 [startIndex, n]for(int istartIndex; in; i) {path.add(i); // 操作当前节点backtracking(i 1, n, k); // 这里是i1不要错写成startIndex1了path.remove(path.size() - 1); // 状态重置}}
}39. 组合总和
【39. 组合总和】 分析 组合问题因此我们也需要一个 startIndex 变量作为遍历的起始位置。这样做是为了避免出现重复的组合例如234 和 324就是重复的
但与上题不同在于该题可以允许组合中的元素重复因此在调用递归方法时startIndex就没必要1了
剪枝为了提高效率我们事先对数组进行排序越往后数字越大如果加到某个节点已经超过了目标值那后面的就没必要在判断了因为加起来和会更大 代码 class Solution {ListListInteger res new ArrayList();ListInteger path new ArrayList();public ListListInteger combinationSum(int[] candidates, int target) {// 排序 后后序剪枝做准备Arrays.sort(candidates);backtracking(0, candidates, target);return res;}public void backtracking(int startIndex, int[] candidates, int target) {// 终止条件if(target 0) {res.add(new ArrayList(path));return;}for(int istartIndex; icandidates.length; i) {// 剪枝因为我们事先已经为数组排好序了越往后数字越大如果当前数字都已经减到负数了那后面的就没必要在判断了if(target - candidates[i] 0) {break;}target - candidates[i];path.add(candidates[i]);backtracking(i, candidates, target);// 状态重置target candidates[i];path.remove(path.size() - 1); }}
}剑指 Offer 34. 二叉树中和为某一值的路径
【剑指 Offer 34. 二叉树中和为某一值的路径】 分析 二叉树的回溯整体上确实是回溯的思想大体思路也差不多。但在处理细节上还是有些不同的例如和前面组合问题相比
二叉树要从根节点处理每次递归中处理的是当前节点而常规回溯题一般不处理根节点每次递归中处理的都是孩子节点而且是多孩子因此在处理细节上是有差异的二叉树代码
public void backtracking(TreeNode root, int target, ListInteger path) {if(root null) {return;}// 处理当前节点target - root.val;path.add(root.val);if(target 0 root.left null root.right null) {res.add(new ArrayList(path));}// 处理左右孩子节点backtracking(root.left, target, path);backtracking(root.right, target, path);// 状态重置target root.val;path.remove(path.size() - 1);
}常规回溯代码
public void backtracking(ListInteger path, int startIndex, int[] candidates, int target) {// 终止条件if(target 0) {res.add(new ArrayList(path));return;}// for循环处理孩子节点for(int istartIndex; icandidates.length; i) {// 剪枝因为我们事先已经为数组排好序了越往后数字越大如果当前数字都已经减到负数了那后面的就没必要在判断了if(target - candidates[i] 0) {break;}target - candidates[i];path.add(candidates[i]);backtracking(path, i, candidates, target);// 状态重置target candidates[i];path.remove(path.size() - 1); }
}代码 class Solution {private ListListInteger res new ArrayList();public ListListInteger pathSum(TreeNode root, int target) {ListInteger path new ArrayList();backtracking(root, target, path);return res;}public void backtracking(TreeNode root, int target, ListInteger path) {if(root null) {return;}// 处理当前节点target - root.val;path.add(root.val);if(target 0 root.left null root.right null) {res.add(new ArrayList(path));}// 递归调用左右子节点backtracking(root.left, target, path);backtracking(root.right, target, path);// 状态重置target root.val;path.remove(path.size() - 1);}
}46. 全排列
【46. 全排列】 分析 因为不是组合问题所以我们每层遍历时都不用缩小可选的范围只需要判断当前路径中是否存在该元素即可 代码 class Solution {ListListInteger res new ArrayList();ListInteger path new ArrayList();public ListListInteger permute(int[] nums) {backtracking(nums);return res;}public void backtracking(int[] nums) {if(path.size() nums.length) {res.add(new ArrayList(path));return;}for(int i0; inums.length; i) {// 若存在重复元素则不添加if(path.contains(nums[i])) {continue;}path.add(nums[i]);backtracking(nums);path.remove(path.size() -1);}}
}47. 全排列 II
【47. 全排列 II】 分析 与上题不同该题中提到序列中可能有重复的元素因此我们要考虑对排列去重 整体逻辑可参考视频【代码随想录回溯算法求解全排列如何去重| LeetCode47.全排列 II】 去重逻辑可参考视频【代码随想录回溯算法中的去重树层去重树枝去重你弄清楚了没| LeetCode:40.组合总和II】
我们使用一个used数组来表示某个下标的元素在当前路径中是否被使用过? 核心代码
/*** 树层去重操作 当前前元素 与 前一个元素相同且前一个元素在当前路径未使用过* 树层去重arr[i] arr[i-1] used[i-1] 0* 树枝去重arr[i] arr[i-1] used[i-1] 1*/
if(i 0 arr[i] arr[i-1] used[i-1] 0) {continue;
}代码 class Solution {ListListInteger res new ArrayList();ListInteger path new ArrayList();public ListListInteger permuteUnique(int[] nums) {int[] used new int[nums.length];// 对元素排序方便去重处理Arrays.sort(nums);backtracking(nums, used);return res;}public void backtracking(int[] nums, int[] used) {if(path.size() nums.length) {// 错误写法res.add(path);// 正确写法res.add(new ArrayList(path));res.add(new ArrayList(path));return;}for(int i0; inums.length; i) {// 【去重处理】若树层重复则直接跳过if(i 0 nums[i-1] nums[i] used[i-1] 0) {continue;}// 已使用过则跳过if(used[i] 1) {continue;}path.add(nums[i]);used[i] 1;backtracking(nums, used);used[i] 0;path.remove(path.size() - 1);}}
}78. 子集
【78. 子集】 分析 其实【子集】问题本身就是【组合】问题。 例如求[1,2,3] 的子集其实就是求 长度为0、长度为1、长度为2、长度为3 的组合的并集 长度为0的组合[] 长度为1的组合[1]、[2]、[3] 长度为2的组合[1,2]、[1,3]、[2,3] 长度为3的组合[1,2,3]
代码不同点 【组合】问题叶子节点收获结果 【子集】问题每个节点都是结果
参考视频【回溯算法解决子集问题树上节点都是目标集和 | LeetCode78.子集】 代码 class Solution {ListListInteger res new ArrayList();ListInteger path new ArrayList();public ListListInteger subsets(int[] nums) {backtracking(0, nums);return res;}public void backtracking(int startIndex, int[] nums) {// 每个节点都是结果res.add(new ArrayList(path));for(int istartIndex; inums.length; i) {path.add(nums[i]);backtracking(i 1, nums);path.remove(path.size() - 1);}}
}51. N 皇后
【51. N 皇后】 分析 参考视频【这就是传说中的N皇后 回溯算法安排| LeetCode51.N皇后】 参考题解51. N-Queens:【回溯法经典问题】详解
用一个二维数组chessBoard来记录棋盘的状态每往下深入一行然后遍历各个列判断 当前点chessBoard[row][col]是否有效是否有效判断逻辑判断当前点 左上方、正上方、右上方 是否有皇后若存在则说明不符合规则 是无效的就返回false 代码 class Solution {ListListString res new ArrayList();public ListListString solveNQueens(int n) {char[][] chessBoard new char[n][n];// 初始化棋盘默认都是.for(char[] chars: chessBoard) {Arrays.fill(chars, .);}backtracking(chessBoard, n, 0);return res;}public void backtracking(char[][] chessBoard, int n, int row) {if(row n) {res.add(arrayToList(chessBoard));return;}for(int col0; coln; col) {if(isValid(chessBoard, n, row, col)) {chessBoard[row][col] Q;backtracking(chessBoard, n, row 1);chessBoard[row][col] .;}}}/*** 检查 chessBoard[row][col] 的 “正上方”、“左上方”、“右上方” 是否有皇后* 存在皇后说明chessBoard[row][col]是无效的返回false不存在说明chessBoard[row][col]是有效的返回true*/public boolean isValid(char[][] chessBoard, int n, int row, int col) {// 检查上方 是否有皇后for(int i0; irow; i) {if(chessBoard[i][col] Q) {return false;}}// 检查左上方 是否有皇后for(int irow-1, jcol-1; i0 j0; i--, j--) { // 往左上角移动if(chessBoard[i][j] Q) {return false;}}// 检查右上方 是否有皇后for(int irow-1, jcol1; i0 jn; i--, j) { // 往右上角移动if(chessBoard[i][j] Q) {return false;}}return true;}/*** 二维字符数组 - 字符串集合*/public List arrayToList(char[][] chessBoard) {ListString list new ArrayList();for(char[] chars: chessBoard) {list.add(new String(chars));}return list;}
}22. 括号生成
【22. 括号生成】 分析 参考题解【虽然不是最秀的但至少能让你看得懂】
还是常规的回溯法一样的配方
该题 可以看做 从 数组 [ ( , ) ] 中进行2*n次排列该数组仅有 左括号 和 有括号 2个元素 在此树的基础上我们要删除掉不符合的路径进行剪枝
需要满足一定条件才能拼接到path路径中剪枝 充要条件左括号数量 n 并且 右括号数量 左括号数量代码left n right left 代码 class Solution {ListString res new ArrayList();StringBuilder path new StringBuilder();public ListString generateParenthesis(int n) {backtracking(0, 0, n);return res;}/*** left、right 分别指左右括号的数量*/public void backtracking(int left, int right, int n) {// 终止条件if(path.length() n * 2) {res.add(path.toString());return;}// 递归处理子孩子因为只有左、右两种括号因此就只有两个孩子if(isValid(left1, right, n)) { // 追加一个“左括号”path.append(();backtracking(left 1, right, n);path.deleteCharAt(path.length() - 1);}if(isValid(left, right1, n)) { // 追加一个“右括号”path.append());backtracking(left, right 1, n);path.deleteCharAt(path.length() - 1);}}/*** 判断是否有效有两个充要条件* 1、leftCount 必须 小于等于 n* 2、leftCount 必须 大于等于 rightCount*/public boolean isValid(int leftCount, int rightCount, int n) {return leftCount n leftCount rightCount;}
}131. 分割回文串
【131. 分割回文串】 分析 该题难点是如何遍历所有的切割方式难点 解决的上面的问题后接下来就是判断切割的字符串是否是回文的判断回文是比较简单的
其实切割方式的遍历类似于组合问题。下面是回溯对应的树形结构
详细题解可参考【「代码随想录」带你学透回溯算法131. 分割回文串】 视频讲解可参考【带你学透回溯算法-分割回文串对应力扣题目131.分割回文串| 回溯法精讲】
该题理解起来还是比较复杂的可以多看几遍视频和题解 代码 初始版本
class Solution {ListListString res new ArrayList();ListString path new ArrayList();public ListListString partition(String s) {backtracking(s, 0);return res;}public void backtracking(String s, int startIndex) {// 分割线到达最后说明已经遍历完一种切割方式if(startIndex s.length()) {res.add(new ArrayList(path));return;}for(int istartIndex; is.length(); i) {// 只有满足[startIndex, i]是回文串才能添加到path中if(isPalindrome(s, startIndex, i)) {String str s.substring(startIndex, i 1);path.add(str);} else {continue;}// 递归继续找下一个分割线backtracking(s, i 1);path.remove(path.size() - 1);}}// 判断是否回文public boolean isPalindrome(String s, int left, int right) {char[] charArr s.toCharArray();while(left right) {if(charArr[left] ! charArr[right]) {return false;}left;right--;}return true;}
}优化方法 将【[i,j]段是否回文】的状态预存在二维数组中
class Solution {ListListString res new ArrayList();ListString path new ArrayList();boolean[][] isPalindrome;public ListListString partition(String s) {int len s.length();isPalindrome new boolean[len][len];// 将[i,j]段是否回文的状态预先存到二维数组-isPalindrome中prepare(s);// 回溯遍历所有切割情况并填充结果集backtracking(s, 0);return res;}public void backtracking(String s, int startIndex) {// 分割线到达最后说明已经遍历完一种切割方式if(startIndex s.length()) {res.add(new ArrayList(path));return;}for(int istartIndex; is.length(); i) {// 只有满足[startIndex, i]是回文串才能添加到path中if(isPalindrome[startIndex][i]) {String str s.substring(startIndex, i 1);path.add(str);} else {continue;}// 递归继续找下一个分割线backtracking(s, i 1);path.remove(path.size() - 1);}}// 预处理判断 [i,j]是否回文将判断结果预存在isPalindrome数组中public void prepare(String s) {for(int i0; is.length(); i) {extendFromCenter(s, i, i); // abaextendFromCenter(s, i, i 1); // abba}}// 中心扩展法public void extendFromCenter(String s, int left, int right) {char[] charArr s.toCharArray();int len charArr.length;while(left 0 right len charArr[left] charArr[right]) {// 满足回文条件打标记isPalindrome[left][right] true;// 向外扩展left--;right;}}
}二分查找 模板 参考视频【最清楚的二分查找LeetCode34题在排序数组中查找元素的第一个和最后一】
参考文章【二分查找算法及其变种详解】 正常搜索目标值
public int binarySearch(int[] nums, int target) {int left 0;int right nums.length - 1;while(left right) {int mid left ((right - left) 1);if(nums[mid] target) {return mid;} else if (nums[mid] target) {left mid 1;} else {right mid - 1;}}return result;
}变种一搜索值为target的第一个下标
/*** 找第一个目标值*/
public int binarySearchFirst(int[] nums, int target) {int left 0;int right nums.length - 1;while(left right) {int mid left ((right - left) 1);if(nums[mid] target) {// 下面两种情况都说明是最左侧的targetif (mid 0 || nums[mid - 1] ! target) return mid;// 否则继续向左半区间查找right mid - 1;} else if (nums[mid] target) {left mid 1;} else {right mid - 1;}}return -1;
}变种二搜索值为target的最后一个下标
/*** 找最后一个目标值*/
public int binarySearchLast(int[] nums, int target) {int left 0;int right nums.length - 1;while(left right) {int mid left ((right - left) 1);if(nums[mid] target) {// 下面两种情况都说明是最右侧的targetif (mid nums.length-1 || nums[mid 1] ! target) return mid;// 否则继续向右半区间查找left mid 1;} else if (nums[mid] target) {left mid 1;} else {right mid - 1;}}return -1;
}变种三查找第一个大于等于 给定值的元素
/*** 第一个 target 的下标*/
public int binarySearch3(int[] nums, int target) {int left 0;int right nums.length - 1;while(left right) {int mid left ((right - left) 1);if(nums[mid] target) {if(mid 0 || nums[mid - 1] target)return mid;right mid - 1;} else {left mid 1;}}return -1;
}变种四查找最后一个小于等于给定值的元素
/*** 最后一个 target 的下标*/
public int binarySearch4(int[] nums, int target) {int left 0;int right nums.length - 1;while(left right) {int mid left ((right - left) 1);if(nums[mid] target) {if(mid nums.length-1 || nums[mid 1] target)return mid;left mid 1;} else {right mid - 1;}}return -1;
}变种五查找第一个大于 给定值的元素
/*** 第一个 target 的下标*/
public int binarySearch5(int[] nums, int target) {int left 0;int right nums.length - 1;while(left right) {int mid left ((right - left) 1);if(nums[mid] target) {if(mid 0 || nums[mid - 1] target)return mid;right mid - 1;} else {left mid 1;}}return -1;
}变种六查找最后一个小于给定值的元素
/*** 最后一个 target 的下标*/
public int binarySearch6(int[] nums, int target) {int left 0;int right nums.length - 1;while(left right) {int mid left ((right - left) 1);if(nums[mid] target) {if(mid nums.length-1 || nums[mid 1] target)return mid;left mid 1;} else {right mid - 1;}}return -1;
}总结注意点 【注意点一】若[left,right] 对应 [0,length-1]当代码中需要mid与相邻元素比较时要和nums[mid1]比较如果和num[mid-1]比较则nums[mid-1]可能会下标越界
若数组只有一个元素其实 nums[mid1]也会越界。因此只有一个元素时要单独当做边界条件处理若数组只有两个元素则mid (01)/2 0那么nums[mid-1]就会越界nums[mid1]则不会越界
35. 搜索插入位置
【35. 搜索插入位置】 分析 该题是个模板题
/*** 二分查找*/
public int binarySearch(int[] nums, int target) {int left 0;int right nums.length - 1;while(left right) {int mid (left right) 1; // 等价于 (left right) / 2if(nums[mid] target) {return mid;}if(nums[mid] target) {left mid 1;} else {right mid - 1;}}return left;
}代码 class Solution {public int searchInsert(int[] nums, int target) {return binarySearch(nums, target);}/*** 二分查找*/public int binarySearch(int[] nums, int target) {int left 0;int right nums.length - 1;while(left right) {int mid (left right) 1; // 等价于 (left right) / 2if(nums[mid] target) {return mid;}if(nums[mid] target) {left mid 1;} else {right mid - 1;}}return left;}
}74. 搜索二维矩阵
【74. 搜索二维矩阵】 分析 首先题中说明 每一行都按照从左到右递增的顺序排序 每一列都按照从上到下递增的顺序排序。 那么一看数据是有序的 那么我们肯定第一时间想到二分查找法。但在着整个二维数组中好像没法直接使用二分查找但是我们可以使用二分查找的思想。
二分查找思想 每一轮比较首先获取一个特殊值然后让目标值与该值进行比较每次比较都能排除一些数据进而缩小搜索的范围。
解决该题我们用的方法和二叉查找法类似也是每次都取一个特殊值与目标值比较每轮都排除一部分数据进而缩小数据的查找范围 B站上讲解视频 https://www.bilibili.com/video/BV12J411i7A6
https://www.bilibili.com/video/BV1Tt411F7YD?spm_id_from333.999.0.0 代码 class Solution {public boolean searchMatrix(int[][] array, int target) {// 套路模板 先判空if(array.length 0) return false;// row表示有几行,col表示有几列。int row array.length;int col array[0].length;// 我们取右上角的值int x 0; int y col - 1;// 不断排除一列或者一行不断缩小范围while(x row-1 y 0) {if(target array[x][y]) {// 排除头一行的数据x;}else if (target array[x][y]) {// 排除后一列的数据y--;}else {return true;}}// 若判处完所有数据仍没有找目标值 该值不存在return false;}
}34. 在排序数组中查找元素的第一个和最后一个位置
【34. 在排序数组中查找元素的第一个和最后一个位置】 分析 分别获取 第一个目标值 和 最后一个目标值 代码 class Solution {public int[] searchRange(int[] nums, int target) {int[] res new int[2];res[0] binarySearchFirst(nums, target);res[1] binarySearchLast(nums, target);return res;}public int binarySearchFirst(int[] nums, int target) {int left 0;int right nums.length - 1;while(left right) {int mid left ((right - left) 1);if(nums[mid] target) {// 下面两种情况都说明是最左侧的targetif (mid 0 || nums[mid - 1] ! target) return mid;// 否则继续向左半区间查找right mid - 1;} else if (nums[mid] target) {left mid 1;} else {right mid - 1;}}return -1;}/*** 找最后一个目标值*/public int binarySearchLast(int[] nums, int target) {int left 0;int right nums.length - 1;while(left right) {int mid left ((right - left) 1);if(nums[mid] target) {// 下面两种情况都说明是最右侧的targetif (mid nums.length-1 || nums[mid 1] ! target) return mid;// 否则继续向右半区间查找left mid 1;} else if (nums[mid] target) {left mid 1;} else {right mid - 1;}}return -1;}
}JZ11 旋转数组的最小数字存在重复值
【JZ11 旋转数组的最小数字】 分析 参考视频【剑指Offer.6.旋转数组的最小数字】 序列可被分为两部分递增序列 第一部分的最小值 第二部分的最最大值
我们每次都取中间下标的值与左右侧的值进行比较
若 min下标的值 最右侧的值 则说明 min下标处于第一部分而最小值在第二部分的范围内因此我们就可以排除 min及左侧的所有数据了最小值在 [min1,right] 的范围内
若 min下标的值 最右侧的值 则说明min下标所处第二部分那么最小值在 [left,min]的范围内
若min下标的值 最右侧的值而对于这种情况又一种特殊情况如下图 直接说结论若 min下标的值 最右侧的值 则直接 right-- 即可右指针后移
while循环的条件是 left right当left right时其实就只有一个数据了该数据就是最小最终直接返回array[left] 或者 array[right] 代码 import java.util.ArrayList;
public class Solution {public int minNumberInRotateArray(int [] array) {// 套路模板先判空if(array.length 0) return -1;return erfen(array, 0, array.length-1);}public int erfen(int[] array, int left, int right) {int min 0;while(left right) { // 因为当leftright时其实就是我们要找的目标值因此这里条件是leftrightmin (left right) 1; // 等同于(leftright)/2// 因为没有目标值因此每次都是 中间下标值 与 最右侧的值进行比较if(array[min] array[right]) { // 此情况说明min处于 第一部分的范围left min 1;}else if(array[min] array[right]) { // 此情况说明min处于 第二部分范围 因为可能是最小值 因此right不再是min1right min;}else { // 若min 等于 最右侧的值 直接right往左移一步即可right--right--;}}// 最后 leftright 就是我们要找的最小值return array[left];}
}153. 寻找旋转排序数组中的最小值不包含重复值
【153. 寻找旋转排序数组中的最小值】 分析 与上题不同该题数组元素是不重复的因此判断逻辑中不需要判断 nums[mid] nums[right]这种情况 代码 class Solution {public int findMin(int[] nums) {int left 0;int right nums.length - 1;while(left right) {int mid (left right) 1;if(nums[mid] nums[right]) {left mid 1;} else {right mid;}}return nums[left];}
}33. 搜索旋转排序数组
【33. 搜索旋转排序数组】 分析 * 假设turningPointIdx为转折点下标此时我们知道这两段递增序列范围若数组本身就没有翻转则还是一个段[0, nums.length-1]分别是
* 第一段[0,turningPointIdx-1]
* 第二段[turningPointIdx, nums.length-1]
* 第一段元素 第二段元素一共分三步
找到转折点下标判断target所在的标有序区间 turningPointIdx 0说明nums本身就是有序的并没有翻转。则target还在[0, nums.length-1]内target nums[0]说明target在[0,turningPointIdx-1]target nums[0]说明target在[turningPointIdx, nums.length-1] 在有序区间内进行二分查找 代码 class Solution {/*** 假设turningPointIdx为转折点下标此时我们知道这两段递增序列范围若数组本身就没有翻转则还是一个段[0, nums.length-1]分别是* 第一段[0,turningPointIdx-1]* 第二段[turningPointIdx, nums.length-1]* 第一段元素 第二段元素*/public int search(int[] nums, int target) {// 【一、找到转折点下标】int turningPointIdx getTurningPoint(nums);// 【二、target与nums[0]比较判断target在 第一段 还是 第二段】// turningPointIdx 0说明nums本身就是有序的并没有翻转int left, right;if(turningPointIdx 0) { left 0;right nums.length - 1;} else if (target nums[0]) {// target在第一段left 0;right turningPointIdx - 1;} else {// target在第二段left turningPointIdx;right nums.length - 1;}// 【三、在有序范围内进行二分查找】return binarySearch(nums, left, right, target);}/*** 寻找旋转点的下标就是找到转折数组的最小值* 若没有旋转本身是有序的则最终返回的下标肯定是0*/public int getTurningPoint(int[] nums) {int left 0;int right nums.length - 1;while(left right) {int mid (left right) 1;if(nums[mid] nums[right]) {left mid 1;} else {right mid;}}return left;}/*** 在有序数组中进行二分查找*/public int binarySearch(int[] nums, int left, int right, int target) {while(left right) {int mid (left right) 1;if(nums[mid] target) {return mid;}if(nums[mid] target) {right mid - 1;} else {left mid 1;}}return -1;}
}栈
20. 有效的括号
【20. 有效的括号】 分析 不算太难哈直接看代码 代码 class Solution {public boolean isValid(String s) {char[] charArr s.toCharArray();StackCharacter stack new Stack();for(char ch: charArr) {if(ch () {stack.push());} else if (ch {) {stack.push(});} else if (ch [) {stack.push(]);} else {if(stack.isEmpty() || ch ! stack.pop()) {return false;}}}return stack.isEmpty();}
}155. 最小栈
【155. 最小栈】 分析 解题步骤 为了解决要求栈的最小值而且要保证时间复杂度较低的要求我们需要还需要一个栈区存某一状态下的最小值。因此 这里一共使用两个栈空间一个栈用于存放普通数据另一个则用于存放最小值数据
// 该栈就是正常的栈添加什么数据就压入什么数据
StackInteger normalStack new Stack();
// 该栈存入的是 相对于normalStack来说 某一状态状态可以理解为栈的大小下的最小值栈顶存最小值
StackInteger minStack new Stack();push方法
首先数据存入到normalStack 中。紧接着该存最小值了。如果minStack是空的那么直接将插入值压入minStack即可。如果minStack不为空那么就取出栈顶元素前个状态的最小值与插入值进行比较如果插入值更小就将插入值压入minStack如果还是前一个状态的最小值更小 就将前个状态的最小值再压入minStack因为minStack的栈顶元素始终存的都是当前状态的最小值当前状态可以理解为normalStack当前的深度、大小
pop方法
normalStack.pop();
minStack.pop();两个栈弹出栈顶元素即可必须都要弹出要保证minStack与normalStack的状态一致
top方法
normalStack.peek();获取normalStack的栈顶元素即可
min方法
minStack.peek();获取minStack的栈顶元素即可 代码 class MinStack {// 实际存储数据的栈StackInteger stack new Stack();// 辅助栈存储当前状态的最小值StackInteger stack1 new Stack();public MinStack() {}public void push(int val) {stack.push(val);if(stack1.isEmpty()) {stack1.push(val);} else {stack1.push(Math.min(stack1.peek(), val));}}public void pop() {stack.pop();stack1.pop();}public int top() {return stack.peek();}public int getMin() {return stack1.peek();}
}739. 每日温度
【739. 每日温度】 分析 单调栈 维护 还未找到后面更高温度的日期
参考视频【单调栈你该了解的这里都讲了LeetCode:739.每日温度】 代码 class Solution {public int[] dailyTemperatures(int[] temperatures) {// 单调递增栈存放还未找到最近最高温度的日期存放的是下标StackInteger stack new Stack();// 存放待返回的结果int[] ret new int[temperatures.length]; stack.push(0);// 遍历温度表for(int i1; itemperatures.length; i) {int cur temperatures[i];// 若栈顶温度 小于 当天温度则说明当天温度 相对于 栈顶元素来说就是最近的更高温度while(!stack.isEmpty() temperatures[stack.peek()] cur) {// 已经为栈顶元素找到了 最近的最高温度则没必要放到栈中了int popedIdx stack.pop();// 记录天数差ret[popedIdx] i - popedIdx;}stack.push(i);}// 最后stack不为空则说明stack中的元素 后面找不到更高温度的日期while(!stack.isEmpty()) {int popedIdx stack.pop();ret[popedIdx] 0;}return ret;}
}42. 接雨水
【42. 接雨水】 分析 参考视频【单调栈经典来袭LeetCode:42.接雨水】
建议先做上一题
找到较低点的前一个较大值 和 后一个较大值则可以算较低点 相对于 前、后两个较大点所接的雨水横向求解水平求解维护一个单调栈存储下标若当前值大于栈顶元素则栈顶元素就是 较低点栈顶第二个元素就是较低点的前一个较大点当前值就是较低点的下一个较大点 代码 class Solution {public int trap(int[] height) {// stack维护一个单调栈非递减存储下标StackInteger stack new Stack();// 记录接雨水的总数int sum 0;for(int i0; iheight.length; i) {int cur height[i];// 若栈顶元素 小于 当前值则弹出表示当前值是栈顶元素的后续第一个较大者while(!stack.isEmpty() height[stack.peek()] cur) {// nextHeight下个较大值(下标)int nextHeight i;// mid就是中间点(下标)int mid stack.pop();if(stack.isEmpty()) { // 若为空 则直接跳过不处理break;}// preHeight:前一个较大值(下标)int preHeight stack.peek();// 高度差int diffY Math.min(height[preHeight], height[nextHeight]) - height[mid];// 宽度差int diffX nextHeight - preHeight - 1;// 面积累计sum diffX * diffY;}stack.push(i);}return sum;}
}堆
数组中的第K个最大元素
【数组中的第K个最大元素】 分析 方法一使用大小为k的小根堆 来维护最大的前k个数
先往小根堆中添加k个元素后序的元素都跟小根堆的堆顶元素最小值比较若大于 堆顶元素最小值则替换。否则不处理
方法二 利用快速排序的思想不断的构造轴点元素当轴点坐标为K时那么arr的topK就是最小的前K个数
可以参考【排序算法之快速排序】 代码 解法一
class Solution {public int findKthLargest(int[] nums, int k) {// 小根堆PriorityQueueInteger minHeap new PriorityQueue((a, b) - a - b);int len nums.length;for(int i0; ik; i) {minHeap.offer(nums[i]);}for(int ik; ilen; i) {if(nums[i] minHeap.peek()) {minHeap.poll();minHeap.offer(nums[i]);}}return minHeap.peek();}
}解法二
class Solution {public int findKthLargest(int[] nums, int k) {quickSort(nums, 0, nums.length - 1, k - 1);return nums[k - 1];}public void quickSort(int[] nums, int left, int right, int k) {if(left right) {return;}int povitIdx povit(nums, left, right);if(povitIdx k) {return;}if(povitIdx k) {quickSort(nums, povitIdx 1, right, k);} else {quickSort(nums, left, povitIdx - 1, k);}} public int povit(int[] nums, int left, int right) {int temp nums[left];while(left right) {while(left right nums[right] temp) {right--;} if(left right) {nums[left] nums[right];left;}while(left right nums[left] temp) {left;}if(left right) {nums[right] nums[left];}if(left right) {nums[left] temp; }}return left;}
}347. 前 K 个高频元素
【347. 前 K 个高频元素】 分析 其实本质上与上一题一样
首先使用map来存储各个数字出现的频率key为数字value为对应频率。使用小根堆来维护频率最大的k个数遍历map的所有key即数字并在小根堆中过滤 分析 class Solution {public int[] topKFrequent(int[] nums, int k) {// map用于维护nums中数字出现的频率MapInteger, Integer map new HashMap();for(int item: nums) {if(map.containsKey(item)) {map.put(item, map.get(item) 1);} else {map.put(item, 1);}}// 创建最小堆根据map中的频率比较PriorityQueueInteger minHeap new PriorityQueue((n1, n2) - map.get(n1) - map.get(n2));// 遍历map的key并从小根堆中过滤for(int key: map.keySet()) {if(minHeap.size() k) {minHeap.offer(key);} else {if(map.get(key) map.get(minHeap.peek())) {minHeap.poll();minHeap.offer(key);}}}// 将小根堆中的元素添加到结果集中int[] res new int[k];for(int i0; ik; i) {res[i] minHeap.poll();}return res;}
}295. 数据流的中位数
【295. 数据流的中位数】 分析 解题思路
B站上视频讲解https://www.bilibili.com/video/BV1J5411J7yj?spm_id_from333.788.top_right_bar_window_history.content.click
https://www.bilibili.com/video/BV1hi4y1b7z5?spm_id_from333.788.top_right_bar_window_history.content.click
有多种解法你可以使用插入排序的写法可以利用前面序列是有序的特性这种方式我不写了。
接下来说另一种用一个大根堆 和 一个小跟堆 来实现
左边的数据 使用 大根堆右边的数据 使用 小跟堆 其实这个图是有问题的。其实我们不能保证左边和右边的数据是递增有序的。 但是我们要保证
左侧大根堆的堆顶元素要满足两点 大于左侧的所有元素大根堆性质就是如此不需要我们来处理同时小于右侧的所有元素需要我们自己去维护这个关系 右侧小根堆的堆顶元素要满足两点 小于右侧的所有元素小根堆性质就是如此不需要我们来处理同时大于左侧的所有元素需要我们自己去维护这个关系 左右两侧数据数量要均衡我是这样处理的 当整体数量为偶数左侧个数 右侧个数当整体数量为奇数 右侧数量 左侧数量 相差1 左侧的元素 都比 右侧的元素小这样一来 大根堆堆顶就是中位数 或者 两个堆顶的平均值是中位数 代码 class MedianFinder {// 统计数据流的个数private int count;// 维护左侧的大根堆维护左侧序列PriorityQueueInteger maxHead new PriorityQueue(new ComparatorInteger() {Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1;}});// 维护右侧的小根堆维护右侧序列PriorityQueueInteger minHead new PriorityQueue();public MedianFinder() {}public void addNum(int num) {if(count % 2 0) { // 偶数/*** 最终添加在右侧序列* 1、首先将数据添加到左侧的大根堆* 2、然后将左侧的最大值添加到右侧的小根堆中最终元素数量增加的是右侧元素*//*** 其实1、2 两步可以理解为是一种【过滤操作】有两个目的* 目的1最终右侧序列新增* 目的2最终添加到右侧序列的元素 保证要 大于左侧的所有元素因此就有了 minHead.offer(maxHead.poll())操作*/maxHead.offer(num);minHead.offer(maxHead.poll()); // 最终添加在右侧序列} else { // 道理同上只是过滤的方向不一样minHead.offer(num);maxHead.offer(minHead.poll()); // 最终添加在左侧序列}count;}public double findMedian() {if(count 0) {return 0;}return count % 2 0 ? (maxHead.peek() minHead.peek()) / 2.0 : minHead.peek();}
}贪心算法
55. 跳跃游戏
【55. 跳跃游戏】 分析 参考视频【LeetCode_55_跳跃游戏】 代码 class Solution {public boolean canJump(int[] nums) {// 最远可到达的下标默认是0int farthestArrivalIndex 0;int len nums.length;for(int i0; ilen; i) {if(farthestArrivalIndex i) { // 说明不能到达i下标return false;}// 更新最远可到达的下标farthestArrivalIndex Math.max(farthestArrivalIndex, i nums[i]);}// 能走到这里说明能走完return true;}
}45. 跳跃游戏 II
【45. 跳跃游戏 II】 分析 参考题解【【跳跃游戏 II】别想那么多就挨着跳吧 II】 代码 class Solution {public int jump(int[] nums) {int len nums.length;if(len 1) { // 长度为1 则不用跳直接返回0return 0;}// 步数int step 1;// 【当前跳】 覆盖的范围int range nums[0];// 【下一跳】 能到达的最远下标。初始值给0int farthestArrivalIndex 0;for(int i1; ilen; i) {// 若【当前跳】范围超过 len-1 则直接返回stepif(range len - 1) {return step;}// 更新 【下一跳】的最远下标farthestArrivalIndex Math.max(farthestArrivalIndex, i nums[i]);// 若到达【当前跳】的范围边界则步数增加。新的开始更新【当前跳】的覆盖范围if(i range) {step;range farthestArrivalIndex;}}return step;}
}763. 划分字母区间
【763. 划分字母区间】 分析 参考视频讲解【贪心算法寻找最远的出现位置 LeetCode763.划分字母区间】 代码 class Solution {public ListInteger partitionLabels(String s) {ListInteger res new ArrayList();char[] charArr s.toCharArray();int len charArr.length;// 记录每个字符 最远的下标位置MapCharacter, Integer map new HashMap();for(int i0; ilen; i) {map.put(charArr[i], i);}// 记录当前段 的 起始位置int start 0;// 记录当前段 的 末尾位置int end 0;for(int i0; ilen; i) {char ch charArr[i];end Math.max(end, map.get(ch));if(i end) {res.add(end - start 1);start i 1;} }return res;}
}动态规划
70. 爬楼梯
【70. 爬楼梯】 分析 因为可以爬1级或者2级 因此最后一爬要么从n-1级台阶 要么从n-2级台阶 爬到n级因此 爬到n级台阶的爬法总和 爬到n-1级的爬法和 爬到n-2级的爬法和 。 dp[i]表示爬到i级台阶的爬法总和。 状态转移方程为 dp[i] dp[i-1] dp[i-2] 其实和斐波那契数列差不多 代码 class Solution {public int climbStairs(int n) {if(n 1) return 1;if(n 2) return 2;int[] dp new int[n1];dp[1] 1; dp[2] 2;for(int i3; in; i) {dp[i] dp[i-1] dp[i-2];}return dp[n];}
}118. 杨辉三角
【118. 杨辉三角】 分析 类似于 打印三角形数据。两层for循环进行打印。 代码更清晰 代码 class Solution {public ListListInteger generate(int numRows) {ListListInteger res new ArrayList();// 两层for循环 打印三角形for(int i0; inumRows; i) {ListInteger list new ArrayList();for(int j0; ji; j) {// 当j0 或者 ji说明是三角形的两个侧边直接赋值为1if(j 0 || j i) {list.add(1);continue;}// 拿到上一层的数值ListInteger upLine res.get(i-1);// 根据上一层数值计算当前值int val upLine.get(j - 1) upLine.get(j);list.add(val);}res.add(list);}return res;}
}322. 零钱兑换
【322. 零钱兑换】 分析 参考视频【腾讯二面笔试题~零钱兑换】
若【爬楼梯】的题改成 每次可爬coins[0]、coins[1] … coins[length-1]个台阶问最少跳多少次能跳到amount 其实就和这题一样了
若这题改成: 求兑换零钱的方法总数 其实就变成了【爬楼梯】的进阶版了
定义dp[n]为兑换n元钱最少需要的硬币数 dp[n]的状态 来源于 dp[n-coins[i]]因此
dp[n] min {dp[n] dp[n - coins[0]] 1dp[n] dp[n - coins[1]] 1dp[n] dp[n - coins[2]] 1...dp[n] dp[n - coins[length-1]] 1
}有点类似于【剑指 Offer 60. n个骰子的点数】这题 代码 class Solution {public int coinChange(int[] coins, int amount) {if(amount 0) {return 0;}/*** 零钱最小值是1因此amount最多换amount个硬币。* 为了考虑换不到零钱的情况我们这里初始值设置为amount1。最后dp[n] 和 amount1比较若仍等于amount1则说明n换不到零钱最终返回-1*/ // dp[n]定义兑换amount最少的兑换次数int[] dp new int[amount 1];Arrays.fill(dp, amount 1);// 当amount为0时则兑换方法为0dp[0] 0;// 遍历amount类似于遍历背包容量for(int i1; iamount; i) {// 遍历金币类似遍历物品for(int j0; jcoins.length; j) {// 若当前金币大于总钱数则直接continueif(coins[j] i) {continue;}// 算出新值1 dp[i - coins[j]]int newVal 1 dp[i - coins[j]];// 更新dp[i]的最小值dp[i] Math.min(newVal, dp[i]);}}return dp[amount] amount 1 ? -1 : dp[amount];}
}279. 完全平方数
【279. 完全平方数】 分析 该题其实与【322. 零钱兑换】基本一致。
整数n我们可以理解为总钱数1、4、9...等这些完全平方和我们可以理解为金币
不同点
完全平方和有11元的金币因此肯定能找到零钱该题我们不需要考虑找不到零钱的情况因此初始化dp都为n即可遍历完全平方和遍历金币是这样的(int j1; j*ji; j) 代码 class Solution {public int numSquares(int n) {int[] dp new int[n1];Arrays.fill(dp, n);dp[0] 0;for(int i1; in; i) {for(int j1; j*ji; j) {int newVal 1 dp[i - j*j];dp[i] Math.min(dp[i], newVal);}}return dp[n];}
}139. 单词拆分
【139. 单词拆分】 分析 类似于完全背包
整个字符串s可以看做是背包词典可看做是物品不过这个背包必须按照一定的顺序才能填充两层for循环。第一层遍历s长度遍历背包容量第二层遍历截取 j到i之间的字符串判断是否在词典中
步骤
dp[n]定义前n个字符组成的字符串是否能被wordDict拼接成功从1开始若 词典包含[j,i) 并且 dp[j]true 则说明[0,i)可被词典拼接
参考视频【动态规划之完全背包你的背包如何装满| LeetCode139.单词拆分】 代码 lass Solution {public boolean wordBreak(String s, ListString wordDict) {int len s.length();// dp[n]定义为前n个字符组成的字符串是否能被wordDict拼接成功从1开始boolean[] dp new boolean[len1];// dp[0]初始为true没什么特殊含义dp[0] true;for(int i1; ilen; i) {for(int j0; ji; j) {// 词典包含[j,i) 并且 dp[j] 为trueif(wordDict.contains(s.substring(j, i)) dp[j]) {dp[i] true;}}}return dp[len];}
}300. 最长递增子序列
【300. 最长递增子序列】 分析 参考视频https://www.bilibili.com/video/BV19b4y1R7K3?spm_id_from333.1007.top_right_bar_window_custom_collection.content.click 代码 class Solution {public int lengthOfLIS(int[] nums) {// 用于最大返回值int res 1;int len nums.length;// dp数组的含义 以nums[i]结尾的最长递增子序列的长度必须包含nums[i]int[] dp new int[len];Arrays.fill(dp, 1);for(int i1; ilen; i) { // 外层循环填dp[i]的值for(int j0; ji; j) { // 内层循环 遍历nums[i]前面的元素// 如果前面的值小于当前值 才能满足升序if(nums[j] nums[i]) {int newVal dp[j] 1; dp[i] Math.max(dp[i], newVal);}}// 从以[0,len)结尾的子序列中找到 最长的一个res Math.max(res, dp[i]);}/*** 错误写法return dp[len-1]* 原因最终的结果并非一定以len-1结尾的而是整个nums子序列因此最终结果并非dp[len-1]*/return res;}
}和最大子数组
【LCR 161. 连续天数的最高销售额】 分析 技巧像这种最大、最小 的 子数组、子序列我们在定义动态数组时大多数这样定义dp[i] 以下标i 值为结尾的 子数组 或者 子序列
遍历nums填写dp数组dp[i]以nums[i]结尾因为dp[i-1]可能小于零因此不能直接写成dp[i] dp[i-1]nums[i]而是 dp[i] Math.max(nums[i], dp[i-1] nums[i])同时全局更新最大和 maxSum Math.max(maxSum, dp[i]) 代码 class Solution {public int maxSales(int[] nums) {int maxSum nums[0];int len nums.length;int[] dp new int[len];dp[0] nums[0];for(int i1; ilen; i) {// 当 dp[i-1]小于0dp[i]nums[i]dp[i] Math.max(nums[i], dp[i-1] nums[i]);maxSum Math.max(maxSum, dp[i]);}return maxSum;}
}152. 乘积最大子数组
【152. 乘积最大子数组】 分析 参考视频【2022-每天一题-乘积最大子数组】
和【和最大子数组】类似。但又有所不同
求最大和 dp[i] Math.max(nums[i], dp[i-1] nums[i]) 即可求最大积 错误写法 dp[i] Math.max(nums[i], dp[i-1] * nums[i])。因为乘积有个特点若当前值为负数则乘以前面最小值才是最大乘积的。因此我们在处理时最大乘积、最小乘积 两种情况都要考虑到最终拿两种情况的最大值正确写法dpMax[i] Math.max(nums[i], Math.max(dpMax[i-1] * nums[i], dpMin[i-1] * nums[i])) 代码 class Solution {public int maxProduct(int[] nums) {int len nums.length;int[] dpMax new int[len];int[] dpMin new int[len];dpMax[0] nums[0]; dpMin[0] nums[0];int maxProduct nums[0];for(int i1; ilen; i) {// 因为不知道dp[i-1]的正负因此使用 Math.max(dpMax[i-1] * nums[i], dpMin[i-1] * nums[i]) 求二者最大dpMax[i] Math.max(nums[i], Math.max(dpMax[i-1] * nums[i], dpMin[i-1] * nums[i]));// 因为在求dpMax时需要用到 dpMin 因此我们要一直维护dpMin。维护方法同上dpMin[i] Math.min(nums[i], Math.min(dpMax[i-1] * nums[i], dpMin[i-1] * nums[i]));// 更新最大乘积maxProduct Math.max(maxProduct, dpMax[i]);}return maxProduct;}
}416. 分割等和子集
【416. 分割等和子集】 分析 原问题 等价于 判断是否存在nums的子集的和为sum/2子集元素不能重复sum为数组元素和且sum必须为偶数
元素不能重复因此属于0-1背包问题建议先学习【0-1背包问题】
代码备注比较详细可直接参考代码理解
参考视频 【带你学透0-1背包问题】 【带你学透0-1背包问题-之滚动数组】 【动态规划之背包问题这个包能装满吗| LeetCode416.分割等和子集】
参考题解 【「代码随想录」帮你把0-1背包学个通透附背包完整攻略】 代码 class Solution {public boolean canPartition(int[] nums) {int sum 0;for(int item: nums) {sum item;}// 若为奇数肯定不能等分if(sum % 2 ! 0) {return false;}int target sum / 2;// 判断是否存在nums的子集的和为target子集元素不能重复因此属于0-1背包问题// 背包容量为target// 物品集为nums/*** 一维数组写法滚动数组* 1、最外层遍历 物品* 2、最内层遍历 背包容量且必须为倒序*/int len nums.length;// dp[j]含义容量为j的背包最大能装的物品容量int[] dp new int[target 1];for(int i0; ilen; i) { // 遍历物品for(int jtarget; j0; j--) { // 遍历背包容量if(j nums[i]) { // 装不下 直接跳过break;}// 因为 “能装的物品容量” “背包容量” 所以这里取【最大值】最终通过 “dp[j] j” 巧妙地判断容量为j的背包是否能刚好装满 dp[j] Math.max(dp[j], dp[j - nums[i]] nums[i]);}}// 当 “容量为target的背包” 最大能装的 “物品总容量为target” 时 说明背包target恰好装满若dp[target] target则说明恰好装满return dp[target] target;}
}打家劫舍系列
198. 打家劫舍
【198. 打家劫舍】 分析 参考视频【动态规划偷不偷这个房间呢| LeetCode198.打家劫舍】
dp[n]定义为考虑第n间房所能偷的最大值 【但不一定要偷第n间只是考虑到第n间】n从0开始
对于第i间来说有两种选择1.偷第i间、2.不偷第i间 1、偷第i间房则不能偷第i-1间房屋也就不能考虑第n-1间房。则此时 value nums[i] dp[i-2]2、不偷第i间房则可以考虑偷第i-1间。则此时 value dp[i-1] 最终取两种情况的最大值因此 dp[i] Math.max(nums[i] dp[i-2], dp[i-1])
初始化dp 若只有一间房子肯定要偷第一间因此dp[0] nums[0] 有两个房间不能两个都偷因此偷最大值因此 dp[1] Math.max(nums[0], nums[1]) 代码 class Solution {public int rob(int[] nums) {int len nums.length;// 只有一个则肯定偷这一个if(len 1) {return nums[0];}// 有两个则偷最大值if(len 2) {return Math.max(nums[0], nums[1]);}// dp[n]定义为考虑第n间房所能偷的最大值 【但不一定要偷第n间只是考虑到第n间】n从0开始int[] dp new int[len];dp[0] nums[0];dp[1] Math.max(nums[0], nums[1]);for(int i2; ilen; i) {/*** 有两种选择1.偷第i间、2.不偷第i间* 1、偷第i间房则不能偷第i-1间房屋也就不能考虑第n-1间房。则此时 value nums[i] dp[i-2]* 2、不偷第i间房则可以考虑偷第i-1间。则此时 value dp[i-1]* 最终取两种情况的最大值因此 dp[i] Math.max(nums[i] dp[i-2], dp[i-1])*/dp[i] Math.max(nums[i] dp[i-2], dp[i-1]);}return dp[len-1];}
}213. 打家劫舍 II
【213. 打家劫舍 II】 分析 环状排列 意味着第一个房子和最后一个房子中 只能选择一个偷窃要么不考虑第一个要么不考虑最后一个因此可以把此 环状排列房间 问题约化为 两个 单排排列房间 子问题
不考虑第一个房子数组范围[1, len)不考虑最后一个房子数组范围[0, len-1)
最终求两种情况的最大值最优解 代码 class Solution {public int rob(int[] nums) {int len nums.length;if(len 1) {return nums[0];}/*** 因为是环形的因此第一个和最后一个不能同时偷。所以我们分成两种情况* 1、不偷第一个* 2、不偷最后一个*/// 情况一int robCase1 myRob(Arrays.copyOfRange(nums, 1, len));// 情况二int robCase2 myRob(Arrays.copyOfRange(nums, 0, len - 1));// 取最大值return Math.max(robCase1, robCase2);}/*** 打家劫舍1*/public int myRob(int[] nums) {int len nums.length;if(len 1) {return nums[0];}int[] dp new int[len];dp[0] nums[0];dp[1] Math.max(nums[0], nums[1]);for(int i2; ilen; i) {dp[i] Math.max(dp[i-1], dp[i-2] nums[i]);}return dp[len-1];}
}337. 打家劫舍 III
【337. 打家劫舍 III】 分析 参考视频讲解【动态规划房间连成树了偷不偷呢| LeetCode337.打家劫舍3】 代码 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public int rob(TreeNode root) {int[] res robTree(root);return Math.max(res[0], res[1]);}public int[] robTree(TreeNode root) {// res[0]不偷当前节点的最优值// res[1]偷当前节点的最优值int[] res new int[2];if(root null) {// 节点为null时res[0]、res[1]均为0return res;}int[] left robTree(root.left);int[] right robTree(root.right);// 不偷当前节点则可以考虑孩子节点。至于到底偷不偷一定是选一个最大的res[0] Math.max(left[0], left[1]) Math.max(right[0], right[1]);// 偷当前节点不可以偷孩子节点res[1] root.val left[0] right[0];return res;}
}多维动态规划
62. 不同路径
【62. 不同路径】 分析 有点像【爬台阶】到达某点的路径 到达上面的路径 到达左边的路径 二维版的【爬台阶】 代码 class Solution {public int uniquePaths(int m, int n) {int[][] dp new int[m][n];// 初始化上边界for(int i0; in; i) {dp[0][i] 1;}// 初始化下边界for(int j0; jm; j) {dp[j][0] 1;}for(int i1; im; i) {for(int j1; jn; j) {dp[i][j] dp[i-1][j] dp[i][j-1];}}return dp[m-1][n-1];}
}63. 不同路径 II
【63. 不同路径 II】 分析 有点像【爬台阶】到达某点的路径 到达上面的路径 到达左边的路径 不同点
该题是二维的存在障碍物若某点是障碍物则到达该点的路径为0初始化边界时要注意若中间遇到障碍物则后序的点不可能再被到达因此dp为0 代码 class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m obstacleGrid.length;int n obstacleGrid[0].length;int[][] dp new int[m][n];/*** 初始化第一行。* 只能 → 从左到右因此如果中遇见障碍物后面就走不到了因此obstacleGrid[0][i]0写在for循环的条件中若不满足则终止for循环* 那么后面的则不能被设置为1最终就是0表示到达该点的路径为0*/for(int i0; in obstacleGrid[0][i]0; i) {// 等于0则说明不是障碍物可以走dp[0][i] 1;}// 初始化第一列。只能↓ 从上到下同上for(int i0; im obstacleGrid[i][0]0; i) {// 等于0则说明不是障碍物可以走dp[i][0] 1;}for(int i1; im; i) {for(int j1; jn; j) {// 只有不是障碍物才能到达该点if(obstacleGrid[i][j] 0) {dp[i][j] dp[i][j-1] dp[i-1][j];}}}return dp[m-1][n-1];}
}初始化边界时的错误写法
// 初始化第一行
for(int i0; in; i) {// 等于0则说明不是障碍物可以走if(obstacleGrid[0][i] 0) {dp[0][i] 1;}
}
// 初始化第一列
for(int i0; in; i) {// 等于0则说明不是障碍物可以走if(obstacleGrid[i][0] 0) {dp[i][0] 1;}
}64. 最小路径和
【64. 最小路径和】 分析 与【剑指 Offer 47. 礼物的最大价值】几乎一模一样一个是求最大值一个是求最小值
要想 到达某个点的路径是最优的 那么到达这个点的上一步的路径一定也是最优的这是一道典型的动态规划问题状态转移方程为dp[i][j] min(dp[i-1][j],dp[i][j-1]) grid[i][j]步骤遍历二维数组填表 代码 class Solution {public int minPathSum(int[][] grid) {int m grid.length;int n grid[0].length;int[][] dp new int[m][n];// 起点初始化为 grid[0][0]dp[0][0] grid[0][0];// 初始化第一行for(int i1; in; i) {dp[0][i] dp[0][i-1] grid[0][i];}// 初始化第一列for(int i1; im; i) {dp[i][0] dp[i-1][0] grid[i][0];}for(int i1; im; i) {for(int j1; jn; j) {dp[i][j] Math.min(dp[i][j-1], dp[i-1][j]) grid[i][j];}}return dp[m-1][n-1];}
}5. 最长回文子串中心扩展法非动态规划解法
【最长回文子串】
解法一暴力 - 遍历所有字串
建议先做第9题【9. 回文数】
代码
class Solution {public String longestPalindrome(String s) {String longestPalindrome ;// 遍历所有的子串若长度比longestPalindrome长 且 是回文串则更新longestPalindromefor(int i0; is.length(); i) {for(int ji; js.length(); j) {if(j - i 1 longestPalindrome.length()) {if(isPalindrome(s.substring(i, j1))) {longestPalindrome s.substring(i, j1);}}}}return longestPalindrome;}// 判断是否是回文字符串public Boolean isPalindrome(String s) {// 双指针int left 0;int right s.length() - 1;while (left right) {if(s.charAt(left) ! s.charAt(right)) {return false;}left ;right --;}return true;}
}总结注意点
第一步先写出 判断是否回文 的方法 isPalindrome 。 利用双指针的思想第二步暴力遍历每个子字符串判断是否回文更长的则更新
时间复杂度 n^3
解法二中心扩展法
参考讲解视频https://www.bilibili.com/video/BV1dN4y1g7p9/?spm_id_from333.337.search-card.all.clickvd_sourcebf2066b8675548fac384ffe3bc83793e
代码
class Solution {// 维护最长回文字符串public String res;public String longestPalindrome(String s) {// 判空处理if(null s s.length() 0) {return ;}// 初始化res res s.substring(0,1);// 遍历s字符串 for(int i0; is.length(); i) {// 考虑 bab 的格式extendFromCenter(s, i, i);// 考虑 baab 的格式extendFromCenter(s, i, i1);}return res;}// 中心扩散public void extendFromCenter(String s, int left, int right) {// 当 left、right 在区间返回内且 s[left] s[right] 才会向外扩散while(left0 rights.length() s.charAt(left)s.charAt(right)) {// 向外扩散left--;right;}// 若当前回文串 比 res长 则更新resif(right - left - 1 res.length()) {// 因为最后一次循环 left-- right了因此实际上回文字符串是[left1, right-1]由于substring是左闭右开[)因此 res s.substring(left1, right)res s.substring(left1, right);}}
}总结注意点
解法一判断字串是否是回文串思想是自外向内的left ; right --;解法二寻找属于回文串的字串且思想是自内向外扩散的left--; right;要考虑 bab、baab 两种回文串的格式 因此在遍历到某个字符时extendFromCenter(s, i, i);extendFromCenter(s, i, i1); 要调两次extendFromCenter
时间复杂度n^2
1143. 最长公共子序列
【1143. 最长公共子序列】 分析 根据两个字符串的长度创建一个二维表格遍历二维表格。也即是遍历 两个字符串的每一个字符两两比较
具体详解可参考视频【最长公共子序列 - 动态规划 Longest Common Subsequence - Dynamic Program】 代码 class Solution {public int longestCommonSubsequence(String text1, String text2) {char[] charArr1 text1.toCharArray();int len1 charArr1.length;char[] charArr2 text2.toCharArray();int len2 charArr2.length;// dp[i][j]含义字符串text1[0,1) 与 字符串text2[0,j) 的最长公共子序列长度int[][] dp new int[len11][len21];for(int i1; ilen1; i) {for(int j1; jlen2; j) {// text1的第i个字符char ch1 charArr1[i-1];// text2的第j个字符char ch2 charArr2[j-1]; if(ch1 ch2) {// 两个字符串各移除一个字符的状态↖状态 1dp[i][j] dp[i-1][j-1] 1;} else {// text1移除一个字符的状态↑状态text2移除一个字符的状态↓状态。二者求最大值dp[i][j] Math.max(dp[i-1][j], dp[i][j-1]);}}}return dp[len1][len2];}
}技巧
169. 多数元素
【169. 多数元素】 分析 某个值在该数组中的个数超过一半该值即叫做多数元素这样的元素在这个数组中肯定只有一个 摩尔投票算法 可以使空间复杂度O(1)时间复杂度为O(n). B站上上视频讲解https://www.bilibili.com/video/BV1Ey4y1n7hb 代码 public class Solution {/* 摩尔投票 */public int MoreThanHalfNum_Solution(int [] arr) {// 票数int rating 0;// m假设是个数超过一半的那个数int m arr[0];for(int i0; iarr.length; i) {// 当票数为0时 将当前数当做m并且票数设为1if(rating 0){m arr[i];rating 1;} else {if(arr[i] m) // 若与m相同 票数就rating;else // 不同则--rating--;}}return m;}
}136. 只出现一次的数字
【136. 只出现一次的数字】 分析 这道题主要利用位运算中异或的性质 异或二进制下用1表示真0表示假则异或的运算法则为0⊕001⊕010⊕111⊕10同为0异为1 对于这道题可使用异或运算 ⊕。异或运算有以下三个性质。
任何数和 0 做异或运算结果仍然是原来的数即 a⊕0a 。任何数和其自身做异或运算结果是 0即 a⊕a0。异或运算满足交换律和结合律即a⊕b⊕a b⊕a⊕a b⊕(a⊕a) b⊕0b。
因为该数组中只有一个数出现一次其他数都是出现两次所有若让数组中所有的数参与异或运算最终的结果肯定是只出现一次的那个数。 代码 class Solution {public int singleNumber(int[] nums) {int res 0;for(int i0; inums.length; i) {res ^ nums[i];}return res;}
}75. 颜色分类
【75. 颜色分类】 分析 经典【荷兰国旗】问题。 我们要对该数组排序排序的规则就是 0 放到最左边2 放到最右边 1 放到中间 需要三个指针left、right、curIdx
left下标之前的元素都是 0right下标之后的元素都是 2curIdx表示当前要判断的元素下标
步骤
使用curIdx遍历所有元素当curIdx right时遍历终止若nums[curIdx] 0则将当前元素移动到left之前并且curIdx可后移因为curIdx之前的元素本身已经有序了不需要再判断了。具体操作如下 swap(nums, curIdx, left)curIdx 若nums[curIdx] 2则将当前元素移动到right之后但curIdx不可后移因为curIdx后面的元素还未排序仍需要判断。具体操作如下 swap(nums, curIdx, right--) 若nums[curIdx] 1本身符合排序规则则curIdx直接后移即可。具体操作 curIdx
参考视频【LeetCode.75.颜色分类】 参考题解【【宫水三叶】经典荷兰国旗问题】 代码 class Solution {public void sortColors(int[] nums) {int len nums.length;int curIdx 0;int left 0;int right len - 1;// 当curIdx right 时才算遍历完了所有元素while(curIdx right) {if(nums[curIdx] 0) {// 将当前值已到left左侧swap(nums, curIdx, left);// curIdx之前的元素本身是有序的因此curIdx可直接后移curIdx;} else if (nums[curIdx] 2) { // 将当前值已到right右侧swap(nums, curIdx, right--);// curIdx之后的元素还未排序curIdx不可直接后移} else {// nums[curIdx] 1当前符合顺序curIdx可直接后移curIdx;}}}// 数值交换public void swap(int[] nums, int idx1, int idx2) {int temp nums[idx1];nums[idx1] nums[idx2];nums[idx2] temp;}
}287. 寻找重复数
【287. 寻找重复数】 分析 可看成寻找环形链表的入环节点 详细题解可参考大佬解释【287.寻找重复数】 代码 class Solution {public int findDuplicate(int[] nums) {int slow 0, fast 0;slow nums[slow]; // 慢指针一次走一步fast nums[nums[fast]]; // 快指针一次走两步while(slow ! fast) {// 慢指针一次走一步slow nums[slow];// 快指针一次走两步fast nums[nums[fast]]; }// 快指针 或者 慢指针 从头结点出发指针指向pHead,慢指针从相遇点出发(指针指向不变)slow 0;// 新一轮移动 一个指针从头结点 一个指针从相遇节点哪个从头结点哪个从相遇点都无所谓while(slow ! fast) {// 快慢指针后移 每轮都走一步slow nums[slow];fast nums[fast];}// 当快慢指针再次相遇时 就是入环节点return fast;}
}
