2021-12-28：給定一個二維數組matrix，matrix[i][j] = k代表:
從(i,j)位置可以随意往右跳<=k步，或者從(i,j)位置可以随意往下跳<=k步，
如果matrix[i][j] = 0，代表來到(i,j)位置必須停止，
傳回從matrix左上角到右下角，至少要跳幾次，
已知matrix中行數n <= 5000, 列數m <= 5000，
matrix中的值，<= 5000。
來自京東。
答案2021-12-28：
方法一：自然智慧。遞歸。複雜度過不了。
方法二：動态規劃+線段樹。
代碼用golang編寫。代碼如下：
package main
import (
"fmt"
"math"
)
func main() {
ret := jump2([][]int{{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}})
fmt.Println(ret)
}
func getMin(a, b int) int {
if a < b {
return a
} else {
return b
}
}
// 優化方法, 利用線段樹做枚舉優化
// 因為線段樹，下标從1開始
// 是以，該方法中所有的下标，請都從1開始，防止亂！
func jump2(arr [][]int) int {
n := len(arr)
m := len(arr[0])
map0 := make([][]int, n+1)
for i := 0; i < n+1; i++ {
map0[i] = make([]int, m+1)
}
for a, b := 0, 1; a < n; a, b = a+1, b+1 {
for c, d := 0, 1; c < m; c, d = c+1, d+1 {
map0[b][d] = arr[a][c]
}
}
rowTrees := make([]*SegmentTree, n+1)
for i := 1; i <= n; i++ {
rowTrees[i] = NewSegmentTree(m)
}
colTrees := make([]*SegmentTree, m+1)
for i := 1; i <= m; i++ {
colTrees[i] = NewSegmentTree(n)
}
rowTrees[n].update0(m, m, 0, 1, m, 1)
colTrees[m].update0(n, n, 0, 1, n, 1)
for col := m - 1; col >= 1; col-- {
if map0[n][col] != 0 {
left := col + 1
right := getMin(col+map0[n][col], m)
next := rowTrees[n].query(left, right, 1, m, 1)
if next != math.MaxInt64 {
rowTrees[n].update0(col, col, next+1, 1, m, 1)
colTrees[col].update0(n, n, next+1, 1, n, 1)
}
}
}
for row := n - 1; row >= 1; row-- {
if map0[row][m] != 0 {
up := row + 1
down := getMin(row+map0[row][m], n)
next := colTrees[m].query(up, down, 1, n, 1)
if next != math.MaxInt64 {
rowTrees[row].update0(m, m, next+1, 1, m, 1)
colTrees[m].update0(row, row, next+1, 1, n, 1)
}
}
}
for row := n - 1; row >= 1; row-- {
for col := m - 1; col >= 1; col-- {
if map0[row][col] != 0 {
// (row,col) 往右是什麼範圍呢？[left,right]
left := col + 1
right := getMin(col+map0[row][col], m)
next1 := rowTrees[row].query(left, right, 1, m, 1)
// (row,col) 往下是什麼範圍呢？[up,down]
up := row + 1
down := getMin(row+map0[row][col], n)
next2 := colTrees[col].query(up, down, 1, n, 1)
next := getMin(next1, next2)
if next != math.MaxInt64 {
rowTrees[row].update0(col, col, next+1, 1, m, 1)
colTrees[col].update0(row, row, next+1, 1, n, 1)
}
}
}
}
return rowTrees[1].query(1, 1, 1, m, 1)
}
// 區間查詢最小值的線段樹
// 注意下标從1開始，不從0開始
// 比如你傳入size = 8
// 則位置對應為1~8，而不是0~7
type SegmentTree struct {
min []int
change []int
update []bool
}
func NewSegmentTree(size int) *SegmentTree {
ret := &SegmentTree{}
N := size + 1
ret.min = make([]int, N<<2)
ret.change = make([]int, N<<2)
ret.update = make([]bool, N<<2)
ret.update0(1, size, math.MaxInt64, 1, size, 1)
return ret
}
func (this *SegmentTree) pushUp(rt int) {
this.min[rt] = getMin(this.min[rt<<1], this.min[rt<<1|1])
}
func (this *SegmentTree) pushDown(rt, ln, rn int) {
if this.update[rt] {
this.update[rt<<1] = true
this.update[rt<<1|1] = true
this.change[rt<<1] = this.change[rt]
this.change[rt<<1|1] = this.change[rt]
this.min[rt<<1] = this.change[rt]
this.min[rt<<1|1] = this.change[rt]
this.update[rt] = false
}
}
// 最後三個參數是固定的, 每次傳入相同的值即可:
// l = 1(固定)
// r = size(你設定的線段樹大小)
// rt = 1(固定)
func (this *SegmentTree) update0(L, R, C, l, r, rt int) {
if L <= l && r <= R {
this.update[rt] = true
this.change[rt] = C
this.min[rt] = C
return
}
mid := (l + r) >> 1
this.pushDown(rt, mid-l+1, r-mid)
if L <= mid {
this.update0(L, R, C, l, mid, rt<<1)
}
if R > mid {
this.update0(L, R, C, mid+1, r, rt<<1|1)
}
this.pushUp(rt)
}
// 最後三個參數是固定的, 每次傳入相同的值即可:
// l = 1(固定)
// r = size(你設定的線段樹大小)
// rt = 1(固定)
func (this *SegmentTree) query(L, R, l, r, rt int) int {
if L <= l && r <= R {
return this.min[rt]
}
mid := (l + r) >> 1
this.pushDown(rt, mid-l+1, r-mid)
left := math.MaxInt64
right := math.MaxInt64
if L <= mid {
left = this.query(L, R, l, mid, rt<<1)
}
if R > mid {
right = this.query(L, R, mid+1, r, rt<<1|1)
}
return getMin(left, right)
} 複制
執行結果如下：
[左神java代碼](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class39/Code04_JumpGameOnMatrix.java)