LeetCode Contest 384

100230. Modify the Matrix

给你一个下标从 0 开始、大小为 m x n 的整数矩阵 matrix ，新建一个下标从 0 开始、名为 answer 的矩阵。使 answer 与 matrix 相等，接着将其中每个值为 -1 的元素替换为所在列的 最大 元素。

返回矩阵 answer 。

测试样例：

输入：matrix = [[1,2,-1],[4,-1,6],[7,8,9]]

输出：[[1,2,9],[4,8,6],[7,8,9]]

解释：发生替换的元素

• 将单元格 [1][1] 中的值替换为列 1 中的最大值 8 。
• 将单元格 [0][2] 中的值替换为列 2 中的最大值 9 。

解答：按照题意先计算每列的最大值，然后第二次扫描的时候把-1替换。

class Solution {
    public int[][] modifiedMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[] mem = new int[n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                mem[j] = Math.max(mem[j], matrix[i][j]);
            }
        }

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == -1) {
                    matrix[i][j] = mem[j];
                }
            }
        }
        return matrix;
    }
}

100219. Maximum Palindromes After Operations

给你一个下标从 0 开始的字符串数组 words ，数组的长度为 n ，且包含下标从 0 开始的若干字符串。

你可以执行以下操作 任意 次数（包括零次）：

-选择整数i、j、x和y，满足0 <= i, j < n，0 <= x < words[i].length，0 <= y < words[j].length，交换 字符 words[i][x] 和 words[j][y] 。

返回一个整数，表示在执行一些操作后，words 中可以包含的回文字符串的 最大 数量。

注意：在操作过程中，i 和 j 可以相等。

测试样例：

输入：words = ["abbb","ba","aa"]

输出：3

解释：在这个例子中，获得最多回文字符串的一种方式是：选择 i = 0, j = 1, x = 0, y = 0，交换 words[0][0] 和 words[1][0] 。words 变成了 ["bbbb","aa","aa"] 。words 中的所有字符串都是回文。因此，可实现的回文字符串的最大数量是 3 。

解答：这题主要需要判断有多少字符是奇数个出现的和多少的字符串是奇数个长度。如果奇数字符小于奇数字符串数，所有字符串都能变成回文。否则就用贪婪算法，优先把较短的字符串变回文。

class Solution {
    public int maxPalindromesAfterOperations(String[] words) {
        int[] count = new int[26];
        int oddCount = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (String w : words) {
            if (w.length() % 2 == 1) {
                oddCount += 1;
                queue.add(w.length() - 1);
            } else {
                queue.add(w.length());
            }
            for (int i = 0; i < w.length(); ++i) {
                count[w.charAt(i) - 'a'] += 1;
            }
        }

        int oddChar = 0, evenCount = 0;
        for (int i = 0; i < count.length; ++i) {
            if (count[i] % 2 == 1) {
                ++oddChar;
                evenCount += count[i] - 1;
            } else {
                evenCount += count[i];
            }
        }

        if (oddChar <= oddCount) {
            return words.length;
        } else {
            int res = 0;
            while (evenCount >= 0 && !queue.isEmpty()) {
                int tmp = queue.peek();
                if (evenCount >= tmp) {
                    queue.poll();
                    evenCount -= tmp;
                    ++res;
                } else {
                    break;
                }
            }
            return res;
        }
    }
}

100198. Number of Subarrays That Match a Pattern II

给你一个下标从 0 开始长度为 n 的整数数组 nums ，和一个下标从 0 开始长度为 m 的整数数组 pattern ，pattern 数组只包含整数 -1 ，0 和 1 。

大小为 m + 1 的子数组 nums[i..j] 如果对于每个元素 pattern[k] 都满足以下条件，那么我们说这个子数组匹配模式数组 pattern ：

• 如果 pattern[k] == 1 ，那么 nums[i + k + 1] > nums[i + k]
• 如果 pattern[k] == 0 ，那么 nums[i + k + 1] == nums[i + k]
• 如果 pattern[k] == -1 ，那么 nums[i + k + 1] < nums[i + k]

请你返回匹配 pattern 的 nums 子数组的 数目 。

测试样例：

输入：nums = [1,2,3,4,5,6], pattern = [1,1]

输出：4

解释：模式 [1,1] 说明我们要找的子数组是长度为 3 且严格上升的。在数组 nums 中，子数组 [1,2,3] ，[2,3,4] ，[3,4,5] 和 [4,5,6] 都匹配这个模式。所以 nums 中总共有 4 个子数组匹配这个模式。

解答：第二题和第四题一样，我就不重复写了。这题可以用kmp算法计算。

class Solution {
    public int countMatchingSubarrays(int[] nums, int[] pattern) {
        int[] fail = kmp(pattern);
        int match = -1, res = 0;
        int n = nums.length;
        for (int i = 1; i < n; ++i) {
            int curNum = Integer.compare(nums[i], nums[i - 1]);
            while (match != -1 && pattern[match + 1] != curNum) {
                match = fail[match];
            }
            if (pattern[match + 1] == curNum) {
                ++match;
                if (match == pattern.length - 1) {
                    ++res;
                    match = fail[match];
                }
            }
        }

        return res;
    }

    public int[] kmp(int[] pattern) {
        int m = pattern.length;
        int[] fail = new int[m];
        Arrays.fill(fail, -1);
        for (int i = 1; i < m; ++i) {
            int j = fail[i - 1];
            while (j != -1 && pattern[j + 1] != pattern[i]) {
                j = fail[j];
            }
            if (pattern[j + 1] == pattern[i]) {
                fail[i] = j + 1;
            }
        }
        return fail;
    }
}

最后祝大家龙年快乐！