LeetCode Contest 437

欢迎大家加QQ群：623375442，可以方便群里面交流。

100531. Find Special Substring of Length K

给你一个字符串 s 和一个整数 k。

判断是否存在一个长度 恰好 为 k 的子字符串，该子字符串需要满足以下条件：

1. 该子字符串 只包含一个唯一字符（例如，"aaa" 或 "bbb"）。
2. 如果该子字符串的 前面 有字符，则该字符必须与子字符串中的字符不同。
3. 如果该子字符串的 后面 有字符，则该字符也必须与子字符串中的字符不同。

如果存在这样的子串，返回 true；否则，返回 false。

子字符串 是字符串中的连续、非空字符序列。

测试样例：

输入：s = "aaabaaa", k = 3

输出：true

解释：子字符串 s[4..6] == "aaa" 满足条件：

• 长度为 3。
• 所有字符相同。
• 子串 "aaa" 前的字符是 'b'，与 'a' 不同。
• 子串 "aaa" 后没有字符。

解答：暴力遍历。

class Solution {
    public boolean hasSpecialSubstring(String s, int k) {
        for (int i = 0; i <= s.length() - k; ++i) {
            char c = s.charAt(i);
            if (i - 1 >= 0 && s.charAt(i - 1) == c) continue;
            if (i + k < s.length() && s.charAt(i + k) == c) continue;
            boolean isValid = true;
            for (int j = 0; j < k; ++j) {
                if (s.charAt(i + j) != c) {
                    isValid = false;
                    break;
                }
            }
            if (isValid) return true;
        }
        return false;
    }
}

100590. Eat Pizzas!

给你一个长度为 n 的整数数组 pizzas，其中 pizzas[i] 表示第 i 个披萨的重量。每天你会吃 恰好 4 个披萨。由于你的新陈代谢能力惊人，当你吃重量为 W、X、Y 和 Z 的披萨（其中 W <= X <= Y <= Z）时，你只会增加 1 个披萨的重量！体重增加规则如下：

• 在 奇数天（按 1 开始计数）你会增加 Z 的重量。
• 在 偶数天，你会增加 Y 的重量。

请你设计吃掉 所有 披萨的最优方案，并计算你可以增加的 最大 总重量。

注意：保证 n 是 4 的倍数，并且每个披萨只吃一次。

测试样例：

输入：pizzas = [1,2,3,4,5,6,7,8]

输出：14

解释：

• 第 1 天，你吃掉下标为 [1, 2, 4, 7] = [2, 3, 5, 8] 的披萨。你增加的重量为 8。
• 第 2 天，你吃掉下标为 [0, 3, 5, 6] = [1, 4, 6, 7] 的披萨。你增加的重量为 6。

吃掉所有披萨后，你增加的总重量为 8 + 6 = 14。

解答：贪婪，计算有多少个奇数天，这些天尽量吃最大重量的披萨，偶数天就只能尽量吃次重的披萨。

class Solution {
    public long maxWeight(int[] pizzas) {
        Arrays.sort(pizzas);
        int days = pizzas.length / 4;
        long res = 0;
        int oddDays = (days - 1) / 2 + 1, evenDays = days - oddDays;
        for (int i = pizzas.length - 1; i >= pizzas.length - oddDays; --i) {
            res += pizzas[i];
        }
        for (int i = pizzas.length - oddDays - 2, j = 0; j < evenDays; ++j, i -= 2) {
            res += pizzas[i];
        }
        return res;
    }
}

100582. Select K Disjoint Special Substrings

给你一个长度为 n 的字符串 s 和一个整数 k，判断是否可以选择 k 个互不重叠的 特殊子字符串 。

特殊子字符串 是满足以下条件的子字符串：

• 子字符串中的任何字符都不应该出现在字符串其余部分中。
• 子字符串不能是整个字符串 s。

注意：所有 k 个子字符串必须是互不重叠的，即它们不能有任何重叠部分。

如果可以选择 k 个这样的互不重叠的特殊子字符串，则返回 true；否则返回 false。

子字符串 是字符串中的连续、非空字符序列。

测试样例：

输入：s = "abcdbaefab", k = 2

输出：true

解释：

• 我们可以选择两个互不重叠的特殊子字符串："cd" 和 "ef"。
• "cd" 包含字符 'c' 和 'd'，它们没有出现在字符串的其他部分。
• "ef" 包含字符 'e' 和 'f'，它们没有出现在字符串的其他部分。

解答：动态规划，先两次遍历计算要覆盖某一个字符，需要的最大范围。利用这个信息，配合动态规划计算是否可以拆分k个小数组。

