网站托管费用多少,建筑工程人才培训网,公司网站备案多少钱,公众号推文模板免费2024.1.19 题目来源我的题解方法一 动态规划方法二 动态规划#xff08;空间优化#xff09; 题目来源
力扣每日一题#xff1b;题序#xff1a;2809
我的题解
题解参考官方题解。
方法一 动态规划 若能找到一个最小的时间t使得数组和小于等于x#xff0c;则最多在一轮… 2024.1.19 题目来源我的题解方法一 动态规划方法二 动态规划空间优化 题目来源
力扣每日一题题序2809
我的题解
题解参考官方题解。
方法一 动态规划 若能找到一个最小的时间t使得数组和小于等于x则最多在一轮遍历n秒中找到否则就找不到。所以观察重置为零的数会按照 nums2的速度增长所以对于所有操作的数我们应该优先操作增长速度慢的数。 如果我们选择多个索引 i 1 , i 2 , … , i k i_1,i_2,…,i_k i1,i2,…,ik那么按照 n u m s 2 [ i 1 ] ≤ n u m s 2 [ i 2 ] ≤ … ≤ n u m s 2 [ i k ] nums_2[i_1]≤nums_2[i_2]≤…≤nums_2[i_k] nums2[i1]≤nums2[i2]≤…≤nums2[ik]的顺序进行设置是最优的。按照 nums2 的大小对所有数值对进行排序非递减顺序。用 dp[j][i] 表示如果对前 j个元素进行 i次操作可以减少的最大总值初始值为零。对于第 j 个元素我们可以选择对其进行操作或者不操作由此可以得到状态转移方程 dp[j][i]max(dp[j−1][i],dp[j−1][i−1] n u m s 2 nums_2 nums2[j−1]×i n u m s 1 nums_1 nums1[j−1]) 其中有 1≤i≤j≤n。 最后返回最小的 t使满足 sum( n u m s 1 nums_1 nums1)sum( n u m s 2 nums_2 nums2)×t−dp[n][t]≤x如果不存在返回 −1。 时间复杂度O( n 2 n^2 n2) 空间复杂度O( n 2 n^2 n2)。动态规划数组空间 public int minimumTime(ListInteger nums1, ListInteger nums2, int x) {int n nums1.size(), s1 0, s2 0;int[][] dp new int[n 1][n 1];//这里是技巧如何不改变原数组对其进行排序Integer index[]new Integer[nums2.size()];for(int i0;i nums2.size();i){index[i]i;}Arrays.sort(index,(a,b)-nums2.get(a)-nums2.get(b));for (int i 0; i n; i) {int a nums1.get(i), b nums2.get(i);s1 a;s2 b;}for (int j 1; j n; j) {int inindex[j-1];int b nums2.get(in), a nums1.get(in);for (int i j; i 0; --i) {dp[j][i] Math.max(dp[j - 1][i], dp[j - 1][i - 1] i * b a);}}for (int i 0; i n; i) {if (s2 * i s1 - dp[n][i] x) {return i;}}return -1;
}方法二 动态规划空间优化 dp[i] 的状态只和 dp[i−1]有关。 所以可以省去第一个维度从而优化空间从 O( n 2 n^2 n2) 优化到 O(n)其中 n 是输入数组的长度。 时间复杂度O( n 2 n^2 n2) 空间复杂度O(n) public int minimumTime(ListInteger nums1, ListInteger nums2, int x) {int n nums1.size(), s1 0, s2 0;int[] dp new int[n 1];Integer index[]new Integer[nums2.size()];for(int i0;i nums2.size();i){index[i]i;}Arrays.sort(index,(a,b)-nums2.get(a)-nums2.get(b));for (int i 0; i n; i) {int a nums1.get(i), b nums2.get(i);s1 a;s2 b;}for (int j 1; j n; j) {int inindex[j-1];int b nums2.get(in), a nums1.get(in);for (int i j; i 0; --i) {dp[i] Math.max(dp[i], dp[i - 1] i * b a);}}for (int i 0; i n; i) {if (s2 * i s1 - dp[i] x) {return i;}}return -1;
}注意技巧如何在不改变原数组的情况下对数组进行排序需要额外的序号数组。
有任何问题欢迎评论区交流欢迎评论区提供其它解题思路代码也可以点个赞支持一下作者哈~
