国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

leetcode410. Split Array Largest Sum

Jonathan Shieber / 817人閱讀

摘要:在這里,邊界被設(shè)置為該數(shù)組中可以得到的子數(shù)組元素和的最小值和最大值。在確定了數(shù)組元素和的上界和下界之后,就需要找出一種方法,來不斷壓縮區(qū)間直到最后一種。可以使用中間位置作為數(shù)組元素和的邊界,即假設(shè)所有的連續(xù)數(shù)組的和都不會(huì)超過值。

題目要求
Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Note:
If n is the length of array, assume the following constraints are satisfied:

1 ≤ n ≤ 1000
1 ≤ m ≤ min(50, n)
Examples:

Input:
nums = [7,2,5,10,8]
m = 2

Output:
18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

將一個(gè)長(zhǎng)度為n的正整數(shù)數(shù)組分割為m個(gè)非空的連續(xù)子數(shù)組,并分別計(jì)算每個(gè)子數(shù)組中所有元素的和。求一種分割方式,使得該分割方式生成的最大子數(shù)組和為所有分割方式中最小的。

比如題目中的例子nums = [7,2,5,10,8],m = 2
一共有四種分割方式:

[7], [2,5,10,8]

[7,2], [5,8,10]

[7,2,5], [8,10]

[7,2,5,8], [10]

其中第三種分割得到的最大子數(shù)組的和 是所有分割中最小的

思路一:動(dòng)態(tài)規(guī)劃

首先,我們可以通過遞歸的方式來遍歷所有的分割方式,從而找到所有分割方式中最符合要求的那一種結(jié)果。代碼如下:

    public int splitArray(int[] nums, int m) {
        //計(jì)算[0...i]中所有元素的和
        int[] sums = new int[nums.length+1];
        for(int i = 1 ; i<=nums.length ; i++) {
            sums[i] = nums[i-1] + sums[i-1];
        }
        return splitArray(nums, m, 0, sums);
    }
    
    //計(jì)算從cur位置開始,將其分割為m個(gè)子數(shù)組的最小分割場(chǎng)景
    public int splitArray(int[] nums, int m, int cur, int[] sums) {
        if(m == 1) {
            return sums[nums.length] - sums[cur];
        }
        int min = Integer.MAX_VALUE;
        int diff = Integer.MAX_VALUE;
        for(int i = cur+1 ; i<=nums.length-m+1 ; i++) {
            //當(dāng)前元素為止,左邊的子數(shù)組的元素和
            int left = sums[i]-sums[cur];
            //對(duì)右邊的剩余元素遞歸的調(diào)用splitArray方法
            int right = splitArray(nums, m-1, i, sums);
            //如果出現(xiàn)二者之間的差遞增的情況,則說明距離最優(yōu)分割越來越遠(yuǎn),則停止繼續(xù)嘗試
            if(diff < Math.abs(left - right)) {
                break;
            }
            diff = Math.abs(left - right);
            min = Math.min(min, Math.max(left, right));
        }
        return min;
    }

