代码随想录算法训练营第八天|344、反转字符串|541、反转字符串Ⅱ|剑指Offer 05、替换空格|151.翻转字符串里的单词|剑指Offer58-Ⅱ、左旋转字符串

344、反转字符串

·两两交换


给字符串翻个面doge

题目链接:https://leetcode.cn/problems/reverse-string/submissions/

思路:首尾交换

代码实现:
     时间复杂度O(n)
     空间复杂度O(1)

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

异或运算实现数组交换:

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

收获摘要:异或运算在数组交换上更快一些

学习的文章链接:https://programmercarl.com/0344.反转字符串.html#其他语言版本

541、反转字符串Ⅱ

·模拟法


给数组局部翻面~

题目链接:https://leetcode.cn/problems/reverse-string-ii/

思路:根据题目模拟就行
   考虑循环怎么减少运算:i步长为2k

代码实现:
     时间复杂度O(n^2)
     空间复杂度O(1)

class Solution {
public:
    void myswop(string& s,int n,int m){
        for(int i=n,j=m;i<j;i++,j--){
            s[i]^=s[j];
            s[j]^=s[i];
            s[i]^=s[j];
        }
    }
    string reverseStr(string s, int k) {
        for(int i=0;i<s.size();i=i+2*k){
            if(i+k>s.size()){
                myswop(s,i,s.size()-1);
            }
            else{
                myswop(s,i,i+k-1);
            }
        }
        return s;
    }
};

收获摘要:理清题目意思,模拟考虑的情况要全而精简

学习的文章链接:https://programmercarl.com/0541.反转字符串II.html#其他语言版本

剑指Offer 05、替换空格

·双指针法


移除元素进化版–>替换元素!

题目链接:https://leetcode.cn/problems/ti-huan-kong-ge-lcof/submissions/

思路:用%20替换空格,数组变长了
   扩充原有数组
   用双指针从后往前填充

代码实现:
     时间复杂度O(n)
     空间复杂度O(1)

class Solution {
public:
    string replaceSpace(string s) {
        int c=0;
        int l=s.size()-1;
        int rl=0;
        for(int i=0;i<=l;i++){
            if(s[i]==' ')c++;
        }
        s.resize(s.size()+c*2);
        rl=l+c*2;
        while(l>=0){
            if(s[l]!=' '){
                s[rl]=s[l];
                rl--;
                l--;
            }
            else
            {
                s[rl]='0';
                s[rl-1]='2';
                s[rl-2]='%';
                rl=rl-3;
                l--;
            }
        }
        return s;
    }
};

收获摘要:双指针一如既往的快啊。学会手动调已有数组长度doge。

学习的文章链接:https://programmercarl.com/剑指Offer05.替换空格.html#其他语言版本

151.翻转字符串里的单词

·模拟!模拟!


本来可以水,不用辅助空间就开始折磨,折磨!啊!泪射了出来.jpg

题目链接:https://leetcode.cn/problems/reverse-words-in-a-string/discussion/

思路:用双指针移除多余空格
   反转字符
   反转单词

代码实现:
     时间复杂度O(n)
     空间复杂度O(1)

class Solution {
public:
    void myswop(string& s,int n,int m){
        for(int i=n,j=m;i<j;i++,j--){
            s[i]^=s[j];
            s[j]^=s[i];
            s[i]^=s[j];
        }
    }

    string reverseWords(string s) {
        int slow=0;
        int l;
        int fast;
        for(fast=0;fast<s.size();fast++){//去空格
            if(s[fast]!=' ')//只有是字母时处理,手动添加空格后添加单词而不是添加字母
            {
                cout<<"fast="<<fast<<endl;
                if(slow!=0){//不是fast!!是slow的第一个单词!!(第一个单词已经添加完)orz
                    s[slow]=' ';
                    slow++;
                }
                while(s[fast]!=' '&&fast<s.size()){
                    s[slow]=s[fast];
                    slow++;
                    fast++;
                }
            }
        }
        l=slow;
        s.resize(l);
        myswop(s,0,l-1);
        slow=0;
        for(int i=0;i<=l;i++){//这里的边界是数组末尾+1
            if(i==l||s[i]==' '){
                myswop(s,slow,i-1);
                slow=i+1;//下一个单词的头下标
            }
        }
        return s;
    }
};

收获摘要:代码就像裹脚布,又臭又长doge
     模拟的过程简直折磨
     coding三分钟,debug一小时orz
     模拟过程渐渐多了起来,最好使用自定义函数,这样模拟过程会更加清晰。

学习的文章链接:https://programmercarl.com/0151.翻转字符串里的单词.html

剑指Offer58-Ⅱ、左旋转字符串

·局部-整体反转


翻翻乐doge

题目链接:https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/submissions/

思路:1、开新数组
   2、不开新数组:
       0-n-1 局部反转
       n-size-1 局部反转
       整体反转

代码实现:
     时间复杂度O(n)
     空间复杂度O(1)

class Solution {
public:
    void myswop(string& s,int n,int m){
        for(int i=n,j=m;i<j;i++,j--){
            s[i]^=s[j];
            s[j]^=s[i];
            s[i]^=s[j];
        }
    }
    string reverseLeftWords(string s, int n) {
        myswop(s,0,n-1);
        myswop(s,n,s.size()-1);
        myswop(s,0,s.size()-1);
        return s;
    }
};

收获摘要:啪!的一下,很快就打完了。思路很巧妙~

学习的文章链接:https://programmercarl.com/剑指Offer58-II.左旋转字符串.html#其他语言版本


学习时长:4h40min
本来以为今天会快一些的,理解得很快,也有思路,但是debug用了很久……

原文地址:http://www.cnblogs.com/tinct/p/16852990.html

发表评论

您的电子邮箱地址不会被公开。