字符串

344. 反转字符串

class Solution {
public:
    void reverseString(vector<char>& s) {
        for(int i=0,j=s.size()-1;i<s.size()/2;i++,j--) {
            swap(s[i],s[j]);
        }
    }
};

541. 反转字符串 II

class Solution {
public:
    string reverseStr(string s, int k) {
        for(int i=0; i<s.size();i+=(2*k)) {
            if(s.size()-i<k) {
                reverse(s.begin()+i, s.end());
            } else {
                reverse(s.begin()+i, s.begin()+i+k);
            }
        } 
        return s;
    }
};

剑指 Offer 05. 替换空格

倒序双指针

class Solution {
public:
    string replaceSpace(string s) {
        int spaceCount = 0;
        for(char ss: s) {
            if(ss==' ') spaceCount++;
        }
        int oldLenghth = s.size();
        s.resize(spaceCount*2+s.size());

        for(int i=oldLenghth-1,j=s.size()-1;i>0,j>0;i--,j--) {
            if(s[i]!=' ') {
                s[j]=s[i];
            } else {
                s[j]='0';
                s[j-1]='2';
                s[j-2]='%';
                j-=2;
            }
        }
        return s;
    }
};

151. 翻转字符串里的单词

  1. 先翻转
  2. 原地去除所有的空格,最左边的让快指针++,中间的如果遇到空格快指针++,没遇到就交换快慢指针,最后的还是让快指针++。slowIndex就是最后的有效长度
  3. 寻找单词进行翻转
class Solution {
public:
    void removeSpace(string& s) {
        int fastIndex = 0, slowIndex = 0;
        // 最左边的
        while(fastIndex<s.size() && s[fastIndex]==' ') {
            fastIndex++;
        }
        // 中间的
        for(;fastIndex<s.size();fastIndex++) {
            if(fastIndex>1 && s[fastIndex]==' ' && s[fastIndex-1]==' '){
                // 遇到了就什么不做,只有fast++
                continue;
            } else {
                s[slowIndex++] = s[fastIndex];
            }
        }
        // 最后的
        if(slowIndex-1>0 &&s[slowIndex-1]==' ') {
            // 当最后是“  ”时候,第一个空格会被忽略,slow在第二个空格的位置
            s.resize(slowIndex-1);
        } else {
            s.resize(slowIndex);
        }

    }
    string reverseWords(string s) {
        reverse(s.begin(), s.end());
        removeSpace(s);
        int satrt = 0, end = 0;
        for(int i=0; i<s.size();i++) {
            if(s[i]==' ') {
                end = i;
                // reverse 左闭右开
                reverse(s.begin()+satrt, s.begin()+end);
                satrt = end+1;
            }
        }
        // 最后没空格,再一次更换
        cout<<satrt;
        reverse(s.begin()+satrt, s.end());
        return s;
    }
};

剑指 Offer 58 - II. 左旋转字符串

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        // 翻转前n个
        reverse(s.begin(),s.begin()+n);
        // 翻转后n个
        reverse(s.begin()+n,s.end());
        // 翻转整个
        reverse(s.begin(),s.end());
        return s;
    }
};

28. 实现 strStr()

KMP算法

class Solution {
public:
    void getNext(int* next, string s) {
        int i = 0; //  i:前缀末尾, j:后缀末尾
        next[0] = 0;
        for(int j=1; j<s.size();j++) {
            // 不等
            while(i>0 && s[i]!=s[j]){
                i = next[i-1];
            }
            if(s[i] == s[j]) {
                // 相等
                i++;
            }

            next[j] = i;
        }
    }
    int strStr(string haystack, string needle) {
        if(needle.size()==0) return 0;
        int next[needle.size()];
        getNext(next, needle);
        int j = 0; // needle 的指针
        for (int i=0;i<haystack.size();i++) {
            while(j>0 && haystack[i] != needle[j]) {
                // 不等
                j = next[j - 1];
            }
            if(haystack[i] == needle[j]) {
                // 相等
                j++;
            }
            if(j==needle.size()) {
                return (i-needle.size()+1);
            }
        }
        return -1;
    }
};

459. 重复的子字符串

数组长度减去最长相同前后缀的长度相当于是第一个周期的长度,也就是一个周期的长度,如果这个周期可以被整除,就说明整个数组就是这个周期的循环。

参考:https://writings.sh/post/algorithm-repeated-string-pattern

class Solution {
public:
    void getNext (int* next, const string& s){
        next[0] = 0;
        int j = 0;
        for(int i = 1;i < s.size(); i++){
            while(j > 0 && s[i] != s[j]) {
                j = next[j - 1];
            }
            if(s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }
    }
    bool repeatedSubstringPattern(string s) {
        int next[s.size()];
        getNext(next,s);
        int len = s.size();
        if(next[len-1]!=0 && len%(len-next[len-1])==0) return true;
        return false;
    }
};
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