🖍情境模擬: 找到需要補充粉筆的學生_Leetcode #1894

Alexander Grey on Unsplash

題目敘述

給定一個長度為 n，而且索引從 0 開始的整數陣列 chalk 和參數 k 。一開始粉筆盒裡總共有 k 支粉筆。
當編號為 i 的學生回答問題時，他會消耗 chalk[i] 支粉筆。如果剩餘粉筆數量 嚴格小於 chalk[i] ，那麼學生 i 需要 補充 粉筆。

請找出需要補充粉筆的學生的學生編號。

測試範例

Example 1:

Input: chalk = [5,1,5], k = 22
Output: 0
Explanation: 
- 編號 0 的學生使用 5 支粉筆，然後 k = 17 。
- 編號 1 的學生使用 1 支粉筆，然後 k = 16 。
- 編號 2 的學生使用 5 支粉筆，然後 k = 11 。
- 編號 0 的學生使用 5 支粉筆，然後 k = 6 。
- 編號 1 的學生使用 1 支粉筆，然後 k = 5 。
- 編號 2 的學生使用 5 支粉筆，然後 k = 0 。
編號 0 的學生沒有足夠的粉筆，所以他需要補充粉筆。

Example 2:

Input: chalk = [3,4,1,2], k = 25
Output: 1
Explanation: 
- 編號 0 的學生使用 3 支粉筆，然後 k = 22 。
- 編號 1 的學生使用 4 支粉筆，然後 k = 18 。
- 編號 2 的學生使用 1 支粉筆，然後 k = 17 。
- 編號 3 的學生使用 2 支粉筆，然後 k = 15 。
- 編號 0 的學生使用 3 支粉筆，然後 k = 12 。
- 編號 1 的學生使用 4 支粉筆，然後 k = 8 。
- 編號 2 的學生使用 1 支粉筆，然後 k = 7 。
- 編號 3 的學生使用 2 支粉筆，然後 k = 5 。
- 編號 0 的學生使用 3 支粉筆，然後 k = 2 。
編號 1 的學生沒有足夠的粉筆，所以他需要補充粉筆。

約束條件

Constraints:

• chalk.length == n

輸入陣列的長度為n

• 1 <= n <= 10^5

n介於1~十萬之間。

• 1 <= chalk[i] <= 10^5

每個學生消耗的粉筆數量介於1~十萬之間。

• 1 <= k <= 109

粉筆總數k介於1~十億之間。

觀察

學生消耗粉筆的過程是重複的，每一位同學消耗的粉筆數量都是固定的。

因此可以先將粉筆總數k 直接對 每回合粉筆消耗總數做除法取餘數，提升模擬的效率。

演算法 模擬消耗粉筆的過程

每經過一名學生，就扣掉對應消耗掉的粉筆數量。

最後，當粉筆不足時，
該名同學的index(代表需要補充粉筆的同學的學號)就是最終答案。

程式碼 模擬消耗粉筆的過程

class Solution:
    def chalkReplacer(self, chalk: List[int], k: int) -> int:

        k %= sum(chalk)

        for i in range(len(chalk)):

            if chalk[i]>k:
                return i

            # Comsume chalk[i] by student_i
            k -= chalk[i]

        return -1

複雜度分析

時間複雜度: O(n)

掃描每位同學消耗的粉筆數量，最多掃描一輪可以知道答案。

空間複雜度: O(1)

所用到的變數都是固定尺寸的臨時變數，所需空間為O(1)。

Reference

[1] Find the Student that Will Replace the Chalk - LeetCode