一個(gè)班級(jí)里有 n 個(gè)學(xué)生，編號(hào)為 0 到 n - 1 。每個(gè)學(xué)生會(huì)依次回答問題，編號(hào)為 0 的學(xué)生先回答，然后是編號(hào)為 1 的學(xué)生，以此類推，直到編號(hào)為 n - 1 的學(xué)生，然后老師會(huì)重復(fù)這個(gè)過程，重新從編號(hào)為 0 的學(xué)生開始回答問題。

給你一個(gè)長度為 n 且下標(biāo)從 0 開始的整數(shù)數(shù)組 chalk 和一個(gè)整數(shù) k 。一開始粉筆盒里總共有 k 支粉筆。當(dāng)編號(hào)為 i 的學(xué)生回答問題時(shí)，他會(huì)消耗 chalk[i] 支粉筆。如果剩余粉筆數(shù)量 嚴(yán)格小于 chalk[i] ，那么學(xué)生 i 需要 補(bǔ)充 粉筆。

請你返回需要 補(bǔ)充 粉筆的學(xué)生 編號(hào) 。

示例 1：

輸入：chalk = [5,1,5], k = 22 輸出：0 解釋：學(xué)生消耗粉筆情況如下：

• 編號(hào)為 0 的學(xué)生使用 5 支粉筆，然后 k = 17 。
• 編號(hào)為 1 的學(xué)生使用 1 支粉筆，然后 k = 16 。
• 編號(hào)為 2 的學(xué)生使用 5 支粉筆，然后 k = 11 。
• 編號(hào)為 0 的學(xué)生使用 5 支粉筆，然后 k = 6 。
• 編號(hào)為 1 的學(xué)生使用 1 支粉筆，然后 k = 5 。
• 編號(hào)為 2 的學(xué)生使用 5 支粉筆，然后 k = 0 。 編號(hào)為 0 的學(xué)生沒有足夠的粉筆，所以他需要補(bǔ)充粉筆。

來源：力扣（LeetCode）

本題LeetCode

讀題

1. 編號(hào)為 i 的學(xué)生回答問題會(huì)消耗 chalk[i] 支粉筆。
2. 如果 剩余粉筆數(shù)量 < chalk[i]，那么這第 i 個(gè)同學(xué)就要補(bǔ)充粉筆。
3. 以上過程可能會(huì)重復(fù)多輪次。

要求：返回需要補(bǔ)充粉筆的學(xué)生編號(hào)。

解題思路（取模簡化模擬過程）

n 個(gè)學(xué)生每一輪消耗粉筆的個(gè)數(shù)是 chalk 數(shù)組之和 sum，一輪消耗后可能 k 還有，所以消耗粉筆這一過程是可能會(huì)重復(fù)的。當(dāng)然也可能不夠一輪。

輪次可能會(huì)有很多，我們模擬每一輪遞減會(huì)超時(shí)。所以就得簡化這個(gè)模擬過程。

將粉筆數(shù)量 k % sum(每一輪消耗) 或得一個(gè)余數(shù)。這個(gè)余數(shù)肯定小于 sum。然后遍歷 chalk ，模擬粉筆的消耗，待 chalk[i] > k 時(shí) 就可得到需要補(bǔ)充粉筆的學(xué)生編號(hào)。

image.png

代碼

class Solution {
public:
    int chalkReplacer(vector<int>& chalk, int k) {
        long long sum = 0;
        for(int i : chalk) sum += i; //求和
        k = k % sum; //取模簡化模擬過程

        int size = chalk.size();
        for(int i = 0; i < size; i++) {
            if(chalk[i] > k) {
                return i;
            }
            k -= chalk[i];
        }
        return -1;
    }
};

其他

• 另外，也整了個(gè)LeetCode題目詳解，堅(jiān)持費(fèi)曼學(xué)習(xí)法，吃進(jìn)去，產(chǎn)出來。

如果感覺本題解對你有幫助，請不要吝嗇點(diǎn)贊????啊 沖沖沖...