算法训练题汇总

前端Jeek 2020/10/21 算法

🌙 算法训练

🌙 二、数组 (opens new window)

🌙 1.合并两个有序数组 (opens new window)

🌙 4.两数之和 II (opens new window)

🌙 7.滑动窗口的最大值 (opens new window)

🌙 8.最长上升子序列 (opens new window)

🌙 10.最长公共子序列 (opens new window)

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function(text1, text2) {
    let len1 = text1.length;
    let len2 = text2.length;

    let dp = new Array(len1 + 1).fill(0).map(d => new Array(len2 + 1).fill(0));

    for(let i=1; i<=len1; i++) {
        for(let j=1; j<=len2; j++) {
            if(text1[i-1] === text2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }

    return dp[len1][len2];
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

DP Table练习工具 (opens new window)

🌙 11.乘积最大子数组 (opens new window)

🌙 12.俄罗斯套娃信封问题【排序+最长上升子序列】 (opens new window)


/**
 * @param {number[][]} envelopes
 * @return {number}
 */
var maxEnvelopes = function(envelopes) {
  if (envelopes.length === 1) return 1;
    // 安左侧升序，相同，安右侧降序
    // [1,5],[2,5],[2,4], [3,4]
    envelopes.sort((a, b) => {
        if (a[0] !== b[0]) return a[0] - b[0];
        else return b[1] - a[1];
    });
    let LISArr = [];
    for (let [key, value] of envelopes) {
      LISArr.push(value);
    }
    console.log( LISArr);
    return LIS(LISArr);
};
  // 计算最长上升子序列
function LIS(arr) {
  let dp = [];
  let maxAns = 0;
  for (let i = 0; i < arr.length; i++) {
    dp[i] = 1;
  }
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j >= 0; j--) {
      if (arr[i] > arr[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1)
      }
      maxAns = Math.max(maxAns, dp[i]);
    }
  }
  return maxAns;
}

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

🌙 13.最长连续递增序列【快慢指针】 (opens new window)


/**
 * @param {number[]} nums
 * @return {number}
 */
var findLengthOfLCIS = function(nums) {
    if (nums.length === 0) return 0;
    const n = nums.length;
    let left = 0, right = 1;
    let globalMaxLen = 1, maxLen = 1;
    while (right < n) {
        if (nums[right] > nums[left]) maxLen++;
        else {
            maxLen = 1;
        }
        left++;
        right++;
        globalMaxLen = Math.max(globalMaxLen, maxLen);
    }
    return globalMaxLen;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

🌙 14.最长连续序列【哈希表】 (opens new window)


/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    if (nums.length === 0) return 0;
    const set = new Set(nums);
    const n = nums.length;
    let globalLongest = 1;
    for (let i = 0; i < n; i++) {
        if (!set.has(nums[i] - 1)) {
            let longest = 1;
            let currentNum = nums[i];
            while (set.has(currentNum + 1)) {
                currentNum += 1;
                longest++;
            }
            globalLongest = Math.max(globalLongest, longest);
        }
    }
    return globalLongest;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

🌙 15.盛最多水的容器【双指针】 (opens new window)


/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let n = height.length;
    let left = 0, right = n - 1;
    let maxOpacity = 0;
    while (left < right) {
        let res = Math.min(height[left], height[right]) * (right - left);
        maxOpacity = Math.max(maxOpacity, res);
        if (height[left] < height[right]) left++
        else right--;
    }
    return maxOpacity;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

🌙 16.删除有序数组中的重复项【快慢指针】 (opens new window)


/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
  if (nums.length <= 1) return nums.length;
  let lo = 0, hi = 0;
  while (hi < nums.length) {
    while (nums[lo] === nums[hi] && hi < nums.length) hi++;
    if (nums[lo] !== nums[hi] && hi < nums.length) {
      lo++;
      nums[lo] = nums[hi];
    }
    hi++;
  }
  return lo + 1;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

🌙 17.和为K的子数组【哈希表】 (opens new window)


/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
    let cnt = 0;
    let sum0_i = 0, sum0_j = 0;
    let map = new Map();
    map.set(0, 1);
    for (let i = 0; i <= nums.length; i++) {
        sum0_i += nums[i];
        sum0_j = sum0_i - k;
        console.log('map', sum0_j, map.get(sum0_j))
        if (map.has(sum0_j)) {
            cnt += map.get(sum0_j);
        }
        let sumCnt = map.get(sum0_i) || 0;
        map.set(sum0_i, sumCnt + 1);
    }
    return cnt;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

🌙 17.接雨水【双指针】 (opens new window)


/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let ans = 0;
    let left = 0, right = height.length - 1;
    let leftMax = 0, rightMax = 0;
    while (left < right) {
        leftMax = Math.max(leftMax, height[left]);
        rightMax = Math.max(rightMax, height[right]);
        if (height[left] < height[right]) {
            ans += leftMax - height[left];
            ++left;
        } else {
            ans += rightMax - height[right];
            --right;
        }
    }
    return ans;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

🌙 18.跳跃游戏(贪心) (opens new window)


/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    let faster = 0;
    for (let i = 0; i < nums.length - 1; i++) {
        faster = Math.max(faster, i + nums[i]);
        if (faster <= i) return false;
    }
    return faster >= nums.length - 1;
};

1
2
3
4
5
6
7
8
9
10
11
12
13

🌙 19.用最少数量的箭引爆气球 (opens new window)


/**
 * @param {number[][]} points
 * @return {number}
 */
var findMinArrowShots = function(points) {
  if(points.length < 1) return 0;

  points.sort((a,b) => a[0] - b[0]);

  let ans = 1;

  for(let i=1; i<points.length; i++) {
    if(points[i][0] > points[i-1][1]) {
      ans++;
    } else {
      points[i][1] = Math.min(points[i][1], points[i-1][1])
    }
  }

  return ans;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

🌙 20.合并区间 (opens new window)

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
  if(intervals.length < 2) return intervals;
  intervals.sort((a,b) => a[0] - b[0]);

  let ans = [intervals[0]];

  for(let i=1; i<intervals.length; i++) {
    let last = ans[ans.length - 1];
    if(last[1] >= intervals[i][0]) {
      last[1] = Math.max(last[1], intervals[i][1])
    } else {
      ans.push(intervals[i])
    }
  }

  return ans;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

🌙 21.在排序数组中查找元素的第一个和最后一个位置 (opens new window)


/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    const left = leftBound(nums, target);
    const right = rightBound(nums, target);
    return [left, right];
};
function leftBound(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    while (left <= right) {
        let mid = Math.floor(left + (right - left) / 2);
        if (nums[mid] === target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    if (left >= nums.length || nums[left] !== target) {
        return -1;
    }
    return left;
}
function rightBound(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    while (left <= right) {
        let mid = Math.floor(left + (right - left) / 2);
        if (nums[mid] === target) {
            left = mid + 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    if (right < 0 || nums[right] !== target) {
        return -1;
    }
    return right;
}

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
46
47
48
49

🌙 六.[队列和广度优先搜索（BFS）]

🌙 3.二叉树的层序遍历 (opens new window)

🌙 4.[解数独]

/**
 * @param {string[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function(/** @type {any} */ board) {
  backtrack(board);
};

/**
 * @param {string | any[]} board
 */
function backtrack(board) {
  for(let i = 0; i < board.length; i++) {
    for(let j = 0; j < board[0].length; j++) {
      if(board[i][j] !== '.') continue;

      for(let k = 1; k <= 9; k++) {
        if(isValid(board, i, j, k.toString())) {
          board[i][j] = k.toString();
          if(backtrack(board)) return true;
          board[i][j] = '.';
        }
      }
      return false;
    }
  }

  return true;
}

/**
 * @param {string | any[]} board
 * @param {number} row
 * @param {number} col
 * @param {string} val
 */
function isValid(board, row, col, val) {
  for(let i = 0; i < 9; i++) {
    if(board[row][i] === val) {
      return false;
    }
  }

  for(let i = 0; i < 9; i++) {
    if(board[i][col] === val) {
      return false;
    }
  }

  const m = Math.floor(row / 3) * 3;
  const n = Math.floor(col / 3) * 3;
  for(let i = m; i < m + 3; i++) {
    for(let j = n; j < n + 3; j++) {
      if(board[i][j] === val) {
        return false;
      }
    }
  }

  return true;
}

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

🌙 5.迷宫问题

/**
 * @param {number[][]} [grid]
 * @param {number} [row]
 * @param {number} [col]
 */
const grid = [
          [0, 1, 0, 0, 0],
          [0, 1, 0, 1, 0],
          [0, 0, 0, 0, 1],
          [0, 1, 1, 1, 0],
          [0, 0, 0, 0, 0],
        ];
const row = 5;
const col = 5;

function resolveMaze(grid = [], row = 1, col = 1) {
  /** @type {number[][]} */
  const res = [];
  const visited = new Map();
  const direction = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  backtrack(grid, 0, 0);

  /**
     * @param {number[][]} arr
     * @param {number} m
     * @param {number} n
     */
  function backtrack(arr, m, n) {
    // 到达终点
    if(m === row - 1 && n === col - 1) {
      res.push([m, n]);

      for(const item of res) {
        console.log(`(${item[0]},${item[1]})`);
      }
      return true;
    }
    if(m < 0 || n < 0 || m >= row || n >= col || visited.has(`${m},${n}`)){
      return false;
    }
    if(grid[m][n] === 1) return false;

    // 记录
    visited.set(`${m},${n}`, true);
    res.push([m, n]);
    // 做选择
    for(let i = 0; i < direction.length; i++) {
      const _row = m + direction[i][0];
      const _col = n + direction[i][1];
      if(backtrack(grid, _row, _col)) {
        return true;
      }
    }

    // 撤销
    visited.delete(`${m},${n}`);
    res.pop();

    return false;
  }
  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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

🌙 七、树 (opens new window)

🌙 1.二叉树的前序遍历 (opens new window)

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    var res = [];
    preOrder(root, res);

    return res;
};

var preOrder = function(root, res) {
    if(!root) return;
    // 根 - 左 - 右
    res.push(root.val);
    preOrder(root.left, res);
    preOrder(root.right, 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

🌙 2.二叉树的中序遍历 (opens new window)

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    var res = [];
    inOrder(root, res);

    return res;
};

var inOrder = function(root, res) {
    if(!root) return;
    // 左 - 根 - 右
    inOrder(root.left, res);
    res.push(root.val);
    inOrder(root.right, 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

🌙 3.二叉树的后序遍历 (opens new window)

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
    var res = [];
    postOrder(root, res);

    return res;
};

var postOrder = function(root, res) {
    if(!root) return;
    // 左 - 右 - 根
    postOrder(root.left, res);
    postOrder(root.right, res);
    res.push(root.val)
}

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

🌙 4.二叉树的层序遍历 (opens new window)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    var res = [];
    // 广度优先遍历
    bfs(root, res);

    return res;
};

var bfs = function(root, res) {
    if(!root) return;
    // 根入队列
    var queue = [root];

    while(queue.length > 0) {
        // 记录size
        var size = queue.length;
        // 保存当前层数据
        var data = [];
        // 此处使用size，不要使用queue.length,因为他是一直变化的
        for(var i=0; i < size; i++) {
            // 出队列
            var cur = queue.shift();
            // 保存数据
            data.push(cur.val);
            // 左子树入队列
            if(cur.left) queue.push(cur.left);
            // 右子树入队列
            if(cur.right) queue.push(cur.right);
        }

        res.push(data);
    }
}

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

🌙 5.二叉树的最大深度 (opens new window)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if(!root) return 0;

    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right))
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

🌙 6.对称二叉树 (opens new window)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if(!root) return true;

    return helper(root.left, root.right);
};

// 判断左右节点是否对称
var helper = function(root1, root2) {
    // 都不存在
    if(!root1 && !root2) return true;
    // 有一个不存在
    if(!root1 || !root2) return false;
    // 都存在，值不同
    if(root1.val !== root2.val) return false;
    // 都存在，值相同,继续比较子节点
    return helper(root1.left, root2.right) && helper(root1.right, root2.left);
}

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

🌙 7.验证二叉搜索树 (opens new window)

递归：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
    return helper(root, -Infinity, Infinity);
};

var helper = function(root, lower, higher) {
    if(!root) return true;
    if(root.val <= lower || root.val >= higher) return false;
    // 维护这个最值，左节点的最大值为root.val；右节点的最小值为root.val
    return helper(root.left, lower, root.val) && helper(root.right, root.val, higher);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

迭代：中序遍历二叉搜索树的结果序列是一个升序序列

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
   // 中序遍历
   let inorder = -Infinity;
   let stack = [];

   while(root !== null || stack.length) {
       // 先遍历左子树
       while(root !== null) {
           stack.push(root);
           root = root.left;
       }
       // 左子树出栈
       root = stack.pop();
        // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
       if(root.val <= inorder) return false;
       inorder = root.val;
       root = root.right;
   }
   return true;
};

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

🌙 8.二叉搜索树的最近公共祖先 (opens new window)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
        //如果根节点和p,q的差相乘是正数，说明这两个差值要么都是正数要么都是负数，也就是说
        //他们肯定都位于根节点的同一侧，就继续往下找
        while ((root.val - p.val) * (root.val - q.val) > 0) {
            root = p.val < root.val ? root.left : root.right;
        }
        //如果相乘的结果是负数，说明p和q位于根节点的两侧，如果等于0，说明至少有一个就是根节点
        return root;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

🌙 9.二叉树的最近公共祖先 (opens new window)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    if(root === null || root === p || root === q) return root;
    
    // 分别在left和right中找p和q的公共祖先
    var left = lowestCommonAncestor(root.left, p, q);
    var right = lowestCommonAncestor(root.right, p, q);
    
    //如果left为空，说明这两个节点在cur结点的右子树上，我们只需要返回右子树查找的结果即可
    if(left === null) return right;
    //同理
    if(right === null) return left;
    
	//如果left和right都不为空，说明这两个节点一个在root的左子树上一个在root的右子树上，
    //我们只需要返回root结点即可。	
    return root;

};

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

