LeetCode 75 - 每日一题

## [283. 移动零 - 力扣（LeetCode）](https://leetcode.cn/problems/move-zeroes/description/?envType=study-plan-v2&envId=leetcode-75) 题目描述 ​ 给定一个数组，将0元素移动到数组末尾，其他元素保持相对顺序。要求不能引入额外的空间。 思路 * 要求不能使用额外的空间，即对原数组进行修改 * 双指针，一个nonZero指针用于指向非0元素的存储下标， 一个i指针遍历数组找出非0元素。找到非0元素存就行了。 * 之后对剩余元素补0. ```java class Solution { public void moveZeroes(int[] nums) { int nonZero = 0; // 将所有非零元素前移 for (int i = 0; i < nums.length; i++) { if (nums[i] != 0) { nums[nonZero++] = nums[i]; } } // 将剩余位置填充为零 for (int i = nonZero; i < nums.length; i++) { nums[i] = 0; } } } ``` 优化写法 * 使用双指针 + 交换 * 一个nonZero 指针 指向非0元素存储的下标。 * 一个i指针，从前向后遍历找出非0元素 * 两个指针值交换，交换后给当前元素赋值为0，因为当前的值已经移动到前面了，该位置就是空的也就是0 ```java class Solution { public void moveZeroes(int[] nums) { int nonZero = 0; // 记录下一个非零元素应该放置的位置 for (int i = 0; i < nums.length; i++) { if (nums[i] != 0) { // 交换当前元素和nonZero位置的元素 int temp = nums[i]; nums[i] = 0; // 将当前位置设为0 nums[nonZero++] = temp; // 将非零元素放到前面 } } } } ``` 我的更多题解：[hnsqls/algorithm-ls: 数据结构，算法](https://github.com/hnsqls/algorithm-ls)

LeetCode 75题 -每日一题

## [334. 递增的三元子序列 - 力扣（LeetCode）](https://leetcode.cn/problems/increasing-triplet-subsequence/description/?envType=study-plan-v2&envId=leetcode-75) 题目描述 ​ 一个数组，判断是否存在至少3个元素递增趋势（存在 i < j< k 满足 nums[i] < nums[j]< nums[k]）。 思路 * 三循环---超时 * 动态规划-超时 * 贪心可以 * 每一步选择中都采取当前状态下最优（即最有利）的选择，从而希望导致结果是全局最优的算法 * 定义 first ,second,遍历，first 存最小的，second 存第二小的，如果还有比这俩更大的就是有解。 * 为了找到这样的三元组，我们可以维护两个变量 `first` 和 `second`，分别表示当前找到的最小和次小的数。通过遍历数组，我们不断更新这两个变量，并在找到一个数大于 `second` 时确认存在递增的三元组。 ```java class Solution { public boolean increasingTriplet(int[] nums) { int first = Integer.MAX_VALUE; int second = Integer.MAX_VALUE; for(int num : nums){ if(num <= first) first = num; else if(num <= second) second = num; else{ return true; } } return false; } } ``` ​

LeetCode 75 部分