class Solution {
    public boolean maxSubstringLength(String s, int k) {
        if (k == 0) return true;
        int[][] appear = new int[26][];
        for (int i = 0; i < s.length(); ++i) {
            int o = s.charAt(i) - 'a';
            if (appear[o] == null) {
                appear[o] = new int[]{i,i};
            } else {
                appear[o][1] = i;
            }
        }
        // 每个字符需要的实际范围
        int[][] realRange = new int[26][];
        for (int i = 0; i < 26; ++i) {
            if (appear[i] == null) continue;
            int st = appear[i][0], ed = appear[i][0];
            realRange[i] = new int[]{appear[i][0], appear[i][1]};
            while (st > realRange[i][0] || ed < realRange[i][1]) {
                while (st > realRange[i][0]) {
                    --st;
                    int o = s.charAt(st) - 'a';
                    realRange[i][0] = Math.min(realRange[i][0], appear[o][0]);
                    realRange[i][1] = Math.max(realRange[i][1], appear[o][1]);
                }
                while (ed < realRange[i][1]) {
                    ++ed;
                    int o = s.charAt(ed) - 'a';
                    realRange[i][0] = Math.min(realRange[i][0], appear[o][0]);
                    realRange[i][1] = Math.max(realRange[i][1], appear[o][1]);
                }
            }
        }
        if (k == 1) {
            for (int[] rr : realRange) {
                if (rr == null) continue;
                if (rr[0] != 0 || rr[1] != s.length() - 1) {
                    return true;
                }
            }
            return false;
        }
        Boolean[][] isValid = new Boolean[s.length()][k + 1];
        return helper(isValid, s, 0, k, realRange);
    }

    private boolean helper(Boolean[][] isValid, String s, int pos, int k, int[][] realRange) {
        if (k == 0) return true;
        else if (pos >= s.length()) return false;
        if (isValid[pos][k] == null) {
            int o = s.charAt(pos) - 'a';
            if (pos == realRange[o][0] && helper(isValid, s, realRange[o][1] + 1, k - 1, realRange)) {
                isValid[pos][k] = true;
            } else {
                isValid[pos][k] = helper(isValid, s, pos + 1, k, realRange);
            }
        }
        return isValid[pos][k];
    }
}

100550. Length of Longest V-Shaped Diagonal Segment

给你一个大小为 n x m 的二维整数矩阵 grid，其中每个元素的值为 0、1 或 2。

V 形对角线段 定义如下：

• 线段从 1 开始。
• 后续元素按照以下无限序列的模式排列：2, 0, 2, 0, ...。
• 该线段：
  • 起始于某个对角方向（左上到右下、右下到左上、右上到左下或左下到右上）。
  • 沿着相同的对角方向继续，保持 序列模式 。
  • 在保持 序列模式 的前提下，最多允许 一次顺时针 90 度转向 另一个对角方向。

返回最长的 V 形对角线段 的 长度 。如果不存在有效的线段，则返回 0。

测试样例：

输入：grid = [[2,2,1,2,2],[2,0,2,2,0],[2,0,1,1,0],[1,0,2,2,2],[2,0,0,2,2]]

输出：5

解释：最长的 V 形对角线段长度为 5，路径如下：(0,2) → (1,3) → (2,4)，在 (2,4) 处进行 顺时针 90 度转向 ，继续路径为 (3,3) → (4,2)。

解答：这个代码有点没写好。主要是4个方向遍历4次矩阵。计算每个方向的最长距离

class Solution {
    private static final int[][] moves = {{-1,-1},{-1,1},{1,-1},{1,1}};
    private static final int[] counterParty = {1,3,0,2};

    public int lenOfVDiagonal(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][][] dp = new int[m][n][4];
        for (int i = 0; i < 4; ++i) {
            int[] mv = moves[i];
            int xst = mv[0] == -1 ? 0 : m - 1, xdir = -mv[0];
            int yst = mv[1] == -1 ? 0 : n - 1, ydir = -mv[1];
            for (int x = xst; x >= 0 && x < m; x += xdir) {
                for (int y = yst; y >= 0 && y < n; y += ydir) {
                    int xt = x + mv[0], yt = y + mv[1];
                    if (xt >= 0 && xt < m && yt >= 0 && yt < n) {
                        if (grid[x][y] != 1) dp[x][y][i] = 1;
                        if (grid[x][y] == 2 && grid[xt][yt] == 0) {
                            dp[x][y][i] = dp[xt][yt][i] + 1;
                        } else if (grid[x][y] == 0 && grid[xt][yt] == 2) {
                            dp[x][y][i] = dp[xt][yt][i] + 1;
                        }
                    } else if (grid[x][y] == 2 || grid[x][y] == 0) {
                        dp[x][y][i] = 1;
                    }
                }
            }
        }
        int res = 0;
        for (int i = 0; i < 4; ++i) {
            int[] mv = moves[i];
            int xst = mv[0] == -1 ? 0 : m - 1, xdir = -mv[0];
            int yst = mv[1] == -1 ? 0 : n - 1, ydir = -mv[1];
            int[] rowDp = new int[n];
            for (int x = xst; x >= 0 && x < m; x += xdir) {
                int[] nextRowDp = new int[n];
                for (int y = yst; y >= 0 && y < n; y += ydir) {
                    int xt = x + mv[0], yt = y + mv[1];
                    if (xt >= 0 && xt < m && yt >= 0 && yt < n) {
                        if (grid[x][y] == 1) {
                            if (grid[xt][yt] == 2) res = Math.max(res, rowDp[yt] + 1);
                            else res = Math.max(res, 1);
                        } else if (grid[x][y] == 2) {
                            nextRowDp[y] = dp[x][y][counterParty[i]];
                            if (grid[xt][yt] == 0) nextRowDp[y] = Math.max(nextRowDp[y], rowDp[yt] + 1);
                        } else if (grid[x][y] == 0) {
                            nextRowDp[y] = dp[x][y][counterParty[i]];
                            if (grid[xt][yt] == 2) nextRowDp[y] = Math.max(nextRowDp[y], rowDp[yt] + 1);
                        }
                    } else if (grid[x][y] == 2 || grid[x][y] == 0) {
                        nextRowDp[y] = dp[x][y][counterParty[i]];
                    } else {
                        res = Math.max(res, 1);
                    }
                }
                rowDp = nextRowDp;
            }
        }
        return res;
    }
}

