标签： medium

目标

给你一个由 正整数 组成、大小为 m x n 的矩阵 grid。你可以从矩阵中的任一单元格移动到另一个位于正下方或正右侧的任意单元格（不必相邻）。从值为 c1 的单元格移动到值为 c2 的单元格的得分为 c2 - c1 。

你可以从 任一 单元格开始，并且必须至少移动一次。

返回你能得到的 最大 总得分。

示例 1：

输入：grid = [[9,5,7,3],[8,9,6,1],[6,7,14,3],[2,5,3,1]]
输出：9
解释：从单元格 (0, 1) 开始，并执行以下移动：
- 从单元格 (0, 1) 移动到 (2, 1)，得分为 7 - 5 = 2 。
- 从单元格 (2, 1) 移动到 (2, 2)，得分为 14 - 7 = 7 。
总得分为 2 + 7 = 9 。

示例 2：

输入：grid = [[4,3,2],[3,2,1]]
输出：-1
解释：从单元格 (0, 0) 开始，执行一次移动：从 (0, 0) 到 (0, 1) 。得分为 3 - 4 = -1 。

说明：

• m == grid.length
• n == grid[i].length
• 2 <= m, n <= 1000
• 4 <= m * n <= 10^5
• 1 <= grid[i][j] <= 10^5

思路

有一个二维矩阵 grid，可以从任意格子出发向下或右移动（不必相邻），移动的得分为元素值之差 to - from，求最大的得分数。

首先想到动态规划，关键点是想清楚最大得分其实就是以当前元素为左上顶点（不包括其自身），以 m - 1, n - 1 为右下顶点的矩形中的最大值减去当前元素值。如果把状态定义错误还是会超时的，比如当前元素出发所能取得的最大值，需要依次向下/向右比较，时间复杂度 O(m * n * (m +n))，m = 1000 n = 95，循环次数 10^5 * (10^3 + 95) 超时，耗时878 ms，下午又提交了几次，耗时 1200 ~ 1300 ms。参考特殊数组II 中的时间复杂度分析。对于O(n)的算法，10^8 差不多就是极限了，单个用例在1s左右，多个肯定超时。

代码

/**
 * @date 2024-08-15 0:22
 */
public class MaxScore3148 {

    /**
     * 修改了dp的定义，表示以i,j为起点到右下的矩形的最大值
     * 执行通过
     */
    public int maxScore_v2(List<List<Integer>> grid) {
        int m = grid.size();
        int n = grid.get(0).size();
        int[][] dp = new int[m][n];
        int res = Integer.MIN_VALUE;
        dp[m - 1][n - 1] = grid.get(m - 1).get(n - 1);
        for (int i = n - 2; i >= 0; i--) {
            int cur = grid.get(m - 1).get(i);
            // 注意这里使用的是上一个位置为顶点的矩形中的最大值
            res = Math.max(dp[m - 1][i + 1] - cur, res);
            // 如果先进行这个计算，然后再进行上面的计算，就有会出现不移动的情况，但积分只有移动才能取得，可以是负值
            dp[m - 1][i] = Math.max(cur, dp[m - 1][i + 1]);
        }
        for (int i = m - 2; i >= 0; i--) {
            int cur = grid.get(i).get(n - 1);
            res = Math.max(dp[i + 1][n - 1] - cur, res);
            dp[i][n - 1] = Math.max(cur, dp[i + 1][n - 1]);
        }

        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                int cur = grid.get(i).get(j);
                res = Math.max(dp[i + 1][j] - cur, res);
                res = Math.max(dp[i][j + 1] - cur, res);
                dp[i][j] = Math.max(cur, dp[i + 1][j]);
                dp[i][j] = Math.max(dp[i][j], dp[i][j + 1]);
            }
        }
        return res;
    }

    /**
     * 560 / 564 超时  m = 1000  n = 95
     * O(m * n * (m +n)) 循环次数 10^5 * (10^3 + 95)
     * 878 ms
     */
    public int maxScore_v1(List<List<Integer>> grid) {
        int m = grid.size();
        int n = grid.get(0).size();
        int[][] dp = new int[m][n];
        for (int[] row : dp) {
            Arrays.fill(row, Integer.MIN_VALUE);
        }
        dp[m - 1][n - 1] = 0;
        int res = Integer.MIN_VALUE;
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                int diff = grid.get(m - 1).get(j) - grid.get(m - 1).get(i);
                if (dp[m - 1][j] > 0) {
                    dp[m - 1][i] = Math.max(diff + dp[m - 1][j], dp[m - 1][i]);
                }
                dp[m - 1][i] = Math.max(diff, dp[m - 1][i]);
            }
            res = Math.max(dp[m - 1][i], res);
        }
        for (int i = m - 2; i >= 0; i--) {
            for (int j = i + 1; j < m; j++) {
                int diff = grid.get(j).get(n - 1) - grid.get(i).get(n - 1);
                if (dp[j][n - 1] > 0) {
                    dp[i][n - 1] = Math.max(diff + dp[j][n - 1], dp[i][n - 1]);
                }
                dp[i][n - 1] = Math.max(diff, dp[i][n - 1]);
            }
            res = Math.max(dp[i][n - 1], res);
        }

        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                for (int h = i + 1; h < m; h++) {
                    int rowDiff = grid.get(h).get(j) - grid.get(i).get(j);
                    if (dp[h][j] > 0) {
                        dp[i][j] = Math.max(rowDiff + dp[h][j], dp[i][j]);
                    }
                    dp[i][j] = Math.max(rowDiff, dp[i][j]);
                }
                for (int k = j + 1; k < n; k++) {
                    int colDiff = grid.get(i).get(k) - grid.get(i).get(j);
                    if (dp[i][k] > 0) {
                        dp[i][j] = Math.max(colDiff + dp[i][k], dp[i][j]);
                    }
                    dp[i][j] = Math.max(colDiff, dp[i][j]);
                }
                res = Math.max(dp[i][j], res);
            }
        }
        return res;
    }

}

