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;elseans += t;return ans;}
};

C. 求一个整数的惩罚数

思路

枚举所有数，搜索 $i * 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 {}; // 最短路无法达到targetfor (auto& e : edges)if (e[2] == -1)e[2] = 1;return edges;}
};