LeetCode Contest 346

6439. Minimum String Length After Removing Substrings

给你一个仅由 大写 英文字符组成的字符串 s 。

你可以对此字符串执行一些操作，在每一步操作中，你可以从 s 中删除 任一个 "AB" 或 "CD" 子字符串。

通过执行操作，删除所有 "AB" 和 "CD" 子串，返回可获得的最终字符串的 最小 可能长度。

注意，删除子串后，重新连接出的字符串可能会产生新的 "AB" 或 "CD" 子串。

测试样例：

输入：s = "ABFCACDB"

输出：2

解释：
你可以执行下述操作：

• 从 "ABFCACDB" 中删除子串 "AB"，得到 s = "FCACDB" 。
• 从 "FCACDB" 中删除子串 "CD"，得到 s = "FCAB" 。
• 从 "FCAB" 中删除子串 "AB"，得到 s = "FC" 。

最终字符串的长度为 2 。可以证明 2 是可获得的最小长度。

解答：利用栈的特性，可以完成递归删除。

class Solution {
    public int minLength(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == 'B') {
                if (!stack.isEmpty() && stack.peek() == 'A') {
                    stack.pop();
                    continue;
                }
            }
            if (s.charAt(i) == 'D') {
                if (!stack.isEmpty() && stack.peek() == 'C') {
                    stack.pop();
                    continue;
                }
            }
            stack.push(s.charAt(i));
        }
        return stack.size();
    }
}

6454. Lexicographically Smallest Palindrome

给你一个由 小写英文字母 组成的字符串 s ，你可以对其执行一些操作。在一步操作中，你可以用其他小写英文字母 替换 s 中的一个字符。

请你执行 尽可能少的操作 ，使 s 变成一个 回文串 。如果执行 最少 操作次数的方案不止一种，则只需选取 字典序最小 的方案。

对于两个长度相同的字符串 a 和 b ，在 a 和 b 出现不同的第一个位置，如果该位置上 a 中对应字母比 b 中对应字母在字母表中出现顺序更早，则认为 a 的字典序比 b 的字典序要小。

返回最终的回文字符串。

测试样例：

输入：s = "egcfe"

输出："efcfe"

解释：
将 "egcfe" 变成回文字符串的最小操作次数为 1 ，修改 1 次得到的字典序最小回文字符串是 "efcfe"，只需将 'g' 改为 'f' 。

解答：因为操作次数最小，有需要字典序最小。那就是应该相同的位置选择较小的char就行了

class Solution {
    public String makeSmallestPalindrome(String s) {
        int st = 0, ed = s.length() - 1;
        StringBuilder sb = new StringBuilder();
        while (st < ed) {
            char c = (char) Math.min(s.charAt(st), s.charAt(ed));
            sb.append(c);
            ++st;
            --ed;
        }
        String tmp = sb.toString();
        if (st == ed) {
            tmp += s.charAt(st);
        }
        String rev = sb.reverse().toString();
        return tmp + rev;
    }
}

6441. Find the Punishment Number of an Integer

给你一个正整数 n ，请你返回 n 的 惩罚数 。

n 的 惩罚数 定义为所有满足以下条件 i 的数的平方和：

• 1 <= i <= n
• i * i 的十进制表示的字符串可以分割成若干连续子字符串，且这些子字符串对应的整数值之和等于 i 。

测试样例

输入：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

解答：这道题范围极小，寻找符合要求的数字计算一下。

class Solution {
    private static final int[] valid = {1,9,10,36,45,55,82,91,99,100,235,297,369,370,379,414,657,675,703,756,792,909,918,945,964,990,991,999,1000};

    public int punishmentNumber(int n) {
        int res = 0;
        for (int i : valid) {
            if (i <= n) {
                res += i * i;
            }
        }
        return res;
    }

    private boolean isValid(int n) {
        int tmp = n * n;
        return isFound(String.valueOf(tmp), 0, n, 0, 0);
    }

    private boolean isFound(String tmp, int pos, int res, int add, int last) {
        if (pos == tmp.length()) {
            return add + last == res;
        } else {
            int p = tmp.charAt(pos) - '0';
            return isFound(tmp, pos + 1, res, add + last, p) || isFound(tmp, pos + 1, res, add, last * 10 + p);
        }
    }
}

6442. Modify Graph Edge Weights

给你一个 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 的方案，请你按任意顺序返回包含所有边的数组（包括未修改边权的边）。如果不存在这样的方案，请你返回一个 空数组 。

注意：你不能修改一开始边权为正数的边。

测试样例

输入：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 。

解答：这道题目，n的范围很小。所以也可以使用暴力算法寻找任意2点之间的最小距离

class Solution {
    private static final int MAX = 2_000_000_000;

    public int[][] modifiedGraphEdges(int n, int[][] edges, int ss, int tt, int target) {
        int m = edges.length;
        ArrayDeque <int[]> neg = new ArrayDeque();
        long[][] dis = new long[n][n];
        boolean valid = false;
        for(int i = 0; i < n; i++) Arrays.fill(dis[i], MAX);
        for(int i = 0; i < n; i++) dis[i][i] = 0;
        for(int i = 0; i < m; i++) {
            if(edges[i][2] < 0) neg.add(new int[]{edges[i][0], edges[i][1], edges[i][2], i});
            else dis[edges[i][0]][edges[i][1]] = dis[edges[i][1]][edges[i][0]] = edges[i][2];
        }
        for(int k = 0; k < n; k++) {
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    dis[i][j] = dis[j][i] = Math.min(dis[i][j], dis[i][k] + dis[j][k]);
                }
            }
        }
        if(dis[ss][tt] < target) return new int[0][3];
        for (int[] ee : neg) {
            int a = ee[0], b = ee[1], d = ee[3];
            long min = Math.min(dis[ss][a] + dis[tt][b], dis[ss][b] + dis[tt][a]);
            if (min < target) {
                edges[d][2] = (int) (target - min);
                valid = true;
                break;
            } else {
                dis[a][b] = dis[b][a] = 1;
                edges[d][2] = 1;
                for(int i = 0; i < n; i++) {
                    for(int j = 0; j < i; j++) {
                        dis[i][j] = dis[j][i] = Math.min(dis[i][j], 1 + Math.min(dis[i][a] + dis[j][b], dis[i][b] + dis[j][a]));
                    }
                }
            }
        }
        if (dis[ss][tt] == target) valid = true;
        if (!valid) return new int[0][3];
        for(int i = 0; i < m; i++) if (edges[i][2] == -1) edges[i][2] = MAX;
        return edges;
    }
}