力扣第346场周赛思路

第二次打周赛，这次拿到了全国160多名的成绩，前面三道题不到二十分钟可以做完，思路也比较好想。最后一道图相关的hard题暴露了短板，以后图还是得多看看。

结果：3/4

删除子串后的字符串最小长度

思路：根据题目的描述，嗯造就完了。

代码：

 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


class Solution {
public:
    int minLength(string s) {
        while(true) {
            bool modified = false;
            while (true) {
                int pos = s.find("AB");
                if (pos == string::npos) {
                    break;
                }
                s.erase(pos, 2);
                modified = true;
            }
            while (true) {
                int pos = s.find("CD");
                if (pos == string::npos) {
                    break;
                }
                s.erase(pos, 2);
                modified = true;
            }
            if (!modified) {
                break;
            }
        }
        return s.length();
    }
};

字典序最小回文串

题目链接：2697. 字典序最小回文串

思路：双指针，如果遇到不相同的字母则修改为字典序更小的一方。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
public:
    string makeSmallestPalindrome(string s) {
        int n = s.size();
        int left = 0, right = n - 1;
        while (left < right) {
            if (s[left] != s[right]) {
                if (s[left] < s[right]) {
                    s[right] = s[left];
                } else {
                    s[left] = s[right];
                }
            }
            left++;
            right--;
        }
        return s;
    }
};

求一个整数的惩罚数

题目链接：2698. 求一个整数的惩罚数

思路：比较简单的搜索，搜索的时候判断是否需要将当前数字加到划分里面，将积累的待加数放到acc里面。

代码：

 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


class Solution {
    bool search(const string &s, int cur, int target, int sum, int acc) {
        if (sum > target) {
            return false;
        }
        if (cur == s.size()) {
            return (sum + acc) == target;
        }
        bool valid = false;
        valid = valid || search(s, cur + 1, target, sum + (acc * 10 + s[cur] - '0'), 0);
        valid = valid || search(s, cur + 1, target, sum, acc * 10 + s[cur] - '0');
        return valid;
    }

public:
    int punishmentNumber(int n) {
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            int x = i * i;
            string s = to_string(x);
            if (search(s, 0, i, 0, 0)) {
                cout << i << endl;
                ans += x;
            }
        }
        return ans;
    }
};