分割数组衍生思考

痛定思痛。 2022-11-28 13:19 111阅读 0赞

### 文章目录 ###

*   *  安排邮筒问题
     *   *  思考
     *  二分查找系列问题
     *   *  小张刷题计划
         *  平方根问题
         *  寻找重复数
         *  爱吃香蕉的珂珂
         *  在D天内送达包裹的能力
         *  制作 m 束花所需的最少天数

> 广告： github上新开立了一个仓库[May-Nodes][]，本篇博客也收录其中。包括但不限于之前面试遇到的相关数据库,计算机操作系统,Java基础知识，计算机网络以及LeetCode等算法题解等知识。届时也会整理学习使用的PDF文档与资源。有需要的小伙伴 可以点个关注和`star`。在持续更新中，总会遇到你想要的。

[分割数组原文地址][Link 1]

## 安排邮筒问题 ##

[安排邮筒][Link 2]

### 思考 ###

同分割数组的最大值[分割数组的最大值][Link 3]，有异曲同工之妙，首先对于分割数组最大值来说给定我们一个一维的数组，其中有不同的值，让我们来进行分割，将原来的数组分割成为不同的几份，然后分割的数组的和的最小值。

**解决方案是利用到动态规划**：对于动态规划二维数组 `dp[i][j]`表示的是说对于给定的数组的前`i`个分割成为 `j`个不同的小数组之后不同数组之间和的**最大值最小**的情况，我们现在来寻求一个转移方程，假设对于 在 `[0,i-1]`范围内，存在一个K值，可以将前半部分`[0,k]`划分成为`j-1`子数组，同时对于`[k+1,i]`范围内至少包含一个元素，作为最后的一个分割（也就是最后一个被分割的小数组），我么每走过一个`i`值时候，就在`0-i`之间进行枚举，比较前`K`个元素与`[k+1,i]`的最大值，就是我们的分割的数组的最大值，然后与`dp[i][j]`进行枚举比较，找出最小值，以此来进行循环判断找出来最终的最小值。

对于当前的**安排邮筒问题**而言，要求我们在一维数组中安排邮筒，然后求得所有的到其最近邮筒的距离的和，还是思考状态转移方程，对于`最后一个邮筒的归属问题`,思考对于最后一个邮筒`能将剩余的住户分割成的两部分如何才能够达到距离最小值`。所以和上面的`分割数组的最小值相同`，在`[0,i]`范围内找寻一个`temp`值,计算`[temp-1][j-1]`表示分割为`j-1`个小组，然后同分割最小一样，分割最小是进行相减操作，这里我们提前计算好，从`[temp，i]`安排一个邮筒的最小值。

public int minDistance(int[] houses, int k) { 
        int len = houses.length;
            int [][] res = new int [len][len];
            Arrays.sort(houses);
            for(int i= 0 ;i<len;i++){ 
                for(int j= i;j<len;j++){ 
                    int mid= i+ (j-i)/2;
                    for(int temp = i;temp<= j;temp++){ 
                        res[i][j] +=Math.abs(houses[temp]-houses[mid]);
                    }
                }
            }
            int [][]dp = new int[len][k+1];
            for(int i= 0;i<len;i++)
                dp[i][0]= Integer.MAX_VALUE/2;
            for(int i= 1;i<len;i++){ 
                for(int j = 1;j<= k;j++){ 
                    dp[i][j] =Integer.MAX_VALUE/2;
                    for(int  temp = 0;temp<=i;temp++){ 
                        int q = 0;
                        if(temp!=0)
                            q= dp[temp-1][j-1];
                        dp[i][j]= Math.min(dp[i][j],q+res[temp][i]);
                    }
                }
            }
            return  dp[len-1][k];
        }

## 二分查找系列问题 ##

之前写过一篇系列的二分查找的题解：[二分查找基础篇][Link 4]对于上一篇进行了基础部分的介绍与学习，同时对于数组分割的衍生题目都如下所示：

### 小张刷题计划 ###

[小张刷题计划][Link 5]

