算法

每日leetcode-124

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:

输入: [1,2,3]

   1
  / \
 2   3

输出: 6
示例 2:

输入: [-10,9,20,null,null,15,7]

  -10
   /
  9  20
    /  
   15   7

输出: 42

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答

有一些因为节点可能是负数导致的坑，在注释里面也写了。

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int ans = 0;

    int checkPathMax(TreeNode* root) {
        int leftPathMax = 0, rightPathMax = 0;
        if (root->left) {
            leftPathMax = max(0, checkPathMax(root->left));  // 如果从下面走更小的话就别走下面了呗……
        }
        if (root->right) {
            rightPathMax = max(0, checkPathMax(root->right));
        }
        ans = max(ans, leftPathMax + root->val + rightPathMax);
        return max(leftPathMax, rightPathMax) + root->val;
    }

    int maxPathSum(TreeNode* root) {
        // 对于每个节点：
        // 1. 计算当前左侧的路径和
        // 2. 计算右侧的路径和
        // 刚开始需要初始化一下
        ans = root->val;  // 注意这里应该不是0，因为让节点从根节点到根节点，所以初始化为root->val
        checkPathMax(root);
        return ans;
    }
};

对应的两个坑的样例：

  • [-3]，应该是-3
  • [1,-2,3]，应该是4
使用—软件—Git

commit之后修改作者信息

来自https://www.jianshu.com/p/1a5c0228efb0

修改git配置

可以修改之后再次commit时候的信息：

1
2
git config user.email "邮箱"
git config user.name "名字"

修改之前已经commit的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
git filter-branch --env-filter '

OLD_EMAIL="旧的邮箱
CORRECT_NAME="正确的名字"
CORRECT_EMAIL="正确的邮箱"

if [ "$GIT_COMMITTER_EMAIL" = "$OLD_EMAIL" ]
then
    export GIT_COMMITTER_NAME="$CORRECT_NAME"
    export GIT_COMMITTER_EMAIL="$CORRECT_EMAIL"
fi
if [ "$GIT_AUTHOR_EMAIL" = "$OLD_EMAIL" ]
then
    export GIT_AUTHOR_NAME="$CORRECT_NAME"
    export GIT_AUTHOR_EMAIL="$CORRECT_EMAIL"
fi
' --tag-name-filter cat -- --branches --tags

之后git push -f就行

算法

每日leetcode-123

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
  随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。  
  注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。  
  因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答

相当于是把整个时间切成两部分，分别可以计算出来这两部分的最大收益。

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
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        if (len == 0) {
            return 0;
        }
        vector<int> got, got_reverse;
        got.push_back(0);
        got_reverse.push_back(0);
        int now_min = prices[0];
        int reverse_now_max = prices[len - 1];
        for (int i = 1; i < len; i++) {
            got.push_back(max(got[i - 1], prices[i] - now_min));
            now_min = min(prices[i], now_min);
            got_reverse.push_back(max(got_reverse[i - 1], reverse_now_max - prices[len - 1 - i]));
            reverse_now_max = max(prices[len - 1 - i], reverse_now_max);
        }
        int ans = 0;
        for (int i = 0; i < len; i++) {
            ans = max(got[i] + got_reverse[len - 1 - i], ans);
        }
        return ans;
    }
};

这里的got和got_reverse分别是从前面开始的数组和从后面开始的数组，长度分别为下标+1。

最后计算的时候，ans = max(got[i] + got_reverse[len - 1 - i], ans);，下标之和为len - 1，也就是两个数组代表的长度之和为len + 1而不是len，这是因为（用i=2，len=5举例，got[2]表示第一天到第三天的，got_reverse[5-2-1]表示第三天到第五天的，可以看到这里第三天其实是重复的）：

  • 如果刚好是这两段里面最多只有一段在第三天有交易，那这样是没问题的；
  • 如果两端里都有第三天，也就是第一段是第三天卖的，第二段是第三天买的，那就不用第三天的时候交易了，相当于只做了一次交易而非两次。
算法

每日leetcode-282

282 给表达式添加运算符

给定一个仅包含数字 0-9 的字符串和一个目标值，在数字之间添加二元运算符（不是一元）+、- 或 * ，返回所有能够得到目标值的表达式。

示例 1:

输入: num = “123”, target = 6
输出: [“1+2+3”, “123”]
示例 2:

输入: num = “232”, target = 8
输出: [“23+2”, “2+32”]
示例 3:

输入: num = “105”, target = 5
输出: [“1*0+5”,”10-5”]
示例 4:

输入: num = “00”, target = 0
输出: [“0+0”, “0-0”, “0*0”]
示例 5:

输入: num = “3456237490”, target = 9191
输出: []

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/expression-add-operators
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

尝试

做了一个特别naive的做法，直接简单递归与求值。

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
class Solution {
public:
    bool checkAns(const string &data, int target) {
        stack<char> op;
        stack<long long> num;
        int len = data.size();
        long long now_number = 0;
        for (int i = 0; i < len; i++) {
            if (data[i] >= '0' && data[i] <= '9') {
                now_number = now_number * 10 + data[i] - '0';
                continue;
            }
            num.push(now_number);
            now_number = 0;
            if (data[i] == '+' || data[i] =='-' || data[i] == '#') {
                // Calculate all before
                while (!op.empty()) {
                    char c = op.top();
                    op.pop();
                    long long b = num.top();
                    num.pop();
                    long long a = num.top();
                    num.pop();
                    if (c == '*') {
                        num.push(a * b);
                    }
                    else if (c == '+') {
                        num.push(a + b);
                    }
                    else {
                        num.push(a - b);
                    }
                }
                op.push(data[i]);
            }
            else if (data[i] == '*') {
                char c = op.empty() ? ' ' : op.top();
                if (c == '*') {
                    op.pop();
                    long long b = num.top();
                    num.pop();
                    long long a = num.top();
                    num.pop();
                    num.push(a * b);
                    op.push('*');
                }
                else {
                    op.push('*');
                }
            }
        }
        return num.top() == target;
    }

