LeetCode周记 EP3

前言

这周双周赛和周赛都没打，之前两周积累的问题有些多了，先只处理每日一题吧。

本周主题：动态规划、贪心

题目：

• 240619每日一题—Maximum Strictly Increasing Cells in a Matrix
• 240622每日一题—Lexicographically Smallest Beautiful String 这两道Hard题稍微看看理解一下就行了，暂时没太多可归纳的，可记忆的点就是二维排序和回文判别（只要一个字符串中的任何字符，都不与它前两个字符相同，这个字符串就不包含任何长度为 2 或者更长的回文字符串）。

动态规划 — Maximum Strictly Increasing Cells in a Matrix

Maximum Strictly Increasing Cells in a Matrix

Given a 1-indexed m x n integer matrix mat, you can select any cell in the matrix as your starting cell.

From the starting cell, you can move to any other cell in the same row or column, but only if the value of the destination cell is strictly greater than the value of the current cell. You can repeat this process as many times as possible, moving from cell to cell until you can no longer make any moves.

Your task is to find the maximum number of cells that you can visit in the matrix by starting from some cell.

Return an integer denoting the maximum number of cells that can be visited.

设 $d[i][j]$ 为移动到单元格 $(i, j)$ 的最大步数, 其中 $(i, j)$ 可以作为起始单元格, 也可以是从其他单元格移动而来。那么我们会考虑从第 $i$ 行以及第 $j$ 列上矩阵数值小于 $\operatorname{mat}[i][j]$ 的位置进行转移, 即取以下数值中的最大值:

• 第 $i$ 行： $\max \left(d[i]\left[j^{\prime}\right]+1\right)$ ，其中 $\operatorname{mat}[i]\left[j^{\prime}\right]<\operatorname{mat}[i][j]$ ；
• 第 $j$ 列： $\max \left(d\left[l^{\prime}\right][j]+1\right)$ ，其中 $\operatorname{mat}\left[i^{\prime}\right][j]<\operatorname{mat}[[][j]$ 。

因此, 整个状态空间在进行转移时是有序的, 我们可以对 mat 进行排序, 从小到大进行转移。但在转移时, 每个状态都要扫描一遍对应的行和列, 时间复杂度为 $O(n+m)$, 而整体求解的时间复杂度为 $O(n m(n+m))$, 可能会超时, 因此需要进行优化。

考虑到所有的 $d[i][j]$ 在更新时, 值只会越来越大, 而转移过程中我们只考虑对应行和对应列上 $d$ 的最大值（由于大于 mat $[i][j]$ 的位置还末遍历到, 它们的状态还末更新, 可设置为 0 )。因此, 设置长度为 $m$ 的数组 row 来维护每一行 $d$ 的最大值, 设置长度为 $n$ 的数组 $c o l$ 来维护每一列的最大值，这样一来:

$$d[i][j]=\max (\operatorname{row}[i], \operatorname{col}[j])+1$$

在每次更新了 $d[i][j]$ 后, 需要更新 $r o w[i]$ 和 $col[j]$ 。另外需要注意的是, 由于 mat 中可能包含相同数字, 我们需要同时更新它们的 $d$ 值, 然后再同时更新它们对应的 row 和 col。

class Solution {
    public int maxIncreasingCells(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        Map<Integer, List<int[]>> mp = new HashMap<Integer, List<int[]>>();
        int[] row = new int[m];
        int[] col = new int[n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                mp.putIfAbsent(mat[i][j], new ArrayList<int[]>());
                mp.get(mat[i][j]).add(new int[]{i, j});
            }
        }
        List<Integer> keys = new ArrayList<Integer>(mp.keySet());
        Collections.sort(keys);
        for (int key : keys) {
            List<int[]> pos = mp.get(key);
            List<Integer> res = new ArrayList<Integer>(); // 存放相同数值的答案，便于后续更新 row 和 col
            for (int[] arr : pos) {
                res.add(Math.max(row[arr[0]], col[arr[1]]) + 1);
            }
            for (int i = 0; i < pos.size(); i++) {
                int[] arr = pos.get(i);
                int d = res.get(i);
                row[arr[0]] = Math.max(row[arr[0]], d);
                col[arr[1]] = Math.max(col[arr[1]], d);
            }
        }
        return Arrays.stream(row).max().getAsInt();
    }
}

贪心 — Lexicographically Smallest Beautiful String

Lexicographically Smallest Beautiful String

A string is beautiful if:

• It consists of the first k letters of the English lowercase alphabet.
• It does not contain any substring of length 2 or more which is a palindrome.

