网站怎么做才有百度权重,阳江房产网春天尚院,金坛市住房和城乡建设局 网站,wordpress the7 使用目录
一#xff0c;3033. 修改矩阵
二#xff0c;3035. 回文字符串的最大数量
三#xff0c;3036. 匹配模式数组的子数组数目 II 一#xff0c;3033. 修改矩阵 这道题直接暴力求解#xff0c;先算出每一列的最大值#xff0c;再将所有为-1的区域替换成该列的最大值3033. 修改矩阵
二3035. 回文字符串的最大数量
三3036. 匹配模式数组的子数组数目 II 一3033. 修改矩阵 这道题直接暴力求解先算出每一列的最大值再将所有为-1的区域替换成该列的最大值代码如下
class Solution {public int[][] modifiedMatrix(int[][] matrix) {int n matrix.length;int m matrix[0].length;int[] max new int[m];for(int j0; jm; j){for(int i0; in; i){//得到每列的最大值max[j] Math.max(max[j],matrix[i][j]);}}for(int i0; in; i){for(int j0; jm; j){if(matrix[i][j] -1){//是-1就进行替换matrix[i][j] max[j];}}}return matrix;}
}
二3035. 回文字符串的最大数量
这道题是问我们怎样交换可以使words数组包含最大数量的回文串注意只要输出回文串的最大数量。再仔细看题就会发现这些数组中字符都是可以相互交换的也就是说我们可以先使用hash或者int[26]题目说了只包含小写字母来统计一下words数组中包含哪些字符及其对应的数目再自己构造出固定长度的回文字符串。
这时还有一个问题就是如何保证我们构造的字符串的数目一定是最大的这里我们就要使用贪心的思想了我们可以先得到words数组中字符串的长度并将其从小到大排序再根据长度从小到大来构造回文字符串这样就可以保证构造出的回文字符串的数目是最大的。
其实再进一步想一想回文字符串的特点是什么不就是对称吗也就是说我们根本不需要知道各个字符的数量只需要知道有多少成对的字符使用two代替又有多少单个字符使用one来代替。 大体思路想好了剩下的就是如何构造字符串假设我们要构造长度为x的回文字符串 1剩下的字符可以构造出字符串 即 two - x/2 0 one - x%2 0同时ans 2剩下的字符不可以构造出字符串: 缺少成对的字符 这时直接返回因为我们是从小到大来构造字符串的如果这个构造的字符串缺少成对的字符那么后面的也一定缺少即 two - x/2 0缺少单个字符即 one - x%2 0 这时候我们要看two是否还多余如果多余我们可以从two中拿出一个同时ans (注意当我们从two中拿出一个时我们的one也要同时1相当于是将一个成对的字符拆成单个字符来使用)如果缺少直接返回。 进阶上述讨论的2.2这种情况真的存在吗 我们这样想一想当答案就等于words.length的时候two是最大的one是最小的而当one是最小的时候他也能满足单个字符的需求也就是说我们不需要关心one只需要关心two即 two - x/2 0 或者 two - x/2 0当 0 时 ans当 0 时直接返回答案。 上代码
class Solution {public int maxPalindromesAfterOperations(String[] words) {int[] m new int[26];//统计各个字符出现的次数int[] t new int[words.length];//统计words数组中字符串的长度for(int i0; iwords.length; i){t[i] words[i].length(); for(char ch : words[i].toCharArray()){m[ch-a];}}Arrays.sort(t);//从小到大排序int two 0;//统计成对字符的数目for(int i0; i26; i){two m[i]/2;}int ans 0;for(int x : t){//从小到大构造回文字符串if(two-x/20){two - x/2;ans;}else{return ans;}}return ans; }
}
三3036. 匹配模式数组的子数组数目 II 这周周赛的二四题是相同的这里就一起讲了。 该题的关键点在于是否能将这道题转换成一个 字符串匹配 问题 我们通过题目给的条件 nums[i] - nums[i-1] 0t[i-1] 1 nums[i] - nums[i-1] 0, t[i-1] 0nums[i] - nums[i-1] 0, t[i-1] -1 可以得到一个 int[] t new int[nums.length-1] 的数组然后通过kmp算法求数组 t 中有多少和数组pattern相同的字数组。 代码如下
class Solution {public int countMatchingSubarrays(int[] nums, int[] pattern) {int n nums.length;int[] t new int[n-1];for(int i1; in; i){if(nums[i]-nums[i-1]0)t[i-1] 0;else if(nums[i]-nums[i-1]0)t[i-1] 1;else t[i-1] -1;}//求next数组int k pattern.length;int[] next new int[k];for(int i1, j0; ik; i){while(j0pattern[i]!pattern[j]){j next[j-1];}if(pattern[i]pattern[j])j;next[i] j;}//字符串匹配int ans 0;for(int i0, j0; in-1; i){while(j0jkt[i]!pattern[j]){j next[j-1];}if(t[i]pattern[j])j;if(jk){j next[j-1];ans;}}return ans;}
}
除了KMP算法之外还可以通过Z函数算法来求解下面简单来讲一讲Z函数算法的思想和KMP的思路差不多只不过kmp中的 next 数组是用来求字符串中的最长前后缀而Z函数中的 z 数组则是用来求字符串的最长前前缀举一个例子 使用该方法麻烦的点是需要手动的将 pattern 数组添加到 t 数组的前面然后只需要统计 z[i] i pattern.length大于等于 pattern.length 的数目就行了。
class Solution {public int countMatchingSubarrays(int[] nums, int[] pattern) {int n nums.length;int[] t new int[n-1];for(int i1; in; i){if(nums[i]-nums[i-1]0)t[i-1] 0;else if(nums[i]-nums[i-1]0)t[i-1] 1;else t[i-1] -1;}ListInteger ls new ArrayList();for(int x : pattern) ls.add(x);for(int x : t) ls.add(x);int ans 0;int k pattern.length;int[] z new int[ls.size()];int l0, r0;for(int i1; ils.size(); i){if(i r)z[i] Math.min(z[i-l], r-i1);while(iz[i]ls.size() ls.get(z[i]) ls.get(iz[i])){l i;r i z[i];z[i];}if(ik z[i]k) ans;}return ans;}
}