LeetCode 75 =========== [1768. 交替合并字符串 - 力扣（LeetCode）](https://leetcode.cn/problems/merge-strings-alternately/description/?envType=study-plan-v2&envId=leetcode-75) ------------------------------------------------------------------------------------------------------------------------------------------- 题目描述 ``` 两个字符串，每个字符串都拆成字符，交替拼接，长的字符串（剩余的字符） 拼接其后。 ``` 思路 * 根据短字符的长度进行遍历，最后拼接上长字符的剩余字符 ```java class Solution { public String mergeAlternately(String word1, String word2) { int minSize = Math.min(word1.length(),word2.length()); StringBuilder res = new StringBuilder(); for(int i = 0 ;i < minSize ;i ++){ res.append(word1.charAt(i)); res.append(word2.charAt(i)); } // 处理剩余字符 if(word1.length() > minSize){ res.append(word1.substring(minSize)); } // 处理剩余字符 if(word2.length() > minSize){ res.append(word2.substring(minSize)); } return res.toString(); } } ``` [1071. 字符串的最大公因子 - 力扣（LeetCode）](https://leetcode.cn/problems/greatest-common-divisor-of-strings/description/?envType=study-plan-v2&envId=leetcode-75) ------------------------------------------------------------------------------------------------------------------------------------------------------ 题目描述 ``` 给出两个字符串，找出最长的公因子（比如 str1 = "ABCABC", str2 = "ABC"， 则最长公因子是“ABC”） ``` 思路 * 最长公因子，最长也就是短串 优化思路 * str1 + str2 = str2 + str1 的时候才会有解，因为有解的情况下，str1可以被除尽，str2也可以被除尽，当然str1+str2 可以被除尽。 * 如果存在这样的字符串x，那么x的长度必须是两个字符串长度的公约数。 ```java class Solution { public String gcdOfStrings(String str1, String str2) { // 检查两个字符串连接后是否相等 // 假设str1是N个x，str2是M个x，那么str1+str2肯定是等于str2+str1的。 if (!(str1 + str2).equals(str2 + str1)) { return ""; } // 计算两个字符串长度的最大公约数 int gcdLength = gcd(str1.length(), str2.length()); // 返回最大公约数长度的前缀子串 return str1.substring(0, gcdLength); } // 计算最大公约数的辅助方法 private int gcd(int a, int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } } ``` [1431. 拥有最多糖果的孩子 - 力扣（LeetCode）](https://leetcode.cn/problems/kids-with-the-greatest-number-of-candies/?envType=study-plan-v2&envId=leetcode-75) ------------------------------------------------------------------------------------------------------------------------------------------------ 题目描述 ``` 一群孩子每个有都拥有n个糖果，现在你有m个糖果，你选择将糖果给某个孩子，判断该孩子是不是拥有最多的糖果数 ``` 思路 * 先找出最多拥有的糖果数 * 遍历如果将自己的糖果全部给该孩子，是否小于最多的糖果数。 ```java class Solution { public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) { int temp = 0; for(int i = 0; i < candies.length; i ++){ if(candies[i] >= temp){ temp = candies[i]; } } List res = new ArrayList<Boolean>(candies.length); for(int i = 0; i < candies.length; i ++){ if(candies[i] + extraCandies >= temp){ res.add(true); }else{ res.add(false); } } return res; } } ``` [605. 种花问题 - 力扣（LeetCode）](https://leetcode.cn/problems/can-place-flowers/description/?envType=study-plan-v2&envId=leetcode-75) ------------------------------------------------------------------------------------------------------------------------------- 题目描述 ``` 一个数组，已经存在一部分元素（不能相邻存在元素），要求插入n个元素，但是不能相邻，判断该n个元素是否能插入。 ``` 思路 * 根据数组大小判断最多可以存多少元素 * 比如说偶数组长度n，最多只能存 n/2. * 奇数，可以存n/2 或者 n/ 2 + 1.(根据第一个元素)------有问题不能这莫分析 * <img src="https://pic.code-nav.cn/post_picture/1813946725418893314/tpk52zGXL5yOTfGP.png" alt="" width="100%" /> ```java class Solution { public boolean canPlaceFlowers(int[] flowerbed, int n) { int cnt = 0; // 计数 for(int i = 0; i< flowerbed.length;i ++){ if(flowerbed[i] == 1) { cnt ++; } } // 最多可以存 //偶数 int max= 0; if(flowerbed.length % 2 == 0){ max = flowerbed.length / 2; } // 奇数 else{ if(flowerbed[0] == 1){ max = flowerbed.length/ 2 +1; } else{ max = flowerbed.length / 2; } } if(cnt + n > max){ return false; } return true; } } ``` 错误  分析：思路有问题，我上述的设想奇数长度的大小，最多可以判断只有在开头种植了才能+1,忽略了结尾，比如上述。 经过实验，对于过一个数组，间隔插入的最大值： 偶数长度 n/2, 奇数长度 (n+1)/2. 但是对于已经存在数据的数组，就不能按上述计算，因为，插入的位置同时可以在偶数位置并且在奇数位置上。 优化思路 * 查找数组的连续0 * 连续0在中间 最多可以插入 (n -1）/ 2 * 连续0 在两边， 最多可以插入 n / 2 如下图 连续0在数组的中间的情况：  连续0在数组两边的情况：  优化思路 * 贪心，能种就种 ```java class Solution { public boolean canPlaceFlowers(int[] flowerbed, int n) { int count = 0; int i = 0; while (i < flowerbed.length) { if (flowerbed[i] == 0) { boolean canPlace = (i == 0 || flowerbed[i - 1] == 0) && // 左边没有花或是数组开头 (i == flowerbed.length - 1 || flowerbed[i + 1] == 0); // 右边没有花或是数组结尾 if (canPlace) { flowerbed[i] = 1; // 种花 count++; if (count >= n) { return true; } i += 2; // 跳过下一个位置，因为不能相邻 // 检查是否能种花，左右都没中种花就可以种花，考虑边界情况，对于边界开头，只需要确保其后没有种花，对于结尾的边界，只需要前面没有种花 //开头边界 boolean first = (i==0) && (flowerbed[i+1] == 0); //结尾边界 boolean end =(i == flowerbed.length -1) && (flowerbed[i-1] == 0); // 中间 boolean center = (flowerbed[i-1] ==0 && flowerbed[i + 1] == 0); } else { i++; } } else { i += 2; // 已经有花，跳过下一个位置 } } return count >= n; } } ``` 边界问题处理了好久，看一下我最初的处理边界 ```java // 检查是否能种花，左右都没中种花就可以种花，考虑边界情况，对于边界开头，只需要确保其后没有种花，对于结尾的边界，只需要前面没有种花 //开头边界 // boolean first = (i==0) && (flowerbed[i+1] == 0); if(i == 0){ if(flowerbed[i+1] == 0){ first = true; } } //结尾边界 // boolean end =(i == flowerbed.length -1) && (flowerbed[i-2] == 0); else if(i == flowerbed.length -1){ if(flowerbed[i-1] == 0){ end = true; } }else{ // 中间 center = (flowerbed[i-1] ==0 && flowerbed[i + 1] == 0); } ``` 还是下标溢出，原因是，假如数组长度就1，在判断开头的时候就i+1，下标溢出 [345. 反转字符串中的元音字母 - 力扣（LeetCode）](https://leetcode.cn/problems/reverse-vowels-of-a-string/description/?envType=study-plan-v2&envId=leetcode-75) ----------------------------------------------------------------------------------------------------------------------------------------------- 题目描述 一个字符串，将其中的元音字母，反转（交换位置）输出结果字符串。 思路 * 双指针，找到元音字母相互交换位置。 ```java class Solution { public String reverseVowels(String s) { // 元音数组 Set<Character> vowels = new HashSet<>( Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U') ); // sting 不可变---》转成数组 char [] check = s.toCharArray(); int l = 0, r = check.size - 1; while(l < r){ // 从左向右找元音 while(l < r && !vowels.contains(check[l])){ l++; } // 从左向右找元音 while(l < r && !vowels.contains(check[r])){ r --; } // 交换元素 if( l < r ){ char t = check[l]; check[l] = check[r]; check[r] = t; l++; r--; } } return new String(check); } } ``` [151. 反转字符串中的单词 - 力扣（LeetCode）](https://leetcode.cn/problems/reverse-words-in-a-string/description/?envType=study-plan-v2&envId=leetcode-75) -------------------------------------------------------------------------------------------------------------------------------------------- 题目描述 ``` 反转单词 一个字符串，包含多个单词，反转单词的顺序。 ``` 题目思路 * 识别单词，存入list,倒叙拼接。 * 主要是处理空格，我们可以使用split()根据空格进行分割，但是假如多个空格分割，值是有空格的？那我存的时候判断一下。 实现有误 ```java class Solution { public String reverseWords(String s) { String[] split =s.split(" "); StringBuilder result = new StringBuilder(); for(int i = split.length - 1 ;i >=0 ;i --){ if(split[i] != " "){ // 最后一个不加空格 if(i == 0){ result.append(split[i]); } // 其他的后边要加一个空格 else{ result.append(split[i] + " "); } } } return result.toString(); } } ``` 原因如下： 在处理最后一个单词的时候，判断要不要加空格，是根据分割后的下标来判断的，这种逻辑是错误的 tips:比较字符串 不要直接使用 == != 而是使用equals。  问题？什么时候应该不加空格，最后一个有效单词，怎么判断？下标是判断不了。换种思路，在添加元素的前面添加空格 ```java class Solution { public String reverseWords(String s) { String[] split =s.split(" "); StringBuilder result = new StringBuilder(); boolean isfirst = true; for(int i = split.length - 1 ;i >=0 ;i --){ if(!split[i].isEmpty()){ // 不是第一个元素，在前面就加空格 if(!isfirst){ result.append(" "); } result.append(split[i]); isfirst =false; } } return result.toString(); } } ``` 更优雅的做法，使用trim()去除首尾空格，同时分割的时候根据一个或者多个空格分割 ```java class Solution { public String reverseWords(String s) { // 去除首尾空格 s = s.trim(); // 按一个或多个空格分割 String[] words = s.split("\\s+"); StringBuilder sb = new StringBuilder(); // 从后向前添加单词 for (int i = words.length - 1; i >= 0; i--) { sb.append(words[i]); if (i > 0) { sb.append(" "); } } return sb.toString(); } } ``` 更简洁的做法： 直接reverse ```java class Solution { public String reverseWords(String s) { // 去除首尾空格，并按一个或多个空格分割 String[] words = s.trim().split("\\s+"); Collections.reverse(Arrays.asList(words)); return String.join(" ", words); } } ``` [238. 除自身以外数组的乘积 - 力扣（LeetCode）](https://leetcode.cn/problems/product-of-array-except-self/description/?envType=study-plan-v2&envId=leetcode-75) ------------------------------------------------------------------------------------------------------------------------------------------------ 题目描述 ``` 一个整型数组， 获得出自己之外的数组相乘的值数组，数组中的每个值相乘（但是不能乘自己） ``` 思路 * 全部相乘除以自己， 注意nums[i] =0 要注意 不要除。---实验发现这种思路错误因为有0的存在导致总和是0，所以不能这样算。 优化思路 * 前缀积 + 后缀积 * 前缀鸡[i] = 前缀鸡[i-1] * 数组[i-1] * 后缀鸡[i] = 后缀鸡[i+1] * 数组[i+1] ```java class Solution { public int[] productExceptSelf(int[] nums) { // 前缀数组 int[] prefix = new int[nums.length]; //前缀乘积 prefix[0] = 1; // 第一个元素的前缀乘积是1 for(int i = 1 ; i < nums.length; i ++){ prefix[i] = prefix[i-1] * nums[i-1]; // 前缀鸡[i] = 前缀鸡[i-1] * 数组[i-1] } // 后缀鸡 int[] suffix = new int[nums.length]; suffix[nums.length -1] = 1; for(int i = nums.length -2 ; i >=0 ; i --){ suffix[i] = suffix[i+1] * nums[i+1]; // 后缀鸡[i] = 后缀鸡[i+1] * 数组[i+1] } // 结果 for(int i = 0; i < nums.length ; i ++){ nums[i] = prefix[i] * suffix[i]; } return nums; } } ``` 内存优化：上述new 了两个数组，可以就弄一个前缀数组，后缀数组不需要，直接使用一个变量存一下，直接计算结果 ```java class Solution { public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] result = new int[n]; // 计算前缀乘积并直接存入结果数组 result[0] = 1; for (int i = 1; i < n; i++) { result[i] = result[i-1] * nums[i-1]; } // 使用一个变量来跟踪后缀乘积，避免使用额外数组 int suffix = 1; for (int i = n-1; i >= 0; i--) { result[i] *= suffix; suffix *= nums[i]; } return result; } } ```

LeetCode 75 -每日一题

## [238. 除自身以外数组的乘积 - 力扣（LeetCode）](https://leetcode.cn/problems/product-of-array-except-self/description/?envType=study-plan-v2&envId=leetcode-75) 题目描述 ​ 一个整型数组， 获得出自己之外的数组相乘的值数组，数组中的每个值相乘（但是不能乘自己） 思路 * 全部相乘除以自己， 注意nums[i] =0 要注意 不要除。---实验发现这种思路错误因为有0的存在导致总和是0，所以不能这样算。 优化思路 * 前缀积 + 后缀积 * 前缀鸡[i] = 前缀鸡[i-1] * 数组[i-1] * 后缀鸡[i] = 后缀鸡[i+1] * 数组[i+1] ```java class Solution { public int[] productExceptSelf(int[] nums) { // 前缀数组 int[] prefix = new int[nums.length]; //前缀乘积 prefix[0] = 1; // 第一个元素的前缀乘积是1 for(int i = 1 ; i < nums.length; i ++){ prefix[i] = prefix[i-1] * nums[i-1]; // 前缀鸡[i] = 前缀鸡[i-1] * 数组[i-1] } // 后缀鸡 int[] suffix = new int[nums.length]; suffix[nums.length -1] = 1; for(int i = nums.length -2 ; i >=0 ; i --){ suffix[i] = suffix[i+1] * nums[i+1]; // 后缀鸡[i] = 后缀鸡[i+1] * 数组[i+1] } // 结果 for(int i = 0; i < nums.length ; i ++){ nums[i] = prefix[i] * suffix[i]; } return nums; } } ``` 内存优化：上述new 了两个数组，可以就弄一个前缀数组，后缀数组不需要，直接使用一个变量存一下，直接计算结果 ```java class Solution { public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] result = new int[n]; // 计算前缀乘积并直接存入结果数组 result[0] = 1; for (int i = 1; i < n; i++) { result[i] = result[i-1] * nums[i-1]; } // 使用一个变量来跟踪后缀乘积，避免使用额外数组 int suffix = 1; for (int i = n-1; i >= 0; i--) { result[i] *= suffix; suffix *= nums[i]; } return result; } } ```

LeetcodeDay1

经过鱼皮大佬的路线分析，现在已经不迷茫了，今天开始刷Leetcode，听说新手一般刷热题，我也从热题开始吧 # 今天的题目是两数之和 之前是有一点算法基础的，过了很长时间没学了，忘的差不多了，以至于我连两数之和的暴力解法都没做出来；看过讲解后理解了，来这里总结一下 ## **首先是暴力解法** ``` //有没有大佬知道这class Solution是啥，我咋一直没见过 class Solution{ //我也不知到这个是啥，但是测试数据是从这里传入的，有意思的 public int[] twoSum(int[] nums,int target) { int n=nums.length;//定义n为nums数组的长度 for(int i=0;i<n;++i){ for(int j=i+1;j<n;++j){ if(nums[i]+nums[j]==target)//用循环嵌套，类似余双指针，i指向数组中的第一个数与j指向第二个数，判断这两个数相加是否等于target，不等则j+1；j大于n则i+1；循环往复； { return new int []{i,j};//这个我明白就是输出结果[x,x] } } } return new int[0];//这个不懂哎，返回这玩意干啥 } ``` 今天时间有限，没安排好，只能先理解暴力解法，明天在搞哈希 # 请大佬们赐教

LeetCode热题100-283.移动零

### 题目描述： **给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。** **请注意 ，必须在不复制数组的情况下原地对数组进行操作。** 示例 1: 输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0] 示例 2: 输入: nums = [0] 输出: [0] 进阶：你能尽量减少完成的操作次数吗？ ### 题解思路-双指针： 使用两个指针 i 和 j 。i 负责遍历整个数组，在遍历数组的时候，j 用来记录当前所有非0元素的个数。遍历的时候每遇到一个非0元素就将其往数组左边挪，挪动到 j 所在的位置，注意是挪动，不是交换位置，j 同时也移动一个位置。当第一次遍历完后，j 指针的下标就指向了已经排完了位置的最后一个非0元素下标。 进行第二次遍历的时候，起始位置就从 j 开始到结束，将剩下的这段区域内的元素全部置为0即可。 <img src="https://pic.code-nav.cn/post_picture/1657061637527474177/5Ax6wD9b0SZFiVGL.webp" alt="image.png" width="100%" /> <img src="https://pic.code-nav.cn/post_picture/1657061637527474177/1PIiXyomOfsOjgmW.webp" alt="image.png" width="100%" /> **时间复杂度是O(n)，空间复杂度则变为O(1)。** ### 代码实现： ```Java /*双指针方式实现*/ public void moveZeroes(int[] nums) { if(nums==null) { return; } //第一次遍历的时候，j指针记录非0的个数，只要是非0的统统都赋给nums[j] int j = 0; for(int i=0;i<nums.length;++i) { if(nums[i]!=0) { // j++ 先赋值再加加 nums[j++] = nums[i]; } } //非0元素统计完了，剩下的都是0了 //所以第二次遍历把末尾的元素都赋为0即可 for(int i=j;i<nums.length;++i) { nums[i] = 0; } } ``` ```Java /*双指针方式实现，但是取消了第二次循环*/ public static void moveZeroes(int[] nums){ if(nums==null) { return; } int j =0; for (int i = 0; i < nums. length; ++i) { if (nums[i] != 0){ nums[j] = nums[i]; if (i != j) { nums[i] = 0; } j++; } } } ``` ```Java /*一次遍历,快速排序的思想*/ public static void moveZeroes2(int[] nums) { if(nums==null) { return; } //两个指针i和j int j = 0; for(int i=0;i<nums.length;i++) { //当前元素!=0，就把其交换到左边，等于0的交换到右边 if(nums[i]!=0) { int tmp = nums[i]; nums[i] = nums[j]; nums[j++] = tmp; } } } ```

互联网大厂社招面试最后的在线coding环节，OJ系统，到底如何进行编码？

### 求职目标 老师您好，我的求职方向和目标。是希望成为一名全栈开发工程师，想进互联网大厂。 ### 个人情况 我是2022届毕业生，在校期间主要学的是Java编程，由于刚开始技术不太精湛，毕业之后找工作方面没有特别地顺利，后来跟着鱼皮老师的项目教程和加入编程导航的学习，感觉不管是技术方面，还是做项目上，收获都挺大的。 ### 求职困惑 但是我确实没有过大厂的校招、社招面试经验。我不是特别了解，像腾讯、百度、美团这种互联网大厂，整体的面试流程。尤其是在面试最后一个环节：在线coding环节。 1、编码中，我是需要不仅要实现算法逻辑，输入输出还需要进行处理不？（面试时候用的OJ系统，和Leetcode好像不是一个OJ系统） 2、编码中，导包import怎么办？背下来使用的类，所需要使用的包吗？ 3、在Leetcode网站中，是需要先做Hop100的题目吗？ 4、剑指offer的题目下线了，得需要哪些题目来做补充呢？ ### 已有尝试 比如说Leetcode第一题：两数之和。在线coding的OJ系统，到底需要这两种中的哪一种的编码呢？ 第一种：只实现了算法逻辑，没有处理输入输出。（没有main方法） ```java import java.util.HashMap; import java.util.Map; public class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement)) { return new int[] { map.get(complement), i }; } map.put(nums[i], i); } throw new IllegalArgumentException("No two sum solution"); } } ``` 第二种：不仅实现了算法逻辑，还需要处理输入输出。（有main方法） ```java import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement)) { return new int[] { map.get(complement), i }; } map.put(nums[i], i); } throw new IllegalArgumentException("No two sum solution"); } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String[] inputArray = scanner.nextLine().split(" "); int[] nums = new int[inputArray.length]; for (int i = 0; i < inputArray.length; i++) { nums[i] = Integer.parseInt(inputArray[i]); } int target = scanner.nextInt(); Solution sol = new Solution(); int[] indices = sol.twoSum(nums, target); System.out.println(indices[0] + " " + indices[1]); } } ``` ### 期望帮助 老师，我期望得到这个帮助，不是特别了解互联网大厂面试的最后一个在线coding环节。求老师帮忙答疑解惑一下，感谢老师。 1、编码中，我是需要不仅要实现算法逻辑，输入输出还需要进行处理不？（面试时候用的OJ系统，和Leetcode好像不是一个OJ系统） 2、编码中，导包import怎么办？背下来使用的类，所需要使用的包吗？ 3、在Leetcode网站中，是需要先做Hop100的题目吗？ 4、剑指offer的题目下线了，得需要哪些题目来做补充呢？

力扣 312. 戳气球 动态规划解法，想了一整天，终于透彻了，太不容易了，打个卡。 题目： 有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。 现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。 求所能获得硬币的最大数量。

从字节面试题中学回溯

## [131. 分割回文串](https://leetcode.cn/problems/palindrome-partitioning/) 给你一个字符串 `s`，请你将 `s` 分割成一些子串，使每个子串都是 **回文串** 。返回 `s` 所有可能的分割方案。 **回文串** 是正着读和反着读都一样的字符串。 **示例 1：** ``` 输入：s = "aab" 输出：[["a","a","b"],["aa","b"]] ``` **示例 2：** ``` 输入：s = "a" 输出：[["a"]] ``` **提示：** - `1 <= s.length <= 16` - `s` 仅由小写英文字母组成 ### 回溯 ```java class Solution { List<List<String>> res = new LinkedList<>(); List<String> track = new LinkedList<>(); public List<List<String>> partition(String s) { backtrack(s, 0); return res; } void backtrack(String s, int start) { if (start == s.length()) { // base case // 越界，即整个 s 被成功分割为若干个回文子串，记下答案 res.add(new ArrayList<String>(track)); } // for 和 if 是用来检查字符串是否应该被放到track列表里的 for (int i = start; i < s.length(); i++) { if (!isPalindrome(s, start, i)) { // s[start..i] 不是回文串，不能分割，继续检查s[start, i+1] continue; } // s[start..i] 是一个回文串，可以进行分割 // 做选择，把 s[start..i] 放入路径列表中 track.addLast(s.substring(start, i + 1)); // 进入回溯树的下一层，继续切分 s[i+1..] backtrack(s, i + 1); // 撤销选择 track.removeLast(); } } // 用双指针技巧判断 s[lo..hi] 是否是一个回文串 boolean isPalindrome(String s, int lo, int hi) { while (lo < hi) { if (s.charAt(lo) != s.charAt(hi)) { return false; } lo++; hi--; } return true; } } ``` - 时间复杂度：`O(N*2^N)`；这里 N 为输入字符串的长度，每一个位置可拆分，也可不拆分，尝试是否可以拆分的时间复杂度为 `O(2^N)`，判断每一个子串是否是回文子串，时间复杂度为 O(N)； - 空间复杂度： - 如果不计算保存结果的空间，空间复杂度为 `O(N)`，递归调用栈的高度为 N； - 如果计算保存答案需要空间 `2^N*N`，这里 `2^N` 为保守估计，实际情况不会这么多。空间复杂度为 `O(2^N*N)`。 ## [90. 子集 II](https://leetcode.cn/problems/subsets-ii/) 给你一个整数数组 `nums` ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。 解集 **不能** 包含重复的子集。返回的解集中，子集可以按 **任意顺序** 排列。 **示例 1：** ``` 输入：nums = [1,2,2] 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]] ``` **示例 2：** ``` 输入：nums = [0] 输出：[[],[0]] ``` **提示：** - `1 <= nums.length <= 10` - `-10 <= nums[i] <= 10` ### 回溯 ```java class Solution { List<List<Integer>> res = new LinkedList<>(); List<Integer> track = new LinkedList<>(); public List<List<Integer>> subsetsWithDup(int[] nums) { // 先排序，让相同的元素靠在一起 Arrays.sort(nums); backtrack(nums, 0); return res; } void backtrack(int[] nums, int start) { // 前序位置，每个节点的值都是一个子集。重点。 res.add(new LinkedList<>(track)); for (int i = start; i < nums.length; i++) { // 剪枝，值相同的相邻树枝，只遍历第一条。重点。 if (i > start && nums[i] == nums[i - 1]) { continue; } track.addLast(nums[i]); backtrack(nums, i + 1); track.removeLast(); } } } ``` - 可能的子集数量为 `2^n`，对于每一个子集，程序都会执行一系列操作，其中包括子集的构造和检查，平均情况下，每个子集的长度是 `O(n)`。回溯搜索的总复杂度可以近似表示为 `O(n*2^n)`，这是因为回溯会对每个可能的子集进行构建和复制。 - `new LinkedList<>(track)` 这行代码会创建一个新的 `LinkedList` 实例，并将当前 `track` 中的所有元素复制到新列表中。复制 `track` 的所有元素的时间复杂度是 O(k)，其中 k 是当前 `track` 的长度。`res.add(...)` 是将新子集加入到结果列表 `res` 中，这个操作本身是常数时间 O(1)，因为 `LinkedList` 的尾插入操作时间复杂度为 O(1)。在回溯生成子集的过程中，`track` 的长度会随着递归的深度变化。最坏情况下，`track` 可以达到最大长度，即 n（输入数组的长度）。因此，复制 `track` 的操作在最坏情况下是 O(n)。因此如果不考虑结果链表res，空间复杂度是 `O(n)`。res的空间复杂度是`O(n*2^n)`。 ## [491. 非递减子序列](https://leetcode.cn/problems/non-decreasing-subsequences/) 给你一个整数数组 `nums` ，找出并返回所有该数组中不同的递增子序列，递增子序列中 **至少有两个元素** 。你可以按 **任意顺序** 返回答案。 数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。 **示例 1：** ``` 输入：nums = [4,6,7,7] 输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]] ``` **示例 2：** ``` 输入：nums = [4,4,3,2,1] 输出：[[4,4]] ``` **提示：** - `1 <= nums.length <= 15` - `-100 <= nums[i] <= 100` ### 回溯 ```java class Solution { public List<List<Integer>> findSubsequences(int[] nums) { if (nums.length == 0) { return res; } backtrack(nums, 0); return res; } List<List<Integer>> res = new LinkedList<>(); // 记录回溯的路径 List<Integer> track = new LinkedList<>(); // 回溯算法主函数 void backtrack(int[] nums, int start) { if (track.size() >= 2) { // 找到一个合法答案，不能返回，还要继续找。重点。 res.add(new LinkedList<>(track)); } // 用哈希集合防止重复选择相同元素，横向作用 Set<Integer> used = new HashSet<>(); // 回溯算法标准框架 for (int i = start; i < nums.length; i++) { // 剪枝，保证集合中元素都是递增顺序。重点。 if (!track.isEmpty() && track.getLast() > nums[i]) { continue; } // 剪枝，确保递增，即不要重复使用相同的元素， if (used.contains(nums[i])) { continue; } // 选择 nums[i] used.add(nums[i]); track.add(nums[i]); // 递归遍历下一层回溯树 backtrack(nums, i + 1); // 撤销选择 nums[i] track.removeLast(); // 这里不能写used.remove(nums[i])，因为used是当前递归层的状态，不是全局状态。 } } } ``` - 时间复杂度为 `O(n*2^n)`。这里 n 是用于每一层循环的复杂度估算，2^n 是由于每个元素都有加入或不加入子序列的选择。`HashSet` 的操作（`add` 和 `contains`）都是 O(1) 的时间复杂度。 - 递归的深度最多为 `n`，因此递归栈的空间复杂度是 O(n)。存储结果的空间复杂度取决于生成的子序列数量和长度，这在最坏情况下接近 `O(2^n*n)`。 ## [47. 全排列 II](https://leetcode.cn/problems/permutations-ii/) 给定一个可包含重复数字的序列 `nums` ，***按任意顺序*** 返回所有不重复的全排列。 **示例 1：** ``` 输入：nums = [1,1,2] 输出： [[1,1,2], [1,2,1], [2,1,1]] ``` **示例 2：** ``` 输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] ``` **提示：** - `1 <= nums.length <= 8` - `-10 <= nums[i] <= 10` ### 回溯 ```java class Solution { List<List<Integer>> res = new LinkedList<>(); // 结果列表 List<Integer> track = new LinkedList<>(); // 用于存储当前的排列内容 boolean[] used; // 标记数组，用来记录nums中的元素是否已经被使用 public List<List<Integer>> permuteUnique(int[] nums) { // 先对数组进行排序，这样相同的数字就会被排列在一起，便于后续剪枝 Arrays.sort(nums); used = new boolean[nums.length]; backtrack(nums); return res; } void backtrack(int[] nums) { // 如果当前排列的长度等于nums的长度，说明找到了一个完整的排列。排列的长度是一样的。 if (track.size() == nums.length) { res.add(new LinkedList(track)); // 将当前排列添加到结果列表中 return; } // 从头开始遍历 for (int i = 0; i < nums.length; i++) { if (used[i]) { // 纵向比较进行剪枝 continue; // 如果nums[i]已经在本路径中被使用过，则跳过 } // 因为数组中有重复元素，所以需要横向比较进行剪枝，以避免产生重复的排列。used是纵向的，即跨递归的，方法二中的prevNum是横向的。 if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) { // 如果当前数字和前一个数字相同，且前一个数字还未被使用过，则跳过 // 这是因为这种情况会产生和前一个数字相同的排列，导致产生相同的排列 continue; } track.add(nums[i]); // 将nums[i]添加到当前排列中 used[i] = true; // 标记nums[i]已经被使用 backtrack(nums); // 递归调用，继续填充排列的下一个数字 track.removeLast(); // 回溯，从当前排列中移除nums[i] used[i] = false; // 取消对nums[i]的使用标记 } } } ``` - 总共有n!种排列，每个排列都需要被复制到res中，这个操作的时间复杂度是O(n)，因此总的时间复杂度是`O(n*n!)` - 记忆数组O(n)，递归栈O(n)。 ### 回溯 ```java class Solution { List<List<Integer>> res = new LinkedList<>(); // 结果列表 LinkedList<Integer> track = new LinkedList<>(); // 用于存储当前的排列内容 boolean[] used; // 标记数组，用来记录nums中的元素是否已经被使用 public List<List<Integer>> permuteUnique(int[] nums) { // 先对数组进行排序，这样相同的数字就会被排列在一起，便于后续剪枝 Arrays.sort(nums); used = new boolean[nums.length]; backtrack(nums, track); return res; } void backtrack(int[] nums, LinkedList<Integer> track) { if (track.size() == nums.length) { res.add(new LinkedList(track)); return; } // 利用prevNum变量记录之前树枝上元素的值 // 题目说 -10 <= nums[i] <= 10，所以初始化为特殊值 // used是全局记忆数组，prevNum是每层递归中的记忆变量 int prevNum = -666; for (int i = 0; i < nums.length; i++) { // 排除不合法的选择 if (used[i]) { continue; } // 注意prevNum是每层递归中的变量，不会跨递归，因此prevNum是本轮递归中的前一个数，即横向的数，不是track中的上一个选择。 if (nums[i] == prevNum) { continue; } track.add(nums[i]); used[i] = true; // 记录这条树枝上的值 prevNum = nums[i]; backtrack(nums, track); track.removeLast(); used[i] = false; } } } ``` ## [37. 解数独](https://leetcode.cn/problems/sudoku-solver/) 编写一个程序，通过填充空格来解决数独问题。 数独的解法需 **遵循如下规则**： 1. 数字 `1-9` 在每一行只能出现一次。 2. 数字 `1-9` 在每一列只能出现一次。 3. 数字 `1-9` 在每一个以粗实线分隔的 `3x3` 宫内只能出现一次。（请参考示例图） 数独部分空格内已填入了数字，空白格用 `'.'` 表示。 **示例 1：** <img src="https://pic.code-nav.cn/post_picture/1790012413649412097/T3fCzq9OUuNmYmm8.png"/> ``` 输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]] 输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]] 解释：输入的数独如上图所示，唯一有效的解决方案如下所示： ``` **提示：** - `board.length == 9` - `board[i].length == 9` - `board[i][j]` 是一位数字或者 `'.'` - 题目数据 **保证** 输入数独仅有一个解 ### 回溯 ```java class Solution { public void solveSudoku(char[][] board) { backtrack(board, 0, 0); // 开始从 (0, 0) 位置开始进行回溯 } boolean backtrack(char[][] board, int i, int j) { int m = 9, n = 9; // 数独的大小固定为 9x9 if (j == n) { // 如果穷举到最后一列的话，就换到下一行重新开始。重点。 return backtrack(board, i + 1, 0); } if (i == m) { // 如果穷举到最后一行，说明找到一个可行解。重点。 return true; } if (board[i][j] != '.') { // 如果当前位置有预设数字，不用我们穷举，直接跳到下一个位置。重点。 return backtrack(board, i, j + 1); } // 尝试填入数字 1 到 9 for (char ch = '1'; ch <= '9'; ch++) { // 如果遇到不合法的数字，跳过 if (!isValid(board, i, j, ch)) continue; board[i][j] = ch; // 做选择：填入数字 ch // 判断 3x3 方框是否存在重复。重点。r/3是从上往下数第几个方块，每一个方块都有三行，所以r/3就是第几行。 if (backtrack(board, i, j + 1)) { return true; } board[i][j] = '.'; // 撤销选择：恢复为空格 } // 穷举完 1 到 9，依然没有找到可行解，返回 false 表示此路不通 return false; } // 判断 board[r][c] 是否可以填入字符 n boolean isValid(char[][] board, int r, int c, char n) { for (int i = 0; i < 9; i++) { // 判断行是否存在重复 if (board[r][i] == n) return false; // 判断列是否存在重复 if (board[i][c] == n) return false; // 判断 3x3 方框是否存在重复。重点。 if (board[(r / 3) * 3 + i / 3][(c / 3) * 3 + i % 3] == n) return false; } return true; // 如果以上条件都不满足，说明可以填入字符 n } } ``` - 在最坏情况下，每个空格都需要穷举 9 个数字。因此最差情况下，时间复杂度是 `O(9^N)`。 - 空间复杂度主要由递归调用栈的深度决定：在最坏情况下，递归的最大深度为 `N`，即数独中所有空格的数量。每次递归调用会使用常数级别的空间（例如局部变量和参数），所以空间复杂度为 `O(N)`。 解释一下判断 3x3 方框是否存在重复的代码。 假设我们在一个数独棋盘上操作，当前的位置是 `(r, c)`，比如说位置 `(4, 4)`，我们要检查数字 `5` 是否可以放在这个位置。 首先，我们需要找到 `(4, 4)` 所在的 3x3 小方框： ``` +-------+-------+-------+ | . . . | . . . | . . . | | . . . | . . . | . . . | | . . . | . . . | . . . | +-------+-------+-------+ | . . . | . . . | . . . | | . . . | . 5 . | . . . | | . . . | . . . | . . . | +-------+-------+-------+ | . . . | . . . | . . . | | . . . | . . . | . . . | | . . . | . . . | . . . | +-------+-------+-------+ ``` 我们看到 `(4, 4)` 在棋盘的中心，位于中间的 3x3 小方框中。 - `(r / 3)` 表示当前行 `r` 所在的 3x3 小方框的行索引。对于 `r = 4`，计算 `(4 / 3) = 1`，表示当前行位于第二个 3x3 小方框的行。 - `(c / 3)` 表示当前列 `c` 所在的 3x3 小方框的列索引。对于 `c = 4`，计算 `(4 / 3) = 1`，表示当前列位于第二个 3x3 小方框的列。 所以，当前 3x3 小方框的左上角坐标是 `(1 * 3, 1 * 3)`，即 `(3, 3)`。 我们需要遍历这个 3x3 小方框的所有位置，检查是否有重复数字 `n`。遍历的索引用 `i` 从 `0` 到 `8`，每个 `i` 对应小方框中的一个位置。 - `i / 3` 是当前元素在 3x3 小方框中的行索引。例如，当 `i` 取 `0`, `1`, `2` 时，对应 3x3 小方框的第一行，`i / 3 = 0`；当 `i` 取 `3`, `4`, `5` 时，对应 3x3 小方框的第二行，`i / 3 = 1`；当 `i` 取 `6`, `7`, `8` 时，对应 3x3 小方框的第三行，`i / 3 = 2`。 - `i % 3` 是当前元素在 3x3 小方框中的列索引。例如，当 `i` 取 `0`, `3`, `6` 时，对应 3x3 小方框的第一列，`i % 3 = 0`；当 `i` 取 `1`, `4`, `7` 时，对应 3x3 小方框的第二列，`i % 3 = 1`；当 `i` 取 `2`, `5`, `8` 时，对应 3x3 小方框的第三列，`i % 3 = 2`。

字节美团快手微软面试题——145. 二叉树的后序遍历

# [145. 二叉树的后序遍历](https://leetcode.cn/problems/binary-tree-postorder-traversal/) 给你一棵二叉树的根节点 `root` ，返回其节点值的 **后序遍历** 。 **示例 1：** **输入：** root = [1,null,2,3] **输出：**[3,2,1] **解释：** <img src="https://pic.code-nav.cn/post_picture/1790012413649412097/xxgFgse29HpxPm8c.png" alt="screenshot-2024-08-29-202743.png" width="254px" /> **示例 2：** **输入：** root = [1,2,3,4,5,null,8,null,null,6,7,9] **输出：**[4,6,7,5,2,9,8,3,1] **解释：** <img src="https://pic.code-nav.cn/post_picture/1790012413649412097/8XoGkoYC6yDZ7HSv.webp" alt="tree_2.png" width="524px" /> **示例 3：** **输入：** root = [] **输出：** [] **示例 4：** **输入：** root = [1] **输出：**[1] **提示：** - 树中节点的数目在范围 `[0, 100]` 内 - `-100 <= Node.val <= 100` **进阶**：递归算法很简单，你可以通过迭代算法完成吗？ ## 有返回值无辅助参数的DFS ```java class Solution { // 动态规划思路 // 定义：输入一个节点，返回以该节点为根的二叉树的后序遍历结果 public List<Integer> postorderTraversal(TreeNode root) { List<Integer> res = new LinkedList<>(); if (root == null) { return res; } // 后序遍历结果特点：先是左子树，接着是右子树，最后是根节点的值 res.addAll(postorderTraversal(root.left)); res.addAll(postorderTraversal(root.right)); res.add(root.val); return res; } } ``` ## 无返回值有辅助参数的DFS ```java class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); postorder(root, res); return res; } public void postorder(TreeNode root, List<Integer> res) { if (root == null) { return; } postorder(root.left, res); postorder(root.right, res); res.add(root.val); } } ``` - 时间复杂度：O(n)，其中 n 是二叉搜索树的节点数。每一个节点恰好被遍历一次。 - 空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。 ## Morris后序遍历 ```java class Solution { public List<Integer> postorderTraversal(TreeNode root) { // 创建结果列表，用于存储后序遍历的节点值 List<Integer> result = new ArrayList<>(); if (root == null) { return result; // 如果根节点为空，直接返回空列表 } // currentNode 表示当前遍历的节点，predecessor 表示当前节点的前驱节点 TreeNode currentNode = root, predecessor = null; // 开始遍历树 while (currentNode != null) { predecessor = currentNode.left; // predecessor 指向 currentNode 的左子节点 if (predecessor != null) { // 寻找 currentNode 节点的前驱节点（左子树中的最右节点） while (predecessor.right != null && predecessor.right != currentNode) { predecessor = predecessor.right; } if (predecessor.right == null) { // 如果前驱节点的右指针为空，将其指向 currentNode，构建线索 predecessor.right = currentNode; // 移动 currentNode 到其左子节点，继续遍历 currentNode = currentNode.left; continue; } else { // 如果前驱节点的右指针指向 currentNode，恢复树的原结构 predecessor.right = null; // 将从 currentNode.left 到 currentNode 的路径（全是往右走）添加到结果中，并反转顺序。重点。在示例2中路径是7,5,2，因为后序遍历是4,6,7,5,2 addPath(result, currentNode.left); } } // 如果没有左子树，直接移动到右子节点 currentNode = currentNode.right; } // 最后将根节点到最右节点的路径添加到结果中，并反转顺序 addPath(result, root); return result; // 返回后序遍历的结果 } /** * 将从 node 到路径的最右节点的值添加到结果列表中，并反转顺序。 * @param result 用于存储节点值的列表 * @param node 当前路径的起始节点 */ public void addPath(List<Integer> result, TreeNode node) { List<Integer> temp = new ArrayList<>(); while (node != null) { temp.add(node.val); // 将节点值添加到临时列表 node = node.right; // 移动到右子节点 } // 反转临时列表的顺序，并将其添加到结果中 for (int i = temp.size() - 1; i >= 0; i--) { result.add(temp.get(i)); } } } ``` - 时间复杂度：O(n)，其中 n 是二叉树的节点数。没有左子树的节点只被访问一次，有左子树的节点被访问两次。 - 空间复杂度：O(1)。只操作已经存在的指针（树的空闲指针），因此只需要常数的额外空间。