公式：f(n) = f(n-1) + f(n-2)
1 2 3 4 5 6 7 8 9 10 11 12 13 var climbStairs = function (n ) if (n == 1 ) return 1 if (n == 2 ) return 2 let res = 0 let pre = 1 let cur = 2 for (let i = 3 ;i <= n;i++){ res = pre + cur pre = cur cur = res } return res };
使用两个指针，将非零的数往前复制，最后将后面的数置换为0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 var moveZeroes = function (nums ) if (nums == null ) return if (nums.length == 1 ) return nums let l = 0 let r = 0 while (r < nums.length){ if (nums[r] != 0 ){ nums[l] = nums[r] l++ } r++ } while (l < nums.length){ nums[l] = 0 l++ } return nums };
因为题目说 nums 中的元素取值都在 [1, n] 之间，即元素本身就和索引成一一映射关系,我们遍历数组，每次遍历到的索引就是在[0,n-1]之间，所以将每次遍历到的值绝对值化减去1，得到的数就在数组范围中，然后我们将该值对应的数组索引上的值变为负数，最后再遍历一次数组，值大于0的值对应的索引+1就是没有消失的值
1 2 3 4 5 6 7 8 9 10 11 12 13 var findDisappearedNumbers = function (nums ) for (let i = 0 ;i < nums.length;i++){ let n = Math .abs(nums[i]) - 1 if (nums[n] > 0 ) nums[n] = -nums[n] } let res = [] for (let i = 0 ;i <nums.length;i++){ if (nums[i] > 0 ){ res.push(i+1 ) } } return res };
使用快慢指针，有环形必相遇
1 2 3 4 5 6 7 8 9 10 var hasCycle = function (head ) if (head == null ) return false let slow = head,fast = head while (fast.next !== null && fast.next.next !== null ){ fast = fast.next.next slow = slow.next if (fast == slow) return true } return false };
背就完事
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 var detectCycle = function (head ) if (head == null ) return null let slow = head let fast= head while (fast.next !== null && fast.next.next !== null ){ fast = fast.next.next slow = slow.next if (fast == slow){ slow = head while (fast !== slow){ fast = fast.next slow = slow.next } return slow } } return null };
冒泡排序（空间复杂度O(1)，时间复杂度O(n平方)）：
冒泡排序就是从数组头开始比较两个相邻的数，如果前面的数大于后面的数就将两个数交换，然后开始下一对数字的比较，直到数组最后的数字比较完。
然后继续重复刚刚的步骤，除了最后一个数字不用，因为它已经是最大的。
这样一步步重复，直到没有数字需要交换位置。
1 2 3 4 5 6 7 8 9 10 11 12 function bubbleSort (arr ) for (let i = 0 ;i < arr.length - 1 ;i++){ for (let j = 0 ;j < arr.length - 1 - i;j++){ if (arr[j] > arr[j + 1 ]){ let temp = arr[j] arr[j] = arr[j + 1 ] arr[j + 1 ] = temp } } } return arr }
选择排序（空间复杂度O(1)，时间复杂度O(n平方)）：
选择排序就是从未排序的数组中找到最小的那一个数放到数组最前面，再从剩余未排序的数组中继续找到最小的数放到已排序的数后面，这样不断的重复直到数组排序完毕。
1、将问题分解成一个个子问题：先把数组按照中点分为两组，对两个数组内的数字按照下标从小到大与中点分别进行比较，如果左边的数组数值比中点小则下标加1更新，右边的比中点大则下标减1，不满足条件则暂停下标更新。
2、当左边或者右边的数组值都暂停更新时，将左右数组两个数互换，这一步的目标是将比中点大的换到数组右边，小的放到左边。
3、每个子问题通过递归完成，由于都是在原数组中进行操作，所以最后数组就是排序好的数组。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 function quickSort (arr,l,r ) if (l >= r) return let i = l - 1 let j = r + 1 let t = arr[r + l >> 1 ] while (i < j){ do {i++} while (arr[i] < t) do {j--} while (arr[j] > t) if (i < j){ let temp = arr[i] arr[i] = arr[j] arr[j] = temp } } quickSort(arr,l,j) quickSort(arr,j + 1 ,r) }
归并与快排的基本思想都是分治，但是归并是一上来就递归。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 function mergeSort (arr,l,r ) if (l >= r) return let mid = r + l >> 1 mergeSort(arr,l,mid) meergeSort(arr,mid + 1 ,r) let t = 0 let i = l let j = mid + 1 let temp = new Array (r - l + 1 ) while (i <= mid && j <= r){ if (arr[i] <= arr[j]) temp[t++] = arr[i++] else temp[t++] = arr[j++] } while (i <= mid) temp[t++] = arr[i++] while (j <= r) temp[t++] = arr[j++] for (let i = l,t = 0 ;i <= r;i++,t++){ arr[i] = temp[t] } }
F (n )=F (n −1)+F (n −2)
1 2 3 4 5 6 7 8 9 10 11 function fn (n ) if (n < 2 ) return 1 let p = 0 ,q = 0 ,r = 1 for (let i = 2 ;i <= n;i++){ p = q q = r r = (p + q) % 1000000007 } return r }
1、有效的括号
使用栈，将左边括号存储进数组中，当出现右括号时，弹出最顶层元素与之比较。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 var isValid = function (s ) if (!s) return let arr = s.split("" ) let stack = [] for (let i = 0 ;i < arr.length;i++){ if (arr[i] == "(" || arr[i] == "[" || arr[i] == "{" ) stack.push(arr[i]) switch (arr[i]){ case ")" : { if (stack.pop() == "(" ) break else return false } case "]" : { if (stack.pop() == "[" ) break else return false } case "}" : { if (stack.pop() == "{" ) break else return false } } } if (stack.length === 0 ) return true else return false };
2、最小栈
用一个栈存储数，一个栈存储所有数中的最小数，每一次push和pop两个栈都需要添加渔删除
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 var MinStack = function ( this .stack = [] this .minStack = [] return null }; MinStack.prototype.push = function (val ) this .stack.push(val) if (this .minStack.length == 0 ) { this .minStack.push(val) } else { this .minStack.push(this .minStack[this .minStack.length - 1 ] <= val ? this .minStack[this .minStack.length - 1 ] : val) } return null }; MinStack.prototype.pop = function ( this .stack.pop() this .minStack.pop() return null }; MinStack.prototype.top = function ( return this .stack[this .stack.length - 1 ] }; MinStack.prototype.getMin = function ( return this .minStack[this .minStack.length - 1 ] };
3、回文链表
第一种做法：先用数组存储链表中所有元素，然后用双指针比较左半边与右半边的元素是否相等
1 2 3 4 5 6 7 8 9 10 11 var isPalindrome = function (head ) let arr= [] while (head !== null ){ arr.push(head.val) head = head.next } for (let i = 0 ;i < Math .ceil(arr.length);i++){ if (arr[i] !== arr[arr.length - 1 - i]) return false } return true };
第二种做法：使用递归思想，倒序遍历链表，然后在回溯过程中进行前后节点比较
1 2 3 4 5 6 7 8 9 10 11 12 let leftvar isPalindrome = function (head ) left = head return fn(head) }; var fn = function (right ) if (right == null ) return true let res = fn(right.next) res = res && (right.val === left.val) left = left.next return res }
第三种做法：使用双指针的方法到达链表中点，然后反转后半部分链表，然后向中点收缩比较节点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 var isPalindrome = function (head ) let slow = fast = head while (fast != null && fast.next != null ){ slow = slow.next fast = fast.next.next } if (fast != null ) slow = slow.next let left = head let right = reverse(slow) while (right != null ){ if (left.val != right.val){ return false } left = left.next right = right.next } return true }; var reverse = function (head ) let pre = null ,cur = head while (cur != null ){ let next = cur.next cur.next = pre pre = cur cur = next } return pre }
4、字符串解码
用栈存储每一个字符，当遇到”]”时将前面的字母弹出，并弹出次数然后重复之后重新压入栈中，最后将栈返回
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 var decodeString = function (s ) let stack = [] let arr = s.split("" ) for (let i = 0 ;i < arr.length;i++){ if (arr[i] !== "]" ) { stack.push(arr[i]) } else { let str = "" let cur = "" while (stack[stack.length - 1 ] !== "[" ){ str = str + stack.pop() } stack.pop() let num = "" cur = stack.pop() while (!isNaN (num)){ num = cur + num cur = stack.pop() } stack.push(cur) stack.push(str.repeat(num)) } } return stack.join("" ) };
5、 最短无序连续子数组
浅拷贝数组然后进行比较，从左往右第一个就是最短无序连续子数组的第一个数，从右往左第一个就是子数组的最后一个数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 var findUnsortedSubarray = function (nums ) if (isSorted(nums)) { return 0 ; } const numsSorted = [...nums].sort((a, b ) => a - b); let left = 0 ; while (nums[left] === numsSorted[left]) { left++; } let right = nums.length - 1 ; while (nums[right] == numsSorted[right]) { right--; } return right - left + 1 ; }; const isSorted = (nums ) => { for (let i = 1 ; i < nums.length; i++) { if (nums[i] < nums[i - 1 ]) { return false ; } } return true ; }
暴力算法：直接遍历两次数组，用一个新数组保存更高温度天数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 var dailyTemperatures = function (temperatures ) let arr = [] for (let i = 0 ;i < temperatures.length;i++){ for (let j = i + 1 ;j < temperatures.length;j++){ if (temperatures[i] < temperatures[j]){ arr.push(j - i) j = temperatures.length } if (j === temperatures.length - 1 ){ arr.push(0 ) } } } arr.push(0 ) return arr };
单调栈算法：只需要遍历一次数组，从后往前遍历温度数组，新建一个栈，遍历数组同时将元素索引放入栈中，当下一个元素比栈中元素大时，将小项元素索引弹出，让大项元素索引入栈，最后直接让索引相减就是当前元素的结果，再用一个数组保存起来。当下一个元素比栈顶元素小时，直接让其索引入栈即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 const dailyT = (T ) => { const res = new Array (T.length).fill(0 ) const stack = [] for (let i = T.length - 1 ;i >= 0 ;i--){ while (stack.length && T[i] >= T[stack[stack.length - 1 ]]){ stack.pop() } if (stack.length){ res[i] = stack[stack.length - 1 ] - i } stack.push(i) } return res }
使用二叉树的前序遍历，用一个数组保存遍历的节点，由于左子节点需要是null，所以使用for循环对数组节点左子节点赋值为null，然后右子节点设置为下一个索引值。
也可以将for循环改为while循环，优化了空间存储。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 var flatten = function (root ) let list= [] a(root,list) let i = 0 while (i < list.length - 1 ){ list[i].left = null list[i].right = list[++i] } return list }; function a (node,list ) if (node !== null ){ list.push(node) a(node.left,list) a(node.right,list) } }
从左到右遍历字符串数组，创建一个栈，如果出现左括号则让该位置的索引入栈，如果栈中有元素且扫描到右括号则进行出栈操作，让max长度为当前索引减去栈顶元素。为了避免一组括号出现之后继续出现括号，max无法计算到前面的一对括号长度，所以在初始化栈的时候将-1压入栈中，如果-1被出栈，那么需要有一个新的参照数进栈，则就是匹配到右括号时且栈长度为0时将当前索引进栈作为参照数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 var longestValidParentheses = function (s ) const arr = s.split("" ) let stack = [] stack.push(-1 ) let max = 0 for (let i = 0 ;i < arr.length;i++){ if (arr[i] === "(" ){ stack.push(i) }else { stack.pop() if (stack.length){ max = Math .max((i - stack[stack.length -1 ]),max) }else { stack.push(i) } } } return max };
方法一：使用递归对左右子树的子节点进行比较，对称需要满足：
它们的两个根结点具有相同的值
每个树的右子树都与另一个树的左子树镜像对称
1 2 3 4 5 6 7 8 9 10 var isSymmetric = function (root ) return check(root,root) }; function check (node1,node2 ) if (!node1 && !node2) return true if (!node1 || !node2) return false return node1.val === node2.val && check(node1.left,node2.right) && check(node1.right,node2.left) }
方法二：使用队列，每一次比较弹出队首两个元素进行比较，使用while循环迭代
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 var isSymmetric = function (root ) return check(root,root) }; function check (node1,node2 ) let queue = [] queue.push(node1) queue.push(node2) while (queue.length){ let p = queue.shift() let q = queue.shift() if (!p && !q) continue if (!p || !q) return false if (p.val === q.val){ queue.push(p.left) queue.push(q.right) queue.push(p.right) queue.push(q.left) }else { return false } } return true }
方法一：深度搜索。节点为空时说明高度为 0，所以返回 0；节点不为空时则分别求左右子树的高度的最大值，同时加1表示当前节点的高度，返回该数值。
1 2 3 4 5 6 var maxDepth = function (root ) if (!root) return 0 let f = maxDepth(root.left) let r = maxDepth(root.right) return Math .max(f,r) + 1 };
方法二：广度搜索
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 var maxDepth = function (root ) let ans = 0 if (!root) return 0 let queue = [] queue.push(root) while (queue.length !== 0 ){ let size = queue.length for (let i = 0 ;i < size;i++){ let node = queue.shift() if (node.left) queue.push(node.left) if (node.right) queue.push(node.right) } ans += 1 } return ans };
使用递归从叶子节点开始翻转，最后回溯到根节点
1 2 3 4 5 6 7 8 var invertTree = function (root ) if (!root) return null let l = invertTree(root.left) let r = invertTree(root.right) root.left = r root.right = l return root };
使用递归
1 2 3 4 5 6 7 8 9 10 11 var isBalanced = function (root ) if (root == null ) return true return fn(root) !== -1 function fn (root ) if (root == null ) return 0 let left = fn(root.left) let right = fn(root.right) if (left == -1 || right == -1 || Math .abs(left - right) > 1 ) return -1 return Math .max(left,right) + 1 } };
使用递归从叶子节点开始回溯，返回值是当前节点的深度，树的直径用max接收，每回溯一次就更新一次，它相当于所有节点的最大左子树深度+所有节点的最大右子树深度。
1 2 3 4 5 6 7 8 9 10 11 12 var diameterOfBinaryTree = function (root ) let max = 0 function check (node ) if (node == null ) return 0 let l = check(node.left) let r = check(node.right) max = Math .max(max,l + r) return Math .max(l,r) + 1 } check(root) return max };
使用dfs深度遍历，每一次递归返回一个节点，回溯的时候将返回的节点作为新节点的左节点或者右节点，最终回溯到根节点
1 2 3 4 5 6 7 8 9 10 var mergeTrees = function (root1, root2 ) if (!root1) return root2 if (!root2) return root1 return new TreeNode( root1.val + root2.val, mergeTrees(root1.left,root2.left), mergeTrees(root1.right,root2.right) ) };
找规律，当n为0或者1时种类是1，当n>=2时,G(N)是把所有节点作为根，左子树与右子树集合个数的乘积。左子树记为G[i - 1],右子树记为G[i - j]。
1 2 3 4 5 6 7 8 9 10 11 12 13 var numTrees = function (n ) let G = new Array (n + 1 ).fill(0 ) G[0 ] = 1 G[1 ] = 1 for (let i = 2 ;i <= n;i++){ for (let j = 1 ;j <= i;j++){ G[i] += G[j - 1 ] * G[i - j] } } console .log(G) return G[n] };
方法一：使用递归思想，用lower与upper记录父节点的值，初始值为负无穷与正无穷，使用&&运算符，如果左子树不满足或者右子树不满足就会返回false。
1 2 3 4 5 6 7 8 var isValidBST = function (root ) function check (root,lower,upper ) if (root == null ) return true if (root.val <= lower || root.val >= upper) return false return check(root.left,lower,root.val) && check(root.right,root.val,upper) } return check(root,-Infinity ,Infinity ) };
方法二：使用中序遍历，使用栈来存储节点，使用两层while循环，在中序遍历的时候实时检查当前节点的值是否大于前一个中序遍历到的节点的值即可。如果均大于说明这个序列是升序的，整棵树是二叉搜索树，否则不是。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 var isValidBST = function (root ) let stack = [] let t = -Infinity while (stack.length || root !== null ){ while (root !== null ){ stack.push(root) root = root.left } root = stack.pop() if (root.val <= t) return false t = root.val root = root.right } return true };
使用bfs进行程序遍历，由于需要将每一层树的节点使用一个数组表示出来，所以对基本的bfs进行了改进，每次使用for循环将一层的节点直接弹出，然后使用数组接收节点的值，节点的左右节点进入队列，在下一次while循环中再全部弹出。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 var levelOrder = function (root ) const res = [] let queue = [] if (root !== null ){ queue.push(root) } while (queue.length !== 0 ){ let n = queue.length res.push([]) for (let i = 0 ;i < n;i++){ let t = queue.shift() res[res.length - 1 ].push(t.val) if (t.left !== null ) queue.push(t.left) if (t.right !== null ) queue.push(t.right) } } return res }
1、遍历+新链表存储
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 var mergeTwoLists = function (list1, list2 ) let node = new ListNode(-1 ,null ) let p = node let n1 = list1 let n2 = list2 while (n1 !== null && n2 !== null ){ if (n1.val > n2.val){ p.next = n2 n2 = n2.next }else { p.next = n1 n1 = n1.next } p = p.next } if (n1 !== null ) p.next = n1 if (n2 !== null ) p.next = n2 return node.next };
2、递归
1 2 3 4 5 6 7 8 9 10 11 12 13 var mergeTwoLists = function (list1, list2 ) if (list1 == null ) return list2 if (list2 == null ) return list1 while (list1 != null && list2 != null ){ if (list1.val <= list2.val){ list1.next = mergeTwoLists(list1.next,list2) return list1 }else { list2.next = mergeTwoLists(list2.next,list1) return list2 } } };
直接将所有元素遍历存进数组中，然后对数组进行排序后，遍历数组将元素从小到大存进数组中。
也可以使用优先队列，但是在js中需要自己实现大根堆或者小根堆，代码量多了一点点….
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 var mergeKLists = function (lists ) let arr = [] for (let i = 0 ;i < lists.length;i++){ let p = lists[i] while (p !== null ){ arr.push(p.val) p = p.next } } arr.sort((a,b ) => { return a - b }) let node = new ListNode(-1 ) let p = node for (let i = 0 ;i < arr.length;i++){ p.next = new ListNode(arr[i]) p = p.next } return node.next };
只用一个循环找出链表中倒数第n个元素的函数：
1、首先，我们先让一个指针 n1 指向链表的头节点 head，然后走 k 步
2、现在的 n1，只要再走 n - k 步，就能走到链表末尾的空指针了对吧？趁这个时候，再用一个指针 n2指向链表头节点head`
3、接下来就很显然了，让 n1 和 n2 同时向前走，n1 走到链表末尾的空指针时前进了 n - k 步，n2 也从 head 开始前进了 n - k 步，停留在第 n - k + 1 个节点上，即恰好停链表的倒数第 k 个节点上
只要用上面的函数找到倒数n+1个元素，让它的下一个元素等于它的下下个元素即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 var removeNthFromEnd = function (head, n ) function checkN (node,k ) let n1 = node for (let i = 0 ;i < k;i++){ n1 = n1.next } let n2 = node while (n1 !== null ){ n1 = n1.next n2 = n2.next } return n2 } let p = new ListNode(-1 ) p.next = head let n2 = checkN(p,n + 1 ) n2.next = n2.next.next return p.next };
我们让两个指针 slow 和 fast 分别指向链表头结点 head。每当慢指针 slow 前进一步，快指针 fast 就前进两步，这样，当 fast 走到链表末尾时，slow 就指向了链表中点。
1 2 3 4 5 6 7 8 var middleNode = function (head ) let slow = head,fast = head while (fast !== null && fast.next !== null ){ slow = slow.next fast = fast.next.next } return slow };
快慢指针也可以用来判断链表是否包含环，当快指针最后是空指针说明链表不包含环，但是如果最后快慢指针相遇则说明存在环。
1、使用双指针a,b分别在两条链表上前进，为了让a，b可以同时到达相交节点，我们可以让a遍历完链表A之后开始遍历链表B，让b遍历完链表B之后开始遍历链表A，这样可以让a,b同时进入公共部分，到达相交节点。如果没有相交节点，也会因为返回null。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 var getIntersectionNode = function (headA, headB ) if (headA === null || headB === null ) { return null ; } let a = headA,b = headB while (a !== b){ if (a == null ) a = headB else a = a.next if (b == null ) b = headA else b = b.next } return a };
2、先计算两个链表的长度，然后让较长的链表上的指针先移动两个链表长度的距离，然后再让两个指针以相同的速度移动，这样也可以保证如果有公共部分可以同时到达。
3、使用哈希表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 var getIntersectionNode = function (headA, headB ) let map = new Map () let node = headA while (node !== null ){ map.set(node,node.val) node = node.next } node = headB while (node !== null ){ if (map.get(node)) return node node = node.next } return null };
1 2 3 4 5 6 7 8 9 var reverseList = function (head ) if (head == null || head.next == null ){ return head } let last = reverseList(head.next) head.next.next = head head.next = null return last };
1、使用递归思想，函数reverseList接收一个头结点，将以该节点为起点的链表反转，并返回反转之后的头结点。
在递归之后，head与last是下图所示：
然后将head的下一个节点的next，即图中的节点2的next指向head，然后将head的next指向null即可。
2、遍历链表
1 2 3 4 5 6 7 8 9 10 11 var reverseList = function (head ) let pre = null let cur = head while (cur !== null ){ let temp = cur.next cur.next = pre pre = cur cur = temp } return pre };
1、基于上面反转链表的递归思想，我们将函数进行修改，用reverse函数实现反转链表前N个节点，就是将head.next从null改为success，success就是第n+1个节点，反转之后将head连接上。
基于reverse函数，我们再来实现反转指定范围的链表，当n=1的时候相当于反转前n个元素；当n!=1的时候，如果我们把 head 的索引视为 1，那么我们是想从第 left 个元素开始反转对吧；如果把 head.next 的索引视为 1 呢？那么相对于 head.next，反转的区间应该是从第 left- 1 个元素开始的……
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 let success = null var reverse = function (head,n ) if (n === 1 ){ success = head.next return head } let last = reverse(head.next,n-1 ) head.next.next = head head.next = success return last } var reverseBetween = function (head, left, right ) if (left === 1 ) return reverse(head,right) head.next = reverseBetween(head.next,left-1 ,right-1 ) return head };
2、基于上面反转链表的第二种方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 var isPalindrome = function (head ) let slow = head let fast = head while (fast !== null && fast.next !== null ){ fast = fast.next.next slow = slow.next } if (fast !== null ){ slow = slow.next } slow = reverse(slow) fast = head while (slow !== null ){ if (fast.val !== slow.val) return false fast = fast.next slow = slow.next } return true function reverse (node ) let pre = null let cur = node while (cur !== null ){ let temp = cur.next cur.next = pre pre = cur cur = temp } return pre } };
使用前缀和数组保存数组每一个索引的前缀和，每一次给定一个区间时，只需要计算sumArr[right + 1] - sumArr[left]即可
1 2 3 4 5 6 7 8 9 10 let sumArr = []var NumArray = function (nums ) sumArr[0 ] = 0 for (let i = 1 ;i <= nums.length;i++){ sumArr[i] = sumArr[i - 1 ] + nums[i - 1 ] } }; NumArray.prototype.sumRange = function (left, right ) return sumArr[right + 1 ] - sumArr[left] };
使用二维前缀和数组保存每一个坐标的前缀和，每次给定左上角坐标与右下角坐标时，只需要计算preSum[x2 + 1]``[y2 + 1] - preSum[x1][y2 + 1] - preSum[x2 + 1][y1] + preSum[x1][y1]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 let preSum = []var NumMatrix = function (matrix ) let m = matrix.length,n = matrix[0 ].length if (m === 0 || n === 0 ) return preSum = new Array (m + 1 ).fill(0 ) for (let i = 0 ;i <= m;i++) preSum[i] = new Array (n + 1 ).fill(0 ) for (let i = 1 ;i <= m;i++){ for (let j = 1 ;j <= n;j++){ preSum[i][j] = preSum[i - 1 ][j] + preSum[i][j - 1 ] + matrix[i - 1 ][j - 1 ] - preSum[i - 1 ][j - 1 ] } } }; NumMatrix.prototype.sumRegion = function (x1, y1, x2, y2 ) return preSum[x2 + 1 ][y2 + 1 ] - preSum[x1][y2 + 1 ] - preSum[x2 + 1 ][y1] + preSum[x1][y1] };
使用前缀和 + 哈希表优化 的方法，只需要一次for循环。在记录前缀和的时候，直接记录下有几个 preSum[j] 和 preSum[i] - k 相等，直接更新结果，就避免了内层的 for 循环 。我们可以用哈希表（js中是用map），在记录前缀和的同时记录该前缀和出现的次数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 var subarraySum = function (nums, k ) let map = new Map () let pre = 0 ,num = 0 map.set(0 ,1 ) for (let i = 0 ;i < nums.length;i++){ pre += nums[i] let res = pre - k if (map.has(res)){ num += map.get(res) } if (map.has(pre)){ map.set(pre,map.get(pre)+1 ) }else { map.set(pre,1 ) } } return num };
根据题意可以看出其实是对数组某个区间元素全部增加一个指定的数的操作。可以使用差分数组的方法，构造出一个差分数组，快速进行区间增减的操作，加入相对区间nums【i..j】的全部元素加3，只需要让差分数组diff[i] += 3，然后diff[j + 1] -= 3即可。最后根据差分数组还原出最终数组。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 var corpFlightBookings = function (bookings, n ) let diff = new Array (n).fill(0 ) for (let a = 0 ;a < bookings.length;a++){ let i = bookings[a][0 ] - 1 let j = bookings[a][1 ] - 1 let val = bookings[a][2 ] diff[i] += val if (j + 1 < diff.length){ diff[j + 1 ] -= val } } let res = new Array (diff.length) res[0 ] = diff[0 ] for (let i = 1 ;i < diff.length;i++){ res[i] = res[i - 1 ] + diff[i] } return res };
使用快慢指针的方法，让慢指针 slow 走在后面，快指针 fast 走在前面探路，找到一个不重复的元素就赋值给 slow 并让 slow 前进一步。这样，就保证了 nums[0..slow] 都是无重复的元素，当 fast 指针遍历完整个数组 nums 后，nums[0..slow] 就是整个数组去重之后的结果。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 var removeDuplicates = function (nums ) if (nums.length === 0 ){ return 0 } let slow = 0 ,fast = 0 while (fast < nums.length){ if (nums[slow] !== nums[fast]){ slow ++ nums[slow] = nums[fast] } fast++ } return slow + 1 };
1、同上面所用的方法一样，只是改为if判断成功时改变slow的next指针到fast上。
1 2 3 4 5 6 7 8 9 10 11 12 13 var deleteDuplicates = function (head ) if (head == null ) return null let slow = head,fast = head while (fast !== null ){ if (slow.val != fast.val){ slow.next = fast slow = slow.next } fast = fast.next } slow.next = null return head };
2、使用递归
1 2 3 4 5 var deleteDuplicates = function (head ) if (head == null || head.next == null ) return head head.next = deleteDuplicates(head.next) return head.val == head.next.val ? head.next : head };
1 2 3 4 5 6 7 8 9 10 11 var removeElement = function (nums, val ) let slow = fast = 0 while (fast < nums.length){ if (nums[fast] !== val){ nums[slow] = nums[fast] slow++ } fast++ } return slow };
这道题目可以用到上面移动元素的方法，由于上面函数返回的数组在0~slow范围已经是排除了val值，所以我们只需要在slow后面把0补上就可以。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 var moveZeroes = function (nums ) let p = removeElement(nums,0 ) for (p;p < nums.length;p++){ nums[p] = 0 } return nums }; var removeElement = function (nums, val ) let slow = fast = 0 while (fast < nums.length){ if (nums[fast] !== val){ nums[slow] = nums[fast] slow++ } fast++ } return slow };
滑动窗口！！！搞了一下午，总算提交通过了淦！
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 var minWindow = function (s, t ) const need = {} const window = {} let arr = t.split("" ) for (let i = 0 ;i < arr.length;i++){ need[arr[i]] = (need[arr[i]] || 0 ) + 1 } let left = 0 ,right = 0 let valid = 0 let start = 0 ,len = Infinity while (right < s.length){ let c = s[right] right++ if (need[c]){ window [c] = (window [c] || 0 ) + 1 if (window [c] == need[c]) valid++ } while (valid === Object .keys(need).length){ if (right - left < len){ start = left len = right - left } let d = s[left] left++ if (need[d]){ if (window [d] === need[d]){ valid-- } window [d]-- } } } return len == Infinity ? "" : s.slice(start,start+len) };
上面的困难题都会了，这道题也是滑动窗口，拿上面代码改改就行
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 var checkInclusion = function (s1, s2 ) let need = {} let window = {} let arr = s1.split('' ) for (let i = 0 ;i < arr.length;i++){ need[arr[i]] = (need[arr[i]] || 0 ) + 1 } let left = 0 ,right = 0 let len = Infinity let valid = 0 while (right < s2.length){ let s = s2[right] right++ if (need[s]){ window [s] = (window [s] || 0 ) + 1 if (window [s] === need[s]) valid++ } while (right - left >= s1.length){ if (valid === Object .values(need).length){ return true } let d = s2[left] left++ if (need[d]){ if (window [d] === need[d]) valid-- window [d]-- } } } return false };
使用滑动窗口，将上面一题的代码改改就行了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 var findAnagrams = function (s, p ) let need = {} let window = {} let res = [] let arr = p.split("" ) for (let i = 0 ;i < arr.length;i++){ need[arr[i]] = (need[arr[i]] || 0 ) + 1 } let left = 0 ,right = 0 let valid = 0 while (right < s.length){ let c = s[right] right++ if (need[c]){ window [c] = (window [c] || 0 ) + 1 if (window [c] === need[c]){ valid++ } } while (right - left >= p.length){ if (valid === Object .values(need).length){ res.push(left) } let d = s[left] left++ if (need[d]){ if (window [d] === need[d]) valid-- window [d]-- } } } return res };
滑动窗口解法：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 var lengthOfLongestSubstring = function (s ) let window = {} let left = 0 ,right = 0 let res = 0 while (right < s.length){ let c = s[right] right++ window [c] = (window [c] || 0 ) + 1 while (window [c] > 1 ){ let d = s[left] left++ window [d]-- } res = Math .max(res,right - left) } return res };
使用二分法，第一个函数left_bound用来寻找第一个位置，第二个函数用来寻找最后一个位置。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 var searchRange = function (nums, target ) return [left_bound(nums,target),right_bound(nums,target)] }; var left_bound = function (nums,target ) let left = 0 ,right = nums.length - 1 while (left <= right){ let mid = left + Math .floor((right - left) / 2 ) if (nums[mid] < target){ left = mid + 1 }else { right = mid - 1 } } if (nums[left] !== target){ return -1 } return left } var right_bound = function (nums,target ) let left = 0 ,right = nums.length - 1 while (left <= right){ let mid = left + Math .floor((right - left) / 2 ) if (nums[mid] > target){ right = mid - 1 }else { left = mid + 1 } } if (nums[right] !== target){ return -1 } return right }
使用左右指针，每次根据相加结果与目标结果进行大小比较判断是增加left还是减少right
1 2 3 4 5 6 7 8 9 10 11 12 13 var twoSum = function (numbers, target ) let left = 0 ,right = numbers.length - 1 while (left <= right){ if (numbers[left] + numbers[right] == target){ return [left+1 ,right+1 ] }else if (numbers[left] + numbers[right] < target){ left++ }else if (numbers[left] + numbers[right] > target){ right-- } } return [-1 ,-1 ] };
使用左右指针就可以：
1 2 3 4 5 6 7 8 9 10 11 var reverseString = function (s ) let left = 0 ,right = s.length - 1 while (left <= right){ let temp = s[left] s[left] = s[right] s[right] = temp left++ right-- } return s };
如果输入相同的 l 和 r，就相当于寻找长度为奇数的回文串，如果输入相邻的 l 和 r，则相当于寻找长度为偶数的回文串。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 var longestPalindrome = function (s ) let res = "" for (let i = 0 ;i < s.length;i++){ let s1 = fn(s,i,i) let s2 = fn(s,i,i+1 ) res = res.length > s1.length ? res : s1 res = res.length > s2.length ? res : s2 } return res }; var fn = function (s,l,r ) while (l >= 0 && r < s.length && s[l] == s[r]){ l-- r++ } return s.substring(l + 1 , r) }
使用前缀和加二分搜索的方法，将权重用前缀和思想表示出来，然后随机产生一个数，用二分查找找到该数在数组中的位置，比该数大的最小元素的权重索引就是我们想要的答案。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 var Solution = function (w ) let n = w.length preSum = new Array (n + 1 ).fill(0 ) preSum[0 ] = 0 for (let i = 1 ;i <= n;i++){ preSum[i] = preSum[i - 1 ] + w[i - 1 ] } }; Solution.prototype.pickIndex = function ( let n = preSum.length let target = Math .floor(Math .random() * preSum[n - 1 ]) + 1 const binarySearch = (x ) => { let low = 0 ,high = preSum.length - 1 while (low < high){ const mid = Math .floor((high - low) / 2 ) + low if (preSum[mid] < x){ low = mid + 1 }else { high = mid } } return low - 1 } return binarySearch(target) };
使用双指针的思想，从两侧向内缩进，每次缩进条件是看哪个比较小
1 2 3 4 5 6 7 8 9 10 var maxArea = function (height ) let max = 0 let i = 0 ,j = height.length - 1 while (i < j){ max = Math .max(Math .min(height[i],height[j]) * (j - i),max) if (height[i] < height[j]) i++ else j-- } return max };
首先对数组进行排序，排序后固定一个数 nums[i]，再使用左右指针指向 nums[i]后面的两端，数字分别为 nums[L]和 nums[R]，计算三个数的和 sum判断是否满足为 00，满足则添加进结果集。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 var threeSum = function (nums ) let arr = [] if (nums == null && nums.length < 3 ) return arr nums.sort((a,b ) => { return a - b }) for (let i = 0 ;i < nums.length;i++){ let l = i + 1 ,r = nums.length - 1 if (nums[i] > 0 ) break if (i > 0 && nums[i] == nums[i-1 ]) continue while (l < r){ let sum = nums[i] + nums[l] + nums[r] if (sum === 0 ){ arr.push([nums[i],nums[l],nums[r]]) while (l < r && nums[l] == nums[l+1 ]) l++ while (l < r && nums[r] == nums[r-1 ]) r-- l++ r-- } else if (sum < 0 ) l++ else if (sum > 0 ) r-- } } return arr };
使用回溯方法，首先使用map存储每个数字对应的所有可能的字母，然后进行回溯操作，回溯过程中维护一个path数组，表示已有的字母排序，该path数组初始为空，每次取电话号码的一位数字，从哈希表中获得该数字对应的所有可能的字母，并将其中一个字母插入到已有的字母排序后面，然后继续处理电话号码的后一位数字，直到处理完电话号码所有数字。然后进行回退操作，遍历其余的字母排序。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 var letterCombinations = function (digits ) const arr = ['' ,'' ,'abc' ,'def' ,'ghi' ,'jkl' ,'mno' ,'pqrs' ,'tuv' ,'wxyz' ] let map = new Map () for (let i = 0 ;i < arr.length;i++){ map.set(i,arr[i]) } let res = [] let path = [] if (digits.length == 0 ) return [] if (digits.length == 1 ) return map.get(Number (digits[0 ])).split('' ) fn(digits.length,0 ) return res function fn (l,r ) if (path.length == l){ res.push(path.join('' )) return } let strArr = map.get(Number (digits[r])).split('' ) for (let i = 0 ;i < strArr.length;i++){ path.push(strArr[i]) fn(l,r+1 ) path.pop() } } };
采用递归，终止条件是字符串的长度等于2n，递归函数传入构建的字符串，左右括号剩余多少，每个位置有两种选择，选择左或者右括号，这里可以进行剪枝优化，只有右括号的保有数量大于左括号的保有数量，才能选右括号，否则肯定不能构成有效括号
1 2 3 4 5 6 7 8 9 10 11 12 13 var generateParenthesis = function (n ) let res = [] fn('' ,0 ,0 ) function fn (str,l,r ) if (l + r == 2 * n) { res.push(str) return } if (l < n) fn(str+'(' ,l + 1 ,r) if (l > r) fn(str+')' ,l,r + 1 ) } return res };
采用两遍扫描的方法，首先从后向前查找第一个顺序对 (i,i+1)，满足 a[i] < a[i+1]。这样「较小数」即为 a[i]。此时 [i+1,n) 必然是下降序列。
如果找到了顺序对，那么在区间 [i+1,n) 中从后向前查找第一个元素 j 满足 a[i]<a[j]。这样「较大数」即为 a[j]。
交换 a[i] 与 a[j]，此时可以证明区间[i+1,n) 必为降序。我们可以直接使用双指针反转区间 [i+1,n) 使其变为升序，而无需对该区间进行排序。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 var nextPermutation = function (nums ) let i = nums.length - 2 while (i >= 0 && nums[i] >= nums[i+1 ]){ i-- } if (i >= 0 ){ let j = nums.length - 1 while (nums[i] >= nums[j]){ j-- } [nums[i],nums[j]] = [nums[j],nums[i]] }else { return nums.reverse() } let m = i+1 let n = nums.length - 1 for (m,n;m < n;m++,n--){ [nums[m],nums[n]] = [nums[n],nums[m]] } return nums };
用二分法，我们将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的。拿示例来看，我们从 6 这个位置分开以后数组变成了 [4, 5, 6] 和 [7, 0, 1, 2] 两个部分，其中左边 [4, 5, 6] 这个部分的数组是有序的，其他也是如此。
这启示我们可以在常规二分查找的时候查看当前 mid 为分割位置分割出来的两个部分 [l, mid] 和 [mid + 1, r] 哪个部分是有序的，并根据有序的那个部分确定我们该如何改变二分查找的上下界，因为我们能够根据有序的那部分判断出 target 在不在这个部分：
如果 [l, mid - 1] 是有序数组，且 target 的大小满足 [nums[l],nums[mid])，则我们应该将搜索范围缩小至 [l, mid - 1]，否则在 [mid + 1, r] 中寻找。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 var search = function (nums, target ) if (!nums.length) return -1 let l = 0 let r = nums.length - 1 while (l <= r){ let mid = (l + r) >> 1 if (nums[mid] == target) return mid if (nums[mid] >= nums[0 ]){ if (nums[mid] > target && nums[0 ] <= target) r = mid - 1 else l = mid + 1 }else { if (nums[mid] < target && nums[r] >= target) l = mid + 1 else r = mid - 1 } } return -1 };
也称为荷兰国旗问题。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 var sortColors = function (nums ) let i = 0 let len = nums.length - 1 let l = 0 while (i < len + 1 ){ if (nums[i] === 0 ){ let temp = nums[i] nums[i] = nums[l] nums[l] = temp i++ l++ }else if (nums[i] === 2 ){ let temp = nums[i] nums[i] = nums[len] nums[len] = temp len-- }else i++ } return nums };
一开始使用数组遍历的方法查找目标值，时间复杂度较高，改为二分查找更快。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 var getSkyline = function (buildings ) const arr = [], ans = [], n = buildings.length; for (let [l, r, h] of buildings) arr.push([l, h], [r, -h]); arr.sort((a, b ) => a[0 ] - b[0 ] || b[1 ] - a[1 ]); const m = arr.length, heights = [0 ]; let preH = 0 ; for (let [l, h] of arr) { if (h > 0 ) heights.splice(search(heights, h), 0 , h); else heights.splice(search(heights, -h), 1 ); if (preH !== heights[0 ]) { ans.push([l, heights[0 ]]) preH = heights[0 ]; } } return ans; }; function search (arr, tar ) let l = 0 , r = arr.length - 1 ; while (l < r) { const mid = l + ((r - l) >> 1 ); if (arr[mid] === tar) return mid; else if (arr[mid] < tar) r = mid; else l = mid + 1 ; } return l; }
我们定义递归函数 dfs(target,combine,idx)表示当前在candidates 数组的第 idx 位，还剩 target 要组合，已经组合的列表为 combine。递归的终止条件为target≤0 或者candidates 数组被全部用完。那么在当前的函数中，每次我们可以选择跳过不用第idx 个数，即执行dfs(target,combine,idx+1)。也可以选择使用第idx 个数，即执行dfs(target−candidates[idx],combine,idx)，注意到每个数字可以被无限制重复选取，因此搜索的下标仍为 idx。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 var combinationSum = function (candidates, target ) const res = [] function dfs (target,combile,idx ) if (target === 0 ){ res.push(combile) return } if (idx === candidates.length){ return } dfs(target,combile,idx+1 ) if (target - candidates[idx] >= 0 ){ dfs(target-candidates[idx],[...combile,candidates[idx]],idx) } } dfs(target,[],0 ) return res };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 var trap = function (height ) if (height === [0 ]) return 0 let n = height.length let leftMax = new Array (n).fill(0 ) let rightMax = new Array (n).fill(0 ) leftMax[0 ] = height[0 ] rightMax[n - 1 ] = height[n - 1 ] for (let i = 1 ;i < n;i++){ leftMax[i] = Math .max(height[i],leftMax[i-1 ]) } for (let i = n - 2 ;i >= 0 ;i--){ rightMax[i] = Math .max(height[i],rightMax[i+1 ]) } let res = 0 for (let i = 0 ;i < n;i++){ res += Math .min(leftMax[i],rightMax[i]) - height[i] } return res };
使用回溯的方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 var permute = function (nums ) let res = [] let path = [] function dfs (use ) if (path.length === nums.length){ res.push([...path]) return } for (let i = 0 ;i < nums.length;i++){ if (use[i]) continue use[i] = true path.push(nums[i]) dfs(use) use[i] = false path.pop() } } dfs([]) return res };
老板给度度熊
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 function (n,arr ) let k = 0 while (true ){ let max = 0 for (let i = 0 ;i < arr.length;i++){ if (arr[i] > arr[max]) max = i } if (arr[max] < n) continue let step = Math .floor(n / arr[max]) for (let i = 0 ;i < arr.length;i++){ if (i !== max) { arr[i] += step } } arr[max] -= step * n k += step } return k }
先把二维矩阵沿对角线反转，然后反转矩阵的每一行，结果就是顺时针反转整个矩阵。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 var rotate = function (matrix ) let n = matrix.length for (let i = 0 ;i < n;i++){ for (let j = i;j < n;j++){ let temp = matrix[i][j] matrix[i][j] = matrix[j][i] matrix[j][i] = temp } } for (let i = 0 ;i < n;i++){ matrix[i].reverse() } return matrix };
由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。
1 2 3 4 5 6 7 8 9 10 11 var groupAnagrams = function (strs ) let map = new Map () for (let str of strs){ let arr = str.split("" ) let key = arr.sort().toString() let list = map.get(key) ? map.get(key) : [] list.push(str) map.set(key,list) } return Array .from(map.values()) };
1 2 3 4 5 6 7 8 var maxSubArray = function (nums ) let pre = 0 ,max = nums[0 ] nums.forEach(item => pre = Math .max(item,pre+item) max = Math .max(pre,max) }) return max };
小红拿到了一个二进制字符串
对于任意二进制字符串，只有形如1….0000的字符串才是2的幂
1 2 3 4 5 6 7 function minCnt (s ) let sum = 0 for (let i =0 ;i < s.length;i++){ if (s[i] === "1" ) sum++ } return sum - 1 }
可以把题意理解为最多能跳多远，如果可以越过最后一格，返回true否则返回false
1 2 3 4 5 6 7 8 var canJump = function (nums ) let max = 0 for (let i = 0 ;i < nums.length - 1 ;i++){ max = Math .max(max,i+nums[i]) if (max <= i) return false } return true };
中等题！！！先手必赢
1 2 3 var stoneGame = function (piles ) return true };
个数， 每一次从
中取出一个最大的减去
个数加上
， 一直重复直到最大的
， 执行次数记为
。老板想知道最少执行多少次操作使得
，她可以删掉其中的一些字符，使得最终该字符串为一个2的幂（即可以表示为
形式的数)。小红想知道，自己最少删几个字符可以达成？请你编写一个函数返回这个答案。
