LeetCode Weekly Contest 294 – #2279 Maximum Bags With Full Capacity of Rocks 解題思路及翻譯

LeetCode Contest

這題出現在LeetCode 每週問題294 上，是屬於Medium難度的第二題

LeetCode題目翻譯

英文原文如下

You have n bags numbered from 0 to n – 1. You are given two 0-indexed integer arrays capacity and rocks. The i^th bag can hold a maximum of capacity[i] rocks and currently contains rocks[i] rocks. You are also given an integer additionalRocks, the number of additional rocks you can place in any of the bags.

Return the maximum number of bags that could have full capacity after placing the additional rocks in some bags.

中文翻譯

你有 n 個袋子，分別標示從 0 到 n-1 的數字。給予你兩個從 0 開始的陣列，分別為 capacity (容量) 及 rocks (石頭). 舉例來說，index 為 i 的袋子，最多可以容納 capacity[i] 顆石頭而且目前袋內有 rocks[i] 顆石頭。另外給了你一個整數 additionalRocks (額外的石頭)，你可以放進任意的袋子內。

回傳最多的可以被塞滿的袋子數量( 在你將 additionalRocks 放進袋子之後 )

沒什麼特別要注意的，capacity 跟 rocks 這兩個陣列的長度相同( = 幾個袋子)

來看看範例解釋下吧

第一題範例

容量 [2,3,4,5] 、 目前石頭 [1,2,4,4]，額外的石頭有2顆

以容量扣掉目前石頭來看，還能夠再放的石頭數各自為 [1,1,0,1]

假設現在我們在 index 0 跟 1 的袋子各放 1 顆石頭，那袋子裡的石頭就會變成 [2,3,4,4]

總共有3個袋子被塞滿了，故回傳 3

不可能有超過 3 個袋子被塞滿，備註 – 塞滿3個袋子的方法不只一種

第二題範例

容量[10,2,2]、目前石頭[2,2,0]，額外的石頭有100顆

在index 0 的袋子塞入 8 顆石頭跟index 2的袋子塞入2 顆石頭後，所有的袋子都滿了

故回傳 3

➡ 可以得到額外的石頭不用用完的消息

解題思路

這題一看完題目，就有了一個大致的雛型

1. 新增一個array用來儲存兩個array的插值
   • (其實現在想想，改為用capacity直接扣掉rocks也是可以的，應該可以省下空間)
2. 加總全部的差異，要是小於額外石頭數量 (代表一定可以塞滿所有帶子)，則直接回傳陣列長度
3. 將差異陣列從小大到排序 ➡ 因為要越多的袋子被塞滿越好，所以從差最少顆的開始塞!
4. 針對差異陣列遞迴，要是額外的石頭可以塞滿袋子，則額外石頭數扣除當次數量

⭐注意 : 初始差異為 0 的袋子也算是滿的 (對的..我這裡也錯過一次)

C# 解答

public class Solution {
    public int MaximumBags(int[] capacity, int[] rocks, int additionalRocks) {
      
        int[]diff = new int[capacity.Length];
        long cnt = 0;
        int resCnt = 0;
        
        for(int i=0 ;i<capacity.Length;i++)
        {
            int diffCnt = capacity[i] - rocks[i];
          
            diff[i] = diffCnt;
            cnt+=(long)diffCnt;
        }
 
        if((long)additionalRocks > cnt)
        {
            return capacity.Length;
        }
        
        Array.Sort(diff);

        foreach(var a in diff)
        {
            if(a == 0)
            {
                resCnt+=1;
                continue;
            }

            if(additionalRocks>=a)
            {
                resCnt+=1;
                additionalRocks-= a;
            }
            else
            {
                return resCnt;
            }
        }
        
        return resCnt;
    }
}

⭐為什麼我們要用long來儲存差異數加總呢?

是個傷心的故事，比賽時前幾次Submit都顯示錯誤，原來是有部分範例的差異總數會超過Int32的上限

Java 解答

class Solution {
    public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
        int[]diff = new int[capacity.length];
        long cnt = 0;
        int resCnt = 0;
        
        for(int i=0 ;i<capacity.length;i++)
        {
            int diffCnt = capacity[i] - rocks[i];
          
            diff[i] = diffCnt;
            cnt+=(long)diffCnt;
        }
 
        if((long)additionalRocks > cnt)
        {
            return capacity.length;
        }
        
        Arrays.sort(diff);

        for(int a : diff)
        {
            if(a == 0)
            {
                resCnt+=1;
                continue;
            }

            if(additionalRocks>=a)
            {
                resCnt+=1;
                additionalRocks-= a;
            }
            else
            {
                return resCnt;
            }
        }
        
        return resCnt; 
    }
}

僅為改寫了一些function的用法，本質上跟C#完全一樣

Python3 解答

class Solution:
    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:
        diff = []
        cnt = 0
        resCnt = 0
        
        for i in range(0,len(capacity)):
            diffCnt = capacity[i] - rocks[i]
            diff.append(diffCnt)
            cnt+=diffCnt

        if additionalRocks > cnt:
            return len(capacity)
        
        diff.sort()

        for a in diff:
            if a == 0:
                resCnt+=1
                continue

            if additionalRocks>=a:
                resCnt+=1
                additionalRocks-= a
            
            else:
                return resCnt
            
        return resCnt

JavaScript 解答

/**
 * @param {number[]} capacity
 * @param {number[]} rocks
 * @param {number} additionalRocks
 * @return {number}
 */
var maximumBags = function(capacity, rocks, additionalRocks) {
    var diff = [];
    var cnt = 0;
    var resCnt = 0;
    
    for(let i=0 ;i<capacity.length;i++)
    {
        var diffCnt = capacity[i] - rocks[i];
        
        diff[i] = diffCnt;
        cnt+=diffCnt;
    }

    if(additionalRocks > cnt)
    {
        return capacity.length;
    }
    
    diff.sort(function(a, b){return a-b});
    //diff.sort();
    //diff.forEach(element => console.log(element));

    for(let j = 0; j<diff.length; j++)
    {
        let a = diff[j];
        if(a == 0)
        {
            resCnt+=1;
            continue;
        }

        if(additionalRocks>=a)
        {
            resCnt+=1;
            additionalRocks-= a;
        }
        else
        {
            return resCnt;
        }
    }
    
    return resCnt; 
};

⭐要注意JavaScript 中的 Array.sort 若沒進行設定，會嘗試將物件轉為 string 並以其 UTF-16 進行比較並排序

結論

算是筆者參加比賽以來，難度相對低的第二題了

要注意的可能就是Interger的上限問題吧

"一日一錢，千日一千，繩鋸木斷，水滴石穿。"
                                                                                    羅大經《鶴林玉露》

封面照片 – Photo by John Salzarulo on Unsplash

題目連結 : Maximum Bags With Full Capacity of Rocks – LeetCode

最新文章

• LeetCode #2073 Time Needed to Buy Tickets 買到票所需要的時間2024-04-17
• LeetCode #1700 Number of Students Unable to Eat Lunch 吃不到午餐的學生數量2024-04-10
• LeetCode #1544 Make The String Great 讓字串變好2024-04-08
• LeetCode #977 Squares of a Sorted Array 已排序陣列的平方2024-03-21
• LeetCode #283 Move Zeroes 移動零2024-03-12