Re: [閒聊] 每日LeetCode已回收
2279. Maximum Bags With Full Capacity of Rocks
給你兩個陣列分別表示袋子的容量和石頭數量，現在我們有additionalRocks個石頭可以
放，試問最多可以裝滿幾個袋子。
Example：
Input: capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2
Output: 3
Explanation:
編號0、1、3的袋子任選兩個裝石頭加上編號2的袋子已經裝滿，所以最多可裝滿3個。
思路：
1.因為要盡可能的裝滿多個袋子，所以我們可以考慮貪婪演算法。
2.我們對"需要最少石頭就可裝滿"的袋子做貪婪演算法，具體的作法就是算出每個
袋子缺多少石頭才會裝滿，並且從少到多開始裝，直到每個袋子都檢查過或是已
經沒石頭可以裝進袋子。
3.我們可以把缺多少石頭的數量排序之後一個一個裝，若need <= additionalRocks 時
count就加一。
Java Code：
--------------------------------
class Solution {
public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
int n = capacity.length;
int[] need = new int[n];
for (int i = 0; i < n; i++) {
need[i] = capacity[i] - rocks[i];
}
Arrays.sort(need);
int count = 0;
int j = 0;
while (j < n && additionalRocks > 0) {
count += (need[j] <= additionalRocks) ? 1 : 0;
additionalRocks -= need[j++];
}
return count;
}
}
--------------------------------
--
https://i.imgur.com/uiFto42.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.106.12 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1672104163.A.8DF.html
→
12/27 09:23,
3年前
, 1F
12/27 09:23, 1F
推
12/27 09:26,
3年前
, 2F
12/27 09:26, 2F
我看到你昨天有在刷題 我不太建議用C刷 全部輪子都要自己造
你要刷可以考慮用C++
※ 編輯: Rushia (1.160.106.12 臺灣), 12/27/2022 09:29:04
推
12/27 09:31,
3年前
, 3F
12/27 09:31, 3F
推
12/27 09:34,
3年前
, 4F
12/27 09:34, 4F
推
12/27 10:18,
3年前
, 5F
12/27 10:18, 5F
推
12/28 00:02,
2年前
, 6F
12/28 00:02, 6F
→
12/28 00:02,
2年前
, 7F
12/28 00:02, 7F
討論串 (同標題文章)
完整討論串 (本文為第 155 之 719 篇)：