网站首页图片滑动怎么做,自己建设网站服务器,长春建网站一般要多少钱,建设信基金管理有限公司网站主要记录算法和数据结构学习笔记#xff0c;新的一年更上一层楼#xff01; 初级算法-字符串一、反转字符串二、反转字符串#xff08;二#xff09;三、替换空格四、翻转字符串里的单词五、左旋转字符串六、实现 strStr()七、重复的子字符串字符串中元素只能是字符String…主要记录算法和数据结构学习笔记新的一年更上一层楼 初级算法-字符串一、反转字符串二、反转字符串二三、替换空格四、翻转字符串里的单词五、左旋转字符串六、实现 strStr()七、重复的子字符串字符串中元素只能是字符String s是空串String sNULL是空白串除串s本身以外的子串都是真子串空串是任何串的子串KMP算法解决字符串匹配问题前缀表next数组前缀不包含最后一个后缀不包含首字母
一、反转字符串
1.题目编写一个函数其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。 示例
示例 1
输入[h,e,l,l,o]
输出[o,l,l,e,h]示例 2
输入[H,a,n,n,a,h]
输出[h,a,n,n,a,H]2.解题思路
/*** param {character[]} s* return {void} Do not return anything, modify s in-place instead.*/
var reverseString function(s) {//Do not return anything, modify s in-place instead.reverse(s)
};var reverse function(s) {let l -1, r s.length;while(l --r) [s[l], s[r]] [s[r], s[l]];
};
// 运行时间120ms
// 内存消耗47.6MB二、反转字符串二
1.题目 给定一个字符串 s 和一个整数 k从字符串开头算起, 每计数至 2k 个字符就反转这 2k 个字符中的前 k 个字符。
如果剩余字符少于 k 个则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个则反转前 k 个字符其余字符保持原样。 示例
输入: s abcdefg, k 2
输出: bacdfeg2.解题思路
/*** param {string} s* param {number} k* return {string}*/
var reverseStr function(s, k) {const len s.length;let resArr s.split(); for(let i 0; i len; i 2 * k) { // 每隔 2k 个字符的前 k 个字符进行反转let l i - 1, r i k len ? len : i k;while(l --r) [resArr[l], resArr[r]] [resArr[r], resArr[l]];}return resArr.join();
};
// 运行时间80ms
// 内存消耗43.8MB三、替换空格
1.题目 请实现一个函数把字符串 s 中的每个空格替换成%20。
示例1
输入s We are happy.
输出We%20are%20happy.2.解题思路
/*** param {string} s* return {string}*/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();
};
// 运行时间60ms
// 内存消耗41MB四、翻转字符串里的单词
1.题目 给定一个字符串逐个翻转字符串中的每个单词。
示例
示例 1
输入: the sky is blue
输出: blue is sky the示例 2
输入: hello world!
输出: world! hello
解释: 输入字符串可以在前面或者后面包含多余的空格但是反转后的字符不能包括。示例 3
输入: a good example
输出: example good a
解释: 如果两个单词间有多余的空格将反转后单词间的空格减少到只含一个。2.解题思路
/*** param {string} s* return {string}*/var 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--;}
}
// 运行时间72ms
// 内存消耗44.4MB 五、左旋转字符串
1.题目 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如输入字符串abcdefg和数字2该函数将返回左旋转两位得到的结果cdefgab。
示例 示例 1
输入: s abcdefg, k 2
输出: cdefgab示例 2
输入: s lrloseumgh, k 6
输出: umghlrlose限制
1 k s.length 100002.解题思路
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);
};
// 运行时间120ms
// 内存消耗47MB// 原字符串上操作
/*** param {string} s* param {number} n* return {string}*/
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();
};
// 运行时间80ms
// 内存消耗43.3MB六、实现 strStr()
1.题目 实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在则返回 -1。 示例
示例 1: 输入: haystack hello, needle ll 输出: 2示例 2: 输入: haystack aaaaa, needle bba 输出: -1说明: 当 needle 是空字符串时我们应当返回什么值呢这是一个在面试中很好的问题。 对于本题而言当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。2.解题思路
// 前缀表统一减一
/*** param {string} haystack* param {string} needle* return {number}*/
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;
};
#运行时间56ms
#内存消耗41.1MB// 前缀表统一不减一
/*** param {string} haystack* param {string} needle* return {number}*/
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;
};
#运行时间72ms
#内存消耗41MB七、重复的子字符串
1.题目 给定一个非空的字符串判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母并且长度不超过10000。 示例
示例 1:
输入: abab
输出: True
解释: 可由子字符串 ab 重复两次构成。示例 2:
输入: aba
输出: False示例 3:
输入: abcabcabcabc
输出: True
解释: 可由子字符串 abc 重复四次构成。 (或者子字符串 abcabc 重复两次构成。)/*** param {string} s* return {boolean}*/
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;
};
#运行时间76ms
#内存消耗47.3MB/*** param {string} s* return {boolean}*/
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;
};
#运行时间72ms
#内存消耗47.3MB
