Loading... <div class="tip inlineBlock warning"> （省时间）推荐题目：最短公共超序列，最长的斐波那契子序列的长度，可被三整除的最大和（网易：可被六整除），获得分数的方法数，最小化目标值与所选元素的差，从栈中取出 K 个硬币的最大面值和（多重背包三连） </div> ### 最短公共超序列（最长公共子序列应用题） <img src="https://sydblog-1999-1256393142.cos.ap-nanjing.myqcloud.com/blog/2023-03-06-140957.png" alt="image.png" style="zoom: 50%;" style=""> <br />思路：找出最长公共子序列，在此基础上添加无关字符->如何找到最长公共子序列？LCS，动态规划->dp\[i][j]第一个字符串前i个字符和第二个字符串前j个字符的公共字符串，第i个字符和第j个字符是否相等有递推关系。<br />找出最长公共子序列，如何逐步推出最长子序列，进而推出题目要求字符串->属于公共子序列直接添加公共字符，不属于公共子序列，看状态由前面那个状态推导过来从而确定添加哪个字符串的字符。 ```java class Solution { public String shortestCommonSupersequence(String str1, String str2) { int n1 = str1.length(); int n2 = str2.length(); int[][] dp = new int[n1 + 1][n2 + 1]; for(int i = 1; i <= n1; i++){ for(int j = 1; j <= n2; j++){ if(str1.charAt(i-1) == str2.charAt(j-1)){ dp[i][j] = dp[i-1][j-1] + 1; }else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); } } StringBuilder sb = new StringBuilder(); int k1 = n1; int k2 = n2; while(k1 > 0 || k2 > 0){ if(k1 == 0){ sb.append(str2.charAt(k2 - 1)); k2--; }else if(k2 == 0){ sb.append(str1.charAt(k1 - 1)); k1--; }else{ if(str1.charAt(k1-1) == str2.charAt(k2-1)){ sb.append(str1.charAt(k1 - 1)); k2--; k1--; }else if(dp[k1][k2] == dp[k1-1][k2]){ sb.append(str1.charAt(k1 - 1)); k1--; }else if(dp[k1][k2] == dp[k1][k2-1]){ sb.append(str2.charAt(k2 - 1)); k2--; } } } return sb.reverse().toString(); } } ``` LCS模板题：[https://leetcode.cn/problems/longest-common-subsequence/description/](https://leetcode.cn/problems/longest-common-subsequence/description/) ### 你能构造出连续值的最大数目 <img src="https://sydblog-1999-1256393142.cos.ap-nanjing.myqcloud.com/blog/2023-03-06-141004.png" alt="image.png" style="zoom:50%;" style=""> <br />思路：类似于贪心首先**数组某一处确定可得到范围[0, x]，那么当前数为a，即加上这个数可以将之前区间扩大为[a, x+a]，重点在于两个区间能否合并，即a <= x + 1确定可合并。** ```java class Solution { public int getMaximumConsecutive(int[] coins) { int x = 0; Arrays.sort(coins); int n = coins.length; for(int i = 0; i < n; i++){ if(coins[i] > x + 1) break; x = x + coins[i]; } return x + 1; } } ``` ### 使字符串平衡的最少删除次数 <img src="https://sydblog-1999-1256393142.cos.ap-nanjing.myqcloud.com/blog/2023-03-06-141009.png" alt="image.png" style="zoom:50%;" style=""> <br />思路：从左往右，加入当前字符怎么不影响字符串的平衡性->动态规划->**当前字符是a，要么自己不加入，要么把前面的b全部删除以保持平衡，根据此作为递归条件。** ```java class Solution { public int minimumDeletions(String s) { int bNum = 0; int n = s.length(); int dp = 0; for(int i = 1; i <= n; i++){ if(s.charAt(i-1) == 'b'){ bNum++; } else dp = Math.min(dp + 1, bNum); } return dp; } } ``` ### 最长的斐波那契子序列的长度(动态规划) <img src="https://sydblog-1999-1256393142.cos.ap-nanjing.myqcloud.com/blog/2023-03-06-141014.png" alt="image.png" style="zoom:50%;" style=""> <br />思路：怎么样固定一个斐波那契数列->知道其开头两个数或者末尾两个数->为什么不开头两个数？顺序不对，确定开头得知道后面的序列情况，而后面序列情况在当前求取之后->**定义以j和i为结尾序列，dp\[i][j]表示以arr[j]和arr[i]结尾的序列的最大斐波那契数列长度->怎么找前面?哈希表，即递推方程dp\[i][j] = Math.max(3, dp\[j][map.get(t)] + 1) **->优化：即使前面都是数列内容也比答案小的，下一个值大于arr[j]的。 ```java class Solution { public int lenLongestFibSubseq(int[] arr) { int n = arr.length; int res = 0; int[][] dp = new int[n][n]; Map<Integer, Integer> map = new HashMap<>(); for(int i = 0; i < n; i++) map.put(arr[i], i); for(int i = 0; i < n; i++){ for(int j = i - 1; j >= 0 && j + 2 > res; j--){ int t = arr[i] - arr[j]; if(t >= arr[j]) break; if(map.containsKey(t)) dp[i][j] = Math.max(3, dp[j][map.get(t)] + 1); res = Math.max(dp[i][j], res); } } return res; } } ``` ### 可被三整除的最大和 <img src="https://sydblog-1999-1256393142.cos.ap-nanjing.myqcloud.com/blog/2023-03-06-141019.png" alt="image.png" style="zoom:50%;" style=""> <br />思路：序列，考虑取前k个元素其可被三整除的最大和，当前元素对之前序列的影响，**当前元素除3余1，那么和之前余2的最大和组合即为当前可能的整除的最大和。**所以要定义三个状态对余0，余1，余2均记录。 ```java class Solution { public int maxSumDivThree(int[] nums) { int n = nums.length; int[][] dp = new int[n + 1][3]; dp[0][0] = 0; dp[0][1] = Integer.MIN_VALUE; dp[0][2] = Integer.MIN_VALUE; for(int i = 1; i <= n; i++){ if(nums[i-1] % 3 == 0){ dp[i][0] = dp[i-1][0] + nums[i-1]; dp[i][1] = dp[i-1][1] + nums[i-1]; dp[i][2] = dp[i-1][2] + nums[i-1]; }else if(nums[i-1] % 3 == 1){ dp[i][0] = Math.max(dp[i-1][0], dp[i-1][2] + nums[i-1]); dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + nums[i-1]); dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] + nums[i-1]); }else{ dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + nums[i-1]); dp[i][1] = Math.max(dp[i-1][1], dp[i-1][2] + nums[i-1]); dp[i][2] = Math.max(dp[i-1][2], dp[i-1][0] + nums[i-1]); } } return dp[n][0]; } } ``` ### 爱吃香蕉的珂珂 <img src="https://sydblog-1999-1256393142.cos.ap-nanjing.myqcloud.com/blog/2023-03-06-141024.png" alt="image.png" style="zoom:50%;" style=""> <br />思路：二分简单题 ```java class Solution { public int minEatingSpeed(int[] piles, int h) { long l = 1; long r = 1000000000; while(l < r){ long mid = l + r >> 1; if(check(piles, h, mid)) r = mid; else l = mid + 1; } return (int)l; } boolean check(int[] p, int h, long m){ int res = 0; for(int i = 0; i < p.length; i++){ res += (int)(p[i] + m - 1) / m; } return res <= h; } } ``` ### 和可被 K 整除的子数组 <img src="https://sydblog-1999-1256393142.cos.ap-nanjing.myqcloud.com/blog/2023-03-06-141028.png" alt="image.png" style="zoom:50%;" style=""> <br />思路：前缀和+哈希表,`int t = (sum[i] % k + k) % k;`形式可记忆，这样避免了Java对负数取余的弊端。 ```java class Solution { public int subarraysDivByK(int[] nums, int k) { int n = nums.length; int[] sum = new int[n + 1]; for(int i = 1; i <= n; i++) sum[i] = sum[i-1] + nums[i-1]; Map<Integer, Integer> map = new HashMap<>(); int res = 0; for(int i = 0; i <= n; i++){ int t = (sum[i] % k + k) % k; map.put(t, map.getOrDefault(t, 0) + 1); res += map.get(t) - 1; } return res; } } ``` ### 获得分数的方法数 <img src="https://sydblog-1999-1256393142.cos.ap-nanjing.myqcloud.com/blog/2023-03-06-141238.png" alt="image-20230306221233382" style="zoom:50%;" style=""> 思路：多重背包模板题 ```java class Solution { public int waysToReachTarget(int target, int[][] types) { int n = types.length; int[] dp = new int[target + 1]; dp[0] = 1; for(int i = 1; i <= n; i++){ for(int j = target; j >= 0; j--){ // dp[i][j] = dp[i-1][j]; for(int k = 1; k * types[i-1][1] <= j && k <= types[i-1][0]; k++){ dp[j] += dp[j - k * types[i-1][1]]; dp[j] %= 1000000007; } } } return dp[target]; } } ``` ### 最小化目标值与所选元素的差 <img src="https://sydblog-1999-1256393142.cos.ap-nanjing.myqcloud.com/blog/2023-03-06-141424.png" alt="image-20230306221416566" style="zoom:50%;" style=""> 思路：每一行可看为一个背包，每个背包可以选一个，目标选出其和与target差值最小。初步可以确定dp\[i][k]表示只取前i行数是否能得到和为k，最后遍历最后一行，找到值为true且和目标最接近的值。实际上背包问题绝大多数可以被优化为一维，本题也可以，注意的是每一行在对行遍历之前要预先赋值为false，和背包问题相同k从大到小便利。 ```java class Solution { public int minimizeTheDifference(int[][] mat, int target) { int maxValue = 5000; int m = mat.length; int n = mat[0].length; boolean[] dp = new boolean[maxValue]; for(int i = 0; i < n; i++) dp[mat[0][i]] = true; for(int i = 1; i < m; i++){ for(int j = maxValue - 1; j >= 0; j--){ dp[j] = false; for(int k = 0; k < n; k++){ // dp[j] = false; if(j >= mat[i][k])dp[j] = dp[j] | dp[j - mat[i][k]]; } } } int res = Integer.MAX_VALUE; for(int i = 0; i < maxValue; i++){ if(dp[i])res = Math.min(res, Math.abs(i - target)); } return res; } } ``` ### 从栈中取出 K 个硬币的最大面值和 <img src="https://sydblog-1999-1256393142.cos.ap-nanjing.myqcloud.com/blog/2023-03-06-143516.png" alt="image-20230306223509365" style="zoom:50%;" style=""> 思路：本题同样是多重背包问题，难点在于转化，栈的特点是具有明显的顺序关系，如取栈第二个值其第一个值也需要出栈。**转换思维：栈对应位置可以想为取出的个数和k相关。这样对于每个栈可以用前缀和优化，前缀和索引为其体积（硬币个数），剩余和多重背包思路一致。** ```java class Solution { public int maxValueOfCoins(List<List<Integer>> piles, int k) { int n = piles.size(); List<List<Integer>> pilseTrans = new ArrayList<>(); for(int i = 0; i < n; i++){ List<Integer> t = new ArrayList<>(); t.add(0); int m = piles.get(i).size(); for(int j = 0; j < m; j++) t.add(t.get(j)+piles.get(i).get(j)); pilseTrans.add(t); } int[][] dp = new int[n + 1][k + 1]; for(int i = 1; i <= n; i++){ for(int j = 0; j <= k; j++){ for(int x = 0; x <= j; x++){ if(j - x <= pilseTrans.get(i-1).size() - 1) dp[i][j] = Math.max(dp[i][j], dp[i-1][x] + pilseTrans.get(i-1).get(j-x)); } } } return dp[n][k]; } } ``` 最后修改：2023 年 03 月 13 日 © 允许规范转载 赞 3 如果觉得我的文章对你有用，请随意赞赏
1 条评论
这一类的题我一直不太懂，看了大佬的解答好像懂了