Re: [閒聊] 每日leetcode
1894. Find the Student that Will Replace the Chalk
有n個學生，標號0~n-1
有一個chalk矩陣，chalk[i]表示第i個學生解題時需要多少粉筆
當n-1號學生解完題後會輪會第0號學生
當目前的粉筆不夠解題時，該學生需要補充粉筆
假設有k隻粉筆，請問是第幾個學生要補充粉筆
思路：
建立一個prefix sum array紀錄到第i個學生時總共消耗了幾隻粉筆
並且計算解題一輪所需要的粉筆數 : sum
假設target = k%sum
用二分搜尋法去找target在prefix sum array的第幾位就是答案
注意如果prefix_sum[i]==target
那是i+1號學生要補充粉筆
golang code :
func chalkReplacer(chalk []int, k int) int {
n := len(chalk)
prefix_sum, sum := make([]int, n+1), chalk[0]
prefix_sum[0] = chalk[0]
prefix_sum[n] = math.MaxInt32
for i := 1; i < n; i++ {
prefix_sum[i] = prefix_sum[i-1] + chalk[i]
sum += chalk[i]
}
remainder := k % sum
ans, _ := slices.BinarySearch(prefix_sum, remainder)
if prefix_sum[ans] == remainder {
return ans + 1
}
return ans
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.10.104 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1725280832.A.AD9.html
討論串 (同標題文章)
完整討論串 (本文為第 794 之 1548 篇)：