性能

目标

如果数组的每一对相邻元素都是两个奇偶性不同的数字，则该数组被认为是一个 特殊数组 。

有一个整数数组 nums 和一个二维整数矩阵 queries，对于 queries[i] = [fromi, toi]，请你帮助检查子数组 nums[fromi..toi] 是不是一个 特殊数组 。

返回布尔数组 answer，如果 nums[fromi..toi] 是特殊数组，则 answer[i] 为 true ，否则，answer[i] 为 false 。

示例 1：

输入：nums = [3,4,1,2,6], queries = [[0,4]]
输出：[false]
解释：
子数组是 [3,4,1,2,6]。2 和 6 都是偶数。

示例 2：

输入：nums = [4,3,1,6], queries = [[0,2],[2,3]]
输出：[false,true]
解释：
子数组是 [4,3,1]。3 和 1 都是奇数。因此这个查询的答案是 false。
子数组是 [1,6]。只有一对：(1,6)，且包含了奇偶性不同的数字。因此这个查询的答案是 true。

说明：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5
• 1 <= queries.length <= 10^5
• queries[i].length == 2
• 0 <= queries[i][0] <= queries[i][1] <= nums.length - 1

思路

类似于特殊数组I，只不过是判断子数组是否是特殊数组。我们可以记录奇偶性相同的下标，如果 queries[i] = [fromi, toi] 包含其中的下标对返回false。但是如果所有元素的奇偶性都相同，下标对有n个，查询也是n次，O(n^2) 对于 10^5 的数据规模会超时。

我们可以将问题转化一下，由于仅考虑相邻元素的奇偶性，将数组中的偶数元素都替换为0，奇数元素都替换为1，这样0与1交替出现的是特殊数组。使用前缀和判断不了是否交替出现，只能初步排除一些区间。

之所以超时是因为进行了许多重复判断，我们想直接判断查询区间是否包含奇偶相同的下标对。可以使用二分查找，如果查出的from，to下标相同，说明不相交。

这里比较坑的一点是，题目中没有说明如果查询区间只包含一个值视为奇偶性不同。

log2(10^5) ≈ 16.6 时间复杂度为O(nlogn)，耗时30ms，说明10^6的数据规模，O(n)的解法不会超时，以后多留意一下。

看了题解，其实可以使用前缀和，只不过不是将原数组转为0或1计算前缀和，而是定义数组diff，原数组nums相邻元素奇偶性相同为0，不同为1。对应给定的区间，我们就可以根据diff的前缀和判断是否含有奇偶性相同的元素。时间复杂度为O(n)，耗时3ms。

也有使用动态规划求解的，记录最近一次奇偶性相同的位置。时间复杂度为O(n)，耗时3ms。

代码

/**
 * @date 2024-08-14 9:58
 */
public class IsArraySpecial3152 {