    void getResult(const string &already, const string &todo, int target, vector<string> &ans) {
        if (todo.empty()) {
            if (checkAns(already + "#", target)) {
                ans.push_back(already);
            }
        }
        else {
            if (*(already.cend() - 1) != '0') {
                getResult(already + todo.substr(0, 1), todo.substr(1, todo.size() - 1), target, ans);
            }
            getResult(already + "+" + todo.substr(0, 1), todo.substr(1, todo.size() - 1), target, ans);
            getResult(already + "-" + todo.substr(0, 1), todo.substr(1, todo.size() - 1), target, ans);
            getResult(already + "*" + todo.substr(0, 1), todo.substr(1, todo.size() - 1), target, ans);
        }
    }

    vector<string> addOperators(string num, int target) {
        vector<string> ans;
        getResult(num.substr(0, 1), num.substr(1, num.size() - 1), target, ans);
        return ans;
    }
};

很明显会超时。

解答

在 https://www.jianshu.com/p/22c9115b3a27 看到的。

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
class Solution {
public:
    vector<string> addOperators(string num, int target) {
        vector<string> res;
        addOperatorsDFS(num, target, 0, 0, "", res);
        return res;
    }
    void addOperatorsDFS(string num, int target, long long diff, long long curNum, string out, vector<string> &res) {
        if (num.size() == 0 && curNum == target) { // 当前已经处理完了所有的
            res.push_back(out);
        }
        for (int i = 1; i <= num.size(); ++i) {
            string cur = num.substr(0, i);
            if (cur.size() > 1 && cur[0] == '0') return;  // 如果当前的数字以0开头并且不是0，就说明操作符肯定只能在0后面，不能继续向后看切割位置
            string next = num.substr(i);  // 在i的地方切成了两部分，cur和next
            if (out.size() > 0) { // 之前已经计算过了有了一个数字的结果之后
                addOperatorsDFS(next, target, stoll(cur), curNum + stoll(cur), out + "+" + cur, res);  // +，当前的diff是cur对应的数字，计算完成的结果是curNum + stoll(cur)，已经计算完成的部分的字符串是out + "+" + cur
                addOperatorsDFS(next, target, -stoll(cur), curNum - stoll(cur), out + "-" + cur, res);  // -，直接把-当作是+负数，这样操作没有什么问题
                addOperatorsDFS(next, target, diff * stoll(cur), (curNum - diff) + diff * stoll(cur), out + "*" + cur, res);  // *，这里需要把前面的一个的结果（diff）拿出来，这样新的diff就是diff * stoll(cur)，因为把diff去掉了所以前面的剩下的结果是 (curNum - diff) ，总的结果就是(curNum - diff) + diff * stoll(cur)
            } else {
                addOperatorsDFS(next, target, stoll(cur), stoll(cur), cur, res);  // 这时还没有开始计算，所以需要把最开始的第一个数字搞出来
            }
        }
    }
};

long long diff, long long curNum, string out这三个参数分别是指上一次加上的计算结果，当前的计算结果，产生的已经计算过的字符串。

这里是把减法看成了加上负数，所以总的来说只是在处理乘法和加法的关系。

在后面写上乘号之后，需要把乘号前面的部分搞出来，所以就是需要diff的地方。

这样的做法可以很好地避免重复计算的过程，我之前的做法就会导致同样的一部分字符串计算求值算很多遍。

算法

每日leetcode-273

将非负整数转换为其对应的英文表示。可以保证给定输入小于 231 - 1 。

示例 1:

输入: 123
输出: “One Hundred Twenty Three”
示例 2:

输入: 12345
输出: “Twelve Thousand Three Hundred Forty Five”
示例 3:

输入: 1234567
输出: “One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven”
示例 4:

输入: 1234567891
输出: “One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One”

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/integer-to-english-words
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解

这个题很简单，直接按照三位分开之后分别转换就行，重点在于单词拼写

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
47
48
49
50
51
class Solution {
public:
    string numberToWords(int num) {
        int splited[4] = { 0 };
        string numbers[] = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
        string tensnumbers[] = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
        string biggertennumbers[] = {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
        if (num == 0) {
            return "Zero";
        }
        for (int i = 0; i < 4; i++) {
            splited[i] = num % 1000;
            num = num / 1000;
        }
        string ans = "";
        for (int i = 3; i >= 0; i--) {
            int data = splited[i];
            if (data > 0) {
                if (data / 100) {
                    ans += numbers[data / 100] + " Hundred ";
                }
                data = data % 100;
                if (data > 0) {
                    if (data < 10) {
                        ans += numbers[data] + " ";
                    }
                    else if (data >= 20) {
                        ans += tensnumbers[data / 10] + " ";
                        data = data % 10;
                        if (data > 0) {
                            ans += numbers[data] + " ";
                        }
                    }
                    else {
                        ans += biggertennumbers[data - 10] + " ";
                    }
                }
                if (i == 3) {
                    ans += "Billion ";
                }
                else if (i == 2) {
                    ans += "Million ";
                }
                else if (i == 1) {
                    ans += "Thousand ";
                }
            }
        }
        return ans.substr(0, ans.size() - 1);
    }
};