又钓了一天鱼...

忘记做防晒了，胳膊肘子都晒红了...

1367. Linked List in Binary Tree

Analysis

判断链表序列是否存在于树的路径中。

Code

先用官方题解的思路水过去了...

class 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：

class 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：

class 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

class 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 curr;
            int add = 0;
            for(int j = len2 - 1; j > i; j--) {
                curr.push_back(0);
            }
            int y = num2.at(i) - '0';
            for(int j = len1 - 1; j >= 0; j--) {
                int x = num1.at(j) - '0';
                int product = x * y + add;
                curr.push_back(product % 10);
                add = product / 10;
            }
            while(add != 0) {
                curr.push_back(add % 10);
                add /= 10;
            }
            reverse(curr.begin(), curr.end());
            for(auto &c: curr) {
                c += '0';
            }
            ans = addStrings(ans, curr);
        }
        return ans;
    }
    string addStrings(string &num1, string &num2) {
        int i = num1.size() - 1, j = num2.size() - 1, add = 0;
        string ans;
        while (i >= 0 || j >= 0 || add != 0) {
            int x = i >= 0 ? num1.at(i) - '0' : 0;
            int y = j >= 0 ? num2.at(j) - '0' : 0;
            int result = x + y + add;
            ans.push_back(result % 10);
            add = result / 10;
            i--;
            j--;
        }
        reverse(ans.begin(), ans.end());
        for (auto &c: ans) {
            c += '0';
        }
        return ans;
    }
};

字符串相加的函数是这个题：415. Add Strings。
做完 415 之后，又把这个题重新做了一下，思路上没有什么变化，只是按照自己的风格写了下：

class 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。

class 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 补了下第一个题。