leetcode-1785-構(gòu)成特定和需要添加的最少元素-創(chuàng)新互聯(lián)

給你一個整數(shù)數(shù)組nums，和兩個整數(shù)limit與goal。數(shù)組nums有一條重要屬性：abs(nums[i])<= limit。

創(chuàng)新互聯(lián)公司-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價比惠民網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式惠民網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋惠民地區(qū)。費(fèi)用合理售后完善，十余年實(shí)體公司更值得信賴。

返回使數(shù)組元素總和等于goal所需要向數(shù)組中添加的 最少元素?cái)?shù)量 ，添加元素 不應(yīng)改變 數(shù)組中abs(nums[i])<= limit這一屬性。

注意，如果x >= 0，那么abs(x)等于x；否則，等于-x。

示例 1：

輸入：nums = [1,-1,1], limit = 3, goal = -4
輸出：2
解釋：可以將 -2 和 -3 添加到數(shù)組中，數(shù)組的元素總和變?yōu)?1 - 1 + 1 - 2 - 3 = -4 。

示例 2：

輸入：nums = [1,-10,9,1], limit = 100, goal = 0
輸出：1

提示：

  • 1<= nums.length<= 10^5
  • 1<= limit<= 10^6
  • -limit<= nums[i]<= limit
  • -10^9<= goal<= 10^9

分析：

看到這道題，第一反應(yīng)就是把nums中的數(shù)加起來，然后用加起來的值和goal的差值除以limit即可得到結(jié)果。

class Solution {public:
    int minElements(vector& nums, int limit, int goal) {int addnum = 0;
        for(auto num : nums)
            addnum += num;
        int gapnum = goal - addnum;
        return (abs(gapnum) - 1)/abs(limit) + 1;
    }
};

很遺憾只能滿足65 / 77 個通過測試用例。原因在于后面的測試用例中nums的和非常大，超出了int所能表示的范圍，因此我們還要考慮其他的方式。

為了防止超出范圍，我想到了一個方法：

在nums求和的過程中，想辦法讓和的絕對值小于limit，我們可以通過給這個和加上或者減去limit來實(shí)現(xiàn)這個效果，并分別記錄加上和減去的次數(shù)，這個次數(shù)在后面是可以相互抵消的。

依照這個思路可得到如下代碼：

class Solution {public:
    int minElements(vector& nums, int limit, int goal) {int addnum = 0;//nums的和(其中加上和減去了多個limit)
        int minustimes = 0;//減limit次數(shù)
        int plustimes = 0;//加limit次數(shù)
        for(auto num : nums){addnum += num;
            if(addnum >= limit){//過大則減
                addnum -= limit;
                ++minustimes;
            }
            if(addnum<= -limit){//過小則加
                addnum += limit;
                ++plustimes;
            }
        }
        int gapnum = goal - addnum;//goal與addnum的差值
        if(gapnum == 0)//正好為0時，可直接返回差值
            return abs(minustimes - plustimes);
        int remaintimes = (abs(gapnum) - 1)/abs(limit) + 1;//加減limit后還需limit的個數(shù)
        int totaltimes = 0;//總次數(shù)
        if(gapnum >0){//gapnum大于0時，remaintimes為加的次數(shù)
            totaltimes = abs(remaintimes + plustimes - minustimes);
        }else{//gapnum小于0時，remaintimes為減的次數(shù)
            totaltimes = abs(remaintimes + minustimes - plustimes);
        }
        return totaltimes;
    }
};

執(zhí)行用時：88 ms, 在所有 C++ 提交中擊敗了92.20%的用戶

內(nèi)存消耗：71.6 MB, 在所有 C++ 提交中擊敗了78.72%的用戶

通過測試用例：77 / 77

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前標(biāo)題：leetcode-1785-構(gòu)成特定和需要添加的最少元素-創(chuàng)新互聯(lián)
URL分享：http://muchs.cn/article26/coedjg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站導(dǎo)航、營銷型網(wǎng)站建設(shè)、面包屑導(dǎo)航、網(wǎng)站排名、網(wǎng)站建設(shè)、全網(wǎng)營銷推廣

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

外貿(mào)網(wǎng)站制作