算法学习Js语言旋转字符串
分析与解法
解法一:暴力移位法
针对长度为n的字符串来说,假设需要移动m个字符到字符串的尾部,那么总共需要 m*n 次操作,同时设立一个变量保存第一个字符,如此,时间复杂度为O(m * n),空间复杂度为O(1),空间复杂度符合题目要求,但时间复杂度不符合,所以,我们得需要寻找其他更好的办法来降低时间复杂度。
解法二:三步反转法
将一个字符串分成X和Y两个部分,在每部分字符串上定义反转操作,如XT,即把X的所有字符反转(如,X=“abc”,那么XT=“cba”),那么就得到下面的结论:(XTYT)^T=YX,显然就解决了字符串的反转问题。
例如,字符串 abcdef ,若要让def翻转到abc的前头,只要按照下述3个步骤操作即可:
首先将原字符串分为两个部分,即X:abc,Y:def;
将X反转,X->XT,即得:abc->cba;将Y反转,Y->YT,即得:def->fed。
反转上述步骤得到的结果字符串XTYT,即反转字符串cbafed的两部分(cba和fed)给予反转,cbafed得到defabc,形式化表示为(XTYT)^T=YX,这就实现了整个反转。
用三步反转法的例子
例子
function rotateString(array, count) {
let a = [];
let b = [];
for (let i = count - 1; i >= 0; i--) {
a.push(array[i]);
}
for (let j = array.length - 1; j >= count; j--) {
b.push(array[j]);
}
let c = a.concat(b);
let d = [];
for (let i = c.length - 1; i >= 0; i--) {
d.push(c[i]);
};
d = d.join("");
console.log(d);
}
测试例子
参考文章https://www.kancloud.cn/wizardforcel/the-art-of-programming-by-july/97202
’待完善链表反转的例子