「每日LeetCode」2020年9月12日

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

Lt557.反转字符串中的单词 III、Lt448.找到所有数组中消失的数字、Lt572.另一个树的子树

557.反转字符串中的单词 III

Category Difficulty Likes Dislikes
algorithms Easy (73.39%) 241 -

Tags
string
Companies
zappos
给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例：

1
2
输入："Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"

****提示：****

  • 在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。

Discussion | Solution

思路

取出每个字符为数组，再遍历个数组，将每个元素反转后再拼接回字符串

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
 * @lc app=leetcode.cn id=557 lang=javascript
 *
 * [557] 反转字符串中的单词 III
 */

// @lc code=start
/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function (s) {
  return s
    .split(" ")
    .map((e) => e.split("").reverse().join(""))
    .join(" ");
};
// @lc code=end
1
2
3
4
Accepted
30/30 cases passed (92 ms)
Your runtime beats 72.77 % of javascript submissions
Your memory usage beats 90.39 % of javascript submissions (44.2 MB)

448.找到所有数组中消失的数字

Category Difficulty Likes Dislikes
algorithms Easy (60.04%) 457 -

Tags
array
Companies
google
给定一个范围在   1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)*的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
*示例:**

1
2
3
4
输入:
[4,3,2,7,8,2,3,1]
输出:
[5,6]

Discussion | Solution

思路

set 去重，再算出长度和缺少的长度，再循环根据下标添加缺少数据结果数组，遍历完后看看 dupLength 是否还大于 0，说明还有没补上的数据，补上后就是结果。
自己的思路求解冗余、占用空间大，还多了排序的步骤，通过集合的 has 方法可以解决，具体看改进算法。

解答

最初

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
/*
 * @lc app=leetcode.cn id=448 lang=javascript
 *
 * [448] 找到所有数组中消失的数字
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDisappearedNumbers = function (nums) {
  const oriLength = nums.length;
  nums = [...new Set(nums)].sort((a, b) => Number(a) - Number(b));
  let dupLength = oriLength - nums.length;
  const res = [];
  for (let i = 0; i < nums[nums.length - 1] && dupLength > 0; i++) {
    if (nums[i] !== i + 1) {
      nums.splice(i, 0, i + 1);
      res.push(i + 1);
      i--;
      dupLength--;
    }
  }
  for (let i = 0; i < dupLength; i++) {
    nums.push(nums[nums.length - 1] + 1);
    res.push(nums[nums.length - 1]);
  }
  return res;
};
// @lc code=end
1
2
3
4
Accepted
34/34 cases passed (344 ms)
Your runtime beats 30.62 % of javascript submissions
Your memory usage beats 17.5 % of javascript submissions (49.5 MB)

改进

1
2
3
4
5
6
7
8
9
10
var findDisappearedNumbers = function (nums) {
  const numsSet = new Set(nums);
  const disappearedNums = [];
  for (let i = 1; i <= nums.length; i++) {
    if (!numsSet.has(i)) {
      disappearedNums.push(i);
    }
  }
  return disappearedNums;
};
1
2
3
4
Accepted
34/34 cases passed (140 ms)
Your runtime beats 62.63 % of javascript submissions
Your memory usage beats 22.5 % of javascript submissions (49.2 MB)

572.另一个树的子树

Category Difficulty Likes Dislikes
algorithms Easy (47.05%) 351 -

Tags
tree
Companies
ebay | facebook | google
给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
示例 1:
给定的树 s:

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

给定的树 t：

1
2
3
4
  / \
 1   2

返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。
示例 2:
给定的树 s：

1
2
3
4
5
6
7
3
    / \
   4   5
  / \
 1   2
    /
   0

给定的树 t：

1
2
3
4
  / \
 1   2

返回 false。

Discussion | Solution

思路

将问题拆开，相当于，遍历一颗树，判断当前节点是否与对应的节点完全一致，参考 100.相同的树。

解答

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
/*
 * @lc app=leetcode.cn id=572 lang=javascript
 *
 * [572] 另一个树的子树
 */

// @lc code=start
/**
 * 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} s
 * @param {TreeNode} t
 * @return {boolean}
 */
var isSubtree = function (s, t) {
  if (!s) return false;
  if (isEqual(s, t)) return true;
  return isSubtree(s.left, t) || isSubtree(s.right, t);
};

const isEqual = (s, t) => {
  if (!s && !t) return true;
  if (!s || !t) return false;
  return (
    s.val === t.val && isEqual(s.left, t.left) && isEqual(s.right, t.right)
  );
};
// @lc code=end
1
2
3
4
Accepted
183/183 cases passed (112 ms)
Your runtime beats 59 % of javascript submissions
Your memory usage beats 15.33 % of javascript submissions (44.8 MB)