订阅号如何开通_私人网官网_宁波seo网络推广选哪家_微博推广方案

反转字符串II

/*** @param {string} s* @param {number} k* @return {string}*/
var reverseStr = function(s, k) {// //字符串=》字符数组// let sArr=s.split('');// let length=s.length;// //每计数2*k for！！！// for(let i=0;i<length;i+=2*k){//     let left=i;//     //right指向要反转的最后字符们不要mid！//     //三元表达式,判断i+k-1右边的指针是否超过字符长度（2k与2k>=k)，没超过就是交换前k//     //超过标识字符小于k，就全交换剩下的字符//     let right=(i+k-1)>=length?length-1:i+k-1;//     while(left<right){//         [sArr[left],sArr[right]]=[sArr[right],sArr[left]];//         left++;//         right--;//     }// }const reverse=(arr,left,right)=>{while(left<right){[arr[left],arr[right]]=[arr[right],arr[left]];left++;right--;}}//核心是模拟，无需讨论情况，每次跳2k，并判断（当前位置+k）是否越界let arr=s.split('');//2*k不是2kfor(let i=0;i<s.length;i+=2*k){//如果剩余元素大于k/有2k个元素if(i+k-1<s.length){reverse(arr,i,i+k-1);}else{reverse(arr,i,s.length);}}return arr.join(''); 
};

翻转字符串中的单词

/*** @param {string} s* @return {string}*/
var reverseWords = function(s) {/*** @param {string} s* @return {string}*/
var reverseWords = function(s) {//推荐let wordArr=s.split(" ");let filtered=wordArr.filter(item=>item!=="");let length=filtered.length;let right=length-1;for(let left=0;left<length;left++){if(left>=right){break;}[filtered[left],filtered[right]]=[filtered[right],filtered[left]];right--;}return filtered.join(" ");// //字符数组// let charArr=Array.from(s);//  var removeBlank=(arr)=>{//     let left=0;//     for(let right=0;right<arr.length;right++){//         //为最前面有空格或连续空格//         if(arr[right]===" "&&(right===0||arr[right-1]===" "))continue;//         else{//             arr[left]=arr[right];//             left++;//         }//     }//     //考虑到移除尾部单个空格//     //因为执行赋值后有left++了，所以此处要再减1//     arr.length=arr[left-1]===" "?left-1:left;//此处求的是长度，slow指针索引，从0开始// }// //移除空格// removeBlank(charArr);// // //思路：去除空格，去除对于空格（双指针）// // //反转全部->反转每个单词// var reverse=(arr,left,right)=>{//     while(left<right){//         [arr[left],arr[right]]=[arr[right],arr[left]];//         left++;//         right--;//     }// }// // //反转全部// reverse(charArr,0,charArr.length-1);// // //反转每个单词// // 没遇到空格就是一个新单词或者到结尾// let left=0;// let right=0;//  //right===charArr.length是right-1才是最后一位// for(;right<=charArr.length;right++ ){//     //right===charArr.length是right-1才是最后一位//     if((charArr[right]===" ")|| (right===charArr.length)){//         reverse(charArr,left,right-1);//         left=right+1;//     }// }//return charArr.join(''); 
}
}

KMP经典应用

