修改矩阵
给你一个下标从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：
如果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子数组的数目。
解题思路
本题跟第二道题类似，不过学习题解之后发现可以通过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;
}
}