算法提升——LeetCode第384场周赛总结

本文主要是介绍算法提升——LeetCode第384场周赛总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

修改矩阵

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

返回矩阵answer。

解题思路

先计算每一列最大值，再更新-1的值。

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

匹配模式数组的子数组数目 I

给你一个下标从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子数组的数目。

解题思路

循环遍历每一个数组判断是否符合条件。

class Solution {public int countMatchingSubarrays(int[] nums, int[] pattern) {int count = 0;int n = nums.length, m = pattern.length;for (int i = 0, j = m - 1; j < n - 1; i++, j++) {boolean flag = true;for (int k = 0; k < m && flag; k++) {int diff = nums[i + k + 1] - nums[i + k];int currPattern = getPattern(diff);if (currPattern != pattern[k]) {flag = false;}}if (flag) {count++;}}return count;}public int getPattern(int diff) {if (diff == 0) {return 0;} else {return diff > 0 ? 1 : -1;}}
}

回文字符串的最大数量

给你一个下标从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可以相等。

解题思路

统计每一个字符出现的次数后，针对奇数字符串最后考虑中间字符。

class Solution {public int maxPalindromesAfterOperations(String[] words) {int oddLetters = 0, oddWords = 0;Set<Character> oddSet = new HashSet<Character>();List<Integer> wordLengths = new ArrayList<Integer>();for (String word : words) {int wordLength = word.length();for (int i = 0; i < wordLength; i++) {char c = word.charAt(i);if (!oddSet.contains(c)) {oddLetters++;oddSet.add(c);} else {oddLetters--;oddSet.remove(c);}}if (wordLength % 2 != 0) {oddWords++;wordLength -= wordLength % 2;}wordLengths.add(wordLength);}Collections.sort(wordLengths, (a, b) -> b - a);int maxPalindromes = words.length;int remain = oddLetters - oddWords;for (int wordLength : wordLengths) {if (remain <= 0) {break;}remain -= wordLength;maxPalindromes--;}return maxPalindromes;}
}

匹配模式数组的子数组数目 II

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

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

解题思路

本题跟第二道题类似，不过学习题解之后发现可以通过KMP算法解决。将数组替换为1,0,-1的关系，然后求有多少个数组符合pattern

class Solution {public int countMatchingSubarrays(int[] nums, int[] pattern) {int m = pattern.length;int[] pi = new int[m];int cnt = 0;for (int i = 1; i < m; i++) {int v = pattern[i];while (cnt > 0 && pattern[cnt] != v) {cnt = pi[cnt - 1];}if (pattern[cnt] == v) {cnt++;}pi[i] = cnt;}int ans = 0;cnt = 0;for (int i = 1; i < nums.length; i++) {int v = Integer.compare(nums[i], nums[i - 1]);while (cnt > 0 && pattern[cnt] != v) {cnt = pi[cnt - 1];}if (pattern[cnt] == v) {cnt++;}if (cnt == m) {ans++;cnt = pi[cnt - 1];}}return ans;}
}