第 207 场周赛回顾

前言

开完班会，回去正好碰上团队搬新楼，只剩下40分钟可以打比赛了。。。差不多够本菜鸡做完前两道题。（给再多时间后面的题我也做不出😅）最终果然只做了前两道。

第一题：重新排列单词间的空格

题解一：模拟

模拟即可，注意考虑单词数为1的边界情况。

class Solution {
    public String reorderSpaces(String text) {
        String[] words = text.trim().split(" +");
        int spaceCount = 0;
        for (char i : text.toCharArray()) {
            if (i == ' ') {
                ++spaceCount;
            }
        }
        int n;
        if (words.length == 1) {
            n = 1;
        } else {
            n = words.length - 1;
        }
        int avgSpace = spaceCount / n;
        StringBuilder spacePart = new StringBuilder();
        for (int i = 0; i < avgSpace; ++i) {
            spacePart.append(' ');
        }
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < n; ++i) {
            ans.append(words[i]);
            ans.append(spacePart);
        }
        if (words.length >= 2) {
            ans.append(words[n]);
        }
        for (int i = 0; i < spaceCount % n; ++i) {
            ans.append(' ');
        }
        return ans.toString();
    }
}

第二题：拆分字符串使唯一子字符串的数目最大

题解一：

用一个集合来存储已经拆分得到的子字符串。递归拆分，对于还没有出现在集合中的子字符串，有拆分加入集合和继续增加字符两种决策；对于已经出现过的子字符串，直接继续增加字符串。

import java.util.HashSet;
import java.util.Set;
class Solution {
    private int max;
    Set<String> set;
    public int maxUniqueSplit(String s) {
        set = new HashSet<>();
        spilt(s, 0);
        return max;
    }
    private void spilt(String s, int begin) {
        if (begin >= s.length()) {
            max = Math.max(max, set.size());
            return;
        }
        for (int i = begin + 1; i <= s.length(); ++i) {
            String subString = s.substring(begin, i);
            // 这个子字符串还没有
            if (!set.contains(subString)) {
                set.add(subString);
                spilt(s, i);
                set.remove(subString);
            }
        }
    }
}

第三题：矩阵的最大非负积

题解一：DFS+剪枝

比赛时第一眼看到就感觉是DP，但是我DP练得还太少了，没有马上想出怎么去建模。做这题的时候只剩10分钟了，看了下数据范围感觉直接DFS暴搜也行。可惜一开始没加对于0的剪枝，最后几个点没过，赛后加上剪枝处理就过了。
注意取余操作再取得最大值返回结果时再进行，中间结果用 long 来存储。

class Solution {
    private long max;
    private int row;
    private int col;
    private final int C = 1000000007;
    public int maxProductPath(int[][] grid) {
        row = grid.length - 1;
        col = grid[0].length - 1;
        max = -1;
        find(grid, 0, 0, grid[0][0]);
        return (int) (max % C);
    }
    private void find(int[][] map, int x, int y, long ans) {
        if ((x == row) && (y == col)) {
            max = Math.max(max, ans);
            return;
        }
        if (ans == 0) {
            max = Math.max(max, ans);
            return;
        }
        if (x + 1 <= row) {
            find(map, x + 1, y, ans * map[x + 1][y]);
        }
        if (y + 1 <= col) {
            find(map, x, y + 1, ans * map[x][y + 1]);
        }
    }
}

题解二：动态规划

此题算是剑指 Offer 47. 礼物的最大价值的变式。由于在任何一步都有可能出现正负转换，两个负数相乘很有可能得到一个最大的正数，因此对于状态的存储应该包括到达每一格时的最大值和最小值，在动态转移方程上有一定的改变。

最终右下角那格的最大值只需要从 dpMax 中取得即可。

class Solution {
    private final int C = 1000000007;
    public int maxProductPath(int[][] grid) {
        final int row = grid.length;
        final int col = grid[0].length;
        // dpMax[i][j]表示到达(i, j)时的最大值
        long[][] dpMax = new long[row][col];
        // dpMin[i][j]表示到达(i, j)时的最小值
        long[][] dpMin = new long[row][col];
        // 边界情况初始化
        dpMax[0][0] = dpMin[0][0] = grid[0][0];
        for (int i = 1; i < row; ++i) {
            dpMax[i][0] = dpMin[i][0] = dpMax[i - 1][0] * grid[i][0];
        }
        for (int i = 1; i < col; ++i) {
            dpMax[0][i] = dpMin[0][i] = dpMax[0][i - 1] * grid[0][i];
        }
        long[] temp = new long[4];
        for (int i = 1; i < row; ++i) {
            for (int j = 1; j < col; ++j) {
                temp[0] = dpMax[i - 1][j] * grid[i][j];
                temp[1] = dpMin[i - 1][j] * grid[i][j];
                temp[2] = dpMax[i][j - 1] * grid[i][j];
                temp[3] = dpMin[i][j - 1] * grid[i][j];
                dpMax[i][j] = Long.MIN_VALUE;
                dpMin[i][j] = Long.MAX_VALUE;
                for (long t : temp) {
                    dpMax[i][j] = Math.max(dpMax[i][j], t);
                    dpMin[i][j] = Math.min(dpMin[i][j], t);
                }
            }
        }
        return Math.max((int) (dpMax[row - 1][col - 1] % C), -1);
    }
}

第四题：

题解一：

思路