next初始化-> 前后缀不相同(回退，next数组）->前后缀相同->j加入next数组
初始化，获取next数组->前后缀不相同(回退，next数组）->前后缀相同->到末尾

/*** @param {string} haystack* @param {string} needle* @return {number}*/
var strStr = function(haystack, needle) {if(needle.length===0)return 0;let next=getNext(needle);let j=0;for(let i=0;i<haystack.length;i++){//字符匹配到不同的，回溯跳!!!whilewhile(j>0 && haystack[i]!==needle[j]){j=next[j-1];//写成need[j-1],excuse me?}//相等时，继续往下匹配if(haystack[i]===needle[j]){j++;}//匹配成功,i此时仍指向最后一字符//气死，length写出lenth，死都找不到那出错了if(j===needle.length){return i-needle.length+1;}}//未找到return -1;};var getNext=function(needle){//初始化let next=[];let j=0;next.push(j);//双指针！for(let i=1;i<needle.length;i++){//前后缀不同，循环回溯while(j>0&&needle[i]!==needle[j]){j=next[j-1];}if(needle[i]===needle[j]){j++;}next.push(j);}//记得返回出去！！！return next;
}

重复的字子字符串（能用KMP！前后缀）

结论：保证next大于0,即有最长前后缀,子串中除去最长前后缀的其他部分为最小重复字符串
除去这个最长相等的前缀和后缀剩下的部分（即重复的子串）是否能整除整个字符串的长度。如果可以整除，说明 s 是由这个更小的字符串重复构成的。

/*** @param {string} s* @return {boolean}*/
var repeatedSubstringPattern = function(s) {let next=getNext(s);//保证next大于0,即有最长前后缀,子串中除去最长前后缀的其他部分为最小重复字符串//next[next.length-1] 表示整个字符串 s 的最长相等的前缀和后缀的长度。//s.length % (s.length - next[next.length-1]) === 0 用于判断，除去这个最长相等的前缀和后缀//剩下的部分（即重复的子串）是否能整除整个字符串的长度。如果可以整除，说明 s 是由这个更小的字符串重复构成的。if(next[next.length-1]>0&&s.length%(s.length-next[next.length-1])===0)return true;return false;
};
var getNext=function(s){//初始化let j=0;let next=[];next.push(j);for(let i=1;i<s.length;i++){//前后缀不相同while(j>0&&s[i]!==s[j]){//回溯j=next[j-1];}//前后缀相同时if(s[i]===s[j]) j++;//更新next数组next.push(j);}return next;
}

有效的括号

/*** @param {string} s* @return {boolean}*/
var isValid = function(s) {// let stack=[];// for(let i=0;i<s.length;i++){//     let cur=s[i];//     switch(cur){//         case "{"://             stack.push("}");//             break;//         case "("://             stack.push(")");//             break;//         case "["://             stack.push("]");//             break;//         default://             let flag=stack.pop()===cur;//             if(!flag)return false;//     }// }// return stack.length===0;const stack = [];//键值对let  obj1  = {"(":")","{":"}","[":"]"};for(const x of s) {if(x in obj1) {//遇到左括号将对应右括号加入栈stack.push(obj1[x]);//跳出本次循环continue;};//遇到右括号从栈中弹出数据，若不同就返回falseif(stack.pop() !== x) return false;}//若还剩数据也不行！！！return !stack.length;};

删除字符串中的所有相邻重复项

/*** @param {string} s* @return {string}*/
var removeDuplicates = function(s) {//初始化空栈let stack=[];for(let i=0;i<s.length;i++){let cur=s[i];//判断栈是否为空if(stack.length>0){//不为空，将当前数据和栈顶数据比较let top=stack[stack.length-1]if(top===cur){//相同就弹出stack.pop();}else{//不相同就将此数据继续加入栈中stack.push(cur);}}else{//当栈中没数据就加入stack.push(cur);}}return stack.join("");};

逆波兰表达式求值

/*** @param {string[]} tokens* @return {number}*/
var evalRPN = function(tokens) {//思路：初始化一个栈，遇到数字就将数字压入栈中//遇到符号就从栈中弹出两个数字，弹出的数字的顺序matters!!!//然后再将结果压入栈，直至处理完成const stack = [];for (const token of tokens) {if (isNaN(Number(token))) { // 非数字const n2 = stack.pop(); // 出栈两个数字const n1 = stack.pop();switch (token) { // 判断运算符类型，算出新数入栈case "+":stack.push(n1 + n2);break;case "-":stack.push(n1 - n2);break;case "*":stack.push(n1 * n2);break;case "/":stack.push(n1 / n2 | 0);break;}} else { // 数字stack.push(Number(token));}}return stack[0]; // 因没有遇到运算符而待在栈中的结果
};

滑动窗口最大值★★★

前K个高频元素★★

大小堆原理详解