补充一个Rust代码版本

static MOVES:[[i32;2];4] = [[-1,-1],[-1,1],[1,-1],[1,1]];
static COUNTER_PARTY:[usize;4] = [1,3,0,2];

impl Solution {
    pub fn len_of_v_diagonal(grid: Vec<Vec<i32>>) -> i32 {
        let m = grid.len();
        let n = grid[0].len();
        let mut dp = vec![vec![[0;4];n];m];
        for i in 0..MOVES.len() {
            let mv = MOVES[i];
            let xst: i32 = if mv[0] == -1 {0} else {m as i32 - 1};
            let xdir = -mv[0];

            let yst: i32 = if mv[1] == -1 {0} else {n as i32 - 1};
            let ydir = -mv[1];

            let mut xp = xst;
            while xp >= 0 && xp < m as i32 {
                let mut yp = yst;
                while yp >= 0 && yp < n as i32 {
                    let x = xp as usize;
                    let y = yp as usize;

                    let xt = xp + mv[0];
                    let yt = yp + mv[1];
                    if xt >= 0 && xt < m as i32 && yt >= 0 && yt < n as i32 {
                        let xt = xt as usize;
                        let yt = yt as usize;
                        if grid[x][y] != 1 {
                            dp[x][y][i] = 1;
                        }
                        if grid[x][y] == 2 && grid[xt][yt] == 0 {
                            dp[x][y][i] = dp[xt][yt][i] + 1;
                        } else if grid[x][y] == 0 && grid[xt][yt] == 2 {
                            dp[x][y][i] = dp[xt][yt][i] + 1;
                        }
                    } else if grid[x][y] == 2 || grid[x][y] == 0 {
                        dp[x][y][i] = 1;
                    }
                    yp += ydir;
                }
                xp += xdir;
            }
        }

        let mut res: i32 = 0;
        for i in 0..4 {
            let mv = MOVES[i];
            let xst: i32 = if mv[0] == -1 {0} else {m as i32 - 1};
            let xdir = -mv[0];

            let yst: i32 = if mv[1] == -1 {0} else {n as i32 - 1};
            let ydir = -mv[1];

            let mut xp = xst;
            let mut row_dp = vec![0;n];
            while xp >= 0 && xp < m as i32 {
                let mut yp = yst;
                let mut next_row_dp = vec![0;n];
                while yp >= 0 && yp < n as i32 {
                    let x = xp as usize;
                    let y = yp as usize;

                    let xt = xp + mv[0];
                    let yt = yp + mv[1];
                    if xt >= 0 && xt < m as i32 && yt >= 0 && yt < n as i32 {
                        let xt = xt as usize;
                        let yt = yt as usize;
                        if grid[x][y] == 1 {
                            if grid[xt][yt] == 2 {res = res.max(row_dp[yt] + 1)}
                            else {res = res.max(1)};
                        } else if grid[x][y] == 2 {
                            next_row_dp[y] = dp[x][y][COUNTER_PARTY[i]];
                            if grid[xt][yt] == 0 {
                                next_row_dp[y] = next_row_dp[y].max(row_dp[yt] + 1);
                            }
                        } else {
                            next_row_dp[y] = dp[x][y][COUNTER_PARTY[i]];
                            if grid[xt][yt] == 2 {
                                next_row_dp[y] = next_row_dp[y].max(row_dp[yt] + 1);
                            }
                        }
                    } else if grid[x][y] == 2 || grid[x][y] == 0 {
                        next_row_dp[y] = dp[x][y][COUNTER_PARTY[i]];
                    } else {
                        res = res.max(1);
                    }
                    yp += ydir;
                }
                row_dp = next_row_dp;
                xp += xdir;
            }
        }
        res
    }
}