1367. Linked List in Binary Tree
Analysis
判断链表序列是否存在于树的路径中。
Code
先用官方题解的思路水过去了...1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
bool dfs(TreeNode *rt, ListNode *head) {
if(head == nullptr) return true;
if(rt == nullptr) return false;
if(rt->val != head->val) return false;
return dfs(rt->left, head->next) || dfs(rt->right, head->next);
}
public:
bool isSubPath(ListNode* head, TreeNode* root) {
if(root == nullptr) return false;
return dfs(root, head) || isSubPath(head, root->left) || isSubPath(head, root->right);
}
};
em，现在再来把这个题做一下。
第一眼看到这个题目的时候，想到的做法其实是先求出所有叶结点的路径，然后再判断链表序列是不是路径的子串即可。可惜，忘记路径怎么求的了。所以，又重新做了一下另外一个题：257. Binary Tree Paths。做完这个题之后，就可以再按照这个思路来做了。
PS：因为路径可以通过 bfs 和 dfs 来求，所以也写出类似的思路吧。
dfs：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
28class Solution {
public:
vector<string> paths;
void dfs(TreeNode *root, string path) {
if(!root) return;
if(!root->left && !root->right) {
path += to_string(root->val);
paths.push_back(path);
return;
}
path += to_string(root->val);
dfs(root->left, path);
dfs(root->right, path);
}
bool isSubPath(ListNode* head, TreeNode* root) {
string listseq;
while(head) {
listseq += to_string(head->val);
head = head->next;
}
dfs(root, "");
int size = paths.size();
for(int i = 0; i < size; i++) {
if(paths[i].find(listseq) != string::npos) return true;
}
return false;
}
};
虽然可以通过，但是时间消耗跟内存消耗实在是惨不忍睹了...
bfs：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
31class Solution {
public:
bool isSubPath(ListNode* head, TreeNode* root) {
string listseq;
while(head) {
listseq += to_string(head->val);
head = head->next;
}
queue<TreeNode*> q;
queue<string> path;
q.push(root);
path.push(to_string(root->val));
while(!q.empty()) {
TreeNode *node = q.front(); q.pop();
string tmp = path.front(); path.pop();
if(!node->left && !node->right) tmp += to_string(node->val);
if(tmp.length() >= listseq.length()) {
if(tmp.find(listseq) != string::npos) return true;
}
if(node->left) {
q.push(node->left);
path.push(tmp + to_string(node->left->val));
}
if(node->right) {
q.push(node->right);
path.push(tmp + to_string(node->right->val));
}
}
return false;
}
};
用 bfs 消耗的时间会比上面的 dfs 要少（尽管依然惨不忍睹），因为使用 bfs 并不是一定要求出所有的路径，只需要判断当前得到的树的结点序列是否包含了链表序列即可。
现在回头来想一下官方题解中用到的方法，实际是就是 dfs 求结点路径的同时遍历链表，这样时间消耗才会降低。
43. Multiply Strings
Analysis
大数乘法，按照列算式做乘法的规则，算出每一位与另外一个数的积，然后依次加起来就可以得到最后结果了。
做这个题的同时算是把大数加法也复习了一下。
Code
method 1
1 | class Solution { |
字符串相加的函数是这个题：415. Add Strings。
做完 415 之后，又把这个题重新做了一下，思路上没有什么变化，只是按照自己的风格写了下：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
47class Solution {
public:
string multiply(string num1, string num2) {
if(num1 == "0" || num2 == "0") return "0";
string ans = "0";
int len1 = num1.length(), len2 = num2.length();
for(int i = len2 - 1; i >= 0; i--) {
string tmp;
int number = num2[i] - '0', carry = 0;
for(int j = len2 - 1; j > i; j--) {
tmp.push_back('0');
}
for(int j = len1 - 1; j >= 0; j--) {
int res = number * (num1[j] - '0') + carry;
if(res > 9) {
carry = res / 10;
res %= 10;
} else carry = 0;
tmp.push_back(res + '0');
}
while(carry) {
tmp.push_back(carry % 10 + '0');
carry /= 10;
}
reverse(tmp.begin(), tmp.end());
ans = addStrings(ans, tmp);
}
return ans;
}
string addStrings(string num1, string num2) {
string ans;
int len1 = num1.length(), len2 = num2.length(), carry = 0;
for(int i = len1 - 1, j = len2 - 1; i >= 0 || j >= 0; i--, j--) {
int sum = carry;
sum += i >= 0 ? num1[i] - '0' : 0;
sum += j >= 0 ? num2[j] - '0' : 0;
if(sum >= 10) {
carry = 1;
sum -= 10;
} else carry = 0;
ans.push_back(sum + '0');
}
if(carry) ans.push_back(carry + '0');
reverse(ans.begin(), ans.end());
return ans;
}
};
按照前面提到的，这种方法本质上是在做加法。
method 2
看了一下官方解法的第二种方法，本质上是先转换为数组，然后进行乘法运算。具体的计算过程其实与做加法是差不多的，只是在处理每一位与另一个数的每一位相乘的结果时，做了一点优化。
按照乘法的计算规则，每次运算得到的结果在最后结果的哪一位（十、百、千位等）上是可以确定，所以直接累加起来就好了，而且这个数字肯定是不大于 100 的，但可能是 2 位数或 1 位数。
然后再统一处理进位，就会比较方便。
最后就是把每一位数字转换为字符了。
还有一点要注意的是，一个 m 位数和一个 n 位数，二者的结果一定是一个 m + n - 1 位数或 m + n 位数，也就是说结果的长度最多不超过 m + n。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution {
public:
string multiply(string num1, string num2) {
if(num1 == "0" || num2 == "0") return "0";
int len1 = num1.length(), len2 = num2.length();
vector<int> ansarr(len1 + len2);
for(int i = len1 - 1; i >= 0; i--) {
int x = num1[i] - '0';
for(int j = len2 - 1; j >= 0; j--) {
int y = num2[j] - '0';
ansarr[i + j + 1] += x * y;
}
}
for(int i = len1 + len2 - 1; i > 0; i--) {
ansarr[i - 1] += ansarr[i] / 10;
ansarr[i] %= 10;
}
int index = ansarr[0] == 0 ? 1 : 0;
string ans;
while(index < len1 + len2) {
ans.push_back(ansarr[index++] + '0');
}
return ans;
}
};
Summary
今天的两个题都是水过去的😑，明天还有点事，早点睡了，后面再补吧...
2022-5-5 23:50 补了下第二个题。
2022-5-6 21:04 补了下第一个题。