You are given a beautiful string s of length n and a positive integer k.

Return the lexicographically smallest string of length n, which is larger than s and is beautiful. If there is no such string, return an empty string.

A string a is lexicographically larger than a string b (of the same length) if in the first position where a and b differ, a has a character strictly larger than the corresponding character in b.

• For example, “abcd” is lexicographically larger than “abcc” because the first position they differ is at the fourth character, and d is greater than c.

首先分析一下美丽字符串的第二个条件：不包含任何长度为 2 或者更长的回文字符串。长度为 2 的回文字符串是两个相同字符构成的字符串。长度为 3 的回文字符串中也有两个相同字符，但下标之差为 2。而任何长度为 2 或者更长的回文字符串，都包含一个长度为 2 或者 3 的回文字符串。因此，只要一个字符串中的任何字符，都不与它前两个字符相同，这个字符串就不包含任何长度为 2 或者更长的回文字符串。

接下来看其他要求，返回的美丽字符串需要字典序大于 s 并且字典序最小。贪心的思路是修改 s 的末尾字符，一点点将字符变大，如果在变大的同时能够满足美丽字符串的两个条件，那么我们就找到了要求的美丽字符串。修改后的字符不能与前两个字符相同，因此我们在将字符变大的时候只需要将字符逐步变大三次，就能判断出修改当前字符能否满足美丽字符串的条件。如果修改末尾字符达不到美丽字符串的条件，则我们需要将被修改的字符改为倒数第二个字符，仍然按照之前的思路一点点增大，并判断是否满足美丽字符串的两个条件。我们从末尾字符开始，往前一点点判断是否可以修改当前字符来找到目标美丽字符串。一旦我们第一次找到了合适的下标，我们就可以来修改字符来达到目标条件。

首先我们需要修改寻找到的下标的字符，将其修改为最小的满足美丽字符串条件的字符。接下来需要修改它右边的字符。因为之前修改的字符已经能保证返回的字符串在字典序上大于 s，我们只需要将后续的字符修改得尽可能小即可，因为每个字符需要与前两个字符不同，因此每个字符只需要遍历 ‘a’∼‘c’ 即可。因为 $k≥ 4$，所以接下来修改的字符一定都能满足美丽字符串的条件。

在代码实现上，我们先用一个循环从 $n−1$ 开始，往前遍历来寻找第一个被修改的字符，找到之后，再用另一个函数 $generate(s,idx,offset)$ 来生成修改后的字符，其中 $idx$ 是我们找到的下标，$offset$ 是将这个下标的字符增大的偏移量。最后返回修改后的字符，如果我们未能找到目标下标，则返回空字符串。

class Solution {
    public String smallestBeautifulString(String s, int k) {
        for (int i = s.length() - 1; i >= 0; i--) {
            Set<Character> blockedCharacters = new HashSet<Character>();
            for (int j = 1; j < 3; j++) {
                if (i - j >= 0) {
                    blockedCharacters.add(s.charAt(i - j));
                }
            }
            for (int j = 1; j < 4; j++) {
                // s.charAt(i) - 'a' + j 需要+1才能与k比较，因为k从1计数
                if (s.charAt(i) - 'a' + j + 1 <= k && !blockedCharacters.contains((char) (s.charAt(i) + j))) {
                    return generate(s, i, j);
                }
            }
        }
        return "";
    }

    public String generate(String s, int idx, int offset) {
        char[] res = s.toCharArray();
        res[idx] += offset;
        for (int i = idx + 1; i < s.length(); i++) {
            Set<Character> blockedCharacters = new HashSet<Character>();
            for (int j = 1; j < 3; j++) {
                if (i - j >= 0) {
                    blockedCharacters.add(res[i - j]);
                }
            }
            for (int j = 0; j < 3; j++) {
                // abc里面一定有一个可用的，因为blockedCharacters只有两个字符
                if (!blockedCharacters.contains((char) ('a' + j))) {
                    res[i] = (char) ('a' + j);
                    break;
                }
            }
        }
        return new String(res);
    }
}

参考文献

[1] https://leetcode.cn/problems/maximum-strictly-increasing-cells-in-a-matrix/solutions/2809597/ju-zhen-zhong-yan-ge-di-zeng-de-dan-yuan-ff4v/
[2] https://leetcode.cn/problems/lexicographically-smallest-beautiful-string/solutions/2814311/zi-dian-xu-zui-xiao-de-mei-li-zi-fu-chua-dr81/

后记

首发于 silencezheng.top，转载请注明出处。

赏

谢谢打赏哟！

支付宝

微信