這種方法在大數(shù)據(jù)量的場(chǎng)景下會(huì)出現(xiàn)超時(shí)的問題,本質(zhì)在于我們沒有足夠的復(fù)用中間的所有場(chǎng)景,如對(duì)于[i-j]這個(gè)子數(shù)組的k次分割的最優(yōu)結(jié)果。如果我們記錄從i到數(shù)組結(jié)尾進(jìn)行k次分割的最優(yōu)結(jié)果,該結(jié)果記錄為dp[i][k],則從j到數(shù)組結(jié)尾進(jìn)行k+1次分割的最優(yōu)結(jié)果為min(max(num(j), dp[j+1][k]), max(nums(j)+num(j+1), dp[j+2][k])... )
代碼如下:

    public int splitArray(int[] nums, int m)
    {
        int L = nums.length;
        //記錄0-i的元素和
        int[] S = new int[L+1];
        S[0]=0;
        for(int i=0; i
思路二:二分法

這是一個(gè)非常難想到的方法。二分法的難點(diǎn)一直在于如何劃分初始邊界,以及如何逐漸縮小邊界并且確保左右指針可以相遇。在這里,邊界被設(shè)置為該數(shù)組中可以得到的子數(shù)組元素和的最小值和最大值。
根據(jù)基本常識(shí)可知,數(shù)組的最大元素決定了該數(shù)組分割出的子數(shù)組的元素和的下界,而數(shù)組的元素和上界一定不會(huì)超過數(shù)組所有元素的和。
在確定了數(shù)組元素和的上界和下界之后, 就需要找出一種方法,來不斷壓縮區(qū)間直到最后一種。

可以使用中間位置作為數(shù)組元素和的邊界,即假設(shè)所有的連續(xù)數(shù)組的和都不會(huì)超過mid值。假如按照這種方式得到的分割結(jié)果大于了規(guī)定的m個(gè),則說明mid值作為最大元素和上界并不能夠做到只分割出m個(gè)子數(shù)組,因此最大元素和上界一定在mid和有界中間。同理,假如按照這種方式得到的分割結(jié)果小于等于規(guī)定的m個(gè),則說明mid值作為最大元素和上界能夠滿足分割出m個(gè)子數(shù)組,但是可能還存在更優(yōu)解。通過這種二分法思路得到的最后結(jié)果就是所需要的最小分割結(jié)果。

    public int splitArray2(int[] nums, int m) {
        long sum = 0;
        int max = Integer.MIN_VALUE;
        for(int i = 0 ; i target) {
                sum = nums[i];
                count++;
                if(count > m) {
                    return false;
                }
            }
        }
        return true;
    }

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/74552.html

相關(guān)文章

  • 410. Split Array Largest Sum

    摘要:題目鏈接枚舉所有可能的,找最小的那個(gè),二分枚舉優(yōu)化復(fù)雜度,因?yàn)閿?shù)組不含負(fù)數(shù),根據(jù)是否滿足條件可以二分結(jié)果。注意由于不含負(fù)數(shù),并且,相當(dāng)于一條遞增,一條遞減的線找交點(diǎn),極端情況沒有交點(diǎn)結(jié)果出現(xiàn)在兩端,所以依然可以找。 410. Split Array Largest Sum 題目鏈接:https://leetcode.com/problems... 枚舉所有可能的largest sum,...

    caige 評(píng)論0 收藏0
  • [LeetCode] Maximum Subarray

    Problem Find the contiguous subarray within an array (containing at least one number) which has the largest sum. Example For example, given the array [-2,1,-3,4,-1,2,1,-5,4],the contiguous subarray [4...

    Donald 評(píng)論0 收藏0
  • [Leetcode] Maximum Subarray 子序列最大和

    摘要:最新更新請(qǐng)見原題鏈接動(dòng)態(tài)規(guī)劃復(fù)雜度時(shí)間空間思路這是一道非常典型的動(dòng)態(tài)規(guī)劃題,為了求整個(gè)字符串最大的子序列和,我們將先求較小的字符串的最大子序列和。而最大子序列和的算法和上個(gè)解法還是一樣的。 Maximum Subarray 最新更新請(qǐng)見:https://yanjia.me/zh/2019/02/... Find the contiguous subarray within an ar...

    summerpxy 評(píng)論0 收藏0
  • leetcode_53 Maximum Subarray

    摘要:如果單開元素加和更大判斷前面的子數(shù)組和是不是小于。此元素就成為了子數(shù)組的第一個(gè)元素。每次操作都要判斷,當(dāng)前是否是最大值,更新值。 題目詳情 Find the contiguous subarray within an array (containing at least one number) which has the largest sum.For example, given t...

    y1chuan 評(píng)論0 收藏0
  • leetcode53 Maximum Subarray 最大連續(xù)子數(shù)組

    摘要:我們可以分別得出這三種情況下的最大子數(shù)列和,并比較得出最大的那個(gè)。我們只需要考慮左子列的最大和以及跨越了左右的中子列的最大值。 題目要求 Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given ...

    Bamboy 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<