做网站的主流技术,西安建设工程信息网怎么看,微信h5页面制作小程序,江西省网站备案2024.1.21 题目来源我的题解方法一 动态规划前缀和方法二 贪心二分方法三 贪心二分#xff08;自己的#xff09; 题目来源
力扣每日一题#xff1b;题序#xff1a;410
我的题解
方法一 动态规划前缀和
参考官方题解 令 dp[i][j]表示将数组的前 i 个数分割为 j段所能得… 2024.1.21 题目来源我的题解方法一 动态规划前缀和方法二 贪心二分方法三 贪心二分自己的 题目来源
力扣每日一题题序410
我的题解
方法一 动态规划前缀和
参考官方题解 令 dp[i][j]表示将数组的前 i 个数分割为 j段所能得到的最大连续子数组和的最小值。在进行状态转移时我们可以考虑第 j段的具体范围即我们可以枚举 k其中前 k个数被分割为 j−1段而第 k1 到第 i个数为第 j段。此时这 j 段子数组中和的最大值就等于 dp[k][j−1] 与 preSum(k1,i) 中的较大值其中 preSum(i,j)表示数组 nums 中下标落在区间 [i,j]内的数的和。 时间复杂度O( n 2 m n^2m n2m) 空间复杂度O(nm) public int splitArray(int[] nums, int m) {int n nums.length;int[][] dp new int[n 1][m 1];for (int i 0; i n; i) {Arrays.fill(dp[i], Integer.MAX_VALUE);}//求前缀和int[] preSum new int[n 1];for (int i 0; i n; i) {preSum[i 1] preSum[i] nums[i];}dp[0][0] 0;for (int i 1; i n; i) {for (int j 1; j Math.min(i, m); j) {for (int k 0; k i; k) {dp[i][j] Math.min(dp[i][j], Math.max(dp[k][j - 1], preSum[i] - preSum[k]));}}}return dp[n][m];
}方法二 贪心二分 参考官方题解。 时间复杂度O(n×log(sum−maxn)) 空间复杂度O(1) public int splitArray(int[] nums, int m) {int left 0, right 0;for (int i 0; i nums.length; i) {right nums[i];if (left nums[i]) {left nums[i];}}while (left right) {int mid (right - left) / 2 left;if (check(nums, mid, m)) {right mid;} else {left mid 1;}}return left;
}public boolean check(int[] nums, int x, int m) {int sum 0;int cnt 1;for (int i 0; i nums.length; i) {if (sum nums[i] x) {cnt;sum nums[i];} else {sum nums[i];}}return cnt m;
}方法三 贪心二分自己的 两个变量need和cur分别表示需要的子数组数量和当前子数组的元素之和。 接下来代码遍历数组nums中的每个元素num。如果cur加上num大于mid则需要增加一个子数组将cur重置为0。然后将num加到cur上。 最后如果need小于等于k则说明当前的mid满足条件将right更新为mid否则将left更新为mid1。 循环结束后返回left作为结果。 时间复杂度O(nlogm)。n为数组长度m为 数组之和-数组中的最大值 空间复杂度O(1) public int splitArray(int[] nums, int k) {int leftArrays.stream(nums).max().getAsInt();int rightArrays.stream(nums).sum();while(leftright){int midleft((right-left)1);int need1;int cur0;for(int num:nums){if(curnummid){need;cur0;}curnum;}if(needk)rightmid;elseleftmid1;}return left;
}有任何问题欢迎评论区交流欢迎评论区提供其它解题思路代码也可以点个赞支持一下作者哈~
