# leetcode **Repository Path**: githubwolf/leetcode ## Basic Information - **Project Name**: leetcode - **Description**: No description available - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2024-02-25 - **Last Updated**: 2024-05-24 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README ```java //124 //https://leetcode.cn/problems/binary-tree-maximum-path-sum/ //求路径最大和 /** * 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 { private int maxPathValue = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { maxSum(root); return maxPathValue; } //注意路径的概念，在一个中间节点上，或者选择左节点，或者选择右节点，也可以不选择子节点。换个角度理解：路径就是一笔画，不可以重复经过同一个节点。 private int maxSum(TreeNode root){ if(null == root){ return 0; } //这个地方得使用Math.max，因为val可能为负数，就不应该贡献值了，否则会导致得到的值更小 //这个地方是个关键点，那计算结果和0进行比对，得到一个贡献值 int leftsum = Math.max(maxSum(root.left), 0); int rightsum = Math.max(maxSum(root.right), 0); //当前节点的最大贡献值 int currentsum = root.val + leftsum + rightsum; //取一个最高值，这个地方也是关键点，只要递归到所有节点，那么就可以得到一个最大值 maxPathValue = Math.max(currentsum, maxPathValue); //当前节点可以左边路径，也可以走右边路径，但是不会两边都走。一笔画，选择最大值作为返回值。这是关键点！ //最大值已经在上面计算过了，函数的返回值是要提供给父节点的，所以或者是左子树或者是右子树，不会是左右子树都包含 return Math.max(root.val + leftsum, root.val + rightsum); } } ``` ```java //105 //https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ //使用preorder和inorder数组构造二叉树 /** * 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 TreeNode buildTree(int[] preorder, int[] inorder) { //前序遍历可以从根节点开始访问，再根据根节点的值在中序数组中查找对应的根节点，分出左右子树。需要查询多次，所以借助hashmap来完成快速查询。 HashMap hashMap = new HashMap(); for(int i = 0; i < inorder.length; i++){ hashMap.put(inorder[i], i); } //起始点什么都包含，接下来就是递归索引了 return build(preorder, 0, preorder.length - 1, inorder, 0, preorder.length - 1, hashMap); } private TreeNode build(int[] preorder, int preorder_start, int preorder_end, int[] inorder, int inorder_start, int inorder_end, HashMap hashMap){ if((preorder_start > preorder_end) || (inorder_start > inorder_end)){ return null; } //preorder里面取得第一个节点作为根节点,根据这个值在inorder里面定位分开左右子树 TreeNode root = new TreeNode(preorder[preorder_start]); //取出根节点在中序遍历数组中的位置，根据这个位置分开左右子树。 int root_index = hashMap.get(preorder[preorder_start]); //算一下左子树的节点数量。这是思维关键的一步！ int left_number = root_index - inorder_start; //递归左子树，关键点是确定数组的访问区间 root.left = build(preorder, preorder_start + 1, //左子树的前序遍历的起点是跳过当前的节点 preorder_start + left_number, //左子树所有节点的数量 inorder, inorder_start, //左子树的中序遍历起点不变 inorder_start + left_number, //根节点是区分点，也可以使用root_index -1 hashMap ); root.right = build(preorder, preorder_start + 1 + left_number, // 跳过左子树的区间 preorder_end, //结束点不变 inorder, root_index + 1, //右子树从root_index右侧偏移1开始 inorder_end, //结束点不变 hashMap); return root; } } ``` ```java //99 //https://leetcode.cn/problems/recover-binary-search-tree/ //恢复二叉搜索树 /** * 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 { private TreeNode x = null; private TreeNode y = null; private TreeNode prev = null; public void recoverTree(TreeNode root) { dfs(root); int tmp = x.val; x.val = y.val; y.val = tmp; // 二进制搜索树：左节点 < 根节点 < 右节点，使用中序遍历，那么前一个节点肯定小于当前节点， // 如果没有满足这个条件，那么前一个节点就是错的。问题：为什么不认为是当前节点是错的呢？ // 题目的前提是只有两个节点的值是错误的，需要交换过来，所以，我们只需要以遍历每个节点及其子节点，找到不不符合值的两个节点。 // 二差搜索树的特性就是中序遍历的方式访问到的值是递增的，最小值肯定是中序遍历的第一个值，最大值是中序遍历的最后一个值。 } // 深度优先，其实也是中序遍历。 // https://zhuanlan.zhihu.com/p/442938081 public void dfs(TreeNode root) { if (root == null) { return; } // 找到叶子节点，从叶子节点开始比较。 dfs(root.left); // prev不为空，而且父节点的值小于前一个节点的值值，意味着当前节点的值不正确。因为是使用中序遍历，所以前一个节点肯定是当前节点的左子树的节点。 if ((prev != null) && (root.val < prev.val)) { // 当前节点是一个不合法的节点，记录下来。 y = root; // x为Null if (x == null) { // x保存为前一个节点,x是第一个找到的节点 x = prev; } else { // x不为null，那么，x和y都有值了，两个节点都找到了，可以退出了。 return; } } // prev总是指向前一个节点。 prev = root; dfs(root.right); } } /** * 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 { //最后需要两个节点交换，所以至少需要定义两个变量。 TreeNode x = null; TreeNode y = null; //二叉搜索树的中序遍历得到的值列表是单向列表的。需要一个指针保存上一个节点。 TreeNode prev = null; public void recoverTree(TreeNode root) { //中序遍历，也就是dsf dsf(root); //交换两个节点的值。 int tmp = x.val; x.val = y.val; y.val = tmp; } public void dsf(TreeNode root){ if(null == root){ return; } //中序遍历，先递归一直到左节点的叶子节点。 dsf(root.left); //prev不为Null,可以比较一下。如果不为Null就没有什么好比较的。 if(prev != null){ //比较一下，看看前一个节点的值和当前节点的值是否不符合了。 if(prev.val > root.val){ //不管怎样，先假设当前节点是错误的， y = root; if(x==null){ //x是第一个非法值。 x = prev; }else{ //x已经找到了，y也找到了，可以退出了。 return; } } } //遍历右子树之前，prev先指向root。 prev = root; //ok了，可以遍历右子树了。 dsf(root.right); } } ``` ```java //509 //https://leetcode.cn/problems/fibonacci-number/description/ //斐波那契数列生成,从第三项开始，每一项的值为前两项的值的和 //0 1 1 2 3 5 8 13 //这种方式是使用递归，代价是算法的复杂度是2的n次方 class Solution { public int fib(int n) { if(n == 0){ return 0; } if((n == 1) || (n == 2) ){ return 1; } //递归分开求子项 return fib(n-1) + fib(n -2); } } //知道递归后就尝试用循环来代替递归 class Solution { public int fib(int n) { int[] values = new int[n+1]; if(n == 0) return 0; if(n == 1) return 1; values[0] = 0; values[1] = 1; //从低位开始循环 for(int i = 2; i myHashMap = new HashMap(); public int coinChange(int[] coins, int amount) { /* * 动态规划的核心： * 确定问题的基本状态，也是退出递归的条件。 * 确定状态是如何变化的。 * 确定选择如何导致变化。 */ return dp(coins, amount); } public int dp(int[] coins, int amount){ //这个地方也是关键，这个res不是全局的，而是局部的。 int res = Integer.MAX_VALUE; if(amount == 0) return 0;//这是终止条件，表示有合适的组合 if(amount < 0) return -1;//已经为负数了，可以停止了 if(myHashMap.containsKey(amount)){ //开始就可以检查是否已经计算过了，如果计算过了就不再重复了。 return myHashMap.get(amount); } //每次递归都需要再次遍历数组 for(int coin: coins){ int subproblem = -1; //这是递归点 subproblem = dp(coins, amount - coin);//数组还是那个数组，但是amount减少了 if(subproblem == -1) continue;//不是合法场景，跳过，注意这个地方并没有个res赋值。 //要计算最小 res = Math.min(res, 1 + subproblem);//消耗了一个coin值，如果subproblem返回-1，则其实是个无效值，也就是是min(res,0)了，没有实际影响。 } int temp = 0; //res值被修改过，那么至少有一个合法组合，否则就是不合法的组合了，直接返回-1 if(res != Integer.MAX_VALUE) temp = res; else temp = -1; //------------这个地方注意一点，返回点才是放入值的点 myHashMap.put(amount, temp); return temp; } } //这个解释更到位:https://leetcode.cn/problems/coin-change/solutions/132979/322-ling-qian-dui-huan-by-leetcode-solution/ class Solution { public int coinChange(int[] coins, int amount) { /* * 动态规划的核心： * 确定问题的基本状态，也是退出递归的条件。 * 确定状态是如何变化的。 * 确定选择如何导致变化。 */ //还是借用递归、动态规划的思想，从最低值开始计算 int[] dp = new int[amount + 1]; //Integer.MAX_VALUE + 1 等于Integer.MIN_VALUE Arrays.fill(dp, amount + 1);//硬币的最小单位是1，所以amount最大的合法值不可能是amount+1，使用Integer.MAX_VALUE反而出错 dp[0] = 0;//如果0 amount，显然是只需要0个coin，注意这个地方是把amount作为索引！！！！这也是关键！ for(int i = 0; i < dp.length; i++){ for(int coin: coins){ //如果amount < 0，明显是非法的。注意这个地方使用的索引有两个：i和i-coin。 if(i-coin < 0) continue; dp[i] = Math.min(dp[i], 1 + dp[i-coin]);//这个地方是其实理解的关键：双层循环，反复跟dp[i]进行比对，从而确保dp[i]可以得到最小值！ } } //遍历完把amount作为索引访问结果 return(dp[amount] == amount + 1)? -1:dp[amount]; } } class Solution { public int coinChange(int[] coins, int amount) { int max = amount + 1; //定义dp[i]为amount为i的最少硬币个数 int[] dp = new int[max]; //初始值为无效值 Arrays.fill(dp, max); //amount为0的最少硬币个数也只能为0 dp[0] = 0; //定义转移方程: dp[i]和coin[j]的关系，使用coin[j]和不使用coin[j] //如果使用coin[j]，那么dp[i]的值为dp[i-coin[j]]+1 //如果不使用coin[j]，那么dp[i]的值为dp[i] //取最小值，为什么要使用dp[i] = Math.min(dp[i],dp[i-coin[j]]+1)呢？因为dp[i]会被反复计算，需要取到一个最小值 for(int i = 1; i <= amount; i++){ for(int j = 0; j < coins.length; j++){ if(i >= coins[j]){//防止越界 dp[i] = Math.min(dp[i], dp[i-coins[j]] + 1); } } } return dp[amount] == max?-1:dp[amount]; } } ``` ```java //518 //https://leetcode.cn/problems/coin-change-ii/description/ //求所有兑换零钱的组合数量，而不是最小的数量 class Solution { public int change(int amount, int[] coins) { //注意index的作用，这个地方是从0开始，就是说只要coins数组里面有的值都可以遍历。 int result = dp(coins, 0, amount); return result; } private int dp(int[] coins, int index,int amount){ if(amount == 0) return 1; if(amount < 0) return 0; if(index >= coins.length) return 0; //其实递归遍历，每一次只能范围0或者1，但是因为结果是返回p1+p2，所以实际上就会导致递增 //有两种情况，当前coin没用，索引往下尝试下一个coin的值，amount不需要减 int p1 = dp(coins, index + 1, amount ); //当前coin是一个可用的值，下一次还有可能继续使用，所以index不需要递增，amount需要减除 int p2 = dp(coins, index, amount-coins[index]); return p1 + p2; } } //上面的方法效率太低，总是递归，会超时，需要使用备忘录，但是这个递归里面有两个可变参数，无法直接使用map。 class Solution { public int change(int amount, int[] coins) { //定义dp[x]为amount为x的硬币组合数，目标也就是求dp[amount] int[] dp = new int[amount+1]; //使用dp数组记得初始化第一个元素 dp[0] = 1;//amount为0，只有一种组合，那就是什么硬币都不选择 //列举各种组合 for(int coin: coins){ for(int i = coin; i <= amount; i++){ //dp[i-coin]前面已经计算过了 dp[i] += dp[i - coin]; } } //动态规划的实现实际上就是生成并填充dp数组 return dp[amount]; } } //面试题 04.02. 最小高度树 //https://leetcode.cn/problems/minimum-height-tree-lcci/description/ //给一个有序数组，创建一个最小高度二叉树 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode sortedArrayToBST(int[] nums) { //注意left, right必须是有效值 return traverse(nums, 0, nums.length -1); } public TreeNode traverse(int[] nums, int left, int right){ //这个地方是关键的判断，返回null的条件 if(left >right){ return null; } int middle = (left + right )/2; TreeNode root = new TreeNode(nums[middle]); //注意以middle为计算点 root.left = traverse(nums, left, middle - 1); root.right = traverse(nums,middle + 1, right); return root; } } //111 //https://leetcode.cn/problems/minimum-depth-of-binary-tree/ //求二叉树的最小深度 //要求得最小深度意味着得遍历所有节点，所以肯定得存储一个最小值。 //首先的遍历根节点到leaf节点的路径，得到深度，然后再和最小值进行比对。 class Solution { public int minDepth(TreeNode root) { //最小深度是根节点到叶子节点的最短路径上的节点数量. //注意！是到有效的叶子节点的路径，而不是到null节点的路径的最小值！否则永远为1了！ return traverse(root); } public int traverse(TreeNode root){ if(root == null){ return 0; } //左右节点都为空则为叶子节点，递归结束。这一点很重要！ if((root.left == null) && (root.right == null)){ return 1; } //这个地方思维需要转变一下，当然一个节点左右节点有一个为空，则需要返回的是有子节点的路径的长度，而不是子节点为Null的路径长度！其实返回的是Max，而不是Min！ int leftDepth = Integer.MAX_VALUE; //左子树或者右子树不为空，当前节点不是叶子节点，需要进一步递归到子节点。 if(root.left != null){ leftDepth = 1 + traverse(root.left); } int rightDepth = Integer.MAX_VALUE; //左子树或者右子树不为空，当前节点不是叶子节点，需要进一步递归到子节点。 if(root.right != null){ rightDepth = 1 + traverse(root.right); } return Math.min(leftDepth, rightDepth); } } class Solution { public int minDepth(TreeNode root) { //最小深度是根节点到叶子节点的最短路径上的节点数量. //注意！是到有效的叶子节点的路径，而不是到null节点的路径的最小值！否则永远为1了！ return traverse(root); } public int traverse(TreeNode root){ if(root == null){ return 0; } //左右节点都为空则为叶子节点，递归结束。这一点很重要！ if((root.left == null) && (root.right == null)){ return 1; } //这个地方思维需要转变一下，当然一个节点左右节点有一个为空，则需要返回的是有子节点的路径的长度，而不是子节点为Null的路径长度！其实返回的是Max，而不是Min！ //如果左右节点都不为null，则返回Min //如果左右节点有一个为null，当前节点不是叶子节点，返回Max if((root.left == null) || (root.right == null)){ //必然一个返回0 return 1+ Math.max(traverse(root.left), traverse(root.right)); } //两个子节点都为空 return 1+Math.min(traverse(root.left), traverse(root.right)); } } //使用一个列表作为记事本来做广度遍历 class Solution { public int minDepth(TreeNode root) { //递归是使用深度遍历，我们也可以使用广度遍历，遍历到第一个叶子节点得到是深度就是最小深度 if(root == null){ return 0; } int depth = 0; LinkedList mylist = new LinkedList(); mylist.add(root); while(!mylist.isEmpty()){ depth++; //得到当前队列中节点数量，需要把当前的节点数量都取完才表示当前这一层已经遍历完了。这是要点！ int currentTotal = mylist.size(); for(int i = 0; i < currentTotal; i++){ //一个个取出来。 //如果当前节点已经是叶子节点了，这个就是最小深度了. TreeNode current = mylist.removeFirst(); if((current.left == null) && (current.right == null)){ return depth; } //当前节点不是叶子节点，继续放到队列中。 if(current.left != null){ mylist.add(current.left); } if(current.right != null){ mylist.add(current.right); } } } return depth; } } //752 //https://leetcode.cn/problems/open-the-lock/ class Solution { public int openLock(String[] deadends, String target) { //初始是是个0000，可以向前旋转也可以向后旋转，每次只能旋转一个数，不能经过deadends //本质上是最短路径，有4个数字，如果分别求4次的最短路径然后再扣除deadends中的数字 //每个数字一次变动可以加一或者减一，但是在遍历的时候其实可以一次做两次操作，也就是同时+1和-1. return myOpenLock(deadends, target); } String plusOne(String target, int index){ char[] chars=target.toCharArray(); if(chars[index]=='9'){ chars[index] = '0'; }else{ chars[index] += 1; } return new String(chars); } String minusOne(String target, int index){ char[] chars=target.toCharArray(); if(chars[index]=='0'){ chars[index] = '9'; }else{ chars[index] -= 1; } return new String(chars); } int myOpenLock(String[] deadends, String target){ int result = -1; HashSet deadendSet = new HashSet(); for(String deadend: deadends){ deadendSet.add(deadend); } HashSet visited = new HashSet(); //从0000开始作为起始点 LinkedList mylist = new LinkedList(); mylist.add("0000"); visited.add("0000"); while(!mylist.isEmpty()){ int currentCount = mylist.size(); result++; /* 理解一下这个循环过程，默认0000， 第一次循环后每位数有两个选项，所以演变出8个字符串 第二次循环后取出8个字符串，每个字符串会演变出8个字符串，最后列表中会得到64个字符串， 第三次循环会得到64*8个字符串，所以整个过程中列表会逐步扩展，最后得到的是由0000衍生出来的所有的排列组合，理论上是2的10次方乘与2的10次方乘与2的10次方乘与2的10次方，也就是2的40次方！ 注意这个过程中得到的集合会包含已经遍历遍历过的，因为第二次循环的时候会有++/--的操作，所以会和上一次循环得到集合重叠，下一次循环包含的会包含上一次循环得到的集合。 但是怎么判断结束点呢？要嘛就是全遍历结束，要嘛就是找到。 怎样才算全遍历结束呢？往前遍历而且遍历过的不再遍历，最后列表为空则是遍历结束。 */ //取出当前的行，逐步往外扩散 for(int i =0;i < currentCount;i++){ String current = mylist.removeFirst(); if(target.equals(current)){ return result; } //当前节点继续向周围扩散，每个字符有两个扩散方向，有4个字符，所以需要再有一个循环 for(int j = 0; j < current.length(); j++){ //注意current才是应该真正要检测的对象，不能直接去检查plusOne,minusOne if(deadendSet.contains(current)){ continue; } String strPlus = plusOne(current, j); String strMinus = minusOne(current, j); //有些字符串已经遍历过了，如果再次放进去就会导致死循环，所以要记录已经使用过的，不能再次放进去 if(!visited.contains(strPlus)){ visited.add(strPlus); mylist.add(strPlus); } //有些字符串已经遍历过了，如果再次放进去就会导致死循环，所以要记录已经使用过的，不能再次放进去 if(!visited.contains(strMinus)){ visited.add(strMinus); mylist.add(strMinus); } } } } //没有找到匹配的！ return -1; } } //141 //https://leetcode.cn/problems/linked-list-cycle/description/ //判断链表是否有环 //可以使用快慢指针，或者使用hashset一直遍历 public class Solution { public boolean hasCycle(ListNode head) { if(head == null){ return false; } //起始点不一样 ListNode slow = head; ListNode fast = head.next; //如果为null，意味着没有环 while((slow != null) && (fast != null)){ //两个节点相等，肯定是有环的 if(slow == fast){ return true; } //慢指针走一步 slow = slow.next; //为null，没有环 if(fast.next == null){ return false; } //快指针走两步 fast = fast.next.next; } //有为null，没有环 return false; } } //141 //https://leetcode.cn/problems/binary-search/ //对数组折半查找 class Solution { public int search(int[] nums, int target) { if(nums.length < 1){ return -1; } return binarySearch(nums, target, 0, nums.length - 1); } public int binarySearch(int[] nums, int target, int left, int right){ while(left <= right){ //对半，检查是否匹配 int middle = (left + right)/2; if(nums[middle] == target){ return middle; } //修改right或者left继续下一个循环 if(nums[middle] > target){ right = middle -1; continue; } if(nums[middle] < target){ left = middle + 1; continue; } } return -1; } } //1 //https://leetcode.cn/problems/two-sum/ //从未排序的数组中找到两数之和为target的元素的下标 class Solution { public int[] twoSum(int[] nums, int target) { //要计算两数之和，可以先把和减去nums[i]，得到差 HashMap myHash = new HashMap(); for(int i = 0; i < nums.length; i++){ //key为值，value为索引 myHash.put(nums[i], i); } for(int i = 0; i < nums.length; i++){ int currentNum = nums[i]; int left = target-currentNum; if(myHash.containsKey(left)){ int index = myHash.get(left); //得排除掉这个 if(index == i){ continue; } int[] result = new int[2]; result[0] = i; result[1] = index; return result; } } return null; } } //167. 两数之和 II - 输入有序数组 //https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/description/ class Solution { public int[] twoSum(int[] numbers, int target) { //这是一个递增的有序数组，一旦是有序数组，就可以用到双指针的方法 int left = 0; int right = numbers.length -1; while(left < right){ int sum = numbers[left] + numbers[right]; if( sum == target){ return new int[]{left+1, right+1};//题目要求索引从1开始 } //相加的和大于target，所以right--，变小一点 if(sum > target){ right--; }else{ //sum小于target，变大一点 left++; } } return new int[]{-1,-1}; } } //7 //反转整数值 class Solution { public int reverse(int x) { //初始值为0 int result = 0; while(x != 0){ if (result < Integer.MIN_VALUE / 10 || result > Integer.MAX_VALUE / 10) { return 0; } //每次得到一位 int modValue = x%10; //左移，乘以10 result = result*10 +modValue; //右移，除以10 x = x/10; } return result; } } //189 轮转数组 //https://leetcode.cn/problems/rotate-array/ class Solution { public void rotate(int[] nums, int k) { int n = nums.length; //使用额外的数组 int[] newnums = new int[n]; for(int i = 0;i target){ right = middle -1; } } return -1; } } //递归的方式 class Solution { public int search(int[] nums, int target) { int left = 0; int right = nums.length-1; return binarySearch(nums, target, left, right); } public int binarySearch(int[] nums, int target, int left, int right){ int middle = (left + right)/2; if(left > right){ return -1;//abort now. } if(nums[middle] == target){ return middle; }else if(nums[middle] < target){ return binarySearch(nums, target, middle +1, right); }else if(nums[middle] > target){ return binarySearch(nums, target, left, middle -1); } return -1; } } //LCR 073 //https://leetcode.cn/problems/nZZqjQ/ //使用二分法找到最小值 class Solution { public int minEatingSpeed(int[] piles, int h) { //题目的要求是获得min速度K，然后在h小时内吃完所有香蕉 //一小时内只会选择一堆 //因为一小时内不能选择两堆香蕉，所以本质上就是一堆一堆地吃完 //这个地方比较关键的是要找到最小值x //题目没有说每堆香蕉的数量是不是相等 //每小时最少吃1根香蕉，最多吃N根，N是一堆香蕉中数量最高的 int highest = 0; for(int pile: piles){ highest = Math.max(highest, pile); } int low = 1; int high = highest; int k = highest; while(low < high){ //这个地方不能是等于号，否则会死循环，因为内部没有return int middleSpeed = (low+high)/2; int time = getHoursForAllPiles(piles, middleSpeed); if(time <= h){ //时间够用，速度太快，要找最小值，可以降低速度。不断降低high，找到最后一个合法值也就是最小值了. //如果是修改low，不断提高low，则得到的是最大值 high = middleSpeed; k = middleSpeed;//k是合法值 }else if(time > h){ //需要的实际时间大于h，需要提高速度 low = middleSpeed + 1; } } return k; } //吃掉一堆香蕉需要的时间 public int getHoursForPile(int pile, int k){ int hours = pile/k; if(pile%k != 0){ hours++; } return hours; } //吃掉所有香蕉需要的时间 public int getHoursForAllPiles(int[] piles, int k){ int hours = 0; for(int i =0; i < piles.length; i++){ hours += getHoursForPile(piles[i], k); } return hours; } } class Solution { public int minEatingSpeed(int[] piles, int h) { //h为时间 //注意一小时内只能吃一次，如果一堆香蕉小于数量K，也占用一次。 //每堆的数量是不确定的，吃的时候按照顺序吃，以及挑着吃没有区别，只要挨个遍历就OK了。 //要求最小速度，暴力方法的话就挨个尝试，逐步递增 //如何选择区间呢？最小值明显是1，最大值是piles里面最大的值 int max = piles[0]; for(int i = 0;i < piles.length; i++){ if(piles[i] > max){ max = piles[i]; } } //从1到max中找到最小值 int left = 1; int right = max + 1;//这个地方是个关键，因为是求平均值然后再求最大最小值，如果这个地方没有+1，会导致遍历范围变小 while(left < right){ //不能有等于号！否则会导致死循环 int middle = (left+right)/2; if(canFinishAll(middle, h, piles)){ //可以吃完，但是可能不是最小值，所以把right变成middle继续求最小值 right = middle; }else{ //不能吃完，需要提高速度 //这个地方不是使用left = middle，否则也有可能死循环。因为left可能反复等于Middle，比如说4,5的middle反复等于4 //如果left //另外记住，middle这个值已经被比较过了，不需要再使用，所以这里做了+1的操作。 left = middle + 1; } //临界状态是得到一个可以吃完的值，但是一旦把进入下个循环的时候又不能吃完了，所以需要记录一下最后一个找到的合法值 //会不会出现死循环? middle = (3 + 4)/2，也就是3，就进入死循环了 } return left; } private boolean canFinishAll(int k, int hours, int[] piles){ int counter = 0; for(int i = 0; i < piles.length; i++){ counter += piles[i]/k; if(piles[i]%k != 0){ counter++; } } if(counter > hours){ return false; }else{ return true; } } } //76 //https://leetcode.cn/problems/minimum-window-substring/ //注意有几个子串是符合要求的，但是需要找到一个最小的子串 class Solution { //这里要求的t是可以不按照顺序在s里面出现的 public String minWindow(String s, String t) { int left = 0; int right = 0; char[] source =s.toCharArray(); char[] target=t.toCharArray(); HashMap window = new HashMap(); HashMap targetHashMap = new HashMap(); String answer = ""; for(char c: target){ addOneCharToHashMap(targetHashMap, c); } boolean hasAll = false; while(right < source.length){ //右侧窗口滑动，添加一个元素到窗口 addOneCharToHashMap(window, source[right]); //判断窗口是不是已经包含所有的元素，如果是，则开始缩小窗口 if(hasAllChars(window, targetHashMap)){ //包含所有的字符了，开始在左侧缩小窗口 while(left <= right ){ //删除左侧的一个字符 removeOneCharFromHashMap(window, source[left]); //检查是不是还包含所有的字符 if(!hasAllChars(window, targetHashMap)){ //已经没有包含所有的字符了，当前是最小窗口了 if(answer.length() == 0){ answer = s.substring(left, right+1); }else{ //已经存过一个值了，要对比一下存储一个更小长度的值 if(answer.length() > (right - left + 1)){ //找到一个更小的字符串 answer = s.substring(left, right+1); } } left++; //已经是最小窗口了，退出去 break; }else{ left++; } } } //滑动右侧窗口 right++; } return answer; } void addOneCharToHashMap(HashMap myHashMap, char c){ int currentCount = myHashMap.getOrDefault(c, 0); myHashMap.put(c, currentCount+1); } void removeOneCharFromHashMap(HashMap myHashMap, char c){ int currentCount = myHashMap.getOrDefault(c, 0); if(currentCount > 0){ myHashMap.put(c, currentCount-1); } } boolean hasAllChars(HashMap window, HashMap targetHashMap){ boolean result = false; //使用entrySet方法得到一个set，再调用iterator方法 Iterator iterator = targetHashMap.entrySet().iterator(); while(iterator.hasNext()){ HashMap.Entry entry = (HashMap.Entry) iterator.next(); Character c = (Character)entry.getKey(); Integer number = (Integer)entry.getValue(); int numberInWindow = window.getOrDefault(c,0); //注意这个地方使用小于号，因为window中的数量可以大于等于target的数量 if(numberInWindow < number){ return false; } } return true; } } //438 //找到字符串的异位词 //异位词意味着字母的数量一样，位置不一样。通过把两个字符串的字母数量汇总到一个数组里面，然后再判断数组是相等，如果数组相等，则字符串是异位词。 //https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/ class Solution { public List findAnagrams(String s, String p) { int sLen = s.length(); int pLen = p.length(); ArrayList ans = new ArrayList(); if(sLen < pLen){ return ans; } int[] sCount = new int[26]; int[] pCount = new int[26]; //先把s的前一部分和p的所有都放到数组中 for(int i = 0; i < pLen; ++i){ //把s和p的字符都统计到数组中 ++sCount[s.charAt(i) - 'a'];//这个地方是个技巧，和'a'算差值 ++pCount[p.charAt(i) - 'a']; } //如果数组相同，则0开始的这个地方就是个有效的位置 //Arrays.equals if(Arrays.equals(sCount, pCount)){ ans.add(0); } //一个字符一个字符的往前对比 for(int i = 0; i <(sLen -pLen); ++i){ //移动窗口左边界，删除一个字符 //减去左窗口的字符，这个地方注意索引是i --sCount[s.charAt(i) - 'a']; //移动窗口右边界添加一个字符 //添加右窗口的字符，索引是i+pLen，因为前面已经读进去了pLen ++sCount[s.charAt(i + pLen) - 'a']; //比较两个数组是不是相等，相等则为异位词 if(Arrays.equals(sCount, pCount)){ //这个地方已经是i+1了 ans.add(i+1); } } return ans; } } class Solution { public List findAnagrams(String s, String p) { List res = new ArrayList(); int sLen = s.length(); int pLen = p.length(); if(sLen < pLen) { return res; } //表示字母出现次数差距 //count[x] = 0 表示 s与p中字母x出现次数相同 都出现了n次(n>=0) //count[x] = n 表示 在s中字母x出现次数比p多 多出现了n次(n>0) //count[x] = -n 表示 在s中字母x出现次数比p少 少出现了n次(n>0) int[] count = new int[26]; for(int i = 0; i < pLen; i++){ ++count[s.charAt(i)-'a']; --count[p.charAt(i)-'a']; } //表示字母差异个数 int differ = 0; for(int j = 0; j < 26; j++){ if(count[j]!=0) ++differ; } if(differ==0){ res.add(0); } //向右滑动 for(int i = 0; i < sLen - pLen; i++){ //缩减时只考虑count[x]==1与count[x]==0的情况 //因为缩减时字母x减少，count[x]会减去1 //(1)count[x]==1时(次数差距1次，不相同) //count[x]==0 -> 次数相同 -> 不相同变相同，字母差异个数减少1 -> differ-- //(2)count[x]==0时(次数相同) //count[x]==-1 -> 次数差距变为1次->相同变不相同 ，字母差异个数增加1 -> differ++ //(3)count[x]==-1时(次数不相同) -> count[x]==-2 次数还是不相同-> 字母差异数不变 //(4)count[x]==2时(次数不相同) -> count[x]==1 次数还是不相同-> 字母差异数不变 //左缩减一位，i if (count[s.charAt(i) - 'a'] == 1) { //窗口中s子串左边减少一个s[i]的数量(把原来多出来的1个s[i]去掉，变得相同) //两个字符串字母差距缩小 --differ; } else if (count[s.charAt(i) - 'a'] == 0) { //窗口中s子串左边减少一个s[i]的数量(把原来相同数量的s[i]的减少了1个，数量变得不相同) //两个字符串字母差距增大 ++differ; } //窗口中s子串左边减少一个字母s[i] --count[s.charAt(i) - 'a']; //添加时只考虑count[x]==-1与count[x]==0的情况，原因分析与缩减时类似 //右添加一位，i+pLen if (count[s.charAt(i + pLen) - 'a'] == -1) { //窗口中s子串右边增加一个s[i+pLen]的数量(把原来缺少的1个s[i]加上，数量变得相同) //两个字符串字母差距缩小 --differ; } else if (count[s.charAt(i + pLen) - 'a'] == 0) { //窗口中s子串右边增加一个s[i+pLen]的数量(把原来相同数量的s[i]多加了1个，变得不相同) //两个字符串字母差距增大 ++differ; } //窗口中s子串右边增加一个字母s[i+pLen] ++count[s.charAt(i + pLen) - 'a']; //两个字符串字母差距为0 if (differ == 0) { res.add(i + 1); } } return res; } } //3 //https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/ //无重复字符的最长子串长度 class Solution { public int lengthOfLongestSubstring(String s){ int[] counter = new int[256]; int total = 0; int length = s.length(); int left = 0; int longest = 0; for(int i = 0; i < length; i++){ char c = s.charAt(i); if(counter[c] == 0){ //还没有存储过字符，可以直接添加 counter[c]++; //有效长度加一 total++; }else if(counter[c] == 1){ //已经存储过字符了，有重复的了,左窗口应该开始进行收缩，应该收缩到重复的那个字符 while(left < i) { char charToRemove = s.charAt(left); left++; counter[charToRemove]--; total--; if( charToRemove == c){ break; } } //还没有存储过字符，可以直接添加 counter[c]++; //有效长度加一 total++; } //处理完一个字符之后都比较一下，得到一个longest longest = Math.max(longest, total); } return longest; } } //300 //https://leetcode.cn/problems/longest-increasing-subsequence/description/ //动态规划，寻找最长的递增子序列 public int lengthOfLIS(int[] nums) { //dp[i]为nums[i]的最长递增子序列的长度 int[] dp = new int[nums.length]; //至少包含自身，所以初始化为1 Arrays.fill(dp, 1); for(int i = 0; i < nums.length; i++){ for(int j = 0; j nums[j]){ //如果nums[i] > nums[j]，那么它的数量至少为nums[j]对应的dp[j]+1，而且是要求最大值。 dp[i] = Math.max(dp[i], dp[j]+1); } } } int res = 0; for(int i = 0; i < dp.length; ++i){ res = Math.max(dp[i], res); } return res; } //354 //俄罗斯套娃信封 //https://leetcode.cn/problems/russian-doll-envelopes/description/ class Solution { public int maxEnvelopes(int[][] envelopes) { //这道题本质上还是要找最长的pair递增序列的长度，或者pair递减序列的长度 //但是有差异的点在于：数组元素的位置是可变的，理论上是要做排序，然后再做动态规划 //先用递增的方式来实现 //sort(envelopes); Arrays.sort(envelopes, new Comparator(){ public int compare(int[] a, int[] b){ return a[0]==b[0]? b[1]-a[1] //从大到小 :a[0]-b[0]; //从小到大 } }); int length = envelopes.length; int[] dp = new int[length]; Arrays.fill(dp, 1); for(int i = 0; i < length; i++){ for(int j = 0; j < i; j++){ if(envelopes[i][1] > envelopes[j][1]){ dp[i] = Math.max(dp[i], dp[j] + 1); } } } int result = 0; for(int i = 0; i envelopes[j+1][0]){ swap(envelopes[j], envelopes[j+1]); } } } } public void swap(int[] en1, int[] en2){ int i1; int i2; i1 = en1[0]; i2 = en1[1]; en1[0] = en2[0]; en1[1] = en2[1]; en2[0] = i1; en2[1] = i2; } } //https://leetcode.cn/problems/longest-common-subsequence/description/ //1143 //返回两个字符串的最长子序列的长度（子序列不需要连续，子串需要连续） class Solution { public int longestCommonSubsequence(String text1, String text2) { //两个字符串，需要用到二维的动态规划数组 char[] chars1 = text1.toCharArray(); char[] chars2 = text2.toCharArray(); int length1 = chars1.length; int length2 = chars2.length; //多占用一个元素 int dp[][] = new int[length1+1][length2+1]; //dp[i][j]定义为以字符chars1[0..i-1], chars2[0..j-1]字符串的LCS长度 int max = 0; //base情况 dp[0][0] = 0; //注意得使用<=，否则会少访问chars1和chars2的最后一个元素 for(int i =1; i <= length1; i++){ for(int j = 1; j <= length2; j++){ if(chars1[i-1] == chars2[j-1]){ dp[i][j] = 1 + dp[i-1][j-1]; max = Math.max(dp[i][j], max); }else{ //二维数组，状态转移得考虑三种情况 dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); max = Math.max(dp[i][j], max); } } } return max; } } //72 //https://leetcode.cn/problems/edit-distance/description/ //编辑距离，把两个单词使用添加、删除、替换 //其实这个题目不需要考虑实际执行的是什么操作，只要不一样就执行一次操作就行了。 //而且求的是最小距离，如果当前位置的两个字符不匹配，最好的情况下是不需要执行任何操作，最坏的情况是执行一次操作。 //求的是最小值，所以需要对left,down,left_down做一个判断，取一个最小值。 class Solution { public int minDistance(String word1, String word2) { int m = word1.length(); int n = word2.length(); if(n*m == 0){ return n+m; } //动态规划本质上还是得全部枚举，但是减少了枚举的次数 //dp[i][j]定义为word1的前i个字符和word2的前j个字符的编辑距离 int[][] dp = new int[m+1][n+1];//注意这个地方都+1了，动态规划中经常这样使用。 //二维数组得考虑base case下的初始值 for(int i = 0; i < m+1; i++){ //dp[i][0]这个场景下表示word2为空，那么word1有多少个字符就需要多少次删除操作就能找到最小的数量 dp[i][0] = i; } for(int j = 0; j < n+1; j++){ //word0为空，则word2有多少个字符就执行多少次插入操作就可以得到结果 dp[0][j] = j; } //从1开始并且得遍历到最后一个元素 for(int i = 1; i < m+1; i++){ for(int j = 1; j < n+1; j++){ //注意这个地方访问的是dp数组，而不是word int left = dp[i-1][j]+1; int down = dp[i][j-1] + 1; int left_down = dp[i-1][j-1]; //这个地方没有+1，为什么呢？因为word1[i-1]和word2[j-1]可能相等，这样就不用进行编辑操作了，直接进行skip。 //注意索引从1开始，为了避免少遍历元素，需要-1，而且这个地方比较的是word，而不是数组 if(word1.charAt(i-1) != word2.charAt(j-1)){ //两个字符不相等，如果两个字符相等，则不需要+1，相当于skip left_down += 1; } dp[i][j] = Math.min(left, Math.min(down, left_down)); } } //这个返回值也很关键。 return dp[m][n]; } } //516 //回文子序列，回文就是从左到右读和从右到左读的结果是一样的 //https://leetcode.cn/problems/longest-palindromic-subsequence/ class Solution { public int longestPalindromeSubseq(String s) { int len = s.length(); //dp[i][j]定义为s[i]到s[j]字符串的回文序列的长度 int[][] dp = new int[len][len]; //当dp[i][i]的时候长度为1，这是base case for(int i = 0; i < len; i++) { dp[i][i] = 1; } //把字符串折叠成一个len*len的二维数组，只需要考虑i= 0; i--) { char c1 = s.charAt(i); for(int j = i +1; j < len; j++)//注意是从i+1开始遍历 { char c2 = s.charAt(j); if(c1 == c2) { //这两个字符相等，那么意味着把索引往中间各自压缩一位得到的长度+2之后的长度就是当前的长度 dp[i][j] = dp[i+1][j-1] + 2; } else { //这是从正方形的右下角开始遍历，dp[i+1][j]和dp[i][j-1]应该是已经计算出来的值 //整个的遍历过程是i--，j++，所以已知的是i+1和j-1 dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]); } } } /* 最后遍历的的顺序是这样的： -------------i 4 -------------i 3 +++j 4 -------------i 2 +++j 3 +++j 4 -------------i 1 +++j 2 +++j 3 +++j 4 -------------i 0 +++j 1 +++j 2 +++j 3 +++j 4 */ return dp[0][len-1]; } } //判断是不是搜索二叉树 //https://leetcode.cn/problems/legal-binary-search-tree-lcci/submissions/521119932/ //搜索二叉树的表现为：中序遍历的情况下，得到的值列表是个递增的数组。 //可以有两种方式。 //递归，但是得传递min, max值 //中序遍历，然后比较前后值的是否是递增 class Solution { public boolean isValidBST(TreeNode root) { if(root == null) return false; return validBST(root, null, null); } //注意Integer作为min,max参数。 boolean validBST(TreeNode root, Integer min, Integer max){ if(null == root){ return true; } //注意这个地方要跟min和max都做比较，而且判断是否为空，这样才能让跟节点的逻辑成立。 if((null != min) && (min >= root.val)) return false; if((null != max) && (max <= root.val)) return false; //注意设置min return validBST(root.left, min, root.val) && validBST(root.right, root.val, max); } } class Solution { //需要使用--Double.MAX_VALUE表示最小值 double pre = -Double.MAX_VALUE; public boolean isValidBST(TreeNode root) { return traverse(root); } boolean traverse(TreeNode root){ //null节点，肯定得是true啊。 if(null == root){ return true; } //递归左节点 boolean res1 = traverse(root.left); if(!res1){ return false; } //左节点递归结束，这时候访问root值，和前一个值进行比对，就是中序遍历了 double current = root.val; if(current <= pre){ return false; } //访问结束，需要把当前节点的值作为前一个值，这样的话才可以进入下一个递归了。 pre = current; //访问右节点 boolean res2 = traverse(root.right); return res2; } } //判断树是不是对称的 //https://leetcode.cn/problems/dui-cheng-de-er-cha-shu-lcof/submissions/521127112/ class Solution { public boolean checkSymmetricTree(TreeNode root) { //这个技巧太聪明了，使用两个指针分别遍历左右子树并进行对比 return check(root, root); } private boolean check(TreeNode root1, TreeNode root2) { if((root1 == null) && (root2 == null)) return true; if((root1 == null) || (root2 == null)) return false;//意味着一个为Null，另外一个不为Null，这个检查很重要 //这个地方也是关键，还得调用两次check，对比root1.left和root2.right，以及roo1.right和roo2.left!!!!!! //思维上得转变，当递归到第二层之后roo1已经和root2已经不是不同的节点了，要检查是否对称，当然得left和right都得检查。 return (root1.val == root2.val)&&check(root1.left, root2.right) && check(root1.right, root2.left); } } //701 二叉树的插入操作 //https://leetcode.cn/problems/insert-into-a-binary-search-tree/ //这个问题似乎并没有涉及到插入的节点有子节点的情况，返回的根节点并没有变 class Solution { public TreeNode insertIntoBST(TreeNode root, int val) { //节点为空，直接返回新建的节点。 if(root == null) return new TreeNode(val); //已经存在节点，返回当前这个基点。 if(root.val == val) return root; //如果当前节点的值小于val，意味着需要把新节点作为当前节点的右节点。 if(root.val < val) root.right = insertIntoBST(root.right, val); //反之，则把把新节点作为当前节点的左节点。 if(root.val > val) root.left = insertIntoBST(root.left, val); //最后返回的还是当前节点。 return root; } } //450 //https://leetcode.cn/problems/delete-node-in-a-bst/ //删除二叉树节点 //核心点是先定位节点位置，一旦定位到位置之后就从左侧找到最大值或者右侧找到最小值来代替当前节点，然后再次调用函数删除节点。 //注意根节点保持不变。 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public TreeNode deleteNode(TreeNode root, int key) { //删除节点的时候有两个方式，一种是直接修改节点的值，访问的时候不需要保留上下级关系， //另外一种是直接修改节点的上下级的关系 //先检查当前节点是不是为空。 if(root == null){ return null; } if(root.val == key){ //当前节点就是要删除的节点，得进一步判断该节点的子节点的状况，保持二叉树关系 //这个地方也是很聪明的一个技巧，如果要被删除的节点只有一个子节点，那么直接返回这个子节点来代替自己 if(root.left == null){ //左节点为null，直接返回右节点，如果右节点为null，返回null，实际上相当于删除当前节点了 return root.right; } if(root.right == null){ return root.left; } //左右节点都不为Null，可以找到左侧大的节点或者右侧最小的节点来替代当前节点 //找右侧最小的节点来代替自己 TreeNode minNode = findMin(root.right); //替代而不是删除 root.val = minNode.val; //旧节点可以删除了，这时候这个旧节点肯定是个leaf节点，删除本质上上就是用null代替返回上一级。 root.right = deleteNode(root.right, minNode.val); }else if(root.val < key){ //当前节点的值小于key，意味着得到当前节点的右节点去查询. //这个地方其实是一个非常重要的点，要把返回的结果存储到root.right里面。如果子节点返回为null，实际上也就删除了一个节点了。 root.right = deleteNode(root.right, key); }else if(root.val > key){ //到左节点去查 root.left = deleteNode(root.left, key); } //我们并不删除节点，而是更新节点的值，所以可以仍然返回root return root; } private TreeNode findMin(TreeNode root){ //注意这个地方检查的是root.left != null，就是找到最小的做节点，也就是最小值 while(root.left != null){ root = root.left; } return root; } }; //https://leetcode.cn/problems/serialize-and-deserialize-bst/description/ //序列化反序列化二叉树 //449 public class Codec { private int counter = 0; // Encodes a tree to a single string. public String serialize(TreeNode root) { StringBuilder stringBuilder = new StringBuilder(); serialize(root, stringBuilder); return stringBuilder.toString(); } //使用前序遍历序列化，null使用"#,"代替，非null使用"val,"代替，需要把一个节点的左右节点都完全展现出来，这是保证序列化反序列化能工作的前提。 public void serialize(TreeNode root, StringBuilder stringBuilder) { if(root == null){ stringBuilder.append("#,"); return; } stringBuilder.append(root.val+","); serialize(root.left, stringBuilder); serialize(root.right, stringBuilder); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { String[] nodes = data.split(",");//split函数进行拆分 counter = 0; return deserialize(nodes); } public TreeNode deserialize(String[] nodes) { //递归的终止条件 if(counter >= nodes.length){ return null; } //null if(nodes[counter].equals("#")){ counter++; return null; } //parseInt函数 int val = Integer.parseInt(nodes[counter]); counter++; TreeNode treeNode = new TreeNode(val); treeNode.left = deserialize(nodes); treeNode.right = deserialize(nodes); return treeNode; } } //后序遍历的方式也可以完成这个目标，但是中序遍历达不到。后续遍历的过程注意是从末尾开始访问数据，然后右节点，然后左节点。 public class Codec { private int counter = 0; // Encodes a tree to a single string. public String serialize(TreeNode root) { StringBuilder stringBuilder = new StringBuilder(); serialize(root, stringBuilder); return stringBuilder.toString(); } public void serialize(TreeNode root, StringBuilder stringBuilder){ if(root == null){ stringBuilder.append("#,"); return; } serialize(root.left, stringBuilder); serialize(root.right, stringBuilder); stringBuilder.append(root.val + ","); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { String[] values = data.split(","); counter = values.length-1; return deserialize(values); } //后续遍历，最后一个节点是根节点，然后是右节点，然后是右节点的左右节点，然后才是根节点的左节点，总结一下就是： //在后续遍历的场景下，得从数组的末尾开始访问，然后访问右节点，然后是左节点 public TreeNode deserialize(String[] values) { if(counter < 0){ return null; } if(values[counter].equals("#")){ counter--; return null; } int value = Integer.parseInt(values[counter--]);//使用一次值，则counter移动一次 TreeNode root = new TreeNode(value); TreeNode nodeRight = deserialize(values); //counter--;//注意这个地方不应该再使用--了，因为这个地方并没有进一步读取数组，前面已经读取了 TreeNode nodeLeft = deserialize(values); //counter--;//注意这个地方不应该再使用--了 root.left = nodeLeft; root.right = nodeRight; return root; } } //https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/ //236最近公共祖先 //递归函数的最开始几行代码都是为了确定递归终止条件的，接下来才是继续遍历 //注意这道题中使用的时后序遍历 class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { //可能的情况，p或者q就是最近公共祖先之一，如果不是，那就是往上找到一个节点，通过这个节点可以遍历到p和q //输入的是根节点，而且没parent指针，只能从根节点往下遍历 //这个题目中不能根据值来进行比对，只能遍历 //基本的思路是先选择一个节点，然后从这个节点下面开始遍历，如果能找到，则是最小公共祖先。然后进一步递归左右节点，最后一个能找到的就是最小的公共祖先 //当使用后序遍历的时候，可以得到最近公共祖先。后续遍历其实就是深度优先。前序遍历是从上往下，后序遍历是从下往上。 //递归终止条件之一，没有找到节点或者root为null，直接返回null if(root == null){ return null; } //递归终止条件之二，如果当前节点是p或者q，那么返回当前节点 //p/q可能就是节点之一，直接作为root节点 if((root == p) ||(root == q)) return root; TreeNode left = lowestCommonAncestor(root.left, p,q); TreeNode right = lowestCommonAncestor(root.right, p,q); //left或者right不为空，意味着在当前节点的左右子节点找到了p和q，那么意味着当前节点就是正在查找的最近公共祖先 //两边找到p或者q，那么当前节点就是最近公共祖先 if(left != null && right != null){ return root; } //两边都没有找到，都为null if(left == null && right == null){ return null; } //其中一个为null，意味着p、q都在当前节点的左节点或者右节点，找到的这个节点也就是p或者q了，也就是最近公共祖先 return left == null? right: left; } } //https://leetcode.cn/problems/next-greater-element-i/ //496 //返回下一个大值，这是使用右侧视图 //从尾部遍历，把所有比当前值小的值给pop出来，因为当前值会盖住比它小的值 //所以得用到双层循环 public class Leetcode { Stack myStack = new Stack<>(); int[] nextGreaterNumber(int[] nums){ int length = nums.length; int[] result = new int[length]; //从末尾开始数 for(int i = length -1; i >=0; i--){ int current = nums[i]; while(!myStack.isEmpty()){ int top = myStack.peek(); if(top <= current){ //栈顶的值小于当前值，从左侧看过来，当前值会大于栈顶的值，栈顶的值就没用了，可以弹出。 myStack.pop(); }else{ //栈顶的值大于当前值，可以退出了 break; } } //如果栈为空，则右侧没有比当前值大的值 if(myStack.isEmpty()){ result[i] = -1; }else{ result[i] = myStack.peek(); } //把当前值作为栈顶的值参与下一轮比较 myStack.push(current); } return result; } public static void main(String[] args){ Leetcode leetcode = new Leetcode(); int[] nums = new int[5]; nums[0] = 2; nums[1] = 1; nums[2] = 2; nums[3] = 4; nums[4] = 3; int[] result = leetcode.nextGreaterNumber(nums); System.out.println(Arrays.toString(result)); } } //https://leetcode.cn/problems/next-greater-element-i/ //496 //返回下一个大值 //使用暴力法，先在nums2中找到nums1[i]的位置，然后从这个位置开始往后遍历查找第一个大于nums1[i]的值，如果没有找到则为-1 class Solution { public int[] nextGreaterElement(int[] nums1, int[] nums2) { int m = nums1.length; int n = nums2.length; int[] res = new int[m]; for(int i = 0; i < m; ++i){ int j = 0; //定位Nums2中nums1[i]的位置 while(j hashMap = new HashMap(); //作为单调栈 Stack stack = new Stack(); //相对nums2进行处理，把结果储存到hashmap里面 for(int i = nums2.length - 1; i >= 0; --i){ while(!stack.isEmpty() && stack.peek() <= nums2[i]){ stack.pop(); } hashMap.put(nums2[i], stack.isEmpty()?-1:stack.peek()); stack.push(nums2[i]); } //把nums2的计算结果送给res[i]，也就是nums1的计算结果 int[] res = new int[nums1.length]; for(int i =0; i < nums1.length; ++i){ res[i] = hashMap.get(nums1[i]); } return res; } } //https://leetcode.cn/problems/iIQa4I/description/ //更暖的气温 class Solution { //这题有点特殊：无效的值不能弹出，一旦弹出了，计算数量的时候就少了。 //所以，要嘛使用暴力算法。要嘛得把弹出的数据重新压栈，跟暴力解法也没啥区别了。 //改进方案：存储到Stack里面的值不能是实际值，而是要有索引信息，不但得有索引信息，还要有值信息，才能进行比较。 //可以使用pair。还可以只存储index，然后根据index访问temperatures public int[] dailyTemperatures(int[] temperatures) { int[] res = new int[temperatures.length]; //stack不存储值而是存储index Stack stack = new Stack(); for(int i = temperatures.length -1; i >= 0; --i){ while(!stack.isEmpty() && (temperatures[stack.peek()] <= temperatures[i])){ stack.pop(); } res[i] = stack.isEmpty()?0:(stack.peek() - i); //这个地方存储的是索引 stack.push(i); } return res; } } //https://leetcode.cn/problems/next-greater-element-ii/ //循环数组下一个较大值的暴力解法 class Solution { public int[] nextGreaterElements(int[] nums) { //题目的要求是返回一个数组，新数组的内容为旧数组中下一个比当前元素大的值，如果不存在则为-1。 //要求的是从元素的右侧找到更大的值，所以比较土的方法是遍历，对于每个元素都遍历一下右侧的元素。 //但是注意这里要求的是一个循环数组，所以对于每个值，理论上要遍历属组的每一个值 //是否有便捷的方案只遍历一遍就能查询出结果呢？ int[] res = new int[nums.length]; for(int i = 0; i < nums.length; i++){ res[i] = -1; for(int j = (i + 1); j < nums.length + i; j++){ int index = j%nums.length; if(nums[index] > nums[i]){ res[i] = nums[index]; break; } } } return res; } } //优化解法 class Solution { public int[] nextGreaterElements(int[] nums) { //题目的要求是返回一个数组，新数组的内容为旧数组中下一个比当前元素大的值，如果不存在则为-1。 //要求的是从元素的右侧找到更大的值，所以比较土的方法是遍历，对于每个元素都遍历一下右侧的元素。 //但是注意这里要求的是一个循环数组，所以对于每个值，理论上要遍历属组的每一个值 //是否有便捷的方案只遍历一遍就能查询出结果呢？ //对于循环数据，最简单的方法是把数组复制一份，就达到把循环平铺的目的了，但是数组的每个元素仍然需要和最多N个元素比较 int length = nums.length; int[] res = new int[length]; Stack stack = new Stack(); //循环2双倍的数量，虽然是双倍，但是后面的值会覆盖前面的值 for(int i = length*2-1; i >= 0; --i){ int index = i%length; while(!stack.isEmpty() && stack.peek() <= nums[index]){ stack.pop(); } res[index] = stack.isEmpty()?-1:stack.peek(); stack.push(nums[index]); } return res; } } //https://leetcode.cn/problems/sliding-window-maximum/ //滑动窗口最大值 //239 class Solution { class MonoStack{ private LinkedList mylist = new LinkedList(); //链表里面只保存当前窗口中比当前值大元素，小于当前元素的值都被删除。 void push(int value){ //从尾部查找，只要比当然值小的其他值都可以删除，为什么可以这样做呢？因为当前值将会是当前窗口内生命周期最长的元素，所以可以放心地删除其他小于这个元素的值。 //注意，等于当前值的元素并不会被删除，列表中可能存在重复的值 while(!mylist.isEmpty() && mylist.getLast() < value){ mylist.pollLast(); } mylist.addLast(value); } int getMax(){ //第一个值成了最大值了 return mylist.getFirst(); } void pop(int value){ //只删除第一个元素，有可能真正的元素已经被删除了，所以只能删除等于当前值的，不等于当前值的不能删除 if(mylist.getFirst() == value){ mylist.pollFirst(); } } } public int[] maxSlidingWindow(int[] nums, int k) { //这个地方也是需要注意的点len-k+1. int[] res = new int[nums.length - k + 1]; MonoStack monostack = new MonoStack(); int i = 0; //先push k个元素 for(i =0; i < k; i++){ monostack.push(nums[i]); } int counter = 0; for(;i < nums.length; i++){ //得到第一个值 res[counter++] = monostack.getMax(); //弹出左侧的第一个元素值 monostack.pop(nums[i-k]); //推入最新值 monostack.push(nums[i]); } //补充最后一个值 res[counter++] = monostack.getMax(); return res; } } //409 回文串最长长度 //https://leetcode.cn/problems/longest-palindrome/ class Solution { public int longestPalindrome(String s) { int[] count = new int[128]; int length = s.length(); for(int i = 0; i < length; i++){ count[s.charAt(i)]++; } int ans = 0; int addOne = 0; for(int v:count){ ans += v/2*2; if(v%2 != 0){ addOne = 1; } } return ans + addOne; } } //LCR 018 只取数字和字母判断是不是回文串 //https://leetcode.cn/problems/XltzEq/ class Solution { public boolean isPalindrome(String s) { int i = 0; int j = s.length() - 1; if((s == null) || s.equals("")){ return true; } while(i < j){ //统一转换成小写字母 char c1 = Character.toLowerCase(s.charAt(i)); //如果不是字母或者数字，则跳过 if(!Character.isLetterOrDigit(c1)){ i++; continue; } char c2 = Character.toLowerCase(s.charAt(j)); if(!Character.isLetterOrDigit(c2)){ j--; continue; } if(c1 != c2){ return false; } i++; j--; } return true; } } //LCR 027 判断是不是回文链表,这个解法是借助栈 //https://leetcode.cn/problems/XltzEq/ class Solution { public boolean isPalindrome(ListNode head) { Stack mystack = new Stack(); ListNode node = head; while(null != node){ mystack.push(node.val); node = node.next; } int size = mystack.size()/2; int i = 0; node = head; while(i <= size - 1){ int top = mystack.pop(); if(node.val != top){ return false; } node = node.next; i++; } return true; } } //不使用栈，而是使用递归，链表也是特殊的树，也具备递归或者前后序遍历的属性 class Solution { //全局变量 ListNode left = null; public boolean isPalindrome(ListNode head) { left = head; return traverse(head); } private boolean traverse(ListNode right){ if(right == null){ return true; } boolean result = traverse(right.next); //递归完成这时候达到链表的尾部 //这个地方是关键，有个&&的过程 result = result && (left.val == right.val); left = left.next; return result; } } //https://leetcode.cn/problems/subsets/description/ //78：子集 class Solution { public List> subsets(int[] nums) { ArrayList> res = new ArrayList>(); //这个题目的核心是:[1,2,3]为[1,2]+3,[1,2]为[1]+2,[1]实际上是{}+1，所以按照这个方式，可以从index 0开始添加，一直递归。 backtrack(res, nums, 0); return res; } void backtrack(ArrayList> res, int[] nums, int index){ if(index >= nums.length){ return; } //第一个要特殊处理一下，添加一个空的列表先。 if(index == 0){ ArrayList currentList = new ArrayList(); res.addLast(currentList); } int currentCount = res.size(); for(int i = 0; i < currentCount; i++){ //把每个列表都取出来，添加一个新的元素，并且又添加到返回结果中 ArrayList tmp = (ArrayList)res.get(i); ArrayList newList = new ArrayList(tmp); newList.addLast(nums[index]); res.addLast(newList); } backtrack(res, nums, index + 1); } } //这才是真正的回溯方法 class Solution { public List> subsets(int[] nums) { //结果 List> result = new ArrayList<>(); //创建一个空链表 ArrayList currentList = new ArrayList<>(); backtrack(nums, 0, currentList, result); return result; } private void backtrack(int[] nums, int start, List subset, List> result) { //复制一个链表 ArrayList newList = new ArrayList<>(subset); result.addLast(newList); // 添加当前子集到结果中 //这个循环也是一个终止条件 for (int i = start; i < nums.length; i++) { //增加当前元素放到子集中 subset.addLast(nums[i]); // 递归生成剩余的子集 backtrack(nums, i + 1, subset, result); // 回溯，移除当前元素 subset.removeLast(); } } } //46 //返回一个数组的全排列 //https://leetcode.cn/problems/permutations/solutions/218275/quan-pai-lie-by-leetcode-solution-2/ //这个也是使用回溯，关键是得对数组循环，而且得检查添加进去的值是不是已经达到的数量要求 //总结一下回溯方法：回溯方法其实也是递归调用，既然是递归调用就得设定递归终止的条件 //回溯方法意味着要先添加元素再删除元素，进入下一个循环。所以回调函数在回溯场景下是需要在一个for循环里面调用的。 //实际上就形成了for循环里面套用for循环再反复套用for循环，所以设定开始条件和终止条件非常重要。 //思考一下什么情况下需要for循环？如果数据选择的时候需要根据数组来选择才可以，那需要在函数外面套一层for循环，否则就不需要用到for循环直接递归就可以了。 class Solution { public List> permute(int[] nums) { List> res = new ArrayList>(); List currentlist = new ArrayList(); permute(nums, 0, res, currentlist); return res; } void permute(int[] nums, int start, List> res, List currentlist){ //如果当前列表已经足够长了，就可以创建一个新的列表添加到结果表中 if(currentlist.size()>= nums.length){ List newlist = new ArrayList(currentlist); res.addLast(newlist); } for(int i = start; i <(nums.length+start); i++){ //实际上要做循环访问 int index = i%nums.length; //如果已经添加了当前节点的值，则可以跳过 if(currentlist.contains(nums[index])) continue; //添加一个值到列表中去 currentlist.addLast(nums[index]); //进入递归 permute(nums, i+1, res, currentlist); //删除一个才可以进行下一个回溯 currentlist.removeLast(); } } } //https://leetcode.cn/problems/subarray-sum-equals-k/description/ //560 //和为 K 的子数组 //暴力解法 class Solution { public int subarraySum(int[] nums, int k) { int res = 0; int[] sums = new int[nums.length + 1]; //先求出连续nums[0..i]的和。这个技巧叫做前缀和，也就是循环得到前N个数的和 //sums[0] = nums[0] //sums[1] = sums[0] + nums[1] //sums[2] = sums[1] + nums[2] //实际上下面的代码的索引+1了！ for(int i = 0; i < nums.length; i++){ sums[1+i] = sums[i] + nums[i]; } for(int i = 1; i <= nums.length; i++){ //把前缀和挨个减去nums的值，如果等于K，则意味着这是一个目标子数组。注意这个地方求的是子数组，也就是说是连续的！ for(int j = 0; j < i; j++){ //暴力相减后得到的则为nums[i..j]的和，这个地方非常重要，并不是sums[i]-nums[j]，而是sums[i]-sums[j]，nums[j]只是一个值，而sums[j]是N个值的前缀和 if((sums[i] - sums[j]) == k){ res++; } } } return res; } } //206 //https://leetcode.cn/problems/reverse-linked-list/ //链表反转 class Solution { public ListNode reverseList(ListNode head) { if((null == head) || (head.next == null)){ return head; } //pre默认为null ListNode pre = null; //使用curr从head开始遍历 ListNode curr = head; while(curr != null){ //先备份一下next ListNode next = curr.next; //把当前节点指向前一个节点 curr.next = pre; //前一个节点指向当前节点 pre = curr; //开始下一个 curr = next; } //只能是pre，因为curr在循环的最后已经是null了 return pre; } } //翻转链表的前N个节点 class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } }; public class Main { ListNode successor = null; public static void main(String[] args) { ListNode head = new ListNode(1); ListNode current = new ListNode(2); head.next = current; ListNode tmp = new ListNode(3); current.next = tmp; current = tmp; tmp = new ListNode(4); current.next = tmp; current = tmp; tmp = new ListNode(5); current.next = tmp; current = tmp; tmp = new ListNode(6); current.next = tmp; current = tmp; Main mymain = new Main(); ListNode newhead = mymain.reverseN(head, 3); System.out.println(""); } private ListNode reverseN(ListNode head, int n) { if((head == null) || (head.next == null) || (n == 1)){ //递归到最后要反转的节点，然后记录下一个节点 successor = head.next; return head; } //这个递归到最后要反转的节点上 ListNode res = reverseN(head.next, n -1); //把翻转的倒数第二个节点指向倒数第一个节点 head.next.next = head; //第一个节点接下来指向没有翻转的开始节点 head.next = successor; return res; } } //https://leetcode.cn/problems/reverse-linked-list-ii/description/ //翻转链表的一部分 class Solution { //记录最后反转的一个节点的下一个几点 ListNode successor = null; public ListNode reverseBetween(ListNode head, int left, int right) { //递归，要构造base case if(left == 1){ return reverseN(head, right); } //注意这个地方left -1，right -1。right - left的数量保持不变!!!其实就是指针往下挪动，起始、终止的索引都减1，但是索引之间的数量没变 ListNode newhead = reverseBetween(head.next, left - 1, right-1); //建立连接关系 head.next = newhead; return head; } public ListNode reverseN(ListNode head, int n){ if(n == 1){ successor = head.next; return head; } //一直移动指针 ListNode tmp = reverseN(head.next, n -1); //反向 head.next.next = head; //指向最后一个指针 head.next = successor; return tmp; } } //https://leetcode.cn/problems/generate-parentheses/ //22 //括号生成 class Solution { public List generateParenthesis(int n) { if(n == 0){ return new LinkedList(); } LinkedList res = new LinkedList(); StringBuilder stringBuilder = new StringBuilder(); backtrack(res,n,n, stringBuilder); return res; } //使用left,right来控制回溯，然后判断left和right的数量进行裁枝，回溯得尝试添加左右括号再会退 void backtrack(LinkedList res, int left, int right, StringBuilder stringBuilder){ if((left < 0) || (right < 0)){ return; } //剩余的左括号应该比剩余的右括号多，不合法。剩余的左括号应该小于等于剩余的右括号 if(left > right) return; //left和right都消耗完了,这应该是个合法的组合，因为已经把非法的去掉了 if(left == 0 && right == 0){ res.addLast(stringBuilder.toString()); } //这个地方也可以使用for循环来代替，遍历可能的组合，这个地方只有左右括号，所以不用for循环也OK //但是需要注意，这个地方使用了left和right来作为回溯的参数 stringBuilder.append('('); backtrack(res, left - 1, right, stringBuilder); stringBuilder.deleteCharAt(stringBuilder.length()-1); stringBuilder.append(')'); backtrack(res, left, right-1, stringBuilder); stringBuilder.deleteCharAt(stringBuilder.length()-1); } } class Solution { public List generateParenthesis(int n) { LinkedList res = new LinkedList(); if(n == 0){ return res; } //实际上长度为2n，每个职位可以是左括号也可以是右括号，就是要枚举所有的可能性，并且判断合法的组合。 StringBuilder sb = new StringBuilder(); backtrace(2*n, 0, 0, 0, res, sb); return res; } void backtrace(int n, int start, int leftCount, int rightCount, LinkedList res, StringBuilder sb){ if(rightCount > leftCount){ //右括号不能大于左括号，否则也是错误的 return; } //终止了，实际上应该不会触发 if(start > n){ return; }else if(start == n){ if(leftCount == rightCount){ //这是一个合法的组合，添加到结果列表里面 res.add(sb.toString()); } return; } //每个位置都可能有两种选择 sb.append('('); backtrace(n, start+1, leftCount+1, rightCount, res, sb); //回退 sb.deleteCharAt(sb.length() - 1); sb.append(')'); backtrace(n, start+1, leftCount, rightCount+1, res, sb); //回退 sb.deleteCharAt(sb.length() - 1); } } //https://leetcode.cn/problems/pancake-sorting/description/ //969 //煎饼排序 class Solution { public List pancakeSort(int[] arr) { //进行反转其实是个递归操作，对n个元素找到最大的那个元素把这个最大的元素翻转到底部，进而对n-1个元素再次查找最大的元素进行反转，重复这个过程 //要把最大的那个元素翻转最多进行2次操作，第一次操作找到最大的元素并且把它反转到最上方，然后再进行一次反转放到最下方 //这个题目中的k表示每次要反转数组中的前k个元素，经过n次翻转后达到有序状态 //注意进行反转的时候其实是要对前k个数组元素进行反转 LinkedList res = new LinkedList(); sort(res, arr.length, arr); return res; } void sort(LinkedList res, int n, int[] arr){ if(n == 0){ return; } //查找前n个元素中最大的元素 int maxIndex = findMax(arr, n); if(n == (maxIndex+1)){ //当前最大的元素已经在最下方了，不需要再进行反转，进入下一个循环 sort(res, n - 1, arr); }else{ //最大元素不在最下方，需要进行两次反转 res.add(maxIndex + 1); //先把最大的元素反转到最上面 reverse(maxIndex, arr); res.add(n); //然后再次反转放到最下面 reverse(n-1, arr); //进入下个循环 sort(res, n-1, arr); } //对前n个元素进行反转把最大的元素放到最底部 //对剩余的n个元素进行递归 } int findMax(int[] arr, int n){ int max = arr[0]; int index = 0; for(int i = 0; i < n; i++){ if(arr[i] >= max){ max = arr[i]; index = i; } } return index; } void reverse(int lastindex, int[] arr){ int i = 0; int j = lastindex; while(i < j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; i++; j--; } } } //https://leetcode.cn/problems/flatten-nested-list-iterator/description/ //341 //扁平化嵌套列表迭代器 /** * // This is the interface that allows for creating nested lists. * // You should not implement it, or speculate about its implementation * public interface NestedInteger { * * // @return true if this NestedInteger holds a single integer, rather than a nested list. * public boolean isInteger(); * * // @return the single integer that this NestedInteger holds, if it holds a single integer * // Return null if this NestedInteger holds a nested list * public Integer getInteger(); * * // @return the nested list that this NestedInteger holds, if it holds a nested list * // Return empty list if this NestedInteger holds a single integer * public List getList(); * } */ public class NestedIterator implements Iterator { private Iterator it; public NestedIterator(List nestedList) { List result = new LinkedList<>(); //遍历每个节点 for(NestedInteger node: nestedList){ traverse(node, result); } //返回iterator this.it = result.iterator(); } @Override public Integer next() { return it.next(); } @Override public boolean hasNext() { return it.hasNext(); } private void traverse(NestedInteger root, List result){ //leaf节点，直接添加 if(root.isInteger()){ result.add(root.getInteger()); //返回 return; } //不是leaf节点，递归当前节点的子节点 for(NestedInteger child: root.getList()){ traverse(child, result); } } } /** * Your NestedIterator object will be instantiated and called as such: * NestedIterator i = new NestedIterator(nestedList); * while (i.hasNext()) v[f()] = i.next(); */ //1011 //https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/submissions/531203930/ //D天内送达包裹的能力 class Solution { public int shipWithinDays(int[] weights, int days) { //这种查询最大、最小值的题目，本质上是一个try的过程，使用不同的值来try，一直try到合适的值，所以肯定得有一个循环尝试不同的值。 //怎样可以设置最小值和最大值来作为搜索范围呢？ //最小值是1，最大值呢？最大值就是所有这些货物的总量 //最小值可以进一步计算为单批货物的最大值，因为不可以把一批货物分批运送，但是可以把多批货物合并了一起运送 int total = 0; int max = 0; for(int weight: weights){ total += weight; max = Math.max(max, weight); } int left = max; int right = total + 1; while(left < right){ int middle = left + (right - left)/2; boolean canDo = canDeliver(middle, weights, days); if(canDo){ //可以完成运输，但是可能还不是最小值，继续搜索 right = middle; }else{ //不能完成运输，需要提高运力 left = middle +1; } } return left; } boolean canDeliver(int target, int[] weights, int days){ //计算运力为target的情况下，需要的天数 int daysNeeded = 1; int leftCapacity = target; //这里关键的地方是货物不允许被拆分而且必须按照顺序 int i = 0; while(i < weights.length){ int weight = weights[i]; if(weight <= leftCapacity){ //当前剩余的空间还允许装载，继续尝试下一个货物 leftCapacity -= weight; i++; }else{ //已经装满了，得等新的一天 daysNeeded++; leftCapacity = target; } } if(daysNeeded <= days){ return true; }else{ return false; } } } class Solution { public int shipWithinDays(int[] weights, int days) { //这种查询最大、最小值的题目，本质上是一个try的过程，使用不同的值来try，一直try到合适的值，所以肯定得有一个循环尝试不同的值。 //怎样可以设置最小值和最大值来作为搜索范围呢？ //最小值是1，最大值呢？最大值就是所有这些货物的总量 //最小值可以进一步计算为单批货物的最大值 int total = 0; int max = 0; for(int weight: weights){ total += weight; max = Math.max(max, weight); } int left = max; int right = total + 1; while(left < right){ int middle = left + (right - left)/2; boolean canDo = canDeliver(middle, weights, days); if(canDo){ //可以完成运输，但是可能还不是最小值，继续搜索 right = middle; }else{ //不能完成运输，需要提高运力 left = middle +1; } } return left; } boolean canDeliver(int target, int[] weights, int days){ int i = 0; for(int day = 0; day < days; day++){ //每天的运力都是target运力 int maxCap = target; //看看当前剩余的运力还能运输多少批货物 while(maxCap >= weights[i]){ maxCap -= weights[i]; i++; //这个地方是关键，每次i变化的时候就检查一下是不是已经运完了 if(i == weights.length){ return true; } } } return false; } } //42 //接雨水 //https://leetcode.cn/problems/trapping-rain-water/ class Solution { public int trap(int[] height) { int n = height.length; if(n == 0){ return 0; } //计算出某一节点左侧的max，如果左侧的节点都小于当前节点，则max为当前节点 int[] leftMax = new int[n]; leftMax[0] = height[0]; for(int i = 1; i < n; i++){ leftMax[i] = Math.max(leftMax[i-1], height[i]); } int[] rightMax = new int[n]; rightMax[n-1] = height[n-1]; for(int i = n-2; i >= 0; i--){ rightMax[i] = Math.max(rightMax[i+1], height[i]); } int ans = 0; for(int i =0; i < n; ++i){ //取左右的max的最小值减去当前值就是当前节点上的容量 ans += Math.min(leftMax[i], rightMax[i]) - height[i]; } return ans; } } class Solution { public int trap(int[] height) { if(height.length ==0 ){ return 0; } int n = height.length; //使用双指针统计0..left, right..n-1节点上的最大值 int lmax = height[0]; int rmax = height[n-1]; //使用双指针 int left = 0; int right = n -1; int ans = 0; while(left < right){ lmax = Math.max(lmax, height[left]); rmax = Math.max(rmax, height[right]); //求得最小值，使用最小值参与计算 if(lmax < rmax){ //lmax是比较小的值 ans += lmax - height[left]; //移动的是小值的一方 left++; }else{ //rmax的值比较小 ans += rmax - height[right]; right--; } } return ans; } } //https://leetcode.cn/problems/remove-duplicates-from-sorted-array/ //删除有序数组中的重复项 //可以有简单的解法但是效率低一些：新建一个新的数组，挨个比较拷贝 //26 class Solution { public int removeDuplicates(int[] nums) { if(nums.length <= 1){ return nums.length; } int left = 0; int right = 1;//也算是快慢指针了 while(right < nums.length){ if(nums[left] != nums[right]){ //如果前一个数和现在的数不一样，那就做一下拷贝 //默认left为0，right为1，两个的值是不一样的，但是先left++的，两个索引值就一样了，相当于原地拷贝，所以数值没有实际变化。 left++; nums[left] = nums[right]; }else{ //如果相等，不需要拷贝，left也不需要动。接下来right++移到下一个元素 } //一个循环，这个right肯定得递增 right++; } return left + 1; } } //https://leetcode.cn/problems/remove-duplicates-from-sorted-list/description/ //83 //删除节点中重复的元素 class Solution { public ListNode deleteDuplicates(ListNode head) { if(head == null){ return null; } ListNode slow = head; ListNode fast = head.next; while(fast != null){ if(slow.val != fast.val){ //不相等，则slow.next指向fast，建立起连接 slow.next = fast; //连接建立完了，slow再次指向fast，也就是上一个节点 slow = fast; } //不管相等不相等，fast都会向后移。指向下一个节点 fast = fast.next; } //最后一个节点清空。 slow.next = null; return head; } } //https://leetcode.cn/problems/longest-palindromic-substring/solutions/255195/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/ //5 //寻找最长回文字符串 class Solution { //这是暴力解法，假设是左侧的字符是回文串的开始 public String longestPalindrome(String s) { int len = s.length(); if(len <= 1){ return s; } int longest = 0; int start = 0; String substring =null; while(start < len){ int end = len -1; while(start < end){ if(isPalindrome(s, start, end)){ if((end-start+1) > longest ){ longest=end-start+1; substring = s.substring(start, end+1); } } end --; } start++; } if(null == substring){ substring = s.substring(0, 1); } return substring; } boolean isPalindrome(String s, int start, int end){ while(start < end){ if(s.charAt(start) != s.charAt(end)){ return false; } start++; end--; } return true; } } class Solution { //优化解法，假设某一个字符是回文字符串的中间，需要考虑字符串长度为基数或者偶数的场景 //核心思想是中心扩散法。中心的left,right的值可能一致，基数，不一致则为偶数。 //本质上还是双指针的思想。 public String longestPalindrome(String s) { String res =""; int len = s.length(); //记录的是start和end int start = 0; int end = 0; for(int i = 0; i < len; i++){ int len1 = palindrome(s,i,i); int len2 = palindrome(s,i,i+1); int max = Math.max(len1, len2); if(max > (end-start)){ start = i - (max-1)/2;//长度-1 end = i + max/2; } } return s.substring(start, end+1); } //中心向两端匹配 int palindrome(String s, int left, int right){ while((left >= 0) && (right < s.length()) && (s.charAt(left) == s.charAt(right))){ left--; right++; } //这是个注意点，可以实际比划一下。 return right - left - 1; } } //https://leetcode.cn/problems/jump-game/description/ //55 //跳跃游戏 //核心思想是使用i+nums[i]计算出从当前位置可以向前跳跃的最长距离，遍历所有的位置，每次遍历的时候都更新longest距离，当到达一个位置i，i > longest，意味着i不可到达 class Solution { public boolean canJump(int[] nums) { //nums[i]表示可以跳跃的最大长度，但是实际上可以跳跃小于这个长度 //最关键的是不能跳到长度为0的位置上 //暴力的方式，使用递归一个尝试，如果跳到为0的表示失败，否则就递归到数组结尾 int n = nums.length; //farthest表示index i上最远可以到达的位置。如果farthest <= i，则意味着当前节点不可到达。 int farthest = 0; for(int i = 0; i < n; i++){ //i是位置，farthest为最远可以到达的位置，i <= farthest表示当前位置是可到到的。 if(i <= farthest){ //当前位置可到达，继续下一个节点的检查 //i+nums[i]为当前节点可以到达的位置。 farthest = Math.max(farthest, i + nums[i]); //如果farthest可以达到最后节点 if(farthest >= n - 1){ return true; } }else{ //i > farthest表示什么呢？表示当前位置不可到达，可以直接退出去了 return false; } } //到达最后的位置了，应该return true还是false？实际证明，这个地方实际不可到达。 return true; } } //45 //https://leetcode.cn/problems/jump-game-ii/ //跳跃游戏2，最少跳跃次数 //核心思想是每次选择都跳跃最远，得标记每次跳跃的结束点。要统计的最小跳跃次数，那么在每次跳跃的结束点才需要做++操作。maxposition每个节点都需要计算。 class Solution { //这题不一样的点在于求最小的跳跃次数 //求极值意味着得尝试才能得到不同的值 //实际上是要针对每个步骤做尝试求最大值，比如第一个节点为2，那么就有两种跳跃选择，跳1和跳2，再进一步根据跳1或者跳2进行递归 //最后看看哪个跳跃路径最后达到最后一个节点 //有一个观点需要转变：跳跃值是最大值，实际跳跃的步数可以小于这个最大值 //所以，如果我们每次跳跃的时候都判断一下下一次跳跃可能最大的值， //那么我们只要每次跳跃前都预先判断下一次跳跃的最远距离就可以选择当前要怎么跳跃了。 //总结一下：每次跳到下一次能跳到最远的地方，重复这个过程 public int jump(int[] nums) { int length = nums.length; //初始值很重要 int end = 0; //跳跃的最远距离,记录[i..end]能跳到的最远距离 int maxPosition = 0; //跳跃的次数 int steps = 0; //为什么是length - 1呢？因为最后一个节点最终点，不需要参与跳跃 for(int i = 0; i = (total -1)){ return 0; } //已经计算过了，不需要再重新计算，直接返回备忘录的值 if(memo[p] != total){ return memo[p]; } //获取当前p的steps，也就是最远能跳的位置 int steps = nums[p]; //遍历steps的每个可能值，进行递归，并得到最小值作为dp[i]的值 for(int i = 1; i <= steps;i++){ //递归解决子问题 int subProblem = dp(nums, total, p+i); //要得到一个最小值作为结果 memo[p] = Math.min(memo[p], subProblem + 1); } //返回最后的结果 return memo[p]; } } class Solution { int[] memo = null; public int jump(int[] nums) { int len = nums.length; memo = new int[len]; //dp[i]定义为索引i节点最少需要跳跃的步数 Arrays.fill(memo, len); //第二个参数为起始索引 return mydp(nums, 0); } public int mydp(int[] nums, int index){ int len = nums.length; //base case，最后的节点不需要再跳转 if(index >= len-1){ return 0; } //memo[index]已经计算过，不需要再重新计算，直接返回 if(memo[index] != len){ return memo[index]; } //当前节点可以跳跃的最多步数 int steps = nums[index]; //挨个尝试，得到最小值 for(int i = 1; i <= steps; i++){ int step = index + i; //子问题的step是关键参数 int subproblem = mydp(nums, step); //最后是要存储到memo里面去，反复比较取得最小值，注意subproblem+1，否则永远得到0。状态变化值！ memo[index] = Math.min(memo[index], subproblem+1); } return memo[index]; } } //https://leetcode.cn/problems/non-overlapping-intervals/description/ //435 //无重叠区间 class Solution { //求的是移除的最小数量，是剩余区间不重叠。只要找到结束时间最早第一个节点，移除和第一个区间有重叠的所有区间，剩余的就是不重叠的两个区间。 public int eraseOverlapIntervals(int[][] intervals) { if(intervals.length == 0){ return 0; } Arrays.sort(intervals, new Comparator(){ public int compare(int[] intervals1, int[] intervals2){ //compare如果是o1-o2是升序，如果是o2-o1是降序。 return intervals1[1] - intervals2[1]; } }); int n = intervals.length; //intervals[i][0]是left, intervals[i][1]是right int right = intervals[0][1]; int ans = 1; //处理排序后的数组 for(int i = 1; i < n; i++){ //如果这个数组的left大于等于当前的right，不重叠了，进入新的区域了。 if(intervals[i][0] >= right){ ++ans; //启用新的right right = intervals[i][1]; } } //ans为不重叠的区间数量，那么剩余的那些区间都是有重叠的，也就是要移除的数量 return n - ans; } } //452 //用最少数量的箭引爆气球 //https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/ class Solution { public int findMinArrowShots(int[][] points) { if(points.length == 0){ return 0; } //先排序 Arrays.sort(points, new Comparator(){ //注意是public public int compare(int[] o1, int[] o2){ //升序排序,可能越界，所以用直接比较的方法 if(o1[1] > o2[1]){ return 1; }else if(o1[1] < o2[1]){ return -1; }else{ return 0; } } }); int count = 1; //取排序后的最小值的end int end = points[0][1]; for(int[] point: points){ //如果这个节点的start > end，则进入新的区域 if(point[0] > end){ count++; //启用新的最小值的end end = point[1]; } } return count; } } //https://leetcode.cn/problems/valid-parentheses/ //20 //判断括号合法性 class Solution { public boolean isValid(String s) { int len = s.length(); Stack stack = new Stack(); for(int i = 0; i < len; i++){ char c = s.charAt(i); //左括号直接放进去 if((c == '(') || (c == '{') || (c == '[')){ stack.push(c); }else{ //有括号，如果栈为空，则非法 if(stack.empty()){ return false; } //检查括号是否匹配 if(c == ']'){ //如果top是[，则是合法的 char top = stack.peek(); if(top == '['){ stack.pop(); }else{ return false; } }else if(c == ')'){ //如果top是(，则是合法的 char top = stack.peek(); if(top == '('){ stack.pop(); }else{ return false; } }else if(c == '}'){ //如果top是{，则是合法的 char top = stack.peek(); if(top == '{'){ stack.pop(); }else{ return false; } } } } if(stack.empty()){ return true; }else{ return false; } } } //855 //https://leetcode.cn/problems/exam-room/description/ //考场就坐 //53 //最大子数组和 //https://leetcode.cn/problems/maximum-subarray/ class Solution { public int maxSubArray(int[] nums) { //假设也是使用动态规划的方式 //总结一下：子数组可能仅仅是依赖前一项dp值，而子序列则可能需要依赖前面前面的dp值，所以还需要二次遍历 int res = nums[0]; //定义dp[i]为以nums[i]为结束的最大连续子数组的和 int len = nums.length; int[] dp = new int[len]; dp[0] = nums[0]; //从i=1开始计算，因为要拿dp[i-1]来判断是否是负数 for(int i = 1; i