105. 从前序与中序遍历序列构造二叉树

  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val, left, right) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.left = (left===undefined ? null : left)
  6.  *     this.right = (right===undefined ? null : right)
  7.  * }
  8.  */
  9. /**
  10.  * @param {number[]} preorder
  11.  * @param {number[]} inorder
  12.  * @return {TreeNode}
  13.  */
  14. var buildTree = function(preorder, inorder) {
  15.     if(!inorder.length) return null
  17.     let temp = preorder[0]
  18.     let mid = inorder.indexOf(temp)
  19.     let root = new TreeNode(temp)
  21.     // 这里递归怎么计算的
  22.     root.left = buildTree(preorder.slice(1,mid+1), inorder.slice(0,mid))
  23.     root.right = buildTree(preorder.slice(mid+1), inorder.slice(mid + 1))
  24.     return root
  25. };

剑指 Offer 10- II. 青蛙跳台阶问题

  1. /**
  2.  * @param {number} n
  3.  * @return {number}
  4.  */
  5.  // dp[1] = 1
  6.  // dp[2] = 2
  7.  // dp[3] = dp[2] + dp[1]
  8. function numWays(n) {
  9.   // 为什么是n + 1， 0 => n
  10.   const dp = new Array(n + 1);
  11.   [dp[0], dp[1]] = [1, 1];
  12.   for (let i = 2; i <= n; i++) {
  13.     dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
  14.   }
  15.   return dp[n];
  16. }

384. 打乱数组

  1. /**
  2.  * @param {number[]} nums
  3.  */
  4. var Solution = function(nums) {
  5.     this.originNums = [...nums]
  6.     this.nums = nums
  7. };
  9. /**
  10.  * @return {number[]}
  11.  */
  12. Solution.prototype.reset = function() {
  13.     this.nums = [...this.originNums]
  14.     return this.nums
  15. };
  17. /**
  18.  * @return {number[]}
  19.  */
  20. Solution.prototype.shuffle = function() {
  21.     let list = []
  23.     while(this.nums.length) {
  24.         const index = Math.floor(this.nums.length * Math.random())
  25.         list.push(this.nums.splice(index, 1))
  26.     }
  27.     this.nums = [...list]
  28.     return list
  29. };
  31. /**
  32.  * Your Solution object will be instantiated and called as such:
  33.  * var obj = new Solution(nums)
  34.  * var param_1 = obj.reset()
  35.  * var param_2 = obj.shuffle()
  36.  */

25. K 个一组翻转链表

198. 打家劫舍

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  6.  // dp[i] = max(nums[i] + dp[i - 2], dp[i - 1])
  7. var rob = function(nums) {
  8.         let pre = 0, cur = 0, tmp;
  9.         for(let num of nums) {
  10.             tmp = cur;
  11.             cur = Math.max(pre + num, cur);
  12.             pre = tmp;
  13.         }
  14.     return cur
  15. };

64. 最小路径和

状态转移方程：
dp[i, j] = nums[i, j] + Min(dp[i, j - 1], dp[i - 1, j])

  1. /**
  2.  * @param {number[][]} grid
  3.  * @return {number}
  4.  */
  5. var minPathSum = function(grid) {
  6.     var dp = grid
  7.     var rowLen = grid.length
  8.     var colLen = grid[0].length
  10.     // 初始化第一行
  11.     for (let i = 1; i < colLen; i++) {
  12.         dp[0][i] += dp[0][i - 1]
  13.     }
  14.     //初始化第一列
  15.     for (let i = 1; i < rowLen; i++) {
  16.         dp[i][0] += dp[i - 1][0]
  17.     }
  18.     for (let i = 1; i < rowLen; i++) {
  19.         for (let j = 1; j < colLen; j++) {
  20.             dp[i][j] = grid[i][j] + Math.min(dp[i][j - 1], dp[i - 1][j])
  21.         }
  22.     }
  23.     return dp[rowLen - 1][colLen - 1]
  24. };