class083 动态规划中用观察优化枚举的技巧-下【算法】
code1 1235. 规划兼职工作
// 规划兼职工作
// 你打算利用空闲时间来做兼职工作赚些零花钱，这里有n份兼职工作
// 每份工作预计从startTime[i]开始、endTime[i]结束，报酬为profit[i]
// 返回可以获得的最大报酬
// 注意，时间上出现重叠的 2 份工作不能同时进行
// 如果你选择的工作在时间X结束，那么你可以立刻进行在时间X开始的下一份工作
// 测试链接 : https://leetcode.cn/problems/maximum-profit-in-job-scheduling/
利用观察单调性 + 二分搜索的方式优化枚举，最优解时间复杂度O(n*logn)
dp[i]：[0…i]的最大报酬
不需要i位置的工作：dp[i-1]
需要i位置的工作：profit[i]+dp[j]：j是结束时间不超过startTime[i]的最右的
package class083; import java.util.Arrays; // 规划兼职工作 // 你打算利用空闲时间来做兼职工作赚些零花钱，这里有n份兼职工作 // 每份工作预计从startTime[i]开始、endTime[i]结束，报酬为profit[i] // 返回可以获得的最大报酬 // 注意，时间上出现重叠的 2 份工作不能同时进行 // 如果你选择的工作在时间X结束，那么你可以立刻进行在时间X开始的下一份工作 // 测试链接 : https://leetcode.cn/problems/maximum-profit-in-job-scheduling/ public class Code01_MaximumProfitInJobScheduling { public static int MAXN = 50001; public static int[][] jobs = new int[MAXN][3]; public static int[] dp = new int[MAXN]; public static int jobScheduling(int[] startTime, int[] endTime, int[] profit) { int n = startTime.length; for (int i = 0; i < n; i++) { jobs[i][0] = startTime[i]; jobs[i][1] = endTime[i]; jobs[i][2] = profit[i]; } // 工作按照结束时间从小到大排序 Arrays.sort(jobs, 0, n, (a, b) -> a[1] - b[1]); dp[0] = jobs[0][2]; for (int i = 1, start; i < n; i++) { start = jobs[i][0]; dp[i] = jobs[i][2]; if (jobs[0][1] <= start) { dp[i] += dp[find(i - 1, start)]; } dp[i] = Math.max(dp[i], dp[i - 1]); } return dp[n - 1]; } // job[0...i]范围上，找到结束时间 <= start，最右的下标 public static int find(int i, int start) { int ans = 0; int l = 0; int r = i; int m; while (l <= r) { m = (l + r) / 2; if (jobs[m][1] <= start) { ans = m; l = m + 1; } else { r = m - 1; } } return ans; } }
code2 629. K 个逆序对数组
// K个逆序对数组
// 逆序对的定义如下：
// 对于数组nums的第i个和第j个元素
// 如果满足0<=i<j<nums.length 且 nums[i]>nums[j]，则为一个逆序对
// 给你两个整数n和k，找出所有包含从1到n的数字
// 且恰好拥有k个逆序对的不同的数组的个数
// 由于答案可能很大，只需要返回对10^9+7取余的结果
// 测试链接 : https://leetcode.cn/problems/k-inverse-pairs-array/
最优解 利用观察 + 构造窗口累加和，已经进入 观察并设计高效的查询结构 的范畴了
只不过这个结构就仅存在于概念，并用一个int类型的变量维护而已
package class083; // K个逆序对数组 // 逆序对的定义如下： // 对于数组nums的第i个和第j个元素 // 如果满足0<=i<j<nums.length 且 nums[i]>nums[j]，则为一个逆序对 // 给你两个整数n和k，找出所有包含从1到n的数字 // 且恰好拥有k个逆序对的不同的数组的个数 // 由于答案可能很大，只需要返回对10^9+7取余的结果 // 测试链接 : https://leetcode.cn/problems/k-inverse-pairs-array/ public class Code02_KInversePairsArray { // 最普通的动态规划 // 不优化枚举 public static int kInversePairs1(int n, int k) { int mod = 1000000007; // dp[i][j] : 1、2、3...i这些数字，形成的排列一定要有j个逆序对，请问这样的排列有几种 int[][] dp = new int[n + 1][k + 1]; dp[0][0] = 1; for (int i = 1; i <= n; i++) { dp[i][0] = 1; for (int j = 1; j <= k; j++) { if (i > j) { for (int p = 0; p <= j; p++) { dp[i][j] = (dp[i][j] + dp[i - 1][p]) % mod; } } else { // i <= j for (int p = j - i + 1; p <= j; p++) { dp[i][j] = (dp[i][j] + dp[i - 1][p]) % mod; } } } } return dp[n][k]; } // 根据观察方法1优化枚举 // 最优解 // 其实可以进一步空间压缩 // 有兴趣的同学自己试试吧 public static int kInversePairs2(int n, int k) { int mod = 1000000007; int[][] dp = new int[n + 1][k + 1]; dp[0][0] = 1; // window : 窗口的累加和 for (int i = 1, window; i <= n; i++) { dp[i][0] = 1; window = 1; for (int j = 1; j <= k; j++) { if (i > j) { window = (window + dp[i - 1][j]) % mod; } else { // i <= j window = ((window + dp[i - 1][j]) % mod - dp[i - 1][j - i] + mod) % mod; } dp[i][j] = window; } } return dp[n][k]; } }
code3 514. 自由之路
// 自由之路
// 题目描述比较多，打开链接查看
// 测试链接 : https://leetcode.cn/problems/freedom-trail/
优化枚举的核心是贪心策略：
下一步做枚举时，不需要枚举所有可能性，只需要枚举 顺时针的最近、逆时针的最近 两种可能性即可
贪心当然会有专题讲述！【必备】课程的动态规划专题结束了，就会开始贪心的专题
package class083; // 自由之路 // 题目描述比较多，打开链接查看 // 测试链接 : https://leetcode.cn/problems/freedom-trail/ public class Code03_FreedomTrail { // 为了让所有语言的同学都可以理解 // 不会使用任何java语言自带的数据结构 // 只使用最简单的数组结构 public static int MAXN = 101; public static int MAXC = 26; public static int[] ring = new int[MAXN]; public static int[] key = new int[MAXN]; public static int[] size = new int[MAXC]; public static int[][] where = new int[MAXC][MAXN]; public static int[][] dp = new int[MAXN][MAXN]; public static int n, m; public static void build(String r, String k) { for (int i = 0; i < MAXC; i++) { size[i] = 0; } n = r.length(); m = k.length(); for (int i = 0, v; i < n; i++) { v = r.charAt(i) - 'a'; where[v][size[v]++] = i; ring[i] = v; } for (int i = 0; i < m; i++) { key[i] = k.charAt(i) - 'a'; } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { dp[i][j] = -1; } } } public static int findRotateSteps(String r, String k) { build(r, k); return f(0, 0); } // 指针当前指着轮盘i位置的字符，要搞定key[j....]所有字符，最小代价返回 public static int f(int i, int j) { if (j == m) { // key长度是m // 都搞定 return 0; } if (dp[i][j] != -1) { return dp[i][j]; } int ans; if (ring[i] == key[j]) { // ring b // i // key b // j ans = 1 + f(i, j + 1); } else { // 轮盘处在i位置，ring[i] != key[j] // jump1 : 顺时针找到最近的key[j]字符在轮盘的什么位置 // distance1 : 从i顺时针走向jump1有多远 int jump1 = clock(i, key[j]); int distance1 = (jump1 > i ? (jump1 - i) : (n - i + jump1)); // jump2 : 逆时针找到最近的key[j]字符在轮盘的什么位置 // distance2 : 从i逆时针走向jump2有多远 int jump2 = counterClock(i, key[j]); int distance2 = (i > jump2 ? (i - jump2) : (i + n - jump2)); ans = Math.min(distance1 + f(jump1, j), distance2 + f(jump2, j)); } dp[i][j] = ans; return ans; } // 从i开始，顺时针找到最近的v在轮盘的什么位置 public static int clock(int i, int v) { int l = 0; // size[v] : 属于v这个字符的下标有几个 int r = size[v] - 1, m; // sorted[0...size[v]-1]收集了所有的下标，并且有序 int[] sorted = where[v]; int find = -1; // 有序数组中，找>i尽量靠左的下标 while (l <= r) { m = (l + r) / 2; if (sorted[m] > i) { find = m; r = m - 1; } else { l = m + 1; } } // 找到了就返回 // 没找到，那i顺指针一定先走到最小的下标 return find != -1 ? sorted[find] : sorted[0]; } public static int counterClock(int i, int v) { int l = 0; int r = size[v] - 1, m; int[] sorted = where[v]; int find = -1; // 有序数组中，找<i尽量靠右的下标 while (l <= r) { m = (l + r) / 2; if (sorted[m] < i) { find = m; l = m + 1; } else { r = m - 1; } } // 找到了就返回 // 没找到，那i逆指针一定先走到最大的下标 return find != -1 ? sorted[find] : sorted[size[v] - 1]; } }
code4 未排序数组中累加和小于或等于给定值的最长子数组长度
// 累加和不大于k的最长子数组
// 给定一个无序数组arr，长度为n，其中元素可能是正、负、0
// 给定一个整数k，求arr所有的子数组中累加和不大于k的最长子数组长度
// 要求时间复杂度为O(n)
// 测试链接 : https://www.nowcoder.com/practice/3473e545d6924077a4f7cbc850408ade
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
强烈推荐先看一下讲解046
利用构造单调数组 + 二分搜索的解不是最优解，时间复杂度O(n*logn)
最优解中包含的贪心思想（窗口的加速建立、可能性的淘汰），是这个题的重点，时间复杂度O(n)
贪心当然会有专题讲述！【必备】课程的动态规划专题结束了，就会开始贪心的专题
package class083; // 累加和不大于k的最长子数组 // 给定一个无序数组arr，长度为n，其中元素可能是正、负、0 // 给定一个整数k，求arr所有的子数组中累加和不大于k的最长子数组长度 // 要求时间复杂度为O(n) // 测试链接 : https://www.nowcoder.com/practice/3473e545d6924077a4f7cbc850408ade // 请同学们务必参考如下代码中关于输入、输出的处理 // 这是输入输出处理效率很高的写法 // 提交以下的code，提交时请把类名改成"Main"，可以直接通过 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.io.StreamTokenizer; // 至今的最优解，全网题解几乎都是我几年前讲的方法 public class Code04_LongestSubarraySumNoMoreK { public static int MAXN = 100001; public static int[] nums = new int[MAXN]; public static int[] minSums = new int[MAXN]; public static int[] minSumEnds = new int[MAXN]; public static int n, k; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StreamTokenizer in = new StreamTokenizer(br); PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); while (in.nextToken() != StreamTokenizer.TT_EOF) { n = (int) in.nval; in.nextToken(); k = (int) in.nval; for (int i = 0; i < n; i++) { in.nextToken(); nums[i] = (int) in.nval; } out.println(compute2()); } out.flush(); out.close(); br.close(); } public static int compute1() { int[] sums = new int[n + 1]; for (int i = 0, sum = 0; i < n; i++) { // sum : 0...i范围上，这前i+1个数字的累加和 sum += nums[i]; // sums[i + 1] : 前i+1个，包括一个数字也没有的时候，所有前缀和中的最大值 sums[i + 1] = Math.max(sum, sums[i]); } int ans = 0; for (int i = 0, sum = 0, pre, len; i < n; i++) { sum += nums[i]; pre = find(sums, sum - k); len = pre == -1 ? 0 : i - pre + 1; ans = Math.max(ans, len); } return ans; } public static int find(int[] sums, int num) { int l = 0; int r = n; int m = 0; int ans = -1; while (l <= r) { m = (l + r) / 2; if (sums[m] >= num) { ans = m; r = m - 1; } else { l = m + 1; } } return ans; } public static int compute2() { minSums[n - 1] = nums[n - 1]; minSumEnds[n - 1] = n - 1; for (int i = n - 2; i >= 0; i--) { if (minSums[i + 1] < 0) { minSums[i] = nums[i] + minSums[i + 1]; minSumEnds[i] = minSumEnds[i + 1]; } else { minSums[i] = nums[i]; minSumEnds[i] = i; } } int ans = 0; for (int i = 0, sum = 0, end = 0; i < n; i++) { while (end < n && sum + minSums[end] <= k) { sum += minSums[end]; end = minSumEnds[end] + 1; } if (end > i) { // 如果end > i， // 窗口范围：i...end-1，那么窗口有效 ans = Math.max(ans, end - i); sum -= nums[i]; } else { // 如果end == i，那么说明窗口根本没扩出来，代表窗口无效 // end来到i+1位置，然后i++了 // 继续以新的i位置做开头去扩窗口 end = i + 1; } } return ans; } }
2023-12-10 12:31:44
