侧边栏壁纸
博主头像
thinkTV博主等级

喜爱动漫的二刺螈一枚,摩托车云爱好者(快要有车了)。 懂一点技术的在读生物医学工程研究生( •̀ ω •́ )✧,多多指教。

  • 累计撰写 127 篇文章
  • 累计创建 17 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

代码随想录算法训练营第八天 | 反转字符串;反转字符串II;替换空格;翻转字符串里的单词;左旋转字符串

thinkTV
2023-04-26 / 0 评论 / 0 点赞 / 991 阅读 / 2,192 字 / 正在检测是否收录...

1. 反转字符串

代码随想录: 原文

力扣题目: 344.反转字符串

图片-1682471550028

1.1 思路

  • 如果题目关键的部分直接用库函数就可以解决,建议不要使用库函数。
  • 如果库函数仅仅是解题过程中的一小部分,并且清楚这个库函数的内部实现原理的话,可以考虑使用库函数。

双指针法

  • 我们定义两个指针(索引下标)
  • 一个从字符串前面,一个从字符串后面
  • 两个指针同时向中间移动,并交换元素
  • 交换s[i] 和s[j]操作使用了swap的库函数

swap可以有两种实现:

  1. 交换数值
int tmp = s[i];
s[i] = s[j];
s[j] = tmp;
  1. 通过位运算
s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];

1.2 代码实现

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

2. 反转字符串II

代码随想录: 原文

力扣题目: 541. 反转字符串II

图片-1682472199587

2.1 思路

  • 遍历字符串的过程中,i 每次移动 2 * k 就,然后判断是否需要有反转的区间
  • 当需要固定规律一段一段去处理字符串的时候,for循环的表达式多考虑高效的方法
  • 库函数reverse区间是左闭右开的(多数C++自带库函数都是)

2.2 代码实现

class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += (2 * k)) {
            // 1. 每隔 2k 个字符的前 k 个字符进行反转
            // 2. 剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符
            if (i + k <= s.size()) {
                reverse(s.begin() + i, s.begin() + i + k );
            } else {
                // 3. 剩余字符少于 k 个,则将剩余字符全部反转。
                reverse(s.begin() + i, s.end());
            }
        }
        return s;
    }
};

3. 替换空格

代码随想录: 原文

力扣题目: 剑指Offer 05.替换空格

图片-1682473972508

3.1 思路

  • 不用额外的辅助空间
  • 首先扩充数组到每个空格替换成"%20"之后的大小
  • 然后用双指针法从后向前替换空格
  • i指向新长度的末尾,j指向旧长度的末尾
  • 当j指向空格时,i填充"%20"

注意:

  • 从前向后填充过于复杂,因为每次添加元素都要将添加元素之后的所有元素向后移动
  • 数组填充类的问题,先预先给数组扩容带填充后的大小,然后在从后向前进行操作

3.2 代码实现

class Solution {
public:
    string replaceSpace(string s) {
        int count = 0; // 统计空格的个数
        int sOldSize = s.size();
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ' ') {
                count++;
            }
        }
        // 扩充字符串s的大小,也就是每个空格替换成"%20"之后的大小
        s.resize(s.size() + count * 2);
        int sNewSize = s.size();
        // 从后先前将空格替换为"%20"
        for (int i = sNewSize - 1, j = sOldSize - 1; j < i; i--, j--) {
            if (s[j] != ' ') {
                s[i] = s[j];
            } else {
                s[i] = '0';
                s[i - 1] = '2';
                s[i - 2] = '%';
                i -= 2;
            }
        }
        return s;
    }
};
  • 时间复杂度:O(n)O(n)
  • 空间复杂度:O(1)O(1)

4. 翻转字符串里的单词

代码随想录: 原文

力扣题目: 151.翻转字符串里的单词

图片-1682475186034

4.1 思路

提高条件:不要使用辅助空间,空间复杂度要求为O(1)O(1)

  1. 移除多余空格

注意: 移除多余空格不建议使用erase,一个erase时间复杂度O(n)O(n)
使用双指针法来去移除空格,然后resize(重新设置)一下字符串的大小

void removeExtraSpaces(string& s) {
    int slowIndex = 0, fastIndex = 0; // 定义快指针,慢指针
    // 去掉字符串前面的空格
    while (s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' ') {
        fastIndex++;
    }
    for (; fastIndex < s.size(); fastIndex++) {
        // 去掉字符串中间部分的冗余空格
        if (fastIndex - 1 > 0
                && s[fastIndex - 1] == s[fastIndex]
                && s[fastIndex] == ' ') {
            continue;
        } else {
            s[slowIndex++] = s[fastIndex];
        }
    }
    if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') { // 去掉字符串末尾的空格
        s.resize(slowIndex - 1);
    } else {
        s.resize(slowIndex); // 重新设置字符串大小
    }
}

精简版本

// 版本二 
void removeExtraSpaces(string& s) {//去除所有空格并在相邻单词之间添加空格, 快慢指针。
    int slow = 0;   //整体思想参考https://programmercarl.com/0027.移除元素.html
    for (int i = 0; i < s.size(); ++i) { //
        if (s[i] != ' ') { //遇到非空格就处理,即删除所有空格。
            if (slow != 0) s[slow++] = ' '; //手动控制空格,给单词之间添加空格。slow != 0说明不是第一个单词,需要在单词前添加空格。
            while (i < s.size() && s[i] != ' ') { //补上该单词,遇到空格说明单词结束。
                s[slow++] = s[i++];
            }
        }
    }
    s.resize(slow); //slow的大小即为去除多余空格后的大小。
}
  1. 将整个字符串反转
// 反转字符串s中左闭右闭的区间[start, end]
void reverse(string& s, int start, int end) {
    for (int i = start, j = end; i < j; i++, j--) {
        swap(s[i], s[j]);
    }
}
  1. 将每个单词反转

4.2 代码实现

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

    void removeExtraSpaces(string& s) {//去除所有空格并在相邻单词之间添加空格, 快慢指针。
        int slow = 0;   //整体思想参考https://programmercarl.com/0027.移除元素.html
        for (int i = 0; i < s.size(); ++i) { //
            if (s[i] != ' ') { //遇到非空格就处理,即删除所有空格。
                if (slow != 0) s[slow++] = ' '; //手动控制空格,给单词之间添加空格。slow != 0说明不是第一个单词,需要在单词前添加空格。
                while (i < s.size() && s[i] != ' ') { //补上该单词,遇到空格说明单词结束。
                    s[slow++] = s[i++];
                }
            }
        }
        s.resize(slow); //slow的大小即为去除多余空格后的大小。
    }

    string reverseWords(string s) {
        removeExtraSpaces(s); //去除多余空格,保证单词之间之只有一个空格,且字符串首尾没空格。
        reverse(s, 0, s.size() - 1);
        int start = 0; //removeExtraSpaces后保证第一个单词的开始下标一定是0。
        for (int i = 0; i <= s.size(); ++i) {
            if (i == s.size() || s[i] == ' ') { //到达空格或者串尾,说明一个单词结束。进行翻转。
                reverse(s, start, i - 1); //翻转,注意是左闭右闭 []的翻转。
                start = i + 1; //更新下一个单词的开始下标start
            }
        }
        return s;
    }
};

5. 左旋转字符串

代码随想录: 原文

力扣题目: 剑指Offer58-II.左旋转字符串

图片-1682476393640

5.1 思路

  • 提高条件:不能申请额外空间,只能在本串上操作
  • 可以通过局部反转+整体反转 达到左旋转的目的

具体步骤:

  1. 反转区间为前n的子串
  2. 反转区间为n到末尾的子串
  3. 反转整个字符串

5.2 代码实现

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

6. 总结

简单题目尽可能减少空间占用时间复杂度

6.1 字符串和数组的区别

  • 字符串是若干字符组成的有限序列,可以理解为是一个字符数组
  • C语言中,把一个字符串存入一个数组时,也把结束符' \0 '存入数组,并以此作为该字符串是否结束的标志
char a[5] = "asd";
for (int i = 0; a[i] != '\0'; i++) {
}
  • 在C++中,提供一个string类,string类会提供 size接口,可以用来判断string类字符串是否结束,就不用’\0’来判断是否结束
string a = "asd";
for (int i = 0; i < a.size(); i++) {
}
  • vector< char > 和 string 基本操作上没有区别,但是 string提供更多的字符串处理的相关接口
  • 处理字符串,优先定义一个string类型

6.2 反转字符串常见操作

  • 反转一个字符串使用了双指针法
  • 固定规律一段一段去处理字符串的时候,在for循环的表达式上做文章
  • 要对一句话里的单词顺序进行反转,发现先整体反转再局部反转是一个很妙的思路
  • 左旋转字符串先局部反转再整体反转

学习时长:140min

0

评论区