「每日LeetCode」2020年10月14日

本文最后更新于：2023年3月19日 晚上

Lt1002. 查找常用字符、461. 汉明距离、543. 二叉树的直径

1002. 查找常用字符

给定仅有小写字母组成的字符串数组 A，返回列表中的每个字符串中都显示的全部字符（包括重复字符）组成的列表。例如，如果一个字符在每个字符串中出现 3 次，但不是 4 次，则需要在最终答案中包含该字符 3 次。
你可以按任意顺序返回答案。
示例 1：

1
2
输入：["bella","label","roller"]
输出：["e","l","l"]

示例 2：

1
2
输入：["cool","lock","cook"]
输出：["c","o"]

提示：

  1. 1 <= A.length <= 100
  2. 1 <= A[i].length <= 100
  3. A[i][j] 是小写字母

思路

哈希

相当于每次都是求两个字符串的交集，可以使用哈希表求解。每次循环设置一个新的哈希表，得到一个相同的字符后，将原来的哈希表里对应元素减一直到删除，再添加到新的哈希表中，全部遍历以后就得到了两个字符串的交集。再对每一个字符串都如此操作可以得到所有字符串的交集。

Array 方法 every、filter

将 A[0]设为标准，遍历 A[0]中的每一个字符。使用 every 判断在每一个字符串中都包含该字符，如果都包含，删除该字符，并将该字符加入结果数组中

解答

哈希

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
/**
 * @param {string[]} A
 * @return {string[]}
 */
var commonChars = function (A) {
  let map = new Map();
  A[0].split("").forEach((e) => map.set(e, map.has(e) ? map.get(e) + 1 : 1));

  for (let i = 1; i < A.length; i++) {
    let temp = new Map();
    for (let j = 0; j < A[i].length; j++) {
      if (map.has(A[i][j])) {
        map.get(A[i][j]) === 1
          ? map.delete(A[i][j])
          : map.set(A[i][j], map.get(A[i][j]) - 1);
        temp.set(A[i][j], temp.has(A[i][j]) ? temp.get(A[i][j]) + 1 : 1);
      }
    }
    map = temp;
  }

  return [...map.entries()].reduce(
    (arr, [e, count]) => arr.concat(Array(count).fill(e)),
    []
  );
};

Array 方法 every、filter

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {string[]} A
 * @return {string[]}
 */
var commonChars = function (A) {
  let ans = [],
    word = A[0];
  for (let s of word) {
    if (A.every((m) => m.includes(s))) {
      A = A.map((m) => m.replace(s, ""));
      ans.push(s);
    }
  }
  return ans;
};

461. 汉明距离

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y，计算它们之间的汉明距离。
注意：
0 ≤ x, y < 2.
示例:

1
2
3
4
5
6
输入: x = 1, y = 4
输出: 2
解释:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

上面的箭头指出了对应二进制位不同的位置。

思路

padStart

将 x 和 y 转化为字符串，并在短的那个字符串前补 0。对每一位进行判断是否相等，不相等则计数加一。

位运算

计算 x 和 y 之间的汉明距离，可以先计算 x XOR y，然后统计结果中等于 1 的位数。

先求 x^y，再对结果的 1 计数即为汉明距离，可以使用 x&1 判断最右的一位是否为 1，再使用 x>>1 使得位数向右移动一位，直到 x==0 为止

解答

padStart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number} x
 * @param {number} y
 * @return {number}
 */
var hammingDistance = function (x, y) {
  x = x.toString(2);
  y = y.toString(2);
  length = Math.max(x.length, y.length);
  x = x.padStart(length, "0");
  y = y.padStart(length, "0");
  let count = 0;
  for (let i = 0; i < x.length; i++) {
    if (x[i] ^ y[i]) count++;
  }
  return count;
};

位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number} x
 * @param {number} y
 * @return {number}
 */
var hammingDistance = function (x, y) {
  let ans = 0;
  x ^= y;
  while (x !== 0) {
    if (x & 1) {
      ans++;
    }
    x >>= 1;
  }
  return ans;
};

543. 二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :
给定二叉树

1
2
3
4
5
1
    / \
   2   3
  / \
 4   5

返回 3, 它的长度是路径 [4,2,1,3] 或者  [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。

思路

编写一个计算树深度的函数，遍历树，计算当前节点左右深度之和，更新最大的深度之和即为结果

解答

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
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function (root) {
  if (!root) return 0;
  let res = 0;
  const getDepth = (root) => {
    if (!root) return 0;
    return 1 + Math.max(getDepth(root.left), getDepth(root.right));
  };
  const visit = (root) => {
    if (!root) return;
    res = Math.max(res, getDepth(root.left) + getDepth(root.right));
    visit(root.left);
    visit(root.right);
  };
  visit(root);
  return res;
};