「每日LeetCode」2020年11月5日

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

Lt78. 子集、回溯算法
Lt1641. 统计字典序元音字符串的数目
Lt1640. 能否连接形成数组

78. 子集

给定一组不含重复元素的整数数组 _nums_，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:

1
2
3
4
5
6
7
8
9
10
11
12
输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

思路

回溯

相当于对数组每一个长度求一次组合，例如求数组内 0、1、2…个元素的组合。在组合的基础上，在外层再加上一个循环即可。

改进

其实求组合的过程的回溯中，其实本来就包含了求数组内 0、1、2…个元素的组合的过程。每次递归时直接添加 temp 种的值到结果数组中即可。

解答

回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function (nums) {
  const res = [];
  const combine = (x, n, temp) => {
    if (temp.length === n) {
      res.push(temp.slice());
      return;
    }
    for (let i = x; i < nums.length; i++) {
      temp.push(nums[i]);
      combine(i + 1, n, temp);
      temp.pop();
    }
  };
  for (let i = 0; i <= nums.length; i++) combine(0, i, []);
  return res;
};

改进

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function (nums) {
  const res = [];
  const combine = (x, temp) => {
    res.push(temp.slice());
    if (temp.length === nums.length) return;
    for (let i = x; i < nums.length; i++) {
      temp.push(nums[i]);
      combine(i + 1, temp);
      temp.pop();
    }
  };
  combine(0, []);
  return res;
};

1641. 统计字典序元音字符串的数目

给你一个整数 n，请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。
字符串 s 按 字典序排列 需要满足：对于所有有效的 i，s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。
示例 1：

1
2
3
输入：n = 1
输出：5
解释：仅由元音组成的 5 个字典序字符串为 ["a","e","i","o","u"]

示例 2：

1
2
3
4
5
输入：n = 2
输出：15
解释：仅由元音组成的 15 个字典序字符串为
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]
注意，"ea" 不是符合题意的字符串，因为 'e' 在字母表中的位置比 'a' 靠后

示例 3：

1
2
输入：n = 33
输出：66045

思考

常规回溯法，只需要计数量，所以只需要常数空间即可，注意组合字符串可以是本身，所以每次递归传入的 x 不需要加一。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number} n
 * @return {number}
 */
var countVowelStrings = function (n) {
  const map = ["a", "i", "u", "e", "o"];
  let res = 0;
  const combine = (x, temp) => {
    if (temp === n) {
      res += 1;
      return;
    }
    for (let i = x; i < map.length; i++) {
      temp++;
      combine(i, temp);
      temp--;
    }
  };
  combine(0, []);
  return res;
};

1640. 能否连接形成数组

给你一个整数数组 arr ，数组中的每个整数 互不相同 。另有一个由整数数组构成的数组 pieces，其中的整数也 互不相同 。请你以 任意顺序 连接 pieces 中的数组以形成 arr 。但是，不允许 对每个数组 pieces[i] 中的整数重新排序。
如果可以连接_ _pieces 中的数组形成 arr ，返回 true ；否则，返回 false 。
 示例 1：

1
2
输入：arr = [85], pieces = [[85]]
输出：true

示例 2：

1
2
3
输入：arr = [15,88], pieces = [[88],[15]]
输出：true
解释：依次连接 [15] 和 [88]

示例 3：

1
2
3
输入：arr = [49,18,16], pieces = [[16,18,49]]
输出：false
解释：即便数字相符，也不能重新排列 pieces[0]

示例 4：

1
2
3
输入：arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
输出：true
解释：依次连接 [91]、[4,64] 和 [78]

示例 5：

1
2
输入：arr = [1,3,5,7], pieces = [[2,4,6,8]]
输出：false

提示：

  • 1 <= pieces.length <= arr.length <= 100
  • sum(pieces[i].length) == arr.length
  • 1 <= pieces[i].length <= arr.length
  • 1 <= arr[i], pieces[i][j] <= 100
  • arr 中的整数 互不相同
  • pieces 中的整数 互不相同（也就是说，如果将 pieces 扁平化成一维数组，数组中的所有整数互不相同）

思路

先生成一个只由第一个元素组成的数组。当元素组长度大于 0 时执行以下步骤：

  1. 取第一个数为当前元素，判断只由第一个元素组成的数组里是否包含该数，不包含返回 false
  2. 截取对应 pieces 内的数组，取得长度，根据长度在元素组中截取相应长度的数组，再删除第一个元素组成的数组对应的元素，即有三个数组的内容需要截取变化。比较截取的原数组和截取的 pieces 数组是否完全相同，不是的话返回 false。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number[]} arr
 * @param {number[][]} pieces
 * @return {boolean}
 */
var canFormArray = function (arr, pieces) {
  const firstNumArr = pieces.map((e) => e[0]);
  while (arr.length > 0) {
    const num = arr[0];
    if (!firstNumArr.includes(num)) return false;
    const pIndex = firstNumArr.indexOf(num);
    const pieceLen = pieces[pIndex].length;
    const arrTemp = arr.splice(0, pieceLen);
    firstNumArr.splice(pIndex, 1);
    const pieceTemp = pieces.splice(pIndex, 1)[0];
    if (
      arrTemp.length === pieceTemp.length &&
      !arrTemp.every((num, index2) => num === pieceTemp[index2])
    )
      return false;
  }
  return true;
};