【C++】字符串的基本 *** 作和相关算法题_python

思路

- 一、问题背景
- 二、字符串的插入、删除和追加 *** 作详解【C++】
- 三、相关算法题【C++】

一、问题背景

首先来说字符串问题是十分经典的类型，我们经常会遇到输入是字符串的题目，然后利用各种STL标准库或者是一些动态规划的方法来求解问题，再或者是一些字符串遍历的一些技巧来提高效率等等，下边将介绍C++中相关的字符串常用 *** 作函数以及我们可能常会遇到的算法问题。
这里我往往会遇到字符串与数字之间的转换，主要有以下的方法：
除了上述图中提到的stoi系列函数（c++11及以上可以直接头文件string，不是c++11的话cstring），我们常常还会用到std :: atoi()函数（同上头文件string），函数格式是int atoi(const char* str)，可以将char字符串转换为数字，如果想把string类型转换为const char*可以用 c_str()方法。
例如，可以这么理解他们的主要区别：

char str[] = "123";
string str1 = "456";
cout<<atoi(str)<<endl;
cout<<stoi(str1)<<endl;
cout<<atoi(str1.c_str());
/* 输出为：
123
456
456
*************************************
除了传入参数的类型不同之外，stoi()会做范围检查，默认范围是在int的范围内的，如果超出范围的话则会runtime error！而atoi()不会做范围检查，如果超出范围的话，超出上界，则输出上界，超出下界，则输出下界；
*/

二、字符串的插入、删除和追加 *** 作详解【C++】

1. 字符串的插入（Insert函数）
1）在字符串s1的第p（从0开始数）个位置前插入字符串s2：s1.insert(p, s2);

string s1 = "abcdefg";
string s2 = "ABC";
s1.insert(3, s2);
cout<<s1<<endl;
// out: abcABCdefg

2）在字符串s1的第p个位置前插入字符串s2（取s2是从begin位置开始到end位置前的一个字符结束的子串[begin, end)）：s1.insert(p, s2, begin, end);

string s1 = "abcdef";
string s2 = "ABC";
s1.insert(3, s2, 0, 2);
cout<<s1<<endl;
// out: abcABdef

在字符串s1的第p个位置前插入n个字符c：s1.insert(p, n, c);

string s1 = "abcdef";
char c = 'A';
s1.insert(3, 3, c);
cout<<s1<<endl;
// out: abcAAAdef

2. 字符串的删除（erase函数）
1）删除字符串s1从第p个位置开始之后所有的字符（包括第p个字符）：s1.erase(p );

string s1 = "abcdef";
s1.erase(3);
cout << s1;
// out: abc

2）删除字符串s1从第p个位置开始的前n个字符：s1.erase(p, n);

string s1 = "abcdef";
s1.erase(3, 2);
cout << s1;
// out: abcf

3. 字符串的追加（append、push_back函数和+）

1）append函数：

string str1="I like C++";  
string str2=",I like the world.";  
string str3="Hello";  
string str4("Hi");  
string str5="abcd";
//====================================  
str1.append(str2);         // 在字符串后追加字符串
str3.append(str2, 11, 7);  // 在字符串后追加字符串从11开始长度为7的字符串子传，
// str3.append(str2, 11);  结果一样: Hello world. 这里意思是追加的字符串str2是从11开始到尾部子串追加上去
str5.append("1234", 2);    // 在字符串后追加具体字符串前2个字符
str4.append(5, '.');       // 在字符串后追加n个重复的字符
//====================================  
cout<<str1<<endl;  
cout<<str3<<endl;  
cout<<str4<<endl;
cout<<str5<<endl;
/*  out: 
	I like C++,I like the world.
	Hello world.
	Hi.....
	abcd12
*/

2）push_back函数：
只能将字符，这里注意不是字符串！！！

str.push_back("123");// 错误
str.push_back('1');  // ok

3）+=拼接：
注意只能将“abd”追加到string类型的字符串上，不能直接单独的两个“abc” + “def”！！

std::string str = "holiday"; 
std::string str_add = "error" + "error";           // 错误 
std::string str_add2 = my_str + "right"; 
std::string str_add3 = my_str + "right" + "right"; 
std::string str_add4 = "right" + my_str; 
std::string str_add5 = "error" + "error" + my_str; // 错误

4. 字符串的查找（fing函数）

find：从前往后查找子串或字符出现的位置
rfind：从后往前查找子串或字符出现的位置
find_first_of：从前往后查找何处出现另一个字符串中包含的字符
find_last_of：从后往前查找何处出现另一个字符串中包含的字符
如果查找到子串或字符时，返回的是string对象字符串中的位置下标；如果未查到时，则返回的是string::npos。string: :npos 是在 string 类中定义的一个静态常量。

string s1("Source Code");
int n;
if ((n = s1.find('u')) != string::npos) //查找 u 出现的位置
	cout << "1) " << n << "," << s1.substr(n) << endl;
    //输出 l) 2,urce Code
if ((n = s1.find("Source", 3)) == string::npos)
    //从下标3开始查找"Source"，找不到
    cout << "2) " << "Not Found" << endl;  //输出 2) Not Found

三、相关算法题【C++】

076.最小覆盖子串（hard）

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：
1.对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
2.如果 s 中存在这样的子串，我们保证它是唯一的答案。
/**********************************************
示例：
输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”
/**********************************************/
输入: s = “a”, t = “aa”
输出: “”
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

567.字符串的排列（medium）

题目：给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。换句话说，s1 的排列之一是 s2 的子串。
示例：
输入：s1 = “ab” s2 = “eidbaooo”
输出：true
解释：s2 包含 s1 的排列之一 (“ba”)
/*************************************************/
输入：s1= “ab” s2 = “eidboaoo”
输出：false

思路：首先我们可能第一反应是想到计算出所有的s1的排列情况，然后在滑动窗口遍历s2，判断是是否存在s1的排列，显然这样是会超时的，为了简化s1的排列情况，这里简化成字符频率分布，只要两个字符串字符分布是相同的话，那么他们肯定归属于同一个字符串的排列。同时由于题目中指出字符都是小写字母，因此我们可以利用数组来构建字符哈希。

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
    	if (s1.size()>s2.size()) return false;
    	int m = s1.size();
    	int n = s2.size();
    	vector<int> hash1(26,0);
    	vector<int> hash2(26,0);
    	for (int i=0; i<m; i++) {
 			hash1[s1[i]-'a']++;
 			hash2[s2[i]-'a']++;   	
    	}
    	for (int i=m; i<n; i++) {
			if (hash1==hash2) return true;
			hash2[s2[i-m]-'a']--;
			hash2[s2[i]-'a']++;
		}
 		return hash1==hash2; // 可能存在最后的一个窗口字符串恰好与s1匹配
	}
};