本文最后更新于：2023年3月19日 晚上
Lt257.二叉树的所有路径、Lt283.移动零、Lt392.判断子序列
| Category |
Difficulty |
Likes |
Dislikes |
| algorithms |
Easy (66.05%) |
363 |
- |
Tags
tree | depth-first-search
Companies
apple | facebook | google
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
1
2
3
4
5
6
7
8
| 输入:
1
/ \
2 3
\
5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
|
Discussion | Solution
思路
和之前求是否存在一条路径的和和目标值相同类似，都是深度优先遍历所有根到节点的路径。树的题思路都是用最小规模来看。
解答
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
|
var binaryTreePaths = function (root) {
const res = [];
let tmp = [];
visit(root, res, tmp);
return res;
};
const visit = (root, res, tmp) => {
if (!root) return;
tmp.push(root.val);
if (root && !root.left && !root.right) {
res.push(tmp.join("->"));
}
if (root.left) visit(root.left, res, tmp);
if (root.right) visit(root.right, res, tmp);
tmp.pop();
};
|
1
2
3
4
| Accepted
209/209 cases passed (88 ms)
Your runtime beats 61.62 % of javascript submissions
Your memory usage beats 64.82 % of javascript submissions (39.6 MB)
|
| Category |
Difficulty |
Likes |
Dislikes |
| algorithms |
Easy (62.28%) |
731 |
- |
Tags
array | two-pointers
Companies
bloomberg | facebook
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
1
2
| 输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
|
说明:
- 必须在原数组上操作，不能拷贝额外的数组。
- 尽量减少操作次数。
Discussion | Solution
思路
是 0 则删除放到最后，没有难度，但应该有更好的解法。
双指针
遍历数组，如果 i 指向的不为 0，则将 nums[k]设为 i 指向的值，k++。遍历完后，前面都为有数值的值，将剩下的都设为 0 即可。
解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
var moveZeroes = function (nums) {
for (let i = 0; i < nums.length; i++) {
if (nums[i] === 0) {
nums.push(nums.splice(i, 1));
i--;
}
}
};
|
1
2
3
4
| Accepted
21/21 cases passed (100 ms)
Your runtime beats 28.13 % of javascript submissions
Your memory usage beats 44.37 % of javascript submissions (39.7 MB)
|
双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
var moveZeroes = function (nums) {
let j = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] !== 0) {
nums[j++] = nums[i];
}
}
while (j < nums.length) {
nums[j++] = 0;
}
};
|
1
2
3
4
| Accepted
21/21 cases passed (92 ms)
Your runtime beats 52.73 % of javascript submissions
Your memory usage beats 34.35 % of javascript submissions (39.8 MB)
|
| Category |
Difficulty |
Likes |
Dislikes |
| algorithms |
Easy (50.53%) |
319 |
- |
Tags
binary-search | dynamic-programming | greedy
Companies
Unknown
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
**示例 1:**
**s** = "abc", **t** = "ahbgdc"
返回 true.
**示例 2:**
**s** = "axc", **t** = "ahbgdc"
返回 false.
**后续挑战** **:**
如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10 亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
致谢:
特别感谢** **@pbrother 添加此问题并且创建所有测试用例。
Discussion | Solution
思路
遍历 t
遍历 t，看是否存在 s
遍历 s
使用 indexof 遍历 s
解答
遍历 t
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
var isSubsequence = function (s, t) {
let k = 0;
for (let i = 0; i < t.length && k < s.length; i++) {
if (t[i] === s[k]) k++;
}
return k === s.length;
};
|
1
2
3
4
| Accepted
15/15 cases passed (96 ms)
Your runtime beats 27.14 % of javascript submissions
Your memory usage beats 40.49 % of javascript submissions (37.9 MB)
|
遍历 s
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
var isSubsequence = function (s, t) {
let tmp = -1;
for (let i = 0; i < s.length; i++) {
let index = t.indexOf(s[i], tmp + 1);
if (index === -1) return false;
tmp = index;
}
return true;
};
|
1
2
3
4
| Accepted
15/15 cases passed (80 ms)
Your runtime beats 80.2 % of javascript submissions
Your memory usage beats 69.63 % of javascript submissions (37.7 MB)
|