代码随想录算法训练营第八天|344 反转字符串、541反转字符串||、151、翻转字符串里的单词

发布时间:2024年01月17日

344 反转字符串

题目链接:反转字符串

思路

反转字符串这道题目比较简单,和我们之前见到的反转链表有一点点相似,然后和反转数组就一模一样了。使用双指针的方法可以轻松解决这个问题。

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

541 反转字符串||

题目链接:反转字符串||

思路

这道题目我感觉具有较强的引导性,就是我第一次做这个题目的时候,总想着对n2k字符处理,再对剩下的字符处理。参考视频后,发现可以一起做处理。
在字符串的i*2k处设置锚点,然后如果i*2k+k<=s.length(),则表明现在字符串至少剩下k个字符,则从i*2k处起,反转k个字符;相反,则表明字符串中剩下的字符串已经小于k个了,则直接将剩余的字符全部反转。

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

151 翻转字符串里的单词

题目链接:翻转字符串里的单词

思路

解法1

一种很直接的方法是:首先将字符串里的所有单词都分割出来,然后从后往前依次相加(中间要加空格),同时你还要考虑输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中,单词间应当仅用单个空格分隔,且不包含任何额外的空格。

解法2

参考解析,还有一种解法是:我们先移除掉字符串s中多余的空格,然后将字符串s翻转,然后再将s中的每个单词翻转,就是我们想要的结果。
那么第一步:移除字符串s中多余的空格,也就是移除元素,怎么弄呢?我们之前做过在数组中移除目标元素,有暴力解法:两层for循环,也有双指针的方法。那么在这里我们可以使用双指针的方法。

class Solution {
public:
    void removeExtraSpace(string &s)
    {
        int slow = 0;
        for (int fast = 0; fast < s.size(); fast++) {
            if (s[fast] != ' ') {
                if (slow != 0) {  // 这个补空格的思路是真的妙
                    s[slow++] = ' ';
                }
                while (s[fast] != ' '&& fast<s.size()) { // 这里得需要判断fast<s.size(),否则会访问出界
                    s[slow++] = s[fast++];
                }

            }
        }
        s.resize(slow);
    }

    string reverseWords(string s) 
    {
        removeExtraSpace(s);
        reverse(s.begin(),s.end());
        int start = 0;
        for(int i=0; i<=s.size(); i++){
            if(s[i] == ' ' || i==s.size()){
                reverse(s.begin()+start, s.begin()+i);//左闭右开
                start = i+1;
            }
        }
        return s;
    }
};

参考链接

  1. https://programmercarl.com/0541.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2II.html#%E6%80%9D%E8%B7%AF
文章来源:https://blog.csdn.net/qq_41596730/article/details/135643636
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。