Commit5e1a4b4

committed

implement: 55

1 parent6934f92 commit5e1a4b4Copy full SHA for 5e1a4b4

File tree

1 file changed

+81

-1

lines changed

src/jump-game
- res.js

1 file changed

+81

-1

lines changed

`‎src/jump-game/res.js`

Lines changed: 81 additions & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -4,6 +4,11 @@`
`4`	`4`	`*@param {number[]} nums`
`5`	`5`	`*@return {boolean}`
`6`	`6`	`*/`
	`7`	`+`
	`8`	`+/**`
	`9`	`+ * 贪心：从右向左迭代，对于每个节点我们检查是否存在一步跳跃可以到达 GOOD 的位置（currPosition + nums[currPosition] >= leftmostGoodIndex）。如果可以到达，当前位置也标记为 GOOD ，同时，这个位置将成为新的最左边的 GOOD 位置，一直重复到数组的开头，如果第一个坐标标记为 GOOD 意味着可以从第一个位置跳到最后的位置。`
	`10`	`+ @param {} nums`
	`11`	`+ */`
`7`	`12`	`varcanJump=function(nums){`
`8`	`13`	`letlastPos=nums.length-1;`
`9`	`14`	`for(letindex=nums.length-1;index>=0;index--){`
`@@ -14,4 +19,79 @@ var canJump = function(nums) {`
`14`	`19`	`}`
`15`	`20`
`16`	`21`	`returnlastPos===0;`
`17`		`-};`
	`22`	`+};`
	`23`	`+`
	`24`	`+/**`
	`25`	`+ * 回溯法：从第一个位置开始，模拟所有可以跳到的位置，然后从当前位置重复上述操作，当没有办法继续跳的时候，就回溯。`
	`26`	`+ @param {} nums`
	`27`	`+ */`
	`28`	`+constcanJump=(nums)=>{`
	`29`	`+constjumpAnalysis=(index)=>{`
	`30`	`+if(index===nums.length-1)returntrue;`
	`31`	`+`
	`32`	`+constmaxLen=Math.min(index+nums[index],nums.length-1);`
	`33`	`+for(leti=index+1;i<=maxLen;i++){`
	`34`	`+if(jumpAnalysis(i))returntrue;`
	`35`	`+}`
	`36`	`+returnfalse;`
	`37`	`+}`
	`38`	`+`
	`39`	`+returnjumpAnalysis(0);`
	`40`	`+}`
	`41`	`+`
	`42`	`+/**`
	`43`	`+ * 动态规划：自顶向下`
	`44`	`+ @param {} nums`
	`45`	`+ */`
	`46`	`+constcanJump=(nums)=>{`
	`47`	`+constmem=nums.map(()=>-1);`
	`48`	`+mem[nums.length-1]=1;`
	`49`	`+`
	`50`	`+constjumpAnalysis=(index)=>{`
	`51`	`+// 当前元素位置如果已经计算过则返回结果`
	`52`	`+if(mem[index]!==-1){`
	`53`	`+returnmem[index]===1 ?true :false;`
	`54`	`+}`
	`55`	`+`
	`56`	`+// 未计算的位置根据可走步数更新 mem`
	`57`	`+constmaxLen=Math.min(index+nums[index],nums.length-1);`
	`58`	`+for(leti=index+1;i<=maxLen;i++){`
	`59`	`+// 如果当前位置已可以跳到结果那么提前结束返回结果`
	`60`	`+if(jumpAnalysis(i)){`
	`61`	`+mem[i]=1;`
	`62`	`+returntrue;`
	`63`	`+}`
	`64`	`+}`
	`65`	`+`
	`66`	`+// 标定当前位置无用`
	`67`	`+mem[index]=0;`
	`68`	`+returnfalse;`
	`69`	`+}`
	`70`	`+`
	`71`	`+returnjumpAnalysis(0);`
	`72`	`+}`
	`73`	`+`
	`74`	`+/**`
	`75`	`+ * 动态规划：自底向上`
	`76`	`+ @param {} nums`
	`77`	`+ */`
	`78`	`+constcanJump=(nums)=>{`
	`79`	`+constlen=nums.length;`
	`80`	`+if(!len)returnfalse;`
	`81`	`+if(len===1)returntrue;`
	`82`	`+constmem=nums.map(()=>0);`
	`83`	`+mem[nums.length-1]=1;`
	`84`	`+`
	`85`	`+for(leti=nums.length-2;i>=0;i--){`
	`86`	`+constmaxLen=Math.min(i+nums[i],nums.length-1);`
	`87`	`+for(letj=i+1;j<=maxLen;j++){`
	`88`	`+if(mem[j]){`
	`89`	`+mem[i]=1;`
	`90`	`+break;`
	`91`	`+}`
	`92`	`+}`
	`93`	`+}`
	`94`	`+`
	`95`	`+returnmem[0]===1;`
	`96`	`+}`
	`97`	`+`

0 commit comments

Comments

(0)

Movatterモバイル変換

Navigation Menu

Search code, repositories, users, issues, pull requests...

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Commit5e1a4b4

File tree

1 file changed

1 file changed

`‎src/jump-game/res.js`

0 commit comments