字符串
1. 回转字符串
标题：
编写一个函数，其作用是将输入的字符串回转过来。输入字符串以字符数组 s 的方式给出。
不要给别的的数组分配额定的空间，你有必要原地修正输入数组、使用 O(1) 的额定空间处理这一问题。
思路：
双指针法，从数组两端开始交流二者数据，直至到达同一方位（中心）。
动画作用：
代码：
/**
* @param {character[]} s
* @return {void} Do not return anything, modify s in-place instead.
*/
var reverseString = function (s) {
let middle = Math.floor(s.length / 2)
for (let i = 0; i < middle; i++)
//解构赋值
[s[i], s[s.length - 1 - i]] = [s[s.length - 1 - i], s[i]]
};
/**
* @param {character[]} s
* @return {void} Do not return anything, modify s in-place instead.
*/
var reverseString = function (s) {
let l = -1, r = s.length
while (++l < --r)
//解构赋值
[s[l], s[r]] = [s[r], s[l]]
};
2. 回转字符串 II
标题：
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就回转这 2k 字符中的前 k 个字符。
- 假如剩下字符少于
k个，则将剩下字符悉数回转。 - 假如剩下字符小于
2k但大于或等于k个，则回转前k个字符，其他字符坚持原样。
思路：
- 将数组按 2k 长度分段
- 分段后的数组判别其长度是否小于 k
- 若不小于 k，则将前 k 段回转；若小于 k，则将其悉数回转，完毕方位一定为数组末尾
- 回转的方法仍然采用双指针法
代码：
留意：在 JavaScript 中，字符串是不可变的（immutable）数据类型，这意味着你不能通过下标直接修正字符串中的某个字符。一旦一个字符串被创建，它的值就无法改动。
/**
* @param {string} s
* @param {number} k
* @return {string}
*/
var reverseStr = function (s, k) {
let arr = s.split("")
for (let i = 0; i < s.length; i += (2 * k)) {
if ((i + k) <= s.length) reverse(arr, i - 1, i + k)
else reverse(arr, i - 1, s.length)
}
return arr.join("")
};
var reverse = function (s, l, r) {
while (++l < --r)
[s[l], s[r]] = [s[r], s[l]]
};
3. 回转字符串中的单词
标题：
给你一个字符串 s ，请你回转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
回来 单词 顺序倒置且 单词 之间用单个空格连接的成果字符串。
留意：输入字符串 s中可能会存在前导空格、尾随空格或许单词间的多个空格。回来的成果字符串中，单词间应当仅用单个空格分隔，且不包括任何额定的空格。
思路：
-
方法一
- 移除剩余空格
- 将整个字符串回转
- 将每个单词回转
-
方法二
- 将字符串按空格切割成数组的方式。
- 采用双指针法，进行单词回转。
- 要点需求将数组中的空串元素除掉——回转元素前需求判别左右值是否为空串，若为空，则去除；若不空，则交流。去除还需求对左右指针进行调整。
- 最后又将数组转换成字符串回来。
代码：
方法二：
/**
* @param {string} s
* @return {string}
*/
var reverseWords = function (s) {
let arr = s.split(" ")
let l = -1, r = arr.length
while (++l <= --r) {
while (arr[l] === "") {
arr.splice(l, 1)
r--
}
while (arr[r] === "") {
arr.splice(r, 1)
r--
}
if (l < r)
[arr[l], arr[r]] = [arr[r], arr[l]]
}
return arr.join(" ")
};
4. 重复的子字符串
标题：
给定一个非空的字符串 s ，检查是否能够通过由它的一个子串重复屡次构成。
思路：
-
暴力解法
- 使用两层循环，一层用来确定子串，一层用来使用子串凑集字符串
- 将凑集的字符串和原字符串比照，若持平，则阐明该子串为最小重复子串回来 true ；若不持平，则持续遍历
- 最终仍无子串满意条件，则阐明原字符串不能够由它的一个子串重复屡次构成回来 false
- 留意：若字符串由重复的子串组成时，则该子串长度必为该字符串长度的因数且长度不超越该字符串长度的2倍（剪枝）
-
移动匹配
当一个字符串由重复的子串组成时，该字符串必然前后有该子串，所以用 该字符串 + 该字符串 组成的字符串中，前一个后面的子串做前串，后一个前面的子串做后串，就一定能组成一个原字符串。故有：
规律：判别字符串 s 是否有重复子串组成，只需两个 s 拼接在一起（要刨除 s + s 的首字符和尾字符），里边还出现一个 s 的话，就阐明 s 是由重复子串组成的。
-
KMP解法
- 在由重复子串组成的字符串中，最长持平前后缀不包括的子串就是最小重复子串
- 故，设：数组长度为：n 。假如
n % (n - next[n - 1]) === 0，即 数组长度 – 最长持平前后缀的长度 正好能够被数组的长度整除，则阐明该字符串是由重复子串组成的。
代码：
-
暴力解法
/** * @param {string} s * @return {boolean} */ var repeatedSubstringPattern = function (s) { let n = s.length for (let i = 1; i <= n / 2; i++) { if (n % i != 0) continue let str = "", res = s.slice(0, i), count = n / i while (count--) str += res if (str === s) return true } return false }; -
移动匹配
/** * @param {string} s * @return {boolean} */ var repeatedSubstringPattern = function (s) { let ss = s + s ss = ss.slice(1, ss.length - 1) if (ss.search(s) != -1) return true return false }; -
KMP解法
/** * @param {string} s * @return {boolean} */ var repeatedSubstringPattern = function (s) { if (s.length === 0) return false let next = getNext(s), n = s.length if (next[n - 1] != 0 && n % (n - next[n - 1]) === 0) return true return false }; var getNext = function (s) { let j = 0, next = []; next[0] = 0; for (let i = 1; i < s.length; i++) { while (j > 0 && s[j] != s[i]) j = next[j - 1] if (s[j] === s[i]) j++ next[i] = j } return next }
