410. 分割数组的最大值 - [困难]- (二分+贪心)

410. 分割数组的最大值 - [困难]- (二分+贪心) ,第1张

力扣https://leetcode-cn.com/problems/split-array-largest-sum/

二分+贪心
  • 想到了子序列的和最大值是整个数组的和,这个作为二分的上界
  • 没想到元素的最大值作为二分的下届
  • 想到了可以不断的从左到右以元素累加的形式找最大值,且想到类似猜数的形式,猜一个最大值,不断探索,但是没想到具体实现代码思路
  • 个人总结
    • 二分标准模板思维已经很熟悉,也想到了猜数的经典套路
    • 但是把问题抽象成这种经典套路的能力还是不行,还需要多练习,持续循环的总结
package com.company.binarySearch;

public class Solution10 {

    public int splitArray(int[] nums, int m) {
        // left 单个元素得最大值,right所有元素得和
        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)) {
                //以mid最为最大值,满足条件的拆分子序列数量 小于目标个数m,则说明mid最为最大值太大了拆分的个数不够m个序列,因此right左移动的目的是缩小最大值
                //以mid最为最大值,满足条件的拆分子序列数量 等于目标个数m,只能说明找到了一种满足条件的拆分方式,但是还没找到子序列最大值最小的情况,为了找到让这个值更小所有此right左移动的目的是缩小最大值
                right = mid;

            } else {
                //调大最大值
                left = mid + 1;
            }
        }
        return left;
    }

    // max 已经假设是这一轮的最大值,所有其它拆分子序列的和必须小于max,当拆分子序列的和大于max的时候开始另外一个拆分
    public boolean check(int[] nums, int max, int m) {
        //拆分子序列的和
        int sum = 0;

        //拆分子序列的个数
        int cnt = 1;

        for (int i = 0; i < nums.length; i++) {
            if (sum + nums[i] > max) {
                cnt++;
                sum = nums[i];
            } else {
                sum += nums[i];
            }
        }

        //满足条件的拆分子序列数量 小于等于目标个数m
        return cnt <= m;
    }
}

基本上能有贪心的问题就能用动态规划 

专项练习动态规划的时候再来做这个

class Solution {
    public int splitArray(int[] nums, int m) {
        int n = nums.length;
        int[][] f = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(f[i], Integer.MAX_VALUE);
        }
        int[] sub = new int[n + 1];
        for (int i = 0; i < n; i++) {
            sub[i + 1] = sub[i] + nums[i];
        }
        f[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++) {
                    f[i][j] = Math.min(f[i][j], Math.max(f[k][j - 1], sub[i] - sub[k]));
                }
            }
        }
        return f[n][m];
    }
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/577790.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-11
下一篇 2022-04-11

发表评论

登录后才能评论

评论列表(0条)

保存