＜冲刺大厂之算法刷题＞字符串_C

📒博客首页：热爱编程的大李子 📒

🌞专栏首页：LeetCode刷题 🌞

🙏博主在学习阶段，如若发现问题，请告知，非常感谢🙏

💙同时也非常感谢各位小伙伴们的支持💙

🌈每日一语：承遇朝霞，年少正恰。整装戎马，刻印风华！ 🌈

💗感谢：我只是站在巨人们的肩膀上整理本篇文章，感谢走在前路的大佬们！💗

🌟最后，祝大家每天进步亿点点！欢迎大家点赞👍➕收藏⭐️➕评论💬支持博主🤞！🌟

⭐️ ⭐️上篇文章-＜冲刺大厂之算法刷题＞Hash表 ⭐️ ⭐️

文章目录

- 344. 反转字符串
- - - 题目描述
    - 思路分析
    - 参考代码
- 541. 反转字符串 II
- - - 题目描述
    - 思路分析
    - 参考代码
- 剑指 Offer 05. 替换空格
- - - 题目描述
    - 思路分析
    - 参考代码
- 151. 翻转字符串里的单词
- - - 题目描述
    - 思路分析
    - 参考代码
- 剑指 Offer 58 - II. 左旋转字符串
- - - 题目描述
    - 思路分析
    - 参考代码
- 28. 实现 strStr()
- - - 题目描述
    - 思路分析
    - 参考代码
- 459. 重复的子字符串
- - - 题目描述
    - 思路分析
    - 参考代码
- 总结

344. 反转字符串题目描述

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 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"]

思路分析

双指针法反转数组

参考代码

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

541. 反转字符串 II 题目描述

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

输入：s = "abcdefg", k = 2
输出："bacdfeg"

示例 2：

输入：s = "abcd", k = 2
输出："bacd"

思路分析

每2k个字符长度,反转前k个的字符==> 这也就决定了i每一轮的增量是2k
如果不够2k但大于k则反转前k个.
如果剩余的小于k,则全部进行反转.

参考代码

string reverseStr(string s, int k) {
	int i = 0;
	for(; i < s.size();i+=2*k){
		if(i+k<s.size()) {//如果每次剩余的字符>k,那么就可以进行反转前k个 
			reverse(s.begin()+i,s.begin()+i+k);
		}else{//如果不够k个,则反转剩余的全部 
			reverse(s.begin()+i,s.end());
		}
	}
	return s; 
}

剑指 Offer 05. 替换空格题目描述

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

示例 1：

输入：s = "We are happy."
输出："We%20are%20happy."

思路分析

方法一:双指针

由于C++ 的string底层维护的也是一个字符数组.我们知道数组元素的删除和插入有时候会导致所有元素都向后移动,这样很花费时间. 所有我们可以提前统计字符串中的空格,然后为字符串重新到最终需要的空间.
处理时我们使用快慢指针,从后往前一边将空格转换成%20,一边将元素放在对应的位置.最终返回字符串即可.

算法步骤:

统计字符串s中的空格个数:cnt
为s重新分配更大的空间:s.size()+cnt*2
定义两个指针i,j从后往前,一边将空格转换成%20,一边将元素放在对应的位置
返回字符串s

方法二:字符串拼接

定义一个字符串变量,如果是非空格字符则直接进行拼接,如果是空格则拼接上%20. 虽然是最普通的方法,但是这个效率还蛮高的,嘿嘿

参考代码

方法一:双指针

#include
using namespace std;

string replaceSpace(string s) {
	int j,k,cnt = 0;
	for(int i = 0;i < s.size();i++){
		if(s[i]==' '){
			cnt++;
		}
	}
	j = s.size()-1;
	k = s.size()+cnt*2-1;
	//进行扩容
	s.resize(s.size()+cnt*2) ;
	
	//从后往前进行遍历
	while(j<k) {
		if(s[j]!=' '){
			s[k] = s[j];//不是空格,则将元素放在指定位置 
			j--;
			k--;
		}else{//为空格,则替换空格为%20 
			s[k] = '0';
			s[k-1] = '2';
			s[k-2] = '%';
			j--;
			k-=3;
		}
	}
	return s;
}

