C++后端开发学习日记（第三周）

2022.4.20 day 12 《代码随想录》之字符串（I） 344.反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O ( 1 ) O(1) O(1) 的额外空间解决这一问题。你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

分析

• reverse()函数可以翻转字符串、数组、vector容器，给出函数原型，该函数等价于通过调用iter_swap来交换元素位置，我们就是要动手实现这个函数

• 位运算的交换比复制交换更快

• s[i] ^= s[j];
  s[j] ^= s[i];
  s[i] ^= s[j];
  

双指针法实现

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

三个参数的实现

void reverse(string& s, int start, int end) {
	for (int i = start, j = end; i < j; i++, j--) {
		swap(s[i], s[j]);
	}
}

541.反转字符串II

给定一个字符串 s 和一个整数 k，你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。如果剩余字符少于 k 个，则将剩余字符全部反转；如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

分析

• 当需要固定规律一段一段去处理字符串的时候，要想想在在for循环的表达式上做做文章

实现

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)) {
            // 1. 每隔 2k 个字符的前 k 个字符进行反转
            // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
            if (i + k <= s.size()) {
                reverse(s, i, i + k - 1);
                continue;
            }
            // 3. 剩余字符少于 k 个，则将剩余字符全部反转。
            reverse(s, i, s.size() - 1);
        }
        return s;
    }
};

剑指Offer 05.替换空格

请实现一个函数，把字符串 s 中的每个空格替换成"%20"

分析

• 首先扩充数组到每个空格替换成"%20"之后的大小。然后从后向前替换空格，也就是双指针法，过程如下：i指向新长度的末尾，j指向旧长度的末尾。
• 其实很多数组填充类的问题，都可以先预先给数组扩容到填充后的大小，然后在从后向前进行 *** 作
• 这么做有两个好处：
  1. 不用申请新数组。
  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;
    }
};

151.翻转字符串里的单词（经典好题）

给定一个字符串，逐个翻转字符串中的每个单词。

分析

• 移除多余空格
• 将整个字符串反转
• 将每个单词反转

实现（双指针法删除多余空格）

class Solution {
public:
    //要求O(1)空间复杂度
    //可以用双指针移除，也可以参考27.的数组移除法  
    //双指针法，翻转字符串中左闭右闭的区间
    //注意参数必须是引用，否则s串不会被删减、翻转
    void reverse(string& s, int begin, int end) {
        for (int i = begin, j = end; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }
    //空格去重
    void remove(string& s) {
        int slow = 0, fast = 0; // 定义快指针，慢指针
        // fast移动到第一个非空格处，去掉字符串前面的空格
        while (s.size() > 0 && fast < s.size() && s[fast] == ' ') {
            fast++;
        }
        // 去掉字符串中间部分的冗余空格
        for (; fast < s.size(); fast++) {
            if (fast - 1 > 0 && s[fast - 1] == s[fast] && s[fast] == ' ') {
                continue;
            } else {
                s[slow++] = s[fast];//双指针填充
            }
        }
        // 去掉字符串末尾的空格
        if (slow - 1 > 0 && s[slow - 1] == ' ') { 
            s.resize(slow - 1);
        } else {
            s.resize(slow); // 重新设置字符串大小
        }
    }
       
    string reverseWords(string s) {
        remove(s);
        reverse(s, 0, s.size() - 1);
        for(int i = 0; i < s.size(); i++) {
            int j = i;// 新单词，j 需要重新赋值
            // 遇不到空格之前 j 一直向前走
            while(j < s.size() && s[j] != ' ') {
                j++;
            }
            reverse(s, i, j - 1);
            i = j;// i 移动到下一个单词开头
        }
        return s;
    }
};

剑指Offer58-II.左旋转字符串

字符串的左旋转 *** 作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转 *** 作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。不能申请额外空间，只能在本串上 *** 作

分析

• 局部分别翻转+整体翻转

实现

class Solution {
public:
    // 严格左闭右闭区间的翻转
    void reverse(string& s, int begin, int end) {
        for (int i = begin, j = end; i < j ; i++, j--) {
            swap(s[i], s[j]);
        }
    }
    string reverseLeftWords(string s, int n) {
        int size = s.size();
        reverse(s, 0, n - 1);//前n个翻转
        reverse(s, n, size - 1);//后k-n个翻转
        reverse(s, 0, size - 1);//整体翻转
        return s;
    }
};

每日小结

• 熟悉了字符串的 *** 作，string比char要方便的多，C++里的string不需要判断’class’。需要抽时间复习基础知识。刷题只能掌握最常见的一些库函数。

2022.4.23 day 13 《代码随想录》之字符串（II） 28. 实现 strStr()-KMP算法

备战百度笔试（C++后端开发学习日记番外篇）_Edison在努力的博客-CSDN博客

459.重复的子字符串

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000

分析

• 想到用KMP去匹配不难，难的是如何确定循环

• 如果 next[len - 1] != -1，则说明字符串有最长相同的前后缀（就是字符串里的前缀子串和后缀子串相同的最长长度）。

  最长相等前后缀的长度为：next[len - 1] + 1。(这里的next数组是以统一减一的方式计算的，因此需要+1)

  数组长度为：len。

  如果len % (len - (next[len - 1] + 1)) == 0 ，则说明 (数组长度-最长相等前后缀的长度) 正好可以被 数组的长度整除，说明有该字符串有重复的子字符串。

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

  强烈建议大家把next数组打印出来，看看next数组里的规律，有助于理解KMP算法

• next[len - 1] = 7，next[len - 1] + 1 = 8，8就是此时字符串asdfasdfasdf的最长相同前后缀的长度。

  (len - (next[len - 1] + 1)) 也就是： 12(字符串的长度) - 8(最长公共前后缀的长度) = 4， 4正好可以被 12(字符串的长度) 整除，所以说明有重复的子字符串（asdf）。

KMP算法实现

Solution public {
:void
    getNext ( int*, nextconst & string) s[{
        next0]= 0 ;int
        = j 0 ;for
        (int= i 1 ;<i . ssize();++ i)while{
            (0j > && [ s]i!= [ s]j)= {
                j [ next-j 1 ];}
            if
            ([s]i== [ s]j)++ {
                j;}
            [
            next]i= ; j}
        }
    bool
    repeatedSubstringPattern ( )string sif {
        ( .ssize()== 0 )return {
            false ;}
        int
        [ next.ssize()];getNext
        (,next) s;int
        = len . ssize();if
        ( [next-len 1 ]!= 0 && % len ( -len ( [next-len 1 ]) )== 0 )return {
            true ;}
        return
        false ;}
    }
;
理解了KMP算法及其应用

每日小结

• 经过百度笔试拷打，发现知识储备还需进一步完善。再接再厉吧，也别冲太猛。分享一句上周转发的动态吧：“你间歇性的努力和蒙混过日子，都是对之前努力的清零”。功不唐捐，玉汝于成。

本周小结