递归与动态规划 暴力递归1 汉诺塔问题---将数量为n的圆盘从最左边移动到最右边,必须小压大function fn(n){ if(n > 0){ func(n,left,right,mid) } function func(n,from,to,other){ if(n === 0){ console.log(1,from,to) } func(n - 1,from,other,to) console.log(n,from,other) func(n - 1,other,to,from) } }2 打印字符串的所有子序列(字串不一定连续，但是相对顺序不能乱)function fn(str){ let arr = str.split('') let ans = [] let path = '' func(arr,0,ans,path) return ans function func(arr,index,ans,path){ if(index === arr.length){ ans.push(path) return } let no = path func(arr,index + 1,ans,path) let yes = path + arr[index] func(arr,index + 1,ans,path) } }

链表 反转链表反转链表主要是靠三个指针，pre指向前一个指针，cur和next指向当前指针，保持这个顺序就可以。function ReverseList(node){ let pre = null let cur = node let next = node while(cur.next != null){ next = cur.next cur.next = pre pre = cur cur = next } return pre }

时间复杂度与空间复杂度 时间复杂度多个复杂度看最高的复杂度，常数也要去掉if,加减乘除都是O(1),O(1)一般被忽略for循环和while循环是O(n)，嵌套的循环是O(n平方)，但是如果是两个for循环就还是O(n)二分搜索是O(logn)用到了排序就是O(nlogn)时间复杂度就是看自己有没有创建空间