建设项目网站,微信网站建设知识,天津站内关键词优化,静态网站建设教程目录
LeetCode#xff1a;344.反转字符串
LeetCode#xff1a;541. 反转字符串II
LeetCode#xff1a;剑指Offer 05.替换空格
LeetCode#xff1a;151.翻转字符串里的单词
LeetCode#xff1a;剑指Offer58-II.左旋转字符串
LeetCode#xff1a;28. 实现 strStr()
…
目录
LeetCode344.反转字符串
LeetCode541. 反转字符串II
LeetCode剑指Offer 05.替换空格
LeetCode151.翻转字符串里的单词
LeetCode剑指Offer58-II.左旋转字符串
LeetCode28. 实现 strStr()
LeetCode459.重复的子字符串 定义两个指针也可以说是索引下标一个从字符串前面一个从字符串后面两个指针同时向中间移动并交换元素。 var reverseString function(s) {let l -1, r s.length;while(l --r) {[s[l], s[r]] [s[r], s[l]];}};
LeetCode541. 反转字符串II
var reverseStr function(s, k) {let resArr s.split();for (let i0; is.length; i2*k) {let l i-1, r i k s.length ? s.length : i k;while(l --r) {[resArr[l], resArr[r]] [resArr[r], resArr[l]];}}return resArr.join();};
LeetCode剑指Offer 05.替换空格 从前向后填充就是O(n^2)的算法了因为每次添加元素都要将添加元素之后的所有元素向后移动。其实很多数组填充类的问题都可以先预先给数组扩容带填充后的大小然后在从后向前进行操作。这么做有两个好处
不用申请新数组。从后向前填充元素避免了从前向后填充元素时每次添加元素都要将添加元素之后的所有元素向后移动的问题。var replaceSpace function(s) {// 字符串转为数组const strArr Array.from(s);let count 0;// 计算空格数量for(let i 0; i strArr.length; i) {if (strArr[i] ) {count;}}let left strArr.length - 1;let right strArr.length count * 2 - 1;while(left 0) {if (strArr[left] ) {strArr[right--] 0;strArr[right--] 2;strArr[right--] %;left--;} else {strArr[right--] strArr[left--];}}// 数组转字符串return strArr.join();
};
LeetCode151.翻转字符串里的单词
提高一下本题的难度不要使用辅助空间空间复杂度要求为O(1)。不能使用辅助空间之后那么只能在原字符串上下功夫了。想一下我们将整个字符串都反转过来那么单词的顺序指定是倒序了只不过单词本身也倒序了那么再把单词反转一下单词不就正过来了。所以解题思路如下
移除多余空格将整个字符串反转将每个单词反转
举个例子源字符串为the sky is blue
移除多余空格 : the sky is blue字符串反转eulb si yks eht单词反转blue is sky thevar reverseWords function(s) {// 字符串转数组const strArr Array.from(s);// 移除多余空格removeExtraSpaces(strArr);// 翻转reverse(strArr, 0, strArr.length - 1);let start 0;for(let i 0; i strArr.length; i) {if (strArr[i] || i strArr.length) {// 翻转单词reverse(strArr, start, i - 1);start i 1;}}return strArr.join();
};// 删除多余空格
function removeExtraSpaces(strArr) {let slowIndex 0;let fastIndex 0;while(fastIndex strArr.length) {// 移除开始位置和重复的空格if (strArr[fastIndex] (fastIndex 0 || strArr[fastIndex - 1] )) {fastIndex;} else {strArr[slowIndex] strArr[fastIndex];}}// 移除末尾空格strArr.length strArr[slowIndex - 1] ? slowIndex - 1 : slowIndex;
}// 翻转从 start 到 end 的字符
function reverse(strArr, start, end) {let left start;let right end;while(left right) {// 交换[strArr[left], strArr[right]] [strArr[right], strArr[left]];left;right--;}
}
LeetCode剑指Offer58-II.左旋转字符串
// 版本一var reverseLeftWords function(s, n) {const length s.length;let i 0;while (i length - n) {s s[length - 1] s;i;}return s.slice(0, length);
};// 版本二在原字符串上修改var reverseLeftWords function (s, n) {/** Utils */function reverseWords(strArr, start, end) {let temp;while (start end) {temp strArr[start];strArr[start] strArr[end];strArr[end] temp;start;end--;}}/** Main code */let strArr s.split();let length strArr.length;reverseWords(strArr, 0, length - 1);reverseWords(strArr, 0, length - n - 1);reverseWords(strArr, length - n, length - 1);return strArr.join();
};
LeetCode28. 实现 strStr()
本题是KMP 经典题目。KMP主要应用在字符串匹配上。KMP的经典思想就是:当出现字符串不匹配时可以记录一部分之前已经匹配的文本内容利用这些信息避免从头再去做匹配。所以如何记录已经匹配的文本内容是KMP的重点也是next数组肩负的重任。
next数组就是一个前缀表。前缀表是用来回退的它记录了模式串与主串(文本串)不匹配的时候模式串应该从哪里开始重新匹配。记录下标i之前包括i的字符串中有多大长度的相同前缀后缀 前缀表是如何记录的呢首先要知道前缀表的任务是当前位置匹配失败找到之前已经匹配上的位置再重新匹配此也意味着在某个字符失配时前缀表会告诉你下一步匹配中模式串应该跳到哪个位置。
构造next数组其实就是计算模式串s前缀表的过程。 主要有如下三步
初始化处理前后缀不相同的情况处理前后缀相同的情况
// 前缀表统一减一var strStr function (haystack, needle) {if (needle.length 0)return 0;const getNext (needle) {let next [];let j -1;next.push(j);for (let i 1; i needle.length; i) {while (j 0 needle[i] ! needle[j 1])j next[j];if (needle[i] needle[j 1])j;next.push(j);}return next;}let next getNext(needle);let j -1;for (let i 0; i haystack.length; i) {while (j 0 haystack[i] ! needle[j 1])j next[j];if (haystack[i] needle[j 1])j;if (j needle.length - 1)return (i - needle.length 1);}return -1;
};// 前缀表统一不减一var strStr function (haystack, needle) {if (needle.length 0)return 0;const getNext (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;}let next getNext(needle);let j 0;for (let i 0; i haystack.length; i) {while (j 0 haystack[i] ! needle[j])j next[j - 1];if (haystack[i] needle[j])j;if (j needle.length)return (i - needle.length 1);}return -1;
};LeetCode459.重复的子字符串
//前缀表统一减一var repeatedSubstringPattern function (s) {if (s.length 0)return false;const getNext (s) {let next [];let j -1;next.push(j);for (let i 1; i s.length; i) {while (j 0 s[i] ! s[j 1])j next[j];if (s[i] s[j 1])j;next.push(j);}return next;}let next getNext(s);if (next[next.length - 1] ! -1 s.length % (s.length - (next[next.length - 1] 1)) 0)return true;return false;
};//前缀表统一不减一var repeatedSubstringPattern function (s) {if (s.length 0)return false;const getNext (s) {let next [];let j 0;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.push(j);}return next;}let next getNext(s);if (next[next.length - 1] ! 0 s.length % (s.length - next[next.length - 1]) 0)return true;return false;
};
