字符串

反转字符串

题号344. 反转字符串

思考

1. 使用双指针，左右调换就行了
2. 小技巧 [s[l],s[r]] = [s[r],s[l]]

/**
 Do not return anything, modify s in-place instead.
 */
function reverseString(s: string[]): void {
    let l = 0 ,r = s.length-1,tmp:string
    while(l<r){
        [s[l],s[r]] = [s[r],s[l]]
        l++
        r--
    }
};

反转字符串进阶

题号541. 反转字符串 II

思考

1. 和反转字符串的思路是一样的，但是条件什么的比较复杂
2. 小技巧 i += 2 * k

function reverseStr(s: string, k: number): string {
    let left: number, right: number;
    let arr: string[] = s.split('');
    let temp: string;
    for (let i = 0, length = arr.length; i < length; i += 2 * k) {
        left = i;
        right = (i + k - 1) >= length ? length - 1 : i + k - 1;
        while (left < right) {
            temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
    return arr.join('');
};

剑指Offer 05.替换空格

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

示例 1： 输入：s = "We are happy." 输出："We%20are%20happy."

思考

1. 将后面的数组拓展为空格的两倍
2. 双指针

function replaceSpace(s: string): string {
    let arr: string[] = s.split('');
    let spaceNum: number = 0;
    let oldLength: number = arr.length;
    for (let i = 0; i < oldLength; i++) {
        if (arr[i] === ' ') {
            spaceNum++;
        }
    }
    arr.length = oldLength + 2 * spaceNum;
    let cur: number = oldLength - 1;
    for (let i = arr.length - 1; i >= 0; i--, cur--) {
        if (arr[cur] !== ' ') {
            arr[i] = arr[cur]
        } else {
            arr[i] = '0';
            arr[--i] = '2';
            arr[--i] = '%';
        }
    }
    return arr.join('');
};

反转字符串中的单词

题号151. 反转字符串中的单词

思考

1. 这道题目难点在于去掉多余的空格
2. 把问题分解为
   1. 翻转字符串（双指针解决）
   2. 删除多余空格

function reverseWords(s: string): string {
    /** Utils **/
    // 删除多余空格, 如'   hello     world   ' => 'hello world'
    function delExtraSpace(arr: string[]): void {
        let left: number = 0,
            right: number = 0,
            length: number = arr.length;
        while (right < length && arr[right] ===   ' ') {
            right++;  
        } 
        while (right < length) {
            if (arr[right] === ' ' && arr[right - 1] === ' ') {
                right++;
                continue;
            }
            arr[left++] = arr[right++];
        }
        if (arr[left - 1] === ' ') {
            arr.length = left - 1;
        } else {
            arr.length = left;
        }
    }
    // 翻转字符串，如：'hello' => 'olleh'
    function reverseWords(strArr: string[], start: number, end: number) {
        while (start < end) {
            [strArr[start],strArr[end]]= [strArr[end],strArr[start]]
            start++;
            end--;
        }
    }

    /** Main code **/
    let strArr: string[] = s.split('');
    delExtraSpace(strArr);
    let length: number = strArr.length;
    // 翻转整个字符串
    strArr.reverse()// reverseWords(strArr, 0, length - 1);
    let start: number = 0,
        end: number = 0;
    while (start < length) {
        end = start;
        while (strArr[end] !== ' ' && end < length) {
            end++;
        }
        // 翻转单个单词
        reverseWords(strArr, start, end - 1);
        start = end + 1;
    }
    return strArr.join('');
};

左旋转字符串

题号LCR 182. 动态口令

思考

1. 这道题目使用先反转局部再反转全体实现左旋字符串
   1. 先反转前target个
   2. target到末尾
   3. 整体翻转

总结

1. 在这篇文章344.反转字符串 (opens new window)，第一次讲到反转一个字符串应该怎么做，使用了双指针法。
2. 然后发现541. 反转字符串II (opens new window)，这里开始给反转加上了一些条件，当需要固定规律一段一段去处理字符串的时候，要想想在for循环的表达式上做做文章。
3. 后来在151.翻转字符串里的单词 (opens new window)中，要对一句话里的单词顺序进行反转，发现先整体反转再局部反转 是一个很妙的思路。
4. 最后再讲到本题，本题则是先局部反转再 整体反转，与151.翻转字符串里的单词 (opens new window)类似，但是也是一种新的思路。

方法一

function dynamicPassword(password: string, target: number): string {
    let strArr: string[] = password.split('');
    let length: number = strArr.length;
    reverseString(strArr, 0, length - 1);
    reverseString(strArr, 0, length - target - 1);
    reverseString(strArr, length - target, length - 1);
    return strArr.join('');
};

function reverseString(arr:string[],start:number,end:number){
    while(start<end){
        [arr[start],arr[end]] = [arr[end],arr[start]]
        start++
        end--
    }
}

方法二

function dynamicPassword(password: string, target: number): string {
    return (password+password).slice(target,password.length+target)
};

找出字符串中第一个匹配项的下标

题号找出字符串中第一个匹配项的下标

KMP算法

在一个串中查找是否出现过另一个串，这是KMP的看家本领

思考

1. 朴素法
2. KMP算法
   1. next数组求法
      1. 初始化
      2. 前后缀不相同
      3. 前后缀相同
      4. next
   2. pattern和目标数组比较
      1. next数组记录的起始位置j
      2. 不匹配 j寻找之前匹配的位置
      3. 匹配，j和i同时向后移动
      4. 如果j=parttern的长度就证明出现了pattern

方法一 朴素法

function strStr(haystack: string, needle: string): number {
    let n = haystack.length,
        m = needle.length 

    for(let i = 0;i<=n-m;i++){
        let a = i,b = 0
        while(b<m&&haystack[a] === needle[b]){
            a++
            b++
        }
        if(b===m)return i
    }
    return  -1
};

方法二 KMP算法

function strStr(haystack: string, needle: string): number {
    if(needle.length === 0)return 0
    let next = getNext(needle)
    let j: number = 0;
    for (let i = 0, length = haystack.length; i < length; i++) {
        while (j > 0 && haystack[i] !== needle[j]) {
            j = next[j - 1];
        }
        if (haystack[i] === needle[j]) {
            if (j === needle.length - 1) {
                return i - j;
            }
            j++;
        }
    }
    return -1;
};

// 获得前缀表
function getNext(str:string){
    let next = [],j = 0
    next[0] = j
    for(let i=1;i<str.length;i++){
        while(j>0&&str[j]!==str[i]){
            j = next[j-1]
        }
        if(str[i]===str[j]){
            j++
        }
        next[i]=j
    }
    return next
}

重复的子字符串

题号459. 重复的子字符串

思考

1. 直接暴力解法两个for循环
2. 移动匹配
3. KMP算法

方法一 移动匹配

function repeatedSubstringPattern(s: string): boolean {
    let ss = s+s
    ss=ss.slice(1,ss.length-1)
    return ss.includes(s)
};

方法二 KMP算法

function repeatedSubstringPattern(s: string): boolean {
    if(s.length===1)return false
    let next = getNext(s),
    q = s.length-next[s.length-1]
    if(next[s.length-1]!==0&&s.length%q===0)return true
    else return false
};

function getNext(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
}