Re: [閒聊] 每日leetcode
3355. Zero Array Transformation I
思路:
用difference 矩陣
difference矩陣在你要對矩陣的1個區域加上相同的值很好用
假設要對[L,R]間的數加上5，那就將difference[L]+5、difference[R+1]-5
將difference矩陣進行prefix sum就可以得到進行相加後的矩陣了
e.g. 假設有一個 [1,3,4,6,10]他的difference矩陣就是[1,2,1,2,4]
要對[1,3]間的數加上4，就會變成[1,6,1,2,0]
最後對difference矩陣進行prefix sum 會變成 [1,7,8,10,10]
可以看出就是原本矩陣[1,3]區間加上4
這題其實就是要對一個長度n且元素都為0的矩陣 : array
按照queries相對應的區間依序加上1
最後看array[i]>=nums[i] 所有i都成立就可以達到題目要求
golang code :
func isZeroArray(nums []int, queries [][]int) bool {
diff := make([]int, len(nums)+1)
for _, val := range queries {
diff[val[0]]++
diff[val[1]+1]--
}
if nums[0] > diff[0] {
return false
}
for i := 1; i < len(nums); i++ {
diff[i] += diff[i-1]
if diff[i] < nums[i] {
return false
}
}
return true
}
3356. Zero Array Transformation II
思路:
用上一題的方式 + 二分搜尋法
要特別注意邊界條件
(1)不用任何queries的情況(nums所有元素都是0)
我是直接去檢查來看是不是所有元素都是0
(2)就算用了所有queries也沒辦法達到要求
我在queries最後面增加了[]int{0, n - 1, 1e6}
這樣 r+1 == len(queries) 就是無法達成題目所需，回傳-1
golang code :
func minZeroArray(nums []int, queries [][]int) int {
l, r, n := 0, len(queries), len(nums)
queries = append(queries, []int{0, n - 1, 1e6})
array, prev_m := make([]int, n+1), -1
sum := 0
for i := 0; i < n; i++ {
sum += nums[i]
}
if sum == 0 {
return 0
}
for r > l {
m := l + (r-l)/2
if m > prev_m {
for i := prev_m + 1; i <= m; i++ {
array[queries[i][0]] += queries[i][2]
array[queries[i][1]+1] -= queries[i][2]
}
} else {
for i := prev_m; i > m; i-- {
array[queries[i][0]] -= queries[i][2]
array[queries[i][1]+1] += queries[i][2]
}
}
prev_m = m
tmp := 0
canBeZero := true
for i := 0; i < n; i++ {
tmp += array[i]
if tmp < nums[i] {
canBeZero = false
break
}
}
if canBeZero {
r = m
} else {
l = m + 1
}
}
r++
if r == len(queries) {
return -1
}
return r
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.214.73 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1732357580.A.731.html
討論串 (同標題文章)
完整討論串 (本文為第 1148 之 1548 篇)：