🌙 11.路径总和 (opens new window)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {boolean}
 */
var hasPathSum = function(root, sum) {
    if(!root) return false;

    if(!root.left && !root.right && root.val === sum) return true;

    return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

🌙 12.从中序与后序遍历序列构造二叉树 (opens new window)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function(inorder, postorder) {
    return helper(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
};

var helper = function(inorder, postorder, inorderStart, inorderEnd, postorderStart, postorderEnd) {
    // 判断越界
    if(inorderStart > inorderEnd || postorderStart > postorderEnd) return null;

    // 根节点
    const rootVal = postorder[postorderEnd];
    const root = new TreeNode(rootVal);
    // 判断是不是只有一个节点
    if(postorderStart === postorderEnd) return root;

    // **在inorder中找到root对应的index将inorder分为左右两个子节点**
    const rootIndex = inorder.indexOf(rootVal);

    root.left = helper(inorder, postorder, inorderStart, rootIndex - 1, postorderStart, postorderStart + ((rootIndex - 1) - inorderStart)); // ((rootIndex - 1) - inorderStart) 即左子树的长度

    root.right = helper(inorder, postorder, rootIndex + 1, inorderEnd, postorderEnd - 1 - (inorderEnd - (rootIndex + 1)), postorderEnd - 1); // (inorderEnd - (rootIndex + 1)) 即右子树的长度

    return root;
}

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

🌙 13.从前序与中序遍历序列构造二叉树 (opens new window)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    return helper(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
};

var helper = function(preorder, inorder, preorderStart, preorderEnd, inorderStart, inorderEnd) {
    // 判断越界
    if(preorderStart > preorderEnd || inorderStart > inorderEnd) return null;
    
    // 根节点
    const rootVal = preorder[preorderStart];
    const root = new TreeNode(rootVal);

    // 判断preorder是不是只有一个节点
    if(preorderStart === preorderEnd) return root;
    // **在中序遍历中找到rootIndex,将inorder分为左右两个子节点**
    const rootIndex = inorder.indexOf(rootVal);

    root.left = helper(preorder, inorder, preorderStart + 1, preorderStart + 1 + ((rootIndex - 1) - inorderStart), inorderStart, rootIndex - 1); // (rootIndex - 1) - inorderStart)即左子树长度

    root.right = helper(preorder, inorder,(preorderEnd - (inorderEnd - (rootIndex + 1))),preorderEnd, rootIndex + 1, inorderEnd); // (inorderEnd - (rootIndex + 1)) 即右子树长度

    return root;
}

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

🌙 14.从前序和后序遍序列历构造二叉树 (opens new window)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} pre
 * @param {number[]} post
 * @return {TreeNode}
 */
var constructFromPrePost = function(pre, post) {
    return helper(pre, post, 0, pre.length - 1, 0, post.length - 1);
};

var helper = function(pre, post, preStart, preEnd, postStart, postEnd) {
    // 判断越界
    if(preStart > preEnd || postStart > postEnd) return null;

    // 根节点
    const rootVal = pre[preStart];
    const root = new TreeNode(rootVal);

    // 判断是不是只有一个节点
    if(preStart === preEnd) return root;

    // 先在preorder中找到左子树的leftRootVal
    const leftRootVal = pre[preStart + 1];
    // **然后在post中找到leftRootIndex, 然后根据这个index将post分为左右两个子节点**
    const index = post.indexOf(leftRootVal);

    root.left = helper(pre, post, preStart + 1, preStart + 1 + (index - postStart) , postStart, index); // (index - postStart) 即左子树长度
    root.right = helper(pre, post, (preEnd - (postEnd - 1 - (index + 1))), preEnd, index + 1, postEnd - 1);  // (postEnd - 1 - (index + 1))即右子树长度

    return root;
}

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

“看我就够了”三种遍历方式构造二叉树的通解 (opens new window)

🌙 15.二叉搜索树转为单链表 (opens new window)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
// 正确解法1
var convertBiNode1 = function(root) {
    let head = new TreeNode(null);
    let pre = head;
    var inOrder = function(root) {
        if(!root) return;
        // 左 - 右 - 根
        inOrder(root.left);
        root.left = null;
        pre.right = root;
        pre = root;
        inOrder(root.right);
    }
    inOrder(root);
    return head.right;
};

// 将inOrder提取出来：
// 错误解法
var convertBiNode = function(root) {
    let head = new TreeNode(null);
    let pre = head;
    inOrder(root, pre);
    return head.right;
};

var inOrder = function(root, pre) {
        if(!root) return;
        // 左 - 根 - 右 
        inOrder(root.left, pre);

        root.left = null;
        pre.right = root;
        pre = root;

        inOrder(root.right, pre);
    }

// 正确解法2
var convertBiNode2 = function(root) {
    let head = new TreeNode(null);
    inOrder(root, head);
    return head.right;
};

var pre;
var inOrder = function(root, head) {
        if(!root) return;
    
    	pre = head;
        // 左 - 根 - 右 
        inOrder(root.left, pre);

        root.left = null;
        pre.right = root;
        pre = root;

        inOrder(root.right, pre);
    }

// 正确解法3
var convertBiNode = function(root) {
    let head = new TreeNode(null);
    inOrder(root, head);
    return head.right;
};

// var pre;
var inOrder = function(root, pre) {
        if(!root) return pre;
        // 左 - 根 - 右 
        pre = inOrder(root.left, pre);

        root.left = null;
        pre.right = root;
        pre = root;

        pre = inOrder(root.right, pre);

        return pre;
    }

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

🌙 16.二叉树转为单链表 (opens new window)

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function(root) {
    let pre = new TreeNode();;

    var preOrder = function(root) {
        if(!root) return;
        let left = root.left;
        let right = root.right;

        root.left = null;
        pre.right = root;
        pre = root;

        preOrder(left);
        preOrder(right);
    }
    
    // 调用
    preOrder(root);
    
    root = pre.right;
};

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

🌙 17.二叉搜索树转为双向链表 (opens new window)

思路：先中序遍历二叉树，在将结果转为循环双向链表

/**
 * // Definition for a Node.
 * function Node(val,left,right) {
 *    this.val = val;
 *    this.left = left;
 *    this.right = right;
 * };
 */
/**
 * @param {Node} root
 * @return {Node}
 */
var treeToDoublyList = function(root) {
    if(!root) return root;
    
    let res = [];

    inOrder(root, res);

    // 方式一：
    // var head = res[0];
    // var tail = res[res.length - 1];
    // tail.right = head;
    // head.left = tail;
    // for(var i=1; i < res.length; i++) {
    //     // 更改left和right指向
    //     head.right = res[i];
    //     res[i].left = head;
    //     head = res[i];
    // }
    
    // 方式二：
    // var pre = null;
    // var head = null;

    // for(var i=0; i < res.length; i++) {
    //    if(pre) {
    //       // 更改left和right指向
    //        pre.right = res[i];
    //        res[i].left = pre;
    //    } else {
    //        head = res[i]
    //    }
    //    pre = res[i];
    //}
    
    // 方式三：
    var pre = res[0];
    var head = res[0];
    
    for(var i=1; i < res.length; i++) {
        // 更改left和right指向
        pre.right = res[i];
        res[i].left = pre;
        
        pre = res[i];
    }
    
    // 循环完毕，pre指向了最后一个节点
    // 处理首尾节点
    pre.right = head;
    head.left = pre;

    return res[0];
};

var inOrder = function(root, res) {
    if(!root) return;
    var left = root.left;
    var right = root.right;
    // 左 - 根 - 右
    inOrder(left, res);
    res.push(root);
    inOrder(right, 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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

改进：在中序遍历的过程中把二叉树转为双向链表，然后再处理首尾链表，转为循环双向链表

/**
 * // Definition for a Node.
 * function Node(val,left,right) {
 *    this.val = val;
 *    this.left = left;
 *    this.right = right;
 * };
 */
/**
 * @param {Node} root
 * @return {Node}
 */
var treeToDoublyList = function(root) {
    if(!root) return root;
    
    let pre = null;
    let head = null;

    var inOrder = function(cur) {
        if(!cur) return;
        
        // 左 - 根 - 右
        inOrder(cur.left);
        
        // 修改为链表
        if(pre) {
            pre.right = cur;
            cur.left = pre;
        } else {
            // 记录第一个节点
            head = cur;
        }
        // 保存当前节点
        pre = cur;

        inOrder(cur.right);
	}
    
    inOrder(root);
    head.left = pre;
    // 此时pre指向了最后一个节点
    pre.right = head;

    return head;
};

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

🌙 18.有序链表转换二叉搜索树 (opens new window)

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {ListNode} head
 * @return {TreeNode}
 */
var sortedListToBST = function(head) {
    // 链表为空
    if(!head) return null;

    // 链表只有一个节点
    if(!head.next) return new TreeNode(head.val);

    // 找到中继节点
    var pre = head; // pre慢slow一步
    // slow每次走一步 fast每次走两步，当fast走到终点时，slow刚好在中途
    var slow = head.next;
    var fast = head.next.next;

    while(fast && fast.next) {
        pre = pre.next;
        slow = slow.next;
        fast = fast.next.next;
    }

    // 此时pre的下一个节点就是中继节点slow，将其打断把链表一分为二
    pre.next = null;

    // 将中继节点作为树根节点
    var root = new TreeNode(slow.val);
    // 左子树开始节点
    var left = head;
    // 右子树开始节点
    var right = slow.next;

    root.left = sortedListToBST(left);
    root.right = sortedListToBST(right);

    return root;
};

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
46
47
48
49
50
51
52
53

🌙 19.搜索树中的二分查找 (opens new window)


/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var searchBST = function(root, val) {
    if (root == null) return null;
    if (root.val === val) return root;
    if (root.val > val) {
        return searchBST(root.left, val);
    } else if (root.val < val) {
        return searchBST(root.right, val);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

🌙 八、动态规划 (opens new window)

🌙 1.编辑距离 (opens new window)

🌙 2.滑动窗口最大值 (opens new window)

🌙 3.滑动窗口中位数 (opens new window)

🌙 4.最长上升子序列 (opens new window)

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    if(!nums || !nums.length) return 0;
    let dp = new Array(nums.length).fill(1);
    
    for(let i=0; i<nums.length; i++) {
        for(let j=i; j>=0; j--) {
            if(nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    
    return Math.max(...dp)
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

🌙 5.剪绳子 (opens new window)

🌙 6.剪绳子 II (opens new window)

🌙 7.有效的字母异位词 (opens new window)

🌙 8.N 皇后 (opens new window)

🌙 9.N皇后 II (opens new window)

🌙 10.买卖股票的最佳时机 (opens new window)

🌙 11.买卖股票的最佳时机 II (opens new window)

🌙 12.买卖股票的最佳时机 III (opens new window)

🌙 13.买卖股票的最佳时机 IV (opens new window)

🌙 14.买卖股票的最佳时机含手续费 (opens new window)

🌙 15.最佳买卖股票时机含冷冻期 (opens new window)

🌙 16.打家劫舍 (opens new window)

🌙 17.打家劫舍 II (opens new window)

🌙 18.打家劫舍 III (opens new window)

🌙 19.岛屿数量 (opens new window)

🌙 20.零钱兑换 (opens new window)


/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
  if (amount === 0) return 0;
  let dp = [];
  for (let i = 0; i <= amount; i++) {
    dp[i] = amount + 1;
  }
  dp[0] = 0;
  for (let i = 0; i <= amount; i++) {
    for (let j = 0; j < coins.length; j++) {
      if (i >= coins[j]) {
        dp[i] = Math.min(dp[i - coins[j]] + 1, dp[i])
      }
    }
  }
  return dp[amount] > amount ? -1 : dp[amount];
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

🌙 21.零钱兑换 II (opens new window)

🌙 22.有效的数独 (opens new window)

🌙 23.路径总和 (opens new window)

🌙 24.路径总和 III (opens new window)

🌙 八、其他

🌙 1.斐波那契数列 (opens new window)

function fibonacci(n) {
    return help(n,1,1)
}

// 尾递归优化
function help(n,a,b) {
    if (n <= 2) {
        return b;
    }
    return help(n - 1, b, a+b);
}

1
2
3
4
5
6
7
8
9
10
11

真正实现尾递归优化，只是改写代码优化还不够，还需要编译器或解释器的支持才行

尾递归优化原理 (opens new window)

leetcode高频题精选 (opens new window)

【LeetCode】代码模板，刷题必会 (opens new window)

🌙 2.字符串加法

function strAdd(a, b) {
    let i = a.toString().trim().length;
    let j = b.toString().trim().length;
    
    let ans = '';
    let carry = 0;
    
    while(i >=0 || j >=0) {
      let sum;
      let x=0, y=0;
      
      if(i>=0) {
          x = +a[i];
          i--;
      }
      
      if(j>=0) {
          y = +b[i];
          j--;
      }
      
      sum = x + y + carry;
      if(sum >= 10) {
          carry = Math.floor(sum / 10);
          sum = sum % 10;
      } else {
          carry = 0;
      }
      
      ans = sum  + ans;
    }
    
    if(carry) {
        ans = carry + ans;
    }
    
    return ans;
}

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

🌙 3.字符串乘法

function strMul(a, b) {
    a = a.toString().trim();
    b = b.toString().trim();
    
    let m = a.length;
    let n = b.length;
    let arr = new Array(m + n).fill(0);
    
    // 从个位开始相乘
    for(let i=m-1; i>=0; i--) {
        for(let j=n-1; j>=0; j--) {
            let mul = a[i] * b[j];
            let p1 = i + j;
            let p2 = i + j + 1;
            let sum = mul + arr[p2];
            arr[p2] = sum % 10;
            arr[p1] += ~~(sum / 10);
        }
    }
    
    // 去除首位多余的0
    let i=0;
    while(i<arr.length && arr[i]===0) {
        i++;
    }
    
    return arr.slice(i).join('') || '0';
}

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

🌙 4.最长回文子串 (opens new window)


/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    if(s.length < 2) return s;
    let ans = '', max = 0;
    
    for(let i=0; i<s.length; i++) {
        let str1 = palindrome(s, i, i);
        let str2 = palindrom(s, i, i+1);
        ans = max < str1.length ? (str1.length < str2.length ? str2 : str1) : ans;
        max = Math.max(max, str1.length, str2.length);
    }
}

function palindrome(s, l, r) {
    while(l >= 0 && r<s.length && s[l]===s[r]) {
        l--;
        r++;
    }
    
    return s.slice(1+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

🌙 5.最长公共前缀 (opens new window)


/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if (strs.length === 0) return "";
    let first = strs[0];
    if (first === "") return "";
    let minLen = Number.MAX_SAFE_INTEGER;
    for (let i = 1; i < strs.length; i++) {
        const len = twoStrLongestCommonPrefix(first, strs[i]);
        minLen = Math.min(len, minLen);
    }
    return first.slice(0, minLen);
};
function twoStrLongestCommonPrefix (s, t) {
    let i = 0, j = 0;
    let cnt = 0;
    while (i < s.length && j < t.length) {
        console.log(s[i], t[j], cnt)
        if (s[i] === t[j])  {
            cnt++;
        } else {
            return cnt;
        }
        i++;
        j++;
    }
    return cnt;
}

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

🌙 6.无重复字符的最长子串 (opens new window)


/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  let window = {};
  let left = 0, right = 0;
  let maxLen = 0, maxStr = '';
  while (right < s.length) {
    let c = s[right];
    right++;
    if (window[c]) window[c]++;
    else window[c] = 1
    while (window[c] > 1) {
      let d = s[left];
      left++;
      window[d]--;
    }
    if (maxLen < right - left) {
      maxLen = right - left;
    }
  }
  return maxLen;
};

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

🌙 7. 最小覆盖子串【滑动窗口】 (opens new window)


/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    let need = {}, window = {};
    // 1.记录需要的字符数
    for (let c of t) {
        if (!need[c]) need[c] = 1;
        else need[c]++;
    }
    // 双指针
    let left = 0, right = 0;
    // 记录需要的数量
    let valid = 0, len = Object.keys(need).length;
    // 记录结果
    let minLen = s.length + 1, minStr = '';
    // right指针先走
    while (right < s.length) {
        const d = s[right];
        right++;
        if (!window[d]) window[d] = 1;
        else window[d]++;
        // 2.记录达标的数量
        if (need[d] && need[d] === window[d]) {
            valid++;
        }
        console.log('left - right', left, right);
        // 3.直到刚好满足需求
        while (valid === len) {
            // 更新结果
            if (right - left < minLen) {
                minLen = right - left;
                minStr = s.slice(left, right);
            }
            console.lo
            // 4.缩小范围
            let c = s[left];
            left++;
            window[c]--;
            if (need[c] && window[c] < need[c]) {
                valid--;
            }
        }
    }
    return minStr;
};

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
46
47
48
49

团灭股票买卖问题

前端Jeek