Re: [閒聊] 每日leetcode
2017. Grid Game
思路:
根據題目grid只有兩列
而且只能往右、下走
假設第一個人是在grid[0][i]選擇往下
那第二個人能得到的點數就是
(1)grid[0][i+1] ~ grid[0][n-1]的總和
(2)grid[1][0] ~ grid[i-1]的總和
上述兩個中較大的那個
所以第一個人就是要找到i最小化上述兩個總和的最大值
搭配preifx sum就可以得到答案了
golang code :
func gridGame(grid [][]int) int64 {
m := len(grid[0])
prefix := [2][]int{}
prefix[0] = make([]int, m+1)
prefix[1] = make([]int, m+1)
prefix[0][1], prefix[1][1] = grid[0][0], grid[1][0]
for i := 1; i < m; i++ {
prefix[0][i+1] = prefix[0][i] + grid[0][i]
prefix[1][i+1] = prefix[1][i] + grid[1][i]
}
ans := math.MaxInt64
for i := 0; i < m; i++ {
ans = min(ans, max(prefix[1][i], prefix[0][m]-prefix[0][i+1]))
}
return int64(ans)
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.60.242 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1737472361.A.AD8.html
→
01/21 23:17,
10月前
, 1F
01/21 23:17, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1298 之 1552 篇)：