菜鸡孙连城

题解

/ 注册

全部文章 / 题解（共65篇）

题解 | #66.不同路径的数目(一)#

很简单的dp，没什么可以说的，(i,j)一定是由(i,j-1)和(i-1,j)两个地方走出来的，因此状态转移方程dp[i][j] = dp[i-1][j]+dp[i][j-1] function uniquePaths( m , n ) { let dp = new Array(m); ...

Javascript Node

2022-03-24

0 301

题解 | #66.最长公共子串#

这里的dp含义和上一次不一样了，最长公共子序列的dp[i][j]表示str1的i位置和st2的j位置截止的最大长度，而最长公共字串的dp[i][j]表示str1的i位置和str2的j位置作为最后一个元素所构成的最长公共字串，也就是str1的第i个位置必须作为公共子串的最后一个元素，在dp的过程中用...

Javascript Node 动态规划

2022-03-24

1 504

题解 | #65.最长公共子序列(二)#

这道题我只写出了最长公共子序列的长度，公共子序列实际是什么参考了题解 dp是一个二维数组，行数为s1的长度，列数为s2的长度，首先对与dp[0][]和dp[][0]赋值为0或1，代码的9-15行状态转移方程： s1[pi] == s2[j]------>dp[i][j] = dp[i-1]...

Javascript Node 动态规划

2022-03-24

1 389

题解 | #64.最小花费爬楼梯#

dp dp 你看我长得像dp吗？刚抄了一道题，还是不太懂dp，dp难dp易，dp就是放狗屁，快点去下地可以用一个数组记录每次爬到第i阶楼梯的最小花费，然后每增加一级台阶就转移一次状态，最终得到结果每次到一个台阶，只有两种情况，要么是它前一级台阶向上一步，要么是它前两级的台阶向上两步，因为在前面...

Javascript Node

2022-03-24

5 446

题解 | #63.跳台阶#

function jumpFloor(number) { if(number==1 || number==0) return 1; if(number==2) return 2; return jumpFloor(number-1) + jumpFloor(number-...

Javascript Node

2022-03-24

1 249

题解 | #62.斐波那契数列#

小技巧：[left,right] = [right,left+right] function Fibonacci(n) { if(n==1 || n==2) return 1; n = n-2; let left=1,right=1; while(n--){ [lef...

Javascript Node

2022-03-24

0 294

题解 | #59.N皇后问题#

递归+回溯创建arr数组存储皇后的摆放情况，初始化为全0 check函数表示当前放置位置是否合法递归：对于每一行，逐列检查是否合法，合法则在arr数组对应的位置置为1，然后递归 function Nqueen( n ) { let count = 0; let arr = []...

Javascript Node 回溯递归

2022-03-24

0 380

题解 | #60.括号生成#

和全排列一样，甚至更简单，不需要used数组记录使用情况递归终止条件：left==n && right==n 本级任务：左括号没用完，加左括号左括号<=n并且left>right时，加右括号不要忘记回溯即可 function generateParenthe...

Javascript Node

2022-03-23

1 306

题解 | #58.字符串的排列#

和全排列一样，只不过由数组变为了字符串可以同样用数组path存储，也可以采用字符串存储数组存储：res.push(path.join('')) 字符串存储： let path = '' path += str[i] path = path.slice(0,path.length-1) funct...

Javascript Node

2022-03-23

1 368

题解 | #55.没有重复项数字的全排列#

按照56题的思路可能更简单一点，和56题有重复项数字的全排列代码一样 function permute( num ) { let path = []; let res = []; let used = []; function traceTrack(){ //pa...

Javascript Node

2022-03-23

0 343