2023.5.21LeetCode346场周赛

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

思路

使用栈模拟，每当遇到AB和CD时出栈

代码

class Solution {
public:
    int minLength(string s) {
        string res = s.substr(0, 1);
        for (int i = 1; i < s.size(); i ++ ) {
            res += s[i];
            int n = res.size();
            while (n > 1) {
                if (res[n - 1] == 'B' && res[n - 2] == 'A' || res[n - 1] == 'D' && res[n - 2] == 'C') {
                    res.pop_back();
                    res.pop_back();
                }
                else break;
            }
        }
        return res.size();
    }
};

B. 字典序最小回文串

思路

双指针，优先选择字典序小的

代码

class Solution {
public:
    string makeSmallestPalindrome(string s) {
        int i = 0, j = s.size() - 1;
        string ans;
        int n = s.size();
        while (i < j) {
            if (s[i] <= s[j]) ans += s[i];
            else ans += s[j];
            i ++ , j -- ;
        }
        string t = ans;
        reverse(t.begin(), t.end());
        if (n % 2)
            ans += s[i] + t;
        else
            ans += t;
        return ans;
    }
};

C. 求一个整数的惩罚数

思路

枚举所有数，搜索$i\ast i$所有可能的分割情况

代码

class Solution {
public:
    bool dfs(int u, int num, int cur, int sum, string s) {
        if (cur > sum) return false;
        if (u == s.size()) {
            if (cur + num == sum)
                return true;
            return false;
        }
        if (dfs(u + 1, s[u] - '0', cur + num, sum, s)) return true;
        if (dfs(u + 1, num * 10 + s[u] - '0', cur, sum, s)) return true;
        return false;
    }
    
    int punishmentNumber(int n) {
        int ans = 0;
        for (int i = 1; i <= n; i ++ )
            if (dfs(0, 0, 0, i, to_string(i * i)))
                ans += i * i;
        return ans;
    }
};

D. 修改图中的边权

思路

转载自https://leetcode.cn/problems/modify-graph-edge-weights/solution/xiang-xi-fen-xi-liang-ci-dijkstrachou-mi-gv1m/

代码

typedef pair<int, int> PII;

class Solution {
public:
    vector<vector<int>> d, edges;
    vector<vector<PII>> g;
    int n, destination;
    int delta = 0;

    void dijkstra(int k) {
        vector<int> st(n);
        while (true) {
            int t = -1;
            // 找出最近的点
            for (int i = 0; i < n; i ++ ) {
                if (!st[i]&& (t == -1 || d[i][k] < d[t][k]))
                    t = i;
            }
            if (t == destination)
                return;
            st[t] = 1;
            for (auto [x, y] : g[t]) {
                int wt = edges[y][2];
                if (wt == -1)
                    wt = 1;
                if (k == 1 && edges[y][2] == -1) { // 可变且要修改
                    int w = delta + d[x][0] - d[t][1]; // 要修改成的权值
                    if (w > wt)
                        edges[y][2] = wt = w;
                }
                d[x][k] = min(d[x][k], d[t][k] + wt);
            }
        }
    }

    vector<vector<int>> modifiedGraphEdges(int _n, vector<vector<int>>& _edges, int source, int _destination, int target) {
        destination = _destination;
        edges = _edges;
        n = _n;
        g.resize(n);
        d.resize(n, vector<int>(2, 1e9));
        for (int i = 0; i < edges.size(); i ++ ) {
            int a = edges[i][0], b = edges[i][1];
            g[a].push_back({b, i}); // 记录的是edge数组中的下标
            g[b].push_back({a, i});
        }
        d[source][0] = d[source][1] = 0;
        dijkstra(0); // 把所有-1当做1计算
        delta = target - d[destination][0]; // 最短路最小的情况下还比target大
        if (delta < 0) return {};
        dijkstra(1); // 重新dijkstra增大权值，计算要更改的权值，按照dijkstra的顺序去修改权值，不会影响其他的最短路
        if (d[destination][1] < target) return {}; // 最短路无法达到target
        for (auto& e : edges)
            if (e[2] == -1)
                e[2] = 1;
        return edges;
    }
};