代码编织梦想

在这里插入图片描述

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨
🌲 作者简介:硕风和炜,CSDN-Java领域优质创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯

🚀 算法题 🚀

在这里插入图片描述

🚩 题目链接

⛲ 题目描述

给定一个非负整数数组 nums 和一个整数 m ,你需要将这个数组分成 m 个非空的连续子数组。

设计一个算法使得这 m 个子数组各自和的最大值最小。

示例 1:

输入:nums = [7,2,5,10,8], m = 2
输出:18
解释:
一共有四种方法将 nums 分割为 2 个子数组。
其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18,在所有情况中最小。
示例 2:

输入:nums = [1,2,3,4,5], m = 2
输出:9
示例 3:

输入:nums = [1,4,4], m = 3
输出:4

提示:

1 <= nums.length <= 1000
0 <= nums[i] <= 106
1 <= m <= min(50, nums.length)

🌟 求解思路&实现代码&运行结果


⚡ 暴力法

🥦 求解思路

  1. 简单概括题目的意思:我们需要将给定的数组nums划分为k个子数组,然后找到每一次可以进行划分方案中的最大值,然后将所有可行的方案中的最小值找出来即可。
  2. 怎么做呢?我们就可以枚举每一个开始的位置i,通过前缀和快速求解从left到i位置子数组的和,然后递归去求后面重复子规模的结果。
  3. 有了基本的思路,接下来我们就来通过代码来实现一下。

🥦 实现代码

class Solution {
    
    int[] sum;
    int[] nums;
    int k;
    int n;

    public int splitArray(int[] nums, int k) {
        this.n=nums.length;
        this.nums=nums;
        this.k=k;
        sum=new int[n+1];
        for(int i=1;i<=n;i++){
            sum[i]=sum[i-1]+nums[i-1];
        }
        return process(0,0);
    }

    public int process(int left,int cnt){
        if(cnt+1==k){
            return sum[n]-sum[left]; 
        }
        int min=Integer.MAX_VALUE;
        for(int i=left;i<nums.length;i++){
            int max=Math.max(sum[i+1]-sum[left],process(i+1,cnt+1));
            min=Math.min(min,max);
        }
        return min;
    }    
}

🥦 运行结果

时间超出了限制,但是不要紧张,这是我们想要的结果!

在这里插入图片描述


⚡ 记忆化搜索

🥦 求解思路

  1. 因为在递归的过程中,会重复的出现一些多次计算的结果,我们通过开辟一个数组,将结果提前缓存下来,算过的直接返回,避免重复计算,通过空间来去换我们的时间。

🥦 实现代码

class Solution {
    
    int[] sum;
    int[] nums;
    int k;
    int[][] dp;
    int n;

    public int splitArray(int[] nums, int k) {
        this.n=nums.length;
        this.nums=nums;
        this.k=k;
        sum=new int[n+1];
        dp=new int[n+1][k+1];
        for(int i=0;i<=n;i++) Arrays.fill(dp[i],-1);
        for(int i=1;i<=n;i++){
            sum[i]=sum[i-1]+nums[i-1];
        }
        return process(0,0);
    }

    public int process(int left,int cnt){
        if(cnt+1==k){
            return sum[n]-sum[left]; 
        }
        if(dp[left][cnt]!=-1) return dp[left][cnt];
        int min=Integer.MAX_VALUE;
        for(int i=left;i<nums.length;i++){
            int max=Math.max(sum[i+1]-sum[left],process(i+1,cnt+1));
            min=Math.min(min,max);
        }
        return dp[left][cnt]=min;
    }    
}

🥦 运行结果

通过缓存,将重复计算的结果缓存下来,通过。
时间情况
在这里插入图片描述

空间情况
在这里插入图片描述


⚡ 动态规划

🥦 求解思路

  1. 有了递归,有了记忆化搜索,接下来就是动态规划了,直接上手。

🥦 实现代码

class Solution {
    
    int[] sum;
    int[] nums;
    int k;
    int[][] dp;
    int n;

    public int splitArray(int[] nums, int k) {
        this.n=nums.length;
        this.nums=nums;
        this.k=k;
        sum=new int[n+1];
        dp=new int[n+1][k+1];
        for(int i=1;i<=n;i++){
            sum[i]=sum[i-1]+nums[i-1];
        }
        for(int i = 0; i <= n; i++){
           Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[n][k]=0;
        for(int left=n-1;left>=0;left--){
            for(int cnt=k-1;cnt>=0;cnt--){
                int min=Integer.MAX_VALUE;
                for(int i=left;i<n;i++){
                    int max=Math.max(sum[i+1]-sum[left],dp[i+1][cnt+1]);
                    min=Math.min(min,max);
                }
                dp[left][cnt]=min;
            }
        }
        return dp[0][0];
    } 
}

🥦 运行结果

动态规划搞定,大家可以积极的尝试。

时间复杂度
在这里插入图片描述

空间复杂度
在这里插入图片描述


💬 共勉

最后,我想和大家分享一句一直激励我的座右铭,希望可以与大家共勉!

在这里插入图片描述

在这里插入图片描述

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Coder_ljw/article/details/130841523

leetcode_240._378.有序数组(递归)-爱代码爱编程

leetcode240号题目: 240解法: 暴力法:二重循环遍历二维数组,没有利用数组已经在行列有序的性质,超出运行时间无法通过。二分法搜索:是将搜索空间不断的减半,从而逼近解的过程。选择一起点,示例代码选择左下角为起点,如果当前位置的数值大于目标数,则对行进行减一以缩小当前位置的数值;大于则同理。代码如下:class Solution { pu