1.  根据具体的情况计算出左右边界的值，对于每天的刷题数目，若是给定的时间足够多，就可以每天只完成一道题目（不可能每天是0个题目）。最多时候就是在一天内完成题目，就是给定数组的和。
2.  进行取中间值，然后表示若是每天刷这么多题目的时候，需要多少天完成目标，若是计算出来的时间要大于我们给定的天数，表示每天完成的题目题目太少，需要对每天完成的题目进行下限的上调处理，若是完成的天数要小于我们给定的规定的天数，表示的是说，每天刷题数是较多的。进行上线的下调。
3.  如何在将耗时最多的题目交给别人完成的同时还能够计算出来自己需要消耗多少天是一个难题。
4.  参考前面一题的思路，对数组进行轮询的相加操作，表示刷题数目的增加，同时计算出来当前范围的最大值，当前计算出来的值减去最大值（就是将最多题目交给别人去做）若是还大于当前给定的刷题的中间值，表示需要添加天数，不然不能够满足我们给定的条件。

public int minTime(int[] time, int m) { 
    
            int left =0;
            int  right=0;
            for(int i =0;i<time.length;i++){ 
                right+=time[i];
            }
            while(left<right){ 
                int mid = left+ (right - left)/2;
                int split = splits(time,mid);
                if(split>m)
                { 
                    left = mid + 1;
                }
                else 
                right = mid;
            }
            return left;
        }
        public  int splits(int [] time,int mid){ 
            int split =1;
            int tempSum = time[0];
            int curMax = time[0];
            for(int i=1;i<time.length;i++){ 
                curMax = Math.max(curMax,time[i]);
                if(tempSum + time[i] - curMax >mid){ 
                    split++;
                    curMax= time[i];
                    tempSum = 0;
                }
                tempSum += time[i];
            }
            return split;
        }

### 平方根问题 ###

[平方根问题][Link 6]

1.  根据具体的情况判断出来左右区间值，对于左区间而言，最小值是1，对于右区间来说，任何`非负整数的平凡根`都会大于等于其一半（其实我们也可以设置右边界为其本身，但是这样的消耗是毫无意义的）。
2.  寻找中间值，将其平方与要求的值进行对比，进行左右边界的判断。

public int mySqrt(int x) { 
            if(x==0)
            return 0;
     long left =1 ;
            long right  = x/2;
            while(left < right){ 
                 long mid = (left + right + 1) >>> 1;
                long  temp = mid * mid;
                if(temp>x)
                right = mid -1;
                else 
                left = mid;
            }
            return  (int)left;
        }

### 寻找重复数 ###

[寻找重复数][Link 7]

1.  对于left 左值应该为1，表示最左边，right 右值为当前的数组的长度减一也就是我们的`n`。
2.  利用二分法的基础原则，找到中间值，然后判断对于数组中小于当前值的有多少，若是数量要大于中间值，表示出现的重复的数在左边，此时最大值的阈值下调，同理，最小值的阈值上调。

int left = 1;
            int right = nums.length-1;
            while(left<right){ 
                int mid = left+(right-left)/2;
                int temp= 0;
                for(int num :  nums)
                { 
                    if(num<=mid)
                        temp++;
                }
    
                if(temp>mid){ 
                    right = mid;
                }
                else { 
                    left= mid+1;
                }
            }
            return  left;

### 爱吃香蕉的珂珂 ###

[爱吃香蕉的珂珂][Link 8]（珂珂真难伺候 淦）

1.  若是时间足够长，珂珂就可以以最小的速度吃饭所有的香蕉，此时的最小值是1。若是时间恰好就是香蕉的堆数，此时最小的速度就是某堆香蕉的值（最大值）。
2.  然后设置中间值，表示若是以当前的速度来吃香蕉求出来需要多少个小时。
3.  若是发现求出来的小时数要大于给定的时间，表示当前的速度太慢，我们需要提高速度，若是要小于给定的时间，表示当前的速度过快，我们要降低速度。
4.  下面就是来判断如何给定当前的速度来求出时间，就是利用当前堆中香蕉的数目/当前的速度，但是在一个小时内，吃不完成也不能够转战其他的地方，所以我们需要对结果进行向上取整 `(M+n-1)/N`。

int MaxLeft =1;
            for(int pile:piles){ 
                MaxLeft = Math.max(MaxLeft,pile);
            }
            int left =1;
            int right=MaxLeft;
            while(left<right){ 
                int mid=left+(right-left)/2;
                if(getmid(piles,mid)>H)
                { 
                    left=mid+1;
                }
                else 
                right=mid;
            }
            return right;
        }
        public int getmid(int [] piles,int speed){ 
            int sum=0;
            for(int pile:piles){ 
                sum+=(pile+speed-1)/speed;
            }
            return sum;
        }

