LeetCode初级算法学习——字符串（二）
时间：2022-12-17 10:00:00
最后四个问题有点难
KMP是现在学的，其他的好
①字符串转换整数 (atoi)
题目大意
给定一个字符串，只包括空格、字母、数字和正反号(如果没有，则为正数)
提取字符串中的第一个有效整数（如果溢出按最大值处理）
eg1.str = " -42"，提取为-42
eg2.str = “word -四五，提取0
eg3. str = “456 with words，提取456
思路讲解
和以前一样反转字符串问题非常相似，需要判断是否溢出。此外，只需单判符号并使用一个符号flag判断是否遇到非数字，需要停止读入
注意！
int min = -247483648
int max = 2147483647
源代码
class Solution {
public: int myAtoi(string s) {
//min = -2147483648 //max = 2147483647 int n = s.size(); int cnt = 0; int res = 0; int flag = 0; while(cnt < n) {
char c = s[cnt]; if(c == ' ') {
if(!flag) {
cnt; continue; } else {
break; } } if(c==' ') {
if(flag == 0) {
flag = 1; } else {
break; } } else if(c == '-')
{
if(flag == 0)
{
flag = 2;
}
else
{
break;
}
}
else if(isdigit(c))
{
if(flag == 0)
{
flag = 1;
}
if(res > 214748364)
{
if(flag == 0 || flag == 1)
return 2147483647;
return -2147483648;
}
else if(res == 214748364)
{
int temp = c-'0';
if(flag == 2)
{
if(temp >= 8)
{
return -2147483648;
}
else
{
res *= 10;
res += temp;
}
}
else
{
if(temp >= 7)
{
return 2147483647;
}
else
{
res *= 10;
res += temp;
}
}
}
else
{
int temp = c-'0';
res *= 10;
res += temp;
}
}
else
{
break;
}
++cnt;
}
if(flag == 2)
{
return (-1*res);
}
else
{
return res;
}
}
};
②实现 strStr()
题目大意
给定一个haystack字符串，给定一个needle字符串，需要找出在haystack中出现needle的第一个位置，若未出现则返回-1
注意，在此处若needle为空，则返回0
思路讲解
KMP问题
之前一直是使用暴力来搜索的方法，这里学到了一个KMP方法，感觉受益匪浅，这里是KMP的标准板子题，所以我直接简述一下KMP即可
注：此处通过CSDN博客学习，原出处：
https://blog.csdn.net/v_JULY_v/article/details/7041827?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165838098416782390589259%2522%252C%2522scm%2522%253A%252220140713.130102334…%2522%257D&request_id=165838098416782390589259&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2alltop_positive~default-1-7041827-null-null.142v33control,185v2control&utm_term=KMP&spm=1018.2226.3001.4187
KMP思路
给定一个例子如
haystack为 “ABCDABDEABCF”
needle为“ABCF”
若暴力求解则需要以每一个字母单独开头来求解，也就是一共要比对12次
如
先比较ABCD（ABDEABCF）是否和ABCF相同
再比较（A）BCDA（BDEABCF）是否和ABCF相同
再比较（AB）CDAB（DEABCF）是否和ABCF相同
直到找到或者没找到将所有的都比对完了
复杂度比较高
而KMP则比较灵性
注意到在比较第一个时，我们只需要找到A出现的位置即可，所以在将needle和ABCD比较完后，直接再比较ABDE和ABCF即可，只需要比对三次！
再进一步
只需要找到前三个为“ABC”的就可以，也就是说我们只需要将needle与ABCD比较完后，直接再比较ABCF即可，只需要比对两次！
但是这是人脑的想法，转换成计算机思维就是，只需要记录相同前后缀出现所间隔的数字即可。
还是拿之前所举的例子来说，我们只需要记录同样以A为前后缀所间隔的数字，同样以ABC为前后缀所间隔的数字即可。
这样就可以记录一个前后缀数组
（haystack为“ABCDABDEABCF”）
所以以每一个字符为一个下标，一共需要大小为12的前后缀数组，其数组为（之后再解释）
{【0】，【0】，【0】，【0】，【1】，【2】，
【0】，【0】，【1】，【2】，【3】，【0】}
解释一下，这个数组就是以某个元素为停止处，前后缀相同的字母数
如在字符串第一个位置停止，则字符串为“A”，前后缀没有，所以数组对应数字为0
在字符串第6个位置停止，则字符串为“ABCDAB”，最长相同前后缀为"AB"，长度为2，所以数组对应数字为2
next数组是在此数组基础上稍微改进了一下。
数组第一个元素恒为-1，所有数组下标向前移动一位
所以next数组为
{【-1】，【0】，【0】，【0】，【0】，【1】，
【2】【0】，【0】，【1】，【2】，【3】}
此数组含义为，以当前元素为截止点，但不记录当前元素，此时字符串最长前后缀长度值。
这样就可以利用这个next数组，在匹配两个字符串失配时，可以不需要重新匹配，只需要移动到相应的位置直接开始匹配即可
（具体的讲解可以移步至上述博客查看，讲的很好！）
KMP的时间复杂度为O(m+n)，m和n为两个字符串的长度
源代码
class Solution {
public:
int strStr(string haystack, string needle) {
int n = needle.size();
vector<int> next(n);
int k = -1;
next[0] = -1;
int j = 0;
while(j<(n - 1))
{
if(k == -1 || needle[k] == needle[j])
{
++k;
++j;
if(needle[k]!=needle[j])
{
next[j] = k;
}
else
{
next[j] = next[k];
}
}
else
{
k = next[k];
}
}
int len = haystack.size();
int i = 0;
j = 0;
while(i<len && j<n)
{
if(j == -1 || haystack[i] == needle[j])
{
++i;
++j;
}
else
{
j = next[j];
}
}
if(j == n)
{
return i-j;
}
return -1;
}
};
③外观数列
题目大意
给定一个递推数列a(n)
a(1)为1
a(2)为11，意思是a(1)中有1个1
a(3)为21，意思是a(2)中有2个1
a(4)为1211，意思是a(3)中有1个1和1个2
a(5)为111221，意思是a(4)中有1个1和1个2和2个1
以此类推，0<=n<=30，给定n，给出a(n)
思路讲解
整体思路不负责，只需要迭代的找即可，找到当前元素最长长度，然后转换成一个字符串，把当前字符串(a(x))全部处理完后，就得到a(x+1)，这样一直处理到a(n)即可
有两个重要函数
string str
str.substr(5)，意思是从第5位开始一直截取到最后，形成新的字符串
str.substr(5,1)，意思是从第5位开始截取1位，形成新的字符串
str = to_string(num)，意思是把num这一整数转换为字符串，赋值到str中
源代码
class Solution {
public:
string countAndSay(int n) {
string str = "1";
for(int i=1;i<n;++i)
{
string res;
int len = str.size();
int cnt = 1;
for(int j=0;j<(len-1);++j)
{
if(str[j] == str[j+1])
{
++cnt;
}
else
{
string num = to_string(cnt);
string temp = str.substr(j,1);
res += num;
res += temp;
cnt = 1;
}
}
if(cnt > 1)
{
string num = to_string(cnt);
string temp = str.substr(len-1,1);
res += num;
res += temp;
}
else
{
string num = to_string(1);
string temp = str.substr(len-1,1);
res += num;
res += temp;
}
str = res;
}
return str;
}
};
④最长公共前缀
题目大意
找到字符串数组中的最长公共前缀
思路讲解
没啥好说的，挺简单，只需要用一个循环找到最短字符串，然后以该长度去遍历整个字符串数组，如果所有字符串在该位都相同，则继续向后遍历，否则该位置-1，就是最长前缀
源代码
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
int n = strs.size();
int minx = 250;
for(int i=0;i<n;++i)
{
int temp = strs[i].size();
minx = min(minx,temp);
}
int j = 0;
bool flag = false;
for(j=0;j<minx;++j)
{
char temp = strs[0][j];
for(int i=0;i<n;++i)
{
if(strs[i][j] != temp)
{
flag = true;
break;
}
}
if(flag)
{
break;
}
}
return strs[0].substr(0,j);
}
};