    public boolean[] isArraySpecial_v1(int[] nums, int[][] queries) {
        int n = nums.length;
        List<Integer> from = new ArrayList<>();
        List<Integer> to = new ArrayList<>();
        for (int i = 1; i < n; i++) {
            int j = i - 1;
            if (nums[i] % 2 == nums[j] % 2) {
                from.add(j);
                to.add(i);
            }
        }
        int l = from.size();
        int[] fromArray = new int[l];
        int[] toArray = new int[l];
        for (int i = 0; i < l; i++) {
            fromArray[i] = from.get(i);
            toArray[i] = to.get(i);
        }
        int length = queries.length;
        boolean[] res = new boolean[length];
        Arrays.fill(res, true);
        for (int i = 0; i < length; i++) {
            int[] query = queries[i];
            if (query[0] == query[1]) {
                // 如果查询区间相同认为是特殊区间
                res[i] = true;
                continue;
            }
            int fromIndex = Arrays.binarySearch(fromArray, query[0]);
            if (fromIndex >= 0) {
                // 如果需要查询的数组包含了query[0]，由于前面判断了相等的情况，
                // 执行到这里query[1] > query[0]，而对应的toIndex 为 fromIndex + 1，
                // 推出 query[1] >= toIndex，说明包含奇偶性相同的下标对，
                res[i] = false;
                continue;
            }
            int toIndex = Arrays.binarySearch(toArray, query[1]);
            if (fromIndex != toIndex) {
                // 执行到这里，fromIndex < 0，如果 toIndex >= 0，由于 query[0] < query[1]，推出 query[0] <= fromIndex
                // 如果 toIndex < 0，说明查询区间开始与结束下标都没有找到，
                // 如果插入位置不同，说明也包含了奇偶性相同的元素
                res[i] = false;
            }
        }
        return res;
    }

}

性能

目标

设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。

实现 MagicDictionary 类：

• MagicDictionary() 初始化对象
• void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构，dictionary 中的字符串互不相同
• bool search(String searchWord) 给定一个字符串 searchWord ，判定能否只将字符串中 一个 字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以，返回 true ；否则，返回 false 。

示例：

输入
["MagicDictionary", "buildDict", "search", "search", "search", "search"]
[[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
输出
[null, null, false, true, false, false]

解释
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // 返回 False
magicDictionary.search("hhllo"); // 将第二个 'h' 替换为 'e' 可以匹配 "hello" ，所以返回 True
magicDictionary.search("hell"); // 返回 False
magicDictionary.search("leetcoded"); // 返回 False

说明：

• 1 <= dictionary.length <= 100
• 1 <= dictionary[i].length <= 100
• dictionary[i] 仅由小写英文字母组成
• dictionary 中的所有字符串 互不相同
• 1 <= searchWord.length <= 100
• searchWord 仅由小写英文字母组成
• buildDict 仅在 search 之前调用一次
• 最多调用 100 次 search

思路

实现这样一个数据结构，初始化一个单词列表，查询 给定单词修改一个字母（修改的字母与原字母不能相同）后是否位于字典中。言外之意，要在字典中查找长度相同，但字母有一个不同的单词。

如何判断两个长度 相等 的字符串之间是否只有一个字母不同？直接的想法是逐个字母比较，并记录不同字母的个数，最坏情况下查询的时间复杂度是 O(mn)，m为被查单词的平均长度，n为单词列表长度。

一个更好的想法是构建一颗字典树，这样只需沿着给定单词的路径去查找而无需与字典中单词一一比较，最坏的情况是第一个字母就不同，这样得遍历字典中同级的其它字母下的子树共|Σ|个，时间复杂度降为O(|Σ|m)。最好的情况就是单词的最后一个字母不同，时间复杂度为O(m)。

针对本题的数据范围以及调用次数，暴力解法就足够了，字典树反而体现不出优势。

代码

/**
 * @date 2024-08-12 9:08
 */
public class MagicDictionary676 {

    private String[] dictionary;

    public MagicDictionary676() {

    }

    public void buildDict(String[] dictionary) {
        this.dictionary = dictionary;
    }

    public boolean search(String searchWord) {
        for (String word : dictionary) {
            int length = searchWord.length();
            if (word.length() != length) {
                continue;
            }
            int cnt = 0;
            for (int i = 0; i < length; i++) {
                if (word.charAt(i) != searchWord.charAt(i)) {
                    cnt++;
                }
                if (cnt > 1) {
                    // 提前结束比较，效率有明显提升
                    break;
                }
            }
            if (cnt == 1) {
                return true;
            }
        }
        return false;
    }

}

性能