### 在D天内送达包裹的能力 ###

[在D天内送法包裹的能力][D]

1.  根据具体的条件分析出来具体的左右值，要求我们求得最低的运载能力，所以最低值就是我们的包裹重量的的最大值（因为不能够再低于这个值，不然不能够承载当前的包裹的重量）。对于最大值来说，就是极端一点就是要求我们再一天之内完成所有的运输，就是所有的包裹的和。
2.  先进行求中间值，然后以当前值，表示的是运载能力，来求出需要多少天才能够完成当前的任务调度。
3.  若是发现求得的值要大于我们给定的天数，表示我们当前的每天的运输能力太弱，才会消耗那么多的时间，所以进行下限值的上移，同理，进行下限值的上移操作。
4.  如何求得消耗的天数，初始化的天数为1，将数组的值进行遍历叠加，若是发现大于我们给定的值，表示运载的太多，我们需要进行重新来开一天进行运载，同时`天数+1`。同基础版本的原理是相同的。

public int shipWithinDays(int[] weights, int D) { 
            
            int sum  = 0;
            int max  = 0;
            for(int i = 0; i< weights.length ; i++){ 
               max =  Math.max(max,weights[i]);
                sum+=weights[i];
            }
            int left = max;
            int right =sum;
            while(left < right){ 
                int mid = left + (right-left)/2;
                int split = splits(weights,mid);
                if(split> D){ 
                    left = mid + 1;
                }
                else
                { 
                    right = mid;
                }
            }
            return left;
        }
        public int splits(int [] nums,int mid){ 
            int split =1;
            int sum =0;
            for(int num : nums){ 
                if(sum+num> mid){ 
                    sum = 0;
                    split++;
                }
                sum+=num;
            }
            return split;
        }

### 制作 m 束花所需的最少天数 ###

[制作 m 束花所需的最少天数][m]

1.  还是先分析最大值与最小值，最小值就是不需要等待，最大值就是需要等待最多的时间(数组中的最大值)。
2.  基础的二分，查找出来根据当前的过去的天数生成的几组相邻的花和我们预期的结果进行比较，大于表示我们的时间太长，小于表示时间过短。
3.  然后在函数里面进行简单的逻辑判断。返回可以的组数。

public int minDays(int[] nums, int m, int k) { 
          if(nums.length<m*k)
                return  -1;
            int left = 0;
            int right = 0;
            for(int temp :nums){ 
                if(temp>right)
                    right = temp;
            }
            while (left<right){ 
                int mid = left+ (right-left)/2;
                // count 表示的是count 个连续的k多花
                int count = getresult(nums,mid,k);
                if(count>=m){ 
                    right = mid;
                }
                else { 
                    left = mid+1;
    
                }
            }
            return  left;
        }
        private  static  int getresult(int [] nums,int mid,int k){ 
            int res = 0; // 表示最后的结果。
            int count = 0;// 表示当前满足情况的个数
            for(int i= 0;i<nums.length;i++){ 
                if(nums[i]<=mid){ 
                    count++;
                    if(count%k==0)
                        // 取模运算表示相等，即可进行结果的++
                    res++;
                }
                else
                    count = 0;
            }
            return  res;
        }

[May-Nodes]: https://github.com/maycope/May-Nodes
[Link 1]: https://blog.csdn.net/weixin_44015043/article/details/107703205
[Link 2]: https://leetcode-cn.com/problems/allocate-mailboxes/
[Link 3]: https://leetcode-cn.com/problems/split-array-largest-sum/
[Link 4]: https://github.com/maycope/May-Nodes/blob/master/All-algorithm/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.md
[Link 5]: https://leetcode-cn.com/problems/xiao-zhang-shua-ti-ji-hua/
[Link 6]: https://leetcode-cn.com/problems/sqrtx/
[Link 7]: https://leetcode-cn.com/problems/find-the-duplicate-number/
[Link 8]: https://leetcode-cn.com/problems/koko-eating-bananas/
[D]: https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/
[m]: https://leetcode-cn.com/problems/minimum-number-of-days-to-make-m-bouquets/