LeetCode Contest 347

6457. Remove Trailing Zeros From a String

给你一个用字符串表示的正整数 num ，请你以字符串形式返回不含尾随零的整数 num 。

测试样例：

输入：num = "51230100"

输出："512301"

解释：
整数 "51230100" 有 2 个尾随零，移除并返回整数 "512301" 。

解答：这道题目直接逆序遍历，寻找第一个非0的字符。把之前的字符串输出

class Solution {
    public String removeTrailingZeros(String num) {
        StringBuilder sb = new StringBuilder();
        boolean isAdd = false;
        for (int i = num.length() - 1; i >= 0; --i) {
            if (num.charAt(i) == '0' && !isAdd) {
                continue;
            }
            isAdd = true;
            sb.append(num.charAt(i));
        }
        return sb.reverse().toString();
    }
}

6440. Difference of Number of Distinct Values on Diagonals

给你一个下标从 0 开始、大小为 m x n 的二维矩阵 grid ，请你求解大小同样为 m x n 的答案矩阵 answer 。

矩阵 answer 中每个单元格 (r, c) 的值可以按下述方式进行计算：

• 令 topLeft[r][c] 为矩阵 grid 中单元格 (r, c) 左上角对角线上 不同值 的数量。
• 令 bottomRight[r][c] 为矩阵 grid 中单元格 (r, c) 右下角对角线上 不同值 的数量。

然后 answer[r][c] = |topLeft[r][c] - bottomRight[r][c]| 。

返回矩阵 answer 。

矩阵对角线 是从最顶行或最左列的某个单元格开始，向右下方向走到矩阵末尾的对角线。

如果单元格 (r1, c1) 和单元格 (r, c) 属于同一条对角线且 r1 < r ，则单元格 (r1, c1) 属于单元格 (r, c) 的左上对角线。类似地，可以定义右下对角线。

测试样例：

输入：grid = [[1]]

输出：[[0]]

解释：
单元格 (0,0) 的右下对角线包含 [] ，左上对角线包含 [] 。对应答案是 |0 - 0| = 0 。

解答：这道题目范围非常小：1 <= m, n, grid[i][j] <= 50。直接按题意暴力运算

class Solution {
    public int[][] differenceOfDistinctValues(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] res = new int[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                Set<Integer> left = new HashSet<>(), right = new HashSet<>();
                int x = i - 1, y = j - 1;
                while (x >= 0 && y >= 0) {
                    left.add(grid[x][y]);
                    --x;
                    --y;
                }

                x = i + 1; y = j + 1;
                while (x < m && y < n) {
                    right.add(grid[x][y]);
                    ++x;
                    ++y;
                }
                res[i][j] = Math.abs(left.size() - right.size());
            }
        }
        return res;
    }
}

6455. Minimum Cost to Make All Characters Equal

给你一个下标从 0 开始、长度为 n 的二进制字符串 s ，你可以对其执行两种操作：

• 选中一个下标 i 并且反转从下标 0 到下标 i（包括下标 0 和下标 i ）的所有字符，成本为 i + 1 。
• 选中一个下标 i 并且反转从下标 i 到下标 n - 1（包括下标 i 和下标 n - 1 ）的所有字符，成本为 n - i 。

返回使字符串内所有字符 相等 需要的 最小成本 。

反转 字符意味着：如果原来的值是 '0' ，则反转后值变为 '1' ，反之亦然。

测试样例

输入：s = "0011"

输出：2

解释：
执行第二种操作，选中下标 i = 2 ，可以得到 s = "0000" ，成本为 2 。可以证明 2 是使所有字符相等的最小成本。

解答：这道题目需要脑筋急转弯一下。如果最后一个操作是第一种操作为例，如果最后字符串内所有数字都一样，那么必然s.charAt(i - 1) == s.charAt(i)。如果最后一个操作是第二种操作，那么必然s.charAt(i + 1) == s.charAt(i)。所以按照左右2遍动态规划，寻找使用某一操作，使得一边数字相同的最小次数。注意这道题目返回是long！！！

class Solution {
    public long minimumCost(String s) {
        int len = s.length();
        long[][] rightDp = new long[len + 1][2];
        for (int i = len - 1; i >= 0; --i) {
            int c = s.charAt(i) - '0';
            if (c == 0) {
                rightDp[i][0] = Math.min(rightDp[i + 1][1] + len - i - 1, rightDp[i + 1][0]);
                rightDp[i][1] = Math.min(rightDp[i + 1][0] + len - i, rightDp[i + 1][1] + len - i - 1 + len - i);
            } else {
                rightDp[i][1] = Math.min(rightDp[i + 1][0] + len - i - 1, rightDp[i + 1][1]);
                rightDp[i][0] = Math.min(rightDp[i + 1][1] + len - i, rightDp[i + 1][0] + len - i - 1 + len - i);
            }
        }

        long res = Long.MAX_VALUE;
        long zero = 0, one = 0;
        for (int i = 0; i < len; ++i) {
            int c = s.charAt(i) - '0';
            long zt = 0, ot = 0;
            if (c == 0) {
                zt = Math.min(one + i, zero);
                ot = Math.min(zero + i + 1, one + i + (i + 1));
            } else {
                ot = Math.min(zero + i, one);
                zt = Math.min(one + i + 1, zero + i + (i + 1));
            }
            zero = zt;
            one = ot;
            res = Math.min(res, Math.min(zero + rightDp[i + 1][0], one + rightDp[i + 1][1]));
        }
        return res;
    }
}

6456. Maximum Strictly Increasing Cells in a Matrix

给你一个下标从 1 开始、大小为 m x n 的整数矩阵 mat，你可以选择任一单元格作为 起始单元格 。

从起始单元格出发，你可以移动到 同一行或同一列 中的任何其他单元格，但前提是目标单元格的值 严格大于 当前单元格的值。

你可以多次重复这一过程，从一个单元格移动到另一个单元格，直到无法再进行任何移动。

请你找出从某个单元开始访问矩阵所能访问的 单元格的最大数量 。

返回一个表示可访问单元格最大数量的整数。

测试样例

输入：mat = [[3,1],[3,4]]

输出：2

解释：从第 1 行、第 2 列的单元格开始，可以访问 2 个单元格。可以证明，无论从哪个单元格开始，最多只能访问 2 个单元格，因此答案是 2 。

解答：这道题目首先需要利用排序，把矩阵中所有数字从小到大排列。然后遍历数组并记录每行与每列最大跳跃次数。

class Solution {
    public int maxIncreasingCells(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        Integer[] sort = new Integer[m * n];
        for (int i = 0; i < sort.length; ++i) {
            sort[i] = i;
        }

        Arrays.sort(sort, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                int x1 = o1 / n, y1 = o1 % n;
                int x2 = o2 / n, y2 = o2 % n;
                return mat[x1][y1] - mat[x2][y2];
            }
        });

        int res = 0;
        int[] rowMem = new int[m], colMem = new int[n];
        int[] nextRowMem = new int[m], nextColMem = new int[n];
        Stack<Integer> rowStack = new Stack<>(), colStack = new Stack<>();
        int last = Integer.MIN_VALUE;
        for (int i = 0; i < sort.length; ++i) {
            int x = sort[i] / n, y = sort[i] % n;
            if (mat[x][y] != last) {
                while (!rowStack.isEmpty()) {
                    int tmp = rowStack.pop();
                    rowMem[tmp] = nextRowMem[tmp];
                }
                while (!colStack.isEmpty()) {
                    int tmp = colStack.pop();
                    colMem[tmp] = nextColMem[tmp];
                }
                last = mat[x][y];
            }
            nextRowMem[x] = Math.max(nextRowMem[x], Math.max(rowMem[x], colMem[y]) + 1);
            nextColMem[y] = Math.max(nextColMem[y], Math.max(rowMem[x], colMem[y]) + 1);
            rowStack.push(x);
            colStack.push(y);
            res = Math.max(res, nextRowMem[x]);
            res = Math.max(res, nextColMem[y]);
        }
        return res;
    }
}