文件名称:
README.md
所在目录:
教材与参考资料 / 程序设计类 / 数据结构＆算法 / 算法 / 面试与力扣题目详解 / Leetcode题目和解答 / java-leetcode / jump-game
文件大小:
924.00 B
下载地址:
文本预览:
## Simulating
```
0 1 2 3 4
A[2,3,1,1,4]
```
from A[0], can jump to every pos between `0` and `0 + A[0]`
from A[1], can jump to every pos between `1` and `1 + A[1]`
so..
from A[i], can jump to every pos between `i` and `i + A[i]`
C[i] is a paper that help us to remember if we can jump to pos `i`
```
0 1 2 3 4
A[2,3,1,1,4]
C[0,0,0,0,0]
```
```
for A[0] C[0 .. 0 + A[0]] = 1
for A[1] C[1 .. 1 + A[1]] = 1
for A[i] C[i .. i + A[i]] = 1
```
thus, code should be like below
```
C[0] = 1
foreach i in A
if C[i] == 1 then
C[i .. i + A[i]] = 1
return C[last i of A]
```
## Array C is not needed
when we set
```
C[i .. i + A[i]] = 1
```
is equals
```
foreach i in A
C[0 .. max of i + A[i]] = 1
```
is equals
```
maxjump = 0
foreach i in A
maxjump = max(maxjump, i + A[i])
```
so `C[i]` can be replaced by `i < maxjump`
Removing C would save memory and the time used for setting them to 1
```
0 1 2 3 4
A[2,3,1,1,4]
```
from A[0], can jump to every pos between `0` and `0 + A[0]`
from A[1], can jump to every pos between `1` and `1 + A[1]`
so..
from A[i], can jump to every pos between `i` and `i + A[i]`
C[i] is a paper that help us to remember if we can jump to pos `i`
```
0 1 2 3 4
A[2,3,1,1,4]
C[0,0,0,0,0]
```
```
for A[0] C[0 .. 0 + A[0]] = 1
for A[1] C[1 .. 1 + A[1]] = 1
for A[i] C[i .. i + A[i]] = 1
```
thus, code should be like below
```
C[0] = 1
foreach i in A
if C[i] == 1 then
C[i .. i + A[i]] = 1
return C[last i of A]
```
## Array C is not needed
when we set
```
C[i .. i + A[i]] = 1
```
is equals
```
foreach i in A
C[0 .. max of i + A[i]] = 1
```
is equals
```
maxjump = 0
foreach i in A
maxjump = max(maxjump, i + A[i])
```
so `C[i]` can be replaced by `i < maxjump`
Removing C would save memory and the time used for setting them to 1
点赞
回复
X