音乐网站开发环境描述,百度联盟app,wordpress 婴儿,网站备案 取名资讯通不过class083 动态规划中用观察优化枚举的技巧-下【算法】
算法讲解083【必备】动态规划中用观察优化枚举的技巧-下 code1 1235. 规划兼职工作
// 规划兼职工作 // 你打算利用空闲时间来做兼职工作赚些零花钱#xff0c;这里有n份兼职工作 // 每份工作预计从startTime[i]开始、e…class083 动态规划中用观察优化枚举的技巧-下【算法】
算法讲解083【必备】动态规划中用观察优化枚举的技巧-下 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个元素 // 如果满足0ijnums.length 且 nums[i]nums[j]则为一个逆序对 // 给你两个整数n和k找出所有包含从1到n的数字 // 且恰好拥有k个逆序对的不同的数组的个数 // 由于答案可能很大只需要返回对10^97取余的结果 // 测试链接 : https://leetcode.cn/problems/k-inverse-pairs-array/
最优解 利用观察 构造窗口累加和已经进入 观察并设计高效的查询结构 的范畴了 只不过这个结构就仅存在于概念并用一个int类型的变量维护而已
package class083;// K个逆序对数组
// 逆序对的定义如下
// 对于数组nums的第i个和第j个元素
// 如果满足0ijnums.length 且 nums[i]nums[j]则为一个逆序对
// 给你两个整数n和k找出所有包含从1到n的数字
// 且恰好拥有k个逆序对的不同的数组的个数
// 由于答案可能很大只需要返回对10^97取余的结果
// 测试链接 : 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 jfor (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 jwindow ((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// jans 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范围上这前i1个数字的累加和sum nums[i];// sums[i 1] : 前i1个包括一个数字也没有的时候所有前缀和中的最大值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来到i1位置然后i了// 继续以新的i位置做开头去扩窗口end i 1;}}return ans;}}
2023-12-10 12:31:44
