华为OD算法复习2——字符串

这些力扣题目来源：AI推荐+karshey博主

目录

344.反转字符串（通过）

541.反转字符串II（通过）

151.反转字符串中的单词（通过）

28.找出字符串中第一个匹配项的下标（KMP）（通过）

459.重复的子字符串（KMP）（通过）

344.反转字符串（通过）

344.反转字符串

i<s.length/2 翻转终止条件不能有等号。因为很可能会多翻转一次。

/** * @param {character[]} s * @return {void} Do not return anything, modify s in-place instead. */ // s = ["h","e","l","l","o"] s=["A"," ","m","a","n",","," ","a"," ","p","l","a","n",","," ","a"," ","c","a","n","a","l",":"," ","P","a","n","a","m","a"] var reverseString = function(s) { for(let i=0;i<s.length/2;i++){ let temp=s[i]; s[i]=s[s.length-i-1]; s[s.length-i-1]=temp; } return s; }; console.log(reverseString(s));

541.反转字符串II（通过）

541.反转字符串II

字符串substr可以取子

/** * @param {string} s * @param {number} k * @return {string} */ // s = "abcdefg", k = 2 s = "abcd", k = 2 var reverseStr = function(s, k) { let ans="" for(let i=0;i<s.length;i+=2*k){ let former =(s.substr(i,k)).split("").reverse().join(""); let later =s.substr(i+k,k); ans+=former+later; } return ans; }; console.log(reverseStr(s,k));

151.反转字符串中的单词（通过）

151.反转字符串中的单词

数组的filter方法可以筛选符合标准的元素

s = "a good example" /** * @param {string} s * @return {string} */ var reverseWords = function(s) { return s.split(" ").filter(item=>item!="").reverse().join(" "); }; console.log(reverseWords(s));

28.找出字符串中第一个匹配项的下标（KMP）（通过）

28.找出字符串中第一个匹配项的下标（KMP）

indexOf可以用来查找是否有元素存在于数组、字符串

let haystack = "sadbutsad", needle = "sad" /** * @param {string} haystack * @param {string} needle * @return {number} */ var strStr = function(haystack, needle) { return haystack.indexOf(needle); }; console.log(strStr(haystack,needle)); // let test = [9,7,4,2].indexOf(4) // console.log(test);

459.重复的子字符串（KMP）（通过）

459.重复的子字符串（KMP）

超出输出限制 -- 力扣报错 是因为忘记删除调试用的console.log

思路：如果一个字符串可以由重复的子串组成，证明它的因数之一（包含1）可以作为子串的长度。先收集因数，然后遍历查询

// s = "abab" s = "abcabcabcabc" // s ="bb" /** * @param {string} s * @return {boolean} */ var repeatedSubstringPattern = function(s) { let record=[] let result =false; for(let i=1;i<s.length;i++){ if(s.length%i==0) record.push(i); } console.log(record); for(let i=record.length-1;i>=0;i--){ let sub=s.substr(0,record[i]) let this_round = true; for(let j=record[i];j<s.length;j+=record[i]){ let temp=s.substr(j,record[i]); if(sub!=temp) { this_round=false; } } if(this_round) { return true; }; } return result; }; console.log(repeatedSubstringPattern(s));