【代码随想录 | Leetcode | 第十一天】字符串 | 反转字符串 | 反转字符串 II | 替换空格 | 反转字符串中的单词 | 左旋转字符串

悠悠 2023-10-13 23:56 35阅读 0赞

## 前言 ##

#### 目录 ####

*  前言
 *  344. 反转字符串
 *  541. 反转字符串 II
 *  剑指 Offer 05. 替换空格
 *  151. 反转字符串中的单词
 *  剑指 Offer 58 - II. 左旋转字符串
 *  总结

--------------------

## 344. 反转字符串 ##

✨[题目链接点这里][Link 1]  
**编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。**

示例 1：  
**输入**：s = \[“h”,“e”,“l”,“l”,“o”\]  
**输出**：\[“o”,“l”,“l”,“e”,“h”\]

示例 2：  
**输入**：s = \[“H”,“a”,“n”,“n”,“a”,“h”\]  
**输出**：\[“h”,“a”,“n”,“n”,“a”,“H”\]

提示：  
1 <= s.length <= 105  
s\[i\] 都是 ASCII 码表中的可打印字符

**就是实现库函数`reverse`**

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]);
        }
    };

![在这里插入图片描述][1d29a3a54ae64b4aaf2567ca653f63fe.png]

--------------------

## 541. 反转字符串 II ##

✨[题目链接点这里][Link 2]  
**给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。如果剩余字符少于 k 个，则将剩余字符全部反转。  
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。**

示例 1：  
**输入**：s = “abcdefg”, k = 2  
**输出**：“bacdfeg”

示例 2：  
**输入**：s = “abcd”, k = 2  
**输出**：“bacd”

提示：  
1 <= s.length <= 104  
s 仅由小写英文组成  
1 <= k <= 104

**分情况讨论一下就可以了~**

class Solution {
        
    public:
        string reverseStr(string s, int k) {
        
            for (int i = 0; i < s.size(); 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;
        }
    };

![在这里插入图片描述][80e25117fecd44799b803a8c0b1226bc.png]

class Solution {
        
    public:
        void reverse(string& s, int start, int end) {
        
            for (int i = start, j = end; i < j; i++, j--) {
        
                swap(s[i], s[j]);
            }
        }
        string reverseStr(string s, int k) {
        
            for (int i = 0; i < s.size(); i += (2 * k)) {
        
                if (i + k <= s.size())
                    reverse(s, i, i + k - 1);
                else 
                    reverse(s, i, s.size() - 1);
            }
            return s;
        }
    };

![在这里插入图片描述][4d2d784f9dc74f9ea0c9d09eb2c460ec.png]

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

![在这里插入图片描述][7a3fe1c9779b450783639a45666b00fd.png]

--------------------

## 剑指 Offer 05. 替换空格 ##

✨[题目链接点这里][Link 3]  
**请实现一个函数，把字符串 s 中的每个空格替换成"%20"。**

示例 1：  
**输入**：s = “We are happy.”  
**输出**：“We%20are%20happy.”

限制：  
0 <= s 的长度 <= 10000

> **思路：**
> 
> > 扩容+双指针  
> > **为什么要从后往前遍历？**
> > 
> > 1.  不用申请新数组。
> > 2.  从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。

class Solution {
        
    public:
        string replaceSpace(string s) {
        
            int count = 0;
            int sOldSize = s.size();
            for (int i = 0; i < sOldSize; i++) {
        
                if (s[i] == ' ') {
        
                    count++;
                }
            }
            s.resize(sOldSize + 2 * count);
            int sNewSize = s.size();
            for (int i = sOldSize - 1, j = sNewSize - 1; i >= 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;
        }
    };

![在这里插入图片描述][287609403d47446fb5c23959431e0f0d.png]

--------------------

## 151. 反转字符串中的单词 ##

✨[题目链接点这里][Link 4]  
**给你一个字符串 s ，请你反转字符串中 单词 的顺序。单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。**

示例 1：  
**输入**：s = “the sky is blue”  
**输出**：“blue is sky the”

示例 2：  
**输入**：s = " hello world "  
**输出**：“world hello”  
**解释**：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：  
**输入**：s = “a good example”  
**输出**：“example good a”  
**解释**：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

提示：  
1 <= s.length <= 104  
s 包含英文大小写字母、数字和空格 ’ ’  
s 中 至少存在一个 单词

> **思路：**
> 
> > 1.  移除多余空格
> > 2.  将整个字符串反转
> > 3.  将每个单词反转  
> >     **移除多于空格大家可以参照[移除元素][Link 5]，思路是一模一样的，最后的单词翻转`if (i == s.size() || s[i] == ' ')`是到达单词末尾或者遇到空格，翻转**

lass Solution {
        
    public:
        void reverse(string& s, int start, int end) {
        
            for (int i = start, j = end; i < j; i++, j-- ) {
        
                swap(s[i], s[j]);
            }
        }
        void removeExtraSpace(string& s) {
        
            int slow = 0;
            for (int i = 0; i < s.size(); i++) {
        
                if (s[i] != ' ') {
        
                    if (slow != 0) {
        
                        s[slow++] = ' ';
                    }
                    while (i < s.size() && s[i] != ' ') {
        
                        s[slow++] = s[i++];
                    }
                }
            }
            s.resize(slow);
        }
        string reverseWords(string s) {
        
            removeExtraSpace(s);
            reverse(s, 0, s.size() - 1);
            int start = 0;
            for (int i = 0;i <= s.size(); i++) {
        
                if (i == s.size() || s[i] == ' ') {
        
                    reverse(s, start, i - 1);
                    start = i + 1;
                }
            }
            return s;
        }
    };

![在这里插入图片描述][a90e0e057ae8497ca26333ce39c33388.png]

--------------------

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

✨[题目链接点这里][Link 6]  
**字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串`"abcdefg"`和数字2，该函数将返回左旋转两位得到的结果`"cdefgab"`。**

示例 1：  
**输入**: s = “abcdefg”, k = 2  
**输出**: “cdefgab”

示例 2：  
**输入**: s = “lrloseumgh”, k = 6  
**输出**: “umghlrlose”

限制：  
1 <= k < s.length <= 10000

> **思路：**
> 
> > 1.  反转区间为前n的子串
> > 2.  反转区间为n到末尾的子串
> > 3.  反转整个字符串  
> >     ![在这里插入图片描述][3cd47bba28ad4947a32c8f9de3c2c92e.png]

class Solution {
        
    public:
        string reverseLeftWords(string s, int n) {
        
            reverse(s.begin(), s.begin() + n);
            reverse(s.begin() + n, s.end());
            reverse(s.begin(), s.end());
            return s;
        }
    };

![在这里插入图片描述][6b12fa1435144413b674ddd21c54e0ef.png]

## 总结 ##

**字符串第一感觉很朴实，但是要提高执行效率，还是可以玩的很花的，比如反转~**

[K]: https://blog.csdn.net/qq_72157449?spm=1000.2115.3001.5343
[Leetcode]: https://blog.csdn.net/qq_72157449/category_12293229.html?spm=1001.2014.3001.5482
[Link 1]: https://leetcode.cn/problems/reverse-string/
[1d29a3a54ae64b4aaf2567ca653f63fe.png]: https://img-blog.csdnimg.cn/1d29a3a54ae64b4aaf2567ca653f63fe.png
[Link 2]: https://leetcode.cn/problems/reverse-string-ii/
[80e25117fecd44799b803a8c0b1226bc.png]: https://img-blog.csdnimg.cn/80e25117fecd44799b803a8c0b1226bc.png
[4d2d784f9dc74f9ea0c9d09eb2c460ec.png]: https://img-blog.csdnimg.cn/4d2d784f9dc74f9ea0c9d09eb2c460ec.png
[7a3fe1c9779b450783639a45666b00fd.png]: https://img-blog.csdnimg.cn/7a3fe1c9779b450783639a45666b00fd.png
[Link 3]: https://leetcode.cn/problems/ti-huan-kong-ge-lcof/
[287609403d47446fb5c23959431e0f0d.png]: https://img-blog.csdnimg.cn/287609403d47446fb5c23959431e0f0d.png
[Link 4]: https://leetcode.cn/problems/reverse-words-in-a-string/
[Link 5]: https://blog.csdn.net/qq_72157449/article/details/131713745
[a90e0e057ae8497ca26333ce39c33388.png]: https://img-blog.csdnimg.cn/a90e0e057ae8497ca26333ce39c33388.png
[Link 6]: https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/
[3cd47bba28ad4947a32c8f9de3c2c92e.png]: https://img-blog.csdnimg.cn/3cd47bba28ad4947a32c8f9de3c2c92e.png
[6b12fa1435144413b674ddd21c54e0ef.png]: https://img-blog.csdnimg.cn/6b12fa1435144413b674ddd21c54e0ef.png