2696. 删除子串后的字符串最小长度
给你一个仅由 大写 英文字符组成的字符串 s 。
你可以对此字符串执行一些操作，在每一步操作中，你可以从 s 中删除 任一个 "AB" 或 "CD" 子字符串。
通过执行操作，删除所有 "AB" 和 "CD" 子串，返回可获得的最终字符串的 最小 可能长度。
注意，删除子串后，重新连接出的字符串可能会产生新的 "AB" 或 "CD" 子串。
示例 1：
输入：s = "ABFCACDB"
输出：2
解释：你可以执行下述操作：
- 从 "ABFCACDB" 中删除子串 "AB"，得到 s = "FCACDB" 。
- 从 "FCACDB" 中删除子串 "CD"，得到 s = "FCAB" 。
- 从 "FCAB" 中删除子串 "AB"，得到 s = "FC" 。
最终字符串的长度为 2 。
可以证明 2 是可获得的最小长度。
示例 2：
输入：s = "ACBBD"
输出：5
解释：无法执行操作，字符串长度不变。
提示：
1 <= s.length <= 100
s 仅由大写英文字母组成解答：直接调用API
class Solution {
public int minLength(String s) {
if(s.contains("AB"))return minLength(s.replace("AB",""));
if(s.contains("CD"))return minLength(s.replace("CD",""));
return s.length();
}
}2697. 字典序最小回文串
给你一个由 小写英文字母 组成的字符串 s ，你可以对其执行一些操作。在一步操作中，你可以用其他小写英文字母 替换 s 中的一个字符。
请你执行 尽可能少的操作 ，使 s 变成一个 回文串 。如果执行 最少 操作次数的方案不止一种，则只需选取 字典序最小 的方案。
对于两个长度相同的字符串 a 和 b ，在 a 和 b 出现不同的第一个位置，如果该位置上 a 中对应字母比 b 中对应字母在字母表中出现顺序更早，则认为 a 的字典序比 b 的字典序要小。
返回最终的回文字符串。
示例 1：
输入：s = "egcfe"
输出："efcfe"
解释：将 "egcfe" 变成回文字符串的最小操作次数为 1 ，修改 1 次得到的字典序最小回文字符串是 "efcfe"，只需将 'g' 改为 'f' 。
示例 2：
输入：s = "abcd"
输出："abba"
解释：将 "abcd" 变成回文字符串的最小操作次数为 2 ，修改 2 次得到的字典序最小回文字符串是 "abba" 。
示例 3：
输入：s = "seven"
输出："neven"
解释：将 "seven" 变成回文字符串的最小操作次数为 1 ，修改 1 次得到的字典序最小回文字符串是 "neven" 。
提示：
1 <= s.length <= 1000
s 仅由小写英文字母组成解答：双指针
class Solution {
public String makeSmallestPalindrome(String s) {
char[] cc=s.toCharArray();
int n=cc.length;
int l=0,r=n-1;
while(l<r){
if(cc[l]!=cc[r]){
if(cc[l]>cc[r]){
cc[l]=cc[r];
}
else{
cc[r]=cc[l];
}
}
l++;r--;
}
return new String(cc);
}
}2698. 求一个整数的惩罚数
给你一个正整数 n ，请你返回 n 的 惩罚数 。
n 的 惩罚数 定义为所有满足以下条件 i 的数的平方和：
1 <= i <= n
i * i 的十进制表示的字符串可以分割成若干连续子字符串，且这些子字符串对应的整数值之和等于 i 。
示例 1：
输入：n = 10
输出：182
解释：总共有 3 个整数 i 满足要求：
- 1 ，因为 1 * 1 = 1
- 9 ，因为 9 * 9 = 81 ，且 81 可以分割成 8 + 1 。
- 10 ，因为 10 * 10 = 100 ，且 100 可以分割成 10 + 0 。
因此，10 的惩罚数为 1 + 81 + 100 = 182
示例 2：
输入：n = 37
输出：1478
解释：总共有 4 个整数 i 满足要求：
- 1 ，因为 1 * 1 = 1
- 9 ，因为 9 * 9 = 81 ，且 81 可以分割成 8 + 1 。
- 10 ，因为 10 * 10 = 100 ，且 100 可以分割成 10 + 0 。
- 36 ，因为 36 * 36 = 1296 ，且 1296 可以分割成 1 + 29 + 6 。
因此，37 的惩罚数为 1 + 81 + 100 + 1296 = 1478
提示：
1 <= n <= 1000解答：递归+回溯枚举所有的情况
class Solution {
private static final int[] PRE_SUM = new int[1001];
static {
for (int i = 1; i <= 1000; i++) {
var s = Integer.toString(i * i).toCharArray();
PRE_SUM[i] = PRE_SUM[i - 1] + (dfs(s, i, 0, 0) ? i * i : 0);
}
}
private static boolean dfs(char[] s, int i, int p, int sum) {
if (p == s.length) // 递归终点
return sum == i; // i 符合要求
int x = 0;
for (int j = p; j < s.length; j++) { // 从 s[p] 到 s[j] 组成的子串
x = x * 10 + s[j] - '0'; // 对应的整数值
if (dfs(s, i, j + 1, sum + x))
return true;
}
return false;
}
public int punishmentNumber(int n) {
return PRE_SUM[n];
}
}
6442. 修改图中的边权
给你一个 n 个节点的 无向带权连通 图，节点编号为 0 到 n - 1 ，再给你一个整数数组 edges ，其中 edges[i] = [ai, bi, wi] 表示节点 ai 和 bi 之间有一条边权为 wi 的边。
部分边的边权为 -1（wi = -1），其他边的边权都为 正 数（wi > 0）。
你需要将所有边权为 -1 的边都修改为范围 [1, 2 * 109] 中的 正整数 ，使得从节点 source 到节点 destination 的 最短距离 为整数 target 。如果有 多种 修改方案可以使 source 和 destination 之间的最短距离等于 target ，你可以返回任意一种方案。
如果存在使 source 到 destination 最短距离为 target 的方案，请你按任意顺序返回包含所有边的数组（包括未修改边权的边）。如果不存在这样的方案，请你返回一个 空数组 。
注意：你不能修改一开始边权为正数的边。
示例 1：
输入：n = 5, edges = [[4,1,-1],[2,0,-1],[0,3,-1],[4,3,-1]], source = 0, destination = 1, target = 5
输出：[[4,1,1],[2,0,1],[0,3,3],[4,3,1]]
解释：上图展示了一个满足题意的修改方案，从 0 到 1 的最短距离为 5 。
示例 2：
输入：n = 3, edges = [[0,1,-1],[0,2,5]], source = 0, destination = 2, target = 6
输出：[]
解释：上图是一开始的图。没有办法通过修改边权为 -1 的边，使得 0 到 2 的最短距离等于 6 ，所以返回一个空数组。
示例 3：
输入：n = 4, edges = [[1,0,4],[1,2,3],[2,3,5],[0,3,-1]], source = 0, destination = 2, target = 6
输出：[[1,0,4],[1,2,3],[2,3,5],[0,3,1]]
解释：上图展示了一个满足题意的修改方案，从 0 到 2 的最短距离为 6 。
提示：
1 <= n <= 100
1 <= edges.length <= n * (n - 1) / 2
edges[i].length == 3
0 <= ai, bi < n
wi = -1 或者 1 <= wi <= 10^7
ai != bi
0 <= source, destination < n
source != destination
1 <= target <= 10^9
输入的图是连通图，且没有自环和重边。解答：通过两次Dijkstra求解
class Solution {
public int[][] modifiedGraphEdges(int n, int[][] edges, int source, int destination, int target) {
List<int[]> g[] = new ArrayList[n];
Arrays.setAll(g, e -> new ArrayList<>());
for (int i = 0; i < edges.length; i++) {
int x = edges[i][0], y = edges[i][1];
g[x].add(new int[]{y, i});
g[y].add(new int[]{x, i}); // 建图，额外记录边的编号
}
var dis = new int[n][2];
for (int i = 0; i < n; i++)
if (i != source)
dis[i][0] = dis[i][1] = Integer.MAX_VALUE;
dijkstra(g, edges, destination, dis, 0, 0);
int delta = target - dis[destination][0];
if (delta < 0) // -1 全改为 1 时，最短路比 target 还大
return new int[][]{};
dijkstra(g, edges, destination, dis, delta, 1);
if (dis[destination][1] < target) // 最短路无法再变大，无法达到 target
return new int[][]{};
for (var e : edges)
if (e[2] == -1) // 剩余没修改的边全部改成 1
e[2] = 1;
return edges;
}
// 朴素 Dijkstra 算法
// 这里 k 表示第一次/第二次
private void dijkstra(List<int[]> g[], int[][] edges, int destination, int[][] dis, int delta, int k) {
int n = g.length;
var vis = new boolean[n];
for (; ; ) {
// 找到当前最短路，去更新它的邻居的最短路
// 根据数学归纳法，dis[x][k] 一定是最短路长度
int x = -1;
for (int i = 0; i < n; ++i)
if (!vis[i] && (x < 0 || dis[i][k] < dis[x][k]))
x = i;
if (x == destination) // 起点 source 到终点 destination 的最短路已确定
return;
vis[x] = true; // 标记，在后续的循环中无需反复更新 x 到其余点的最短路长度
for (var e : g[x]) {
int y = e[0], eid = e[1];
int wt = edges[eid][2];
if (wt == -1)
wt = 1; // -1 改成 1
if (k == 1 && edges[eid][2] == -1) {
// 第二次 Dijkstra，改成 w
int w = delta + dis[y][0] - dis[x][1];
if (w > wt)
edges[eid][2] = wt = w; // 直接在 edges 上修改
}
// 更新最短路
dis[y][k] = Math.min(dis[y][k], dis[x][k] + wt);
}
}
}
}
