124. Binary Tree Maximum Path Sum

原题：124. Binary Tree Maximum Path Sum

source code

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
// Runtime: 108 ms, faster than 13.49% of JavaScript online submissions for Binary Tree Maximum Path Sum.
// Memory Usage: 45.1 MB, less than 15.23% of JavaScript online submissions for Binary Tree Maximum Path Sum.
var maxPathSum = function (root) {
  if (!root) {
    return 0;
  }
  let sum = -Infinity;

  //这道题最重要是理解helper的作用，这里helper(root)返回以root为路径端点（其后代节点构造成路径）的最大和
  const helper = function (root) {
    if (!root) {
      return 0;
    }
    const left = helper(root.left);
    const right = helper(root.right);
    sum = Math.max(
      left + root.val,
      root.val + right,
      left + root.val + right,
      root.val,
      sum
    );
    return Math.max(left, right, 0) + root.val;
  };

  helper(root);
  return sum;
};

test cases

1
2
3
4
5
6
7
test("test1", () => {
  expect(maxPathSum(makeTree([1, 2, 3]))).toEqual(6);
});

test("test2", () => {
  expect(maxPathSum(makeTree([-10, 9, 20, null, null, 15, 7]))).toEqual(42);
});

优化

1
2
3
4
5
6
7
8
9
10
//helper可以进一步优化
const helper = function (root) {
  if (!root) {
    return 0;
  }
  const left = Math.max(helper(root.left), 0); //如果helper(root.left)是负数，那么其实完全可以舍弃左边的节点，直接返回root.val
  const right = Math.max(helper(root.right), 0);
  sum = Math.max(left + root.val + right, sum);
  return Math.max(left, right) + root.val;
};

展开全文 >>

227. Basic Calculator II

原题：227. Basic Calculator II

source code

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
// Runtime: 128 ms, faster than 13.03% of JavaScript online submissions for Basic Calculator II.
// Memory Usage: 55.8 MB, less than 5.44% of JavaScript online submissions for Basic Calculator II.
var calculate = function (s) {
  const chs = s
    .replace(/\s/g, "")
    .replace(/([^\d])/g, "&$1&") //这里有点投机取巧了
    .split("&");
  const queue = [];
  for (let i = 0; i < chs.length; i++) {
    //注意这里不能用while(chs.length) {ch.shift()}，当case很大的时候数组操作耗时会超时
    const ch = chs[i];
    if (/\d/.test(ch)) {
      queue.push(parseInt(ch));
    } else {
      const b = parseInt(chs[++i]);
      if (ch === "+") {
        queue.push(b);
      } else if (ch === "-") {
        queue.push(-b);
      } else {
        const a = parseInt(queue.pop());
        queue.push(ch === "*" ? a * b : ~~(a / b));
      }
    }
  }

  return queue.reduce((a, b) => a + b, 0); //because the given expression is always valid
};

test cases

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
test("test1", () => {
  expect(calculate("3+2*2")).toEqual(7);
});

test("test2", () => {
  expect(calculate(" 3/2 ")).toEqual(1);
});

test("test3", () => {
  expect(calculate(" 3+5 / 2 ")).toEqual(5);
});

test("test4", () => {
  expect(calculate("12+37*5")).toEqual(197);
});

test("test5", () => {
  expect(calculate("1+1+1")).toEqual(3);
});

//这里还有个超大的case，一不注意就容易超时

其它解法：

展开全文 >>

454. 4Sum II

原题：454. 4Sum II

思路

这道题用dfs会超时，最终用分治 + 2-Sum的思想 解出。

source code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Runtime: 736 ms, faster than 9.18% of JavaScript online submissions for 4Sum II.
// Memory Usage: 101.7 MB, less than 9.94% of JavaScript online submissions for 4Sum II.
var fourSumCount = function (A, B, C, D) {
  const helper = function (arr1, arr2) {
    const map = {};
    for (let num1 of arr1) {
      for (let num2 of arr2) {
        const sum = num1 + num2;
        map[sum] = (map[sum] || 0) + 1;
      }
    }

    return map;
  };

  const map1 = helper(A, B);
  const map2 = helper(C, D);
  let count = 0;
  for (let num1 in map1) {
    count += map1[num1] * (map2[-num1] || 0);
  }

  return count;
};

test cases

1
2
3
4
5
6
7
8
9
test("test1", () => {
  expect(fourSumCount([1, 2], [-2, -1], [-1, 2], [0, 2])).toEqual(2);
});

test("test2", () => {
  expect(fourSumCount([0, 0], [0, 0], [0, 0], [0, 0])).toEqual(16);
});

//这里还有一个超大的case，不赘述了。。

展开全文 >>

斐波那契求解效率对比

方法1：递归（不剪枝）

时间复杂度：O(2^n)

方法2：递推

时间复杂度：O(n)

方法3：通项公式/矩阵相乘

时间复杂度：O(logn)

重点来说下这种解法，下面是推导过程：

推导过程

因此最终问题简化成求解 n-1个矩阵相乘 。类似pow(x, n)，用分治法求解时间复杂度为log(n)。

关于矩阵乘法，阮一峰老师的这篇文章讲得很清楚：理解矩阵乘法。

展开全文 >>

并查集的实现

用js实现一个并查集

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
class UFS {
  constructor() {
    this.set = [];
  }

  //初始化节点
  makeSet(x) {
    this.set[x] = {
      parent: x,
      rank: 0,
    };
  }

  //找出x的根节点
  find(x) {
    const node = this.set[x];
    if (!node) {
      return -1; //error
    } else if (node.parent == x) {
      return x;
    } else {
      return this.find(node.parent);
    }
  }

  //判断x和y是否在同一个集合中
  connected(x, y) {
    return this.find(x) === this.find(y);
  }

  //合并两个集合
  union(x, y) {
    if (this.connected(x, y)) {
      return true;
    }
    const xRoot = this.set[this.find(x)];
    const yRoot = this.set[this.find(y)];
    if (!xRoot || !yRoot) {
      //error
      return false;
    }

    if (xRoot.rank < yRoot.rank) {
      //往rank大的元素挂载，这样不增加rank
      xRoot.parent = y;
    } else if (xRoot.rank > yRoot.rank) {
      yRoot.parent = x;
    } else {
      xRoot.parent = y;
      yRoot.rank += 1;
    }

    return true;
  }
}

展开全文 >>

200. Number of Islands

原题：200. Number of Islands

方法一

思路：路径染色

时间复杂度：O(n^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
31
32
// Runtime: 80 ms, faster than 29.80% of JavaScript online submissions for Number of Islands.
// Memory Usage: 37.2 MB, less than 100.00% of JavaScript online submissions for Number of Islands.
var numIslands = function (grid) {
  if (!grid || !grid.length) {
    return 0;
  }
  const dx = [-1, 0, 1, 0]; //四连通图，注意这里不能把上、左方向省略，原因请看test case3
  const dy = [0, 1, 0, -1];
  const m = grid.length;
  const n = grid[0].length;
  let count = 0;
  const helper = function (i, j) {
    //这里用BFS（队列）或者DFS（递归）做都可以
    if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] != "1") {
      return;
    }
    grid[i][j] = 0; //染色
    for (let k = 0; k < 4; k++) {
      helper(i + dx[k], j + dy[k]);
    }
  };
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === "1") {
        helper(i, j);
        count++;
      }
    }
  }

  return count;
};

方法二

思路：并查集

时间复杂度：O(n^2)

UFS的代码可参考 并查集的实现

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
// Runtime: 180 ms, faster than 5.23% of JavaScript online submissions for Number of Islands.
// Memory Usage: 40.1 MB, less than 32.26% of JavaScript online submissions for Number of Islands.
var numIslands = function (grid) {
  if (!grid || !grid.length) {
    return 0;
  }
  const ufs = new UFS();
  const m = grid.length;
  const n = grid[0].length;
  const transform = function (i, j) {
    //展平二维数组
    return i * m + j;
  };

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === "1") {
        ufs.makeSet(transform(i, j));
      }
    }
  }

  const dx = [-1, 0, 1, 0]; //四连通图，注意这里不能把上、左方向省略，原因请看test case3
  const dy = [0, 1, 0, -1];
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === "1") {
        for (let k = 0; k < 4; k++) {
          const di = i + dx[k];
          const dj = j + dy[k];
          if (di >= 0 && dj >= 0 && di < m && dj < n && grid[di][dj] === "1") {
            ufs.union(transform(i, j), transform(di, dj));
          }
        }
      }
    }
  }

  const set = new Set();
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === "1") {
        set.add(ufs.find(transform(i, j)));
      }
    }
  }

  return set.size;
};

test("test1", () => {
  expect(
    numIslands([
      ["1", "1", "1", "1", "0"],
      ["1", "1", "0", "1", "0"],
      ["1", "1", "0", "0", "0"],
      ["0", "0", "0", "0", "0"],
    ])
  ).toEqual(1);
});

test("test2", () => {
  expect(
    numIslands([
      ["1", "1", "0", "0", "0"],
      ["1", "1", "0", "0", "0"],
      ["0", "0", "1", "0", "0"],
      ["0", "0", "0", "1", "1"],
    ])
  ).toEqual(3);
});

test("test2", () => {
  expect(
    numIslands([
      ["1", "1", "1"],
      ["0", "1", "0"],
      ["1", "1", "1"],
    ])
  ).toEqual(1);
});

test cases

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
test("test1", () => {
  expect(
    numIslands([
      ["1", "1", "1", "1", "0"],
      ["1", "1", "0", "1", "0"],
      ["1", "1", "0", "0", "0"],
      ["0", "0", "0", "0", "0"],
    ])
  ).toEqual(1);
});

test("test2", () => {
  expect(
    numIslands([
      ["1", "1", "0", "0", "0"],
      ["1", "1", "0", "0", "0"],
      ["0", "0", "1", "0", "0"],
      ["0", "0", "0", "1", "1"],
    ])
  ).toEqual(3);
});

test("test2", () => {
  expect(
    numIslands([
      ["1", "1", "1"],
      ["0", "1", "0"],
      ["1", "1", "1"],
    ])
  ).toEqual(1);
});

总结

路径染色更高效，并查集更符合直觉。

展开全文 >>

72. Edit Distance

原题：72. Edit Distance

source code

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
// Runtime: 100 ms, faster than 57.51% of JavaScript online submissions for Edit Distance.
// Memory Usage: 40.7 MB, less than 50.00% of JavaScript online submissions for Edit Distance.
var minDistance = function (word1, word2) {
  //注意这里创建的长度是(word1.length+1)*(word2.length+1)，因为word1、word2可能是空串，因此i/j实际表示的是子串的长度（从index 0开始）
  //因此dp[i][j]表示word1[i-1]演变到word2[j-1]最少需要的操作数
  const dp = new Array(word1.length + 1)
    .fill(0)
    .map((v) => new Array(word2.length + 1).fill(0));
  for (let i = 0; i <= word1.length; i++) {
    //从word1[i]演变到word2[0]，只能删除i个字符
    dp[i][0] = i;
  }

  for (let j = 0; j <= word2.length; j++) {
    //从word1[0]演变成word2[j]，只能新增j个字符
    dp[0][j] = j;
  }

  for (let i = 1; i <= word1.length; i++) {
    for (let j = 1; j <= word2.length; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        //三种操作：
        //insert: dp[i][j - 1]; 因为word1[i]只能演变成word2[j-1]，因此如果要演变成word2[j]，需要插入一个字符（word2中索引为j-1的字符）
        //remove: dp[i - 1][j]; 因为word1[i-1]已经成演变成[j]，因此需要移除word1索引为i-1的字符
        //replace: dp[i - 1][j - 1];
        dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1;
      }
    }
  }

  return dp[word1.length][word2.length];
};

test cases

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
test("test1", () => {
  expect(minDistance("horse", "ros")).toEqual(3);
});
// horse -> rorse (replace 'h' with 'r')
// rorse -> rose (remove 'r')
// rose -> ros (remove 'e')

test("test2", () => {
  expect(minDistance("intention", "execution")).toEqual(5);
});
// intention -> inention (remove 't')
// inention -> enention (replace 'i' with 'e')
// enention -> exention (replace 'n' with 'x')
// exention -> exection (replace 'n' with 'c')
// exection -> execution (insert 'u')

test("test3", () => {
  expect(minDistance("a", "a")).toEqual(0);
});

test("test4", () => {
  expect(minDistance("", "a")).toEqual(1);
});

test("test5", () => {
  expect(minDistance("a", "")).toEqual(1);
});

展开全文 >>

形如if(0<100<0)怎么执行

面试时候遇到的一道题，因为不熟悉编译原理，被虐的体无完肤。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//写出下面的打印结果
if (0 < 100 < 0) {
  console.log("a");
} else {
  console.log("b");
}

if (0 < 100 < 0 + 4) {
  console.log("c");
} else {
  console.log("d");
}

// output:
// a
// c

解析

第一个if语句中从左往右执行，0<100 为 true，true<0 getPrimitive后变成 1<0，因此第一个结果为 false。

第二if语句中，+优先级大于<，因为变成 0<100<4， 0<100 为 true，true<4 getPrimitive后变成 1<4，因此第一个结果为 true。

javascript运算符笔记

运算符 描述
. [] () 字段访问、数组下标、函数调用以及表达式分组
++ – - ~ ! delete new typeof void 一元运算符、返回数据类型、对象创建、未定义值
* / % 乘法、除法、取模
+ - + 加法、减法、字符串连接
<< >> >>> 移位
< <= > >= instanceof 小于、小于等于、大于、大于等于、instanceof
== != === !== 等于、不等于、严格相等、非严格相等
& 按位与
^ 按位异或
| 按位或
&& 逻辑与
|| 逻辑或
?: 条件
= oP= 赋值、运算赋值
, 多重求值

展开全文 >>

322. Coin Change

原题：322. Coin Change

source code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Runtime: 168 ms, faster than 29.19% of JavaScript online submissions for Coin Change.
// Memory Usage: 43.1 MB, less than 9.09% of JavaScript online submissions for Coin Change.
var coinChange = function (coins, amount) {
  const dp = [0]; //dp[i]标识组成i的最小硬币数
  for (let i = 1; i <= amount; i++) {
    let min = Infinity;
    for (let coin of coins) {
      if (i < coin || dp[i - coin] < 0) {
        continue;
      }
      min = Math.min(min, dp[i - coin]);
    }
    if (min === Infinity) {
      dp[i] = -1;
    } else {
      dp[i] = min + 1;
    }
  }

  return dp[amount];
};

更简洁的写法（Recommended）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Runtime: 112 ms, faster than 55.89% of JavaScript online submissions for Coin Change.
// Memory Usage: 40.9 MB, less than 9.09% of JavaScript online submissions for Coin Change.
var coinChange = function (coins, amount) {
  const dp = new Array(amount + 1).fill(amount + 1); //dp[i]标识组成i的最小硬币数
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (let coin of coins) {
      if (i >= coin) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }

  return dp[amount] > amount ? -1 : dp[amount];
};

test cases

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
test("test1", () => {
  expect(coinChange([1], 0)).toEqual(0);
});

test("test2", () => {
  expect(coinChange([1, 2, 5], 11)).toEqual(3);
});

test("test3", () => {
  expect(coinChange([2], 3)).toEqual(-1);
});

test("test4", () => {
  expect(coinChange([1], 100)).toEqual(100);
});

test("test5", () => {
  expect(coinChange([100], 1)).toEqual(-1);
});

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

不思进取的前端开发攻城狮。<br>梦想是躺着也能拯救世界。