废话不多说,我们来直接看题目!没参与本次周赛的小伙伴也可以先点进去自己试试看!第 384 场周赛 - 力扣(LeetCode)
第一题:修改矩阵
题目
题析
好的家人们,这个第一题,我们也是必须拿下的好吧,一道非常简单的模拟送分题,它的意思是,让我们把矩阵中,值为-1的数,变为它所在这一列最大的值,这样我们只需要模拟它的整个过程就行咯!
最简单的思路就是,双重遍历一下这个二维数组,一旦遍历到是-1,就把它替换成它这一列最大的数就OK了。果然简单到爆炸啊家人们,来,我们这就开干!
代码
/**
* @param {number[][]} matrix
* @return {number[][]}
*/
var modifiedMatrix = function(matrix) {
// 特判
if (!matrix || matrix.length === 0 || matrix[0].length === 0) return matrix;
//设置辅助函数 -> 用于计算每列的最大值
const big = a => {
let res = matrix[0][a];
for (let i = 1; i < matrix.length; i++) {
if (matrix[i][a] > res) {
res = matrix[i][a];
}
}
return res;
};
//双重遍历每个值,遇到-1则替换
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == -1) {
matrix[i][j] = big(j);
}
}
}
return matrix;
};
当然啦,靓仔,你可能会想到去优化一下代码,毕竟我们在计算的过程中,是会涉及到重复计算每列的最大值等等,还不如用一个Map、Set去缓存或递推等很多优化方式,但是捏,笔者认为,对于这道题,这种影响作用并不是很明显,得不偿失,第一题我们就到此为止,非常简单!
第二题:匹配模式数组的子数组数目I
题目
题析
看完题目,可见,出题人这小子还是有点老滑头啊,这铺天盖地的文字,属实是让人看了有点伤脑筋,其实,总的来说,题目的意思是:现在我有两个字符串,一个叫主串,另一个叫模板串,我需要在主串中,寻找能够匹配模板串的“子串”数量(这里的“子串”即主串的子集)
代码
咦,你会不会听完有种感觉,这不就是我们普通的字符串匹配问题嘛,我只需要找到主串中能够匹配到完整模板串的“子串”数量不就好了,如果是这样,我们很容易想到的一个做法是,我首先先设置一个变量count,用于记录“子串”数量,其次,我通过遍历主串,在每次循环中,以遍历到的这个索引为起始点,去判断它是否满足模板串,如果满足,则count加1,最后循环走完了,这个count不就是我们所要求的“子串”数量嘛,诶,还真是个不错的想法,我酷酷暴力,不说了,直接动手!
/**
* @param {number[]} nums
* @param {number[]} pattern
* @return {number}
*/
var countMatchingSubarrays = function(nums, pattern) {
let count = 0;
const n = nums.length;
const m = pattern.length;
for (let i = 0; i <= n - m - 1; i++) {
let matches = true;
//用于判断其是否满足模板串
for (let k = 0; k < m; k++) {
if ((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]))) {
matches = false;
break;
}
}
if (matches) {
count++;
}
}
return count;
};
诶嘿,还真有点小帅,两道签到题,做得我美滋滋!
第三题:回文字符串的最大数量
题目
题析
简单来说,题目的意思是,给出一个数组,数组里面包含了多个字符串,我们拥有一种能力,就是我们可以随意交换这些字符串中的任意两个字符(包括不同字符串上的字符,均可),这些操作,是为了保证这个数组中所拥有的回文字符串的数量最大,这个数量,就是我们本题的解!
emm....看完感觉还是有点棘手的,毕竟在做交换的时候,我们不仅要考虑到我们此次交换是否能生成一个回文串,而且还要保证说,此次交换是否为全局的最优解,会不会影响其他回文串。
啊!想到这里,如果我关用模拟的思路去走的话,我的脑海里为什么全是贪心跟dp呢,那我要不然换种思路,我们知道,不管我们交换多少次,数组里面每个字符串的长度都是不能发生改变的,只是原来的布局发生了变化,那我们不妨将所有的字符都拿出来,然后对他们进行排布,保证尽可能多地凑齐回文串,这样不就可以了嘛。(提到尽可能多,短的自然会比长的容易凑齐回文串,所以,我们选择先凑短的回文串,再考虑长的)
代码
/**
* @param {string[]} words
* @return {number}
*/
var maxPalindromesAfterOperations = function(words) {
//统计每个字母出现的次数
const arr=new Array(26).fill(0)
for(const word of words){
for(const s of word){
const i=s.charCodeAt()-'a'.charCodeAt()
arr[i]+=1
}
}
//计算可以用来组成回文串的一侧的字母的个数
let left=arr.reduce((pre,cur)=>pre+=(cur>>1),0)
//按照字符串长度,从小到大填入字母
let ans=0
words.sort((a,b)=>(a.length-b.length))
for(const word of words){
const len=word.length>>1
if(left<len){
break
}
left-=len
ans+=1
}
return ans
};
第四题:匹配模式数组的子数组数目II
题目
题目与第二问一样,与第二问不同的是,此时的数据量变大了!
在问题二中,遍历数组的方法,显而易见,它的时间复杂度:O((N-M+1)*M),其中N是主串的长度,M是模板串的长度。
咦,小鬼,这时候,你想想,如果数组特别大的话,这种相乘的形式,它的效率是非常之慢的!那有没有其他更好的解决方案呢?
那当然有!就是我们大名鼎鼎的KMP算法,对于这一小问,你有没有发现,它无非就是想在主串里面,寻找符合模板串的“子串”个数嘛,第一个阻碍我们的就是,主串它的格式,并不能直接将它与模板串进行比对得到,那我们为什么不能先将主串转为模板串的格式,接下来的工作,我们就只需要找到,主串中含有多少个模板串不就好了嘛,至于如何找到有多少个,那就是用KMP算法来帮助我们解决!
对于KMP算法还不太熟悉的伙伴,这里推荐看以下两个视频,相信你能有所收获!【天勤考研】KMP算法易懂版,KMP算法之求next数组代码讲解
/**
* @param {number[]} nums
* @param {number[]} pattern
* @return {number}
*/
var countMatchingSubarrays = function (nums, pattern) {
let arr = [];
// 将主串转换为模板串的格式
for (let i = 0; i < nums.length - 1; i++) {
arr.push(nums[i] > nums[i + 1] ? -1 : (nums[i] < nums[i + 1] ? 1 : 0));
}
const next = getNext(pattern);
// 获取next数组
function getNext(pattern) {
const m = pattern.length;
const next = Array(m).fill(0);
for (let i = 1, j = 0; i < m; i++) {
while (j > 0 && pattern[i] !== pattern[j]) {
j = next[j - 1];
}
if (pattern[i] === pattern[j]) {
next[i] = ++j;
}
}
return next;
}
// 匹配的过程
function kmp(arr, pattern) {
const n = arr.length;
const m = pattern.length;
let i = 0;
let j = 0;
let count = 0;
while (i < n) {
if (pattern[j] === arr[i]) {
i++;
j++;
}
if (j === m) {
count++;
j = next[j - 1];
} else if (i < n && pattern[j] !== arr[i]) {
if (j !== 0) {
j = next[j - 1];
} else {
i++;
}
}
}
return count;
}
return kmp(arr, pattern)
};
此时KMP算法的时间复杂度为O(N+M),其中N是主串的长度,M是模板串的长度。这里,你能否感受到KMP的强大之处呢!
最后,祝大家新年快乐,新的一年要天天开心呀!文章来源:https://www.toymoban.com/news/detail-836781.html
文章来源地址https://www.toymoban.com/news/detail-836781.html
到了这里,关于LeetCode 第384 场周赛题解(JavaScript版)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!