代码随想录算法训练营第九天|LeetCode151.翻转字符串里的单词、卡码网：55.右旋转字符串、LeetCode28.实现strStr()、459.重复的子字符串

前言

打卡代码随想录算法训练营第49期第九天︿(￣︶￣)︿

首先十分推荐学算法的同学可以先了解一下代码随想录，可以在B站卡哥B站账号、代码随想录官方网站代码随想录了解，卡哥清晰易懂的算法教学让我直接果断关注，也十分有缘和第49期的训练营大家庭一起进步。

今日题目

LeetCode 151 翻转字符串里的单词

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

文章讲解：翻转字符串里的单词

视频讲解：卡哥讲解 —— 翻转字符串里的单词

本题真的会让我PTSD，在没有知道卡哥之前就做过，给我做的是神志不清啊，看了卡哥之后又看到这道题还是会很恐惧，每次都会做错。

这道题的重点是去除字符串里的“ ”字符，且让整个单词位置切换，去除空字符可以直接使用双指针和去除目标数字一个原理。然后翻转单词可以先单独翻转单词字符串，然后再将整体翻转即可得到目标。

public class Solution {
    public string ReverseWords(string s) {
        int slow = 0;//慢指针
        char[] cc = s.ToArray<char>();
        for(int fast = 0; fast < s.Length; fast++)
        {
            if(cc[fast] != ' ')
            {
                if(slow != 0)//除了第一次前面没有空格 剩下所有单词前面都有空格
                    cc[slow++] = ' ';
                while(fast < s.Length && s[fast] !=' ')
                {
                    cc[slow++] = cc[fast];
                    fast++;
                }       
            }
        }
        char[] c = new char[slow];
        for(int i = 0; i < slow; i++)
            c[i] = cc[i];
        string ss = new string(c);
        string[] strs = ss.Split(" ");
        string res = "";
        for(int i = strs.Length - 1; i > 0; i--)
        {
            res += strs[i];
            res += " ";
        }
        res += strs[0];
        return res;
    }
}

卡码网 55.右旋转字符串

题目链接：右旋转字符串

文章讲解：右旋转字符串

本题和Leetcode189一样的 轮转数组这里使用卡码网的思想和上体一样，先翻转0 - Length - n的数组，再翻转n - Length的数组，最后再整体翻转即可。

#include<iostream>
#include<algorithm>
using namespace std;
int main() {
    int n;
    string s;
    cin >> n;
    cin >> s;
    int len = s.size(); //获取长度
    reverse(s.begin(), s.begin() + len - n); // 先反转前一段，长度len-n ，注意这里是和版本一的区别
    reverse(s.begin() + len - n, s.end()); // 再反转后一段
    reverse(s.begin(), s.end()); // 整体反转
    cout << s << endl;
}

轮转数组解法 

public class Solution {
    public void Rotate(int[] nums, int k) {
        int[] temp = new int[nums.Length];
        //申明临时数组
        for(int i = 0; i < nums.Length; i++)
            temp[i] = nums[i];
        //进行轮转赋值
        for(int i = 0; i < nums.Length; i++)
            nums[(i + k) % nums.Length] = temp[i];
    }
}

LeetCode 28 实现strStr()

题目链接：28. 实现 strStr()

文章讲解：实现 strStr()（KMP算法）

视频讲解：KMP1、KMP2

在字符串匹配这里一直有个大头是KMP算法，可以说是十分的抽象，我看了几遍理解也不是十分到位，直接看视频就完事了。

public class Solution {
    public int StrStr(string haystack, string needle) {
        int[] next = GetNext(needle);
        int i = 0;//对应haystack的位置
        int j = 0;//对应needle的位置
        while(i < haystack.Length)
        {
            if(haystack[i] == needle[j])
            {
                i++;
                j++;
            }
            if(j == needle.Length)//j == needle.Length代表匹配到了目标字符串
                return i - j;
            else if(i < haystack.Length && haystack[i] != needle[j])
            {
                if(j != 0)
                    j = next[j - 1];
                else
                    i++;
            }
        }
        return -1;
    }
    //求得next数组
    public int[] GetNext(string needle)
    {
        int[] next = new int[needle.Length];
        int j = 0;
        next[0] = j;
        for(int i = 1; i < needle.Length; i++)
        {
            while(j > 0 && needle[i] != needle[j])
                j = next[j - 1];//回退到上一位next数组的值的位置
            if(needle[i] == needle[j])
                j++;
            next[i] = j;
        }
        return next;
    }
}

LeetCode 459 重复的子字符串

题目链接：459 重复的子字符串

文章讲解：重复的子字符串

视频讲解：卡哥讲解 —— 重复的子字符串

本题卡哥还是想用KMP算法来做，但是因为上一题使用过了，所以这里简单一点就直接上简单的首尾相连方式。

public class Solution {
    public bool RepeatedSubstringPattern(string s) {
        string ss = s + s;//首尾相连
        char[] c = ss.ToArray<char>();
        c[0] = ' ';//首字符置空
        c[c.Length - 1] = ' '; //尾字符置空
        string newString = new string(c);
        if(newString.Contains(s))//如果新字符串包含旧字符串即可判断为重复字符串
            return true;
        return false;
    }
}

今天的KMP算法是真的虐啊，下次看到不知道能不能吃透，明天见~~~