方法二:字符串拼接

string replaceSpace(string s) {
	string ans="";
	for(int i = 0;i < s.size();i++){
		if(s[i]!=' '){
			ans+=s[i];
		}else{
			ans +="%20";
		}
	}
	return ans;
}

151. 翻转字符串里的单词题目描述

给你一个字符串 s ，逐个翻转字符串中的所有单词。

单词是由非空格字符组成的字符串。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"

解释：如果两个单词间有多余的空格，将翻转后单词间的空格减少到只含一个。

示例 4：

输入：s = "  Bob    Loves  Alice   "
输出："Alice Loves Bob"

示例 5：

输入：s = "Alice does not even like bob"
输出："bob like even not does Alice"

思路分析

提高一下题目的难度:不要使用辅助空间,空间复杂度要求为 O ( 1 ) O(1) O(1)

解题思路:

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

举个栗子,源字符串为："the sky is blue "

移除多余空格 : “the sky is blue”
字符串反转：“eulb si yks eht”
单词反转：“blue is sky the”

这样我们就完成了翻转字符串里的单词。

但是如何去除单词间的空格呢?

身为菜鸡的我想到的是循环+判断+erase() ,但是要知道erase()的时间复杂度也是O(n),从而也就导致了整体时间复杂度为O(n^2);

想一下我们还有其他办法降低时间复杂度嘛,突然,灵光一现,俺想到了之前数组篇章的—去除数组中指定元素,我们采用的是双指针 ,从而移除空格这个方法就搞定了!

**注意:**由于自带的reverse无法满足我们对字符串中的子串进行反转,所以我们需要自定义reverse方法.

参考代码

#include
using namespace std;

//移除空格方法
void removeExtraSpaces(string& s) {
	int slow = 0,fast = 0;

	//移除字符串前面的空格
	while(fast<s.size() && s[fast]==' ') {//  a good   example
		fast++;
	}

	//移除字符串中间的空格
	while(fast<s.size()) {
		if(fast>=1&&s[fast]==' '&&s[fast-1]==' ') { //fast>=1
			fast++;
		} else {
			s[slow] = s[fast];
			slow++;
			fast++;
		}
	}

	//移除字符串后面的空格(如果有则肯定是一个)
	if(slow-1>=0&&s[slow-1]==' ') {
		s.resize(slow-1);//如果最后一个字符是空格
	} else {
		s.resize(slow);//如果最后一个字符不是空格
	}
}

//反转字符串 时间复杂度O(N)
void reverse(string& s,int i,int j) {
	while(i<j) {
		swap(s[i],s[j]);
		i++;
		j--;
	}
}

string reverseWords(string s) {
	removeExtraSpaces(s);//移除空格 
	reverse(s,0,s.size()-1);//整体反转
	int i = 0,j;
	while(i<s.size()) {//反转单词 
		j = i;
		while(j<s.size()&&s[j]!=' '){//寻找空格的位置 j
			j++;
		}
		reverse(s,i,j-1);//反转单词 
		i = j+1;//更新i 
	}
	return s; 
}

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

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

题目描述

示例 1：

输入: s = "abcdefg", k = 2
输出: "cdefgab"

示例 2：

输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"

思路分析

方法一

直接进行字符串截取,然后拼接在一块就行(毫无技术含量)

方法二

我们再次成为大佬,提高下难度:不能申请额外空间，只能在本串上 *** 作

做法:局部+整体反转

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

参考代码

#include
using namespace std;

//手动实现的reverse 
void reverse(string& s,int begin,int end) {
	while(begin<end){
		swap(s[begin],s[end]) ;
		begin++;
		end--;
	}
}

//其中可以手动实现个reverse 
string reverseLeftWords(string s, int n) {
//	reverse(s.begin(),s.-()+n);
//	reverse(s.begin()+n,s.end());
//	reverse(s.begin(),s.end());
	reverse(s,0,n-1) ;
	reverse(s,n,s.size()-1) ;
	reverse(s,0,s.size()-1 ;
	return s;
}

28. 实现 strStr() 题目描述

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

说明：

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

示例 1：

输入：haystack = "hello", needle = "ll"
输出：2

示例 2：

输入：haystack = "aaaaa", needle = "bba"
输出：-1

示例 3：

输入：haystack = "", needle = ""
输出：0

思路分析

纯正的KMP算法,不懂的可以看我这篇博客

求Next()数组的方法.

参考代码

//haystack:文本串  needle:模板串
void getNext(int* Next,const string& s) {
	int i = 1,j = 0;//初始化i,j
	Next[0]  = 0;
	for(; i<s.size(); i++) {
		//寻找相同字符
		while(j>0&&s[i]!=s[j]) {//如果s[i] 和s[j] 不相等,则j进行后退当上一个公共前缀位置,直到相等或者j=0(也就是无法继续后退)
			j = Next[j-1];
		}
		if(s[i]==s[j]) { //判断后退之后的两个字符是否相等
			j++;
		}
		Next[i]  = j;//更新Next.
	}
}

//haystack:文本串  needle:模板串
int strStr(string haystack, string needle) {

	int Next[needle.size()] ;//定义Next数组
	getNext(Next,needle);//初始化
	int j = 0,i = 0;
	for(; i<haystack.size(); i++) {
		//如果不相等,则模板串调到最长公共前缀的下一个位置
		while(j>0 &&haystack[i]!=needle[j]) {
			j = Next[j-1] ;
		}

		if(haystack[i]==needle[j]) {
			j++;
		}
		if(j==needle.size()) { //寻找完毕
			return i-needle.size()+1;//返回查找到的起始下标.
		}
	}
	return -1;//没有找到则返回-1
}

459. 重复的子字符串题目描述

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

示例 1:

输入: "abab"

输出: True

解释: 可由子字符串 “ab” 重复两次构成。

示例 2:

输入: "aba"

输出: False

示例 3:

输入: "abcabcabcabc"

输出: True

解释: 可由子字符串 “abc” 重复四次构成。 (或者子字符串 “abcabc” 重复两次构成。)

思路分析

KMP算法的经典使用外加一点小技巧
假设数组长度为len,如果len % (len - next[len - 1]) == 0 ,则说明字符串有重复的子字符串.
为什么呢?
数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。
我们看一下Next数组就很清楚了,如下:

**分析:**在第一个周期内next[x]=0,当走出第一个周期后next[i]>0,所以如果该字符串可以由某一个子串组成,那么len - next[len - 1] 一定会被len整除的.

参考代码

#include
using namespace std;

void getNext(int* Next,const string& s){
	int i = 1,j = 0;//定义及 初始化 
	Next[0] = 0;
	for(;i<s.size();i++) {
		while(j>0&&s[i]!=s[j]){//如果不相等,则j进行后退当上一个公共前缀位置,直到相等或者j=0(也就是无法继续后退)
			j = Next[j-1];
		}
		//判断是否相等
		if(s[i]==s[j]) {
			j++;
		}
		//更新Next[i]
		Next[i] = j; 
	}
	
}

bool repeatedSubstringPattern(string s) {
	//主要思想是:字符串长度 % (字符串长度-最长公共前缀 ) = 0,则说明出现重复的子字符串
	int len = s.size();
	int Next[len] ;//定义Next数组
	getNext(Next,s) ;
	if(Next[len-1]&&len % (len - Next[len-1])==0){
		return true;
	}
	return false;
}

int main(){
	string str = "abababaaba";
	cout<<repeatedSubstringPattern(str)<<endl;
	return 0;
}