4.字符串
字符串理论基础
什么是字符串
字符串是若⼲字符组成的有限序列,也可以理解为是⼀个字符数组,但是很多语⾔对字符串做了特殊的规定,接下来我来说⼀说C/C++中的字符串。
在C语⾔中,把⼀个字符串存⼊⼀个数组时,也把结束符 '\0’存⼊数组,并以此作为该字符串是否结束的标志。
例如这段代码:
char a[5] = "asd";
for (int i = 0; a[i] != '\0'; i++) {
}
在C++中,提供⼀个string类,string类会提供 size接⼝,可以⽤来判断string类字符串是否结束,就不⽤’\0’来判断
是否结束。
例如这段代码:
string a = "asd";
for (int i = 0; i < a.size(); i++) {
}
那么vector< char > 和 string ⼜有什么区别呢?
其实在基本操作上没有区别,但是 string提供更多的字符串处理的相关接⼝,例如string 重载了+,⽽vector却没
有。
所以想处理字符串,我们还是会定义⼀个string类型。
字符串套路总结
双指针法
在344.反转字符串 (opens new window),我们使用双指针法实现了反转字符串的操作,双指针法在数组,链表和字符串中很常用。
接着在字符串:替换空格 (opens new window),同样还是使用双指针法在时间复杂度O(n)的情况下完成替换空格。
其实很多数组填充类的问题,都可以先预先给数组扩容带填充后的大小,然后在从后向前进行操作。
那么针对数组删除操作的问题,其实在27. 移除元素 (opens new window)中就已经提到了使用双指针法进行移除操作。
同样的道理在151.翻转字符串里的单词 (opens new window)中我们使用O(n)的时间复杂度,完成了删除冗余空格。
反转系列
在反转上还可以在加一些玩法,其实考察的是对代码的掌控能力。
541. 反转字符串II (opens new window)中,一些同学可能为了处理逻辑:每隔2k个字符的前k的字符,写了一堆逻辑代码或者再搞一个计数器,来统计2k,再统计前k个字符。
其实当需要固定规律一段一段去处理字符串的时候,要想想在在for循环的表达式上做做文章。
只要让 i += (2 * k),i 每次移动 2 * k 就可以了,然后判断是否需要有反转的区间。
因为要找的也就是每2 * k 区间的起点,这样写程序会高效很多。
在151.翻转字符串里的单词 (opens new window)中要求翻转字符串里的单词,这道题目可以说是综合考察了字符串的多种操作。是考察字符串的好题。
这道题目通过 先整体反转再局部反转,实现了反转字符串里的单词。
后来发现反转字符串还有一个牛逼的用处,就是达到左旋的效果。
在字符串:反转个字符串还有这个用处? (opens new window)中,我们通过先局部反转再整体反转达到了左旋的效果
KMP
什么是KMP
说到KMP,先说一下KMP这个名字是怎么来的,为什么叫做KMP呢。
因为是由这三位学者发明的:Knuth,Morris和Pratt,所以取了三位学者名字的首字母。所以叫做KMP
KMP有什么用
KMP主要应用在字符串匹配上。
KMP的主要思想是当出现字符串不匹配时,可以知道一部分之前已经匹配的文本内容,可以利用这些信息避免从头再去做匹配了。
所以如何记录已经匹配的文本内容,是KMP的重点,也是next数组肩负的重任
什么是前缀表
写过KMP的同学,一定都写过next数组,那么这个next数组究竟是个啥呢?
next数组就是一个前缀表(prefix table)。
前缀表有什么作用呢?
前缀表是用来回退的,它记录了模式串与主串(文本串)不匹配的时候,模式串应该从哪里开始重新匹配。前缀表是如何记录的呢?
首先要知道前缀表的任务是当前位置匹配失败,找到之前已经匹配上的位置,再重新匹配,此也意味着在某个字符失配时,前缀表会告诉你下一步匹配中,模式串应该跳到哪个位置。
那么什么是前缀表:记录下标i之前(包括i)的字符串中,有多大长度的相同前缀后缀。
最长公共前后缀
文章中字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。
后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
正确理解什么是前缀什么是后缀很重要!
因为前缀表要求的就是相同前后缀的长度。
而最长公共前后缀里面的“公共”,更像是说前缀和后缀公共的长度。这其实并不是前缀表所需要的。
所以字符串a的最长相等前后缀为0。 字符串aa的最长相等前后缀为1。 字符串aaa的最长相等前后缀为2。 等等…。
为什么一定要用前缀表
这就是前缀表,那为啥就能告诉我们 上次匹配的位置,并跳过去呢?
回顾一下,刚刚匹配的过程在下标5的地方遇到不匹配,模式串是指向f,如图:
然后就找到了下标2,指向b,继续匹配:如图:
以下这句话,对于理解为什么使用前缀表可以告诉我们匹配失败之后跳到哪里重新匹配 非常重要!
下标5之前这部分的字符串(也就是字符串aabaa)的最长相等的前缀 和 后缀字符串是 子字符串aa ,因为找到了最长相等的前缀和后缀,匹配失败的位置是后缀子串的后面,那么我们找到与其相同的前缀的后面重新匹配就可以了。
所以前缀表具有告诉我们当前位置匹配失败,跳到之前已经匹配过的地方的能力。
很多介绍KMP的文章或者视频并没有把为什么要用前缀表?这个问题说清楚,而是直接默认使用前缀表。
如何计算前缀表
接下来就要说一说怎么计算前缀表。
如图:
长度为前1个字符的子串a
,最长相同前后缀的长度为0。(注意字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串;后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。)
长度为前2个字符的子串aa
,最长相同前后缀的长度为1。
长度为前3个字符的子串aab
,最长相同前后缀的长度为0。
以此类推: 长度为前4个字符的子串aaba
,最长相同前后缀的长度为1。 长度为前5个字符的子串aabaa
,最长相同前后缀的长度为2。 长度为前6个字符的子串aabaaf
,最长相同前后缀的长度为0。
那么把求得的最长相同前后缀的长度就是对应前缀表的元素,如图:
可以看出模式串与前缀表对应位置的数字表示的就是:下标i之前(包括i)的字符串中,有多大长度的相同前缀后缀。
再来看一下如何利用 前缀表找到 当字符不匹配的时候应该指针应该移动的位置。如动画所示:
找到的不匹配的位置, 那么此时我们要看它的前一个字符的前缀表的数值是多少。
为什么要前一个字符的前缀表的数值呢,因为要找前面字符串的最长相同的前缀和后缀。
所以要看前一位的 前缀表的数值。
前一个字符的前缀表的数值是2, 所以把下标移动到下标2的位置继续比配。 可以再反复看一下上面的动画。
最后就在文本串中找到了和模式串匹配的子串了。
前缀表与next数组
很多KMP算法的实现都是使用next数组来做回退操作,那么next数组与前缀表有什么关系呢?
next数组就可以是前缀表,但是很多实现都是把前缀表统一减一(右移一位,初始位置为-1)之后作为next数组。
为什么这么做呢,其实也是很多文章视频没有解释清楚的地方。
其实这并不涉及到KMP的原理,而是具体实现,next数组既可以就是前缀表,也可以是前缀表统一减一(右移一位,初始位置为-1)。
后面我会提供两种不同的实现代码,大家就明白了。
使用next数组来匹配
以下我们以前缀表统一减一之后的next数组来做演示。
有了next数组,就可以根据next数组来 匹配文本串s,和模式串t了。
注意next数组是新前缀表(旧前缀表统一减一了)。
匹配过程动画如下:
时间复杂度分析
其中n为文本串长度,m为模式串长度,因为在匹配的过程中,根据前缀表不断调整匹配的位置,可以看出匹配的过程是O(n),之前还要单独生成next数组,时间复杂度是O(m)。所以整个KMP算法的时间复杂度是O(n+m)的。
暴力的解法显而易见是O(n × m),所以KMP在字符串匹配中极大地提高了搜索的效率。
为了和力扣题目28.实现strStr保持一致,方便大家理解,以下文章统称haystack为文本串, needle为模式串。
都知道使用KMP算法,一定要构造next数组。
还是感觉太复杂,直接用string::find()来代替KMP功能
练习
Hjk掌握的单词个数
题目描述
有一个字符串数组 words 和一个字符串 chars。
假如可以用 chars 中的字母拼写出 words 中的某个“单词”(字符串),那么我们就认为你掌握了这个单词。
words 的字符仅由 a-z 英文小写字母组成,例如 “abc”
chars 由 a-z 英文小写字母和 “?” 组成。其中英文 “?” 表示万能字符,能够在拼写时当作任意一个英文字母。例如:“?” 可以当作 “a” 等字母。
注意:每次拼写时,chars 中的每个字母和万能字符都只能使用一次。
输出词汇表 words 中你掌握的所有单词的个数。没有掌握任何单词,则输出0。
输入描述
第一行:输入数组 words 的个数,记作N。
第二行 ~ 第N+1行:依次输入数组words的每个字符串元素
第N+2行:输入字符串chars
3
blue
hair
id
bd?lue
输出描述
输出一个整数,表示词汇表 words 中你掌握的单词个数
2
备注
1 ≤ words.length ≤ 100
1 ≤ words[i].length, chars.length ≤ 100
所有字符串中都仅包含小写英文字母、英文问号
首先读入words
数组的大小和元素,然后读入chars
字符串。接着,它使用getwords
函数来计算可以使用chars
字符串中的字符(包括万能字符)拼写的单词数量。canspell
函数用于判断单个单词是否可以被拼写,通过对字符的使用计数和处理万能字符的逻辑。最后,程序输出掌握的单词数量。
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
bool canspell(std::string& word, std::unordered_map<char, int> charsmap, int wildcount ) {
for(char c: word) {
if (charsmap[c] > 0) {
charsmap[c] --;
}
else if (wildcount > 0) { // 如果有通配符可用
wildcount--;
} else { // 如果字符不在映射中且没有通配符可用
return false;
}
}
return true;
}
int getwords(std::vector<std::string>& words, const std::string& chars) {
std::unordered_map<char, int> charsmap;
int wildcount = 0;
for (char i: chars) {
if (i == '?') wildcount ++;
else charsmap[i] ++;
}
int count = 0;
for (std::string word: words) {
if (canspell(word, charsmap, wildcount)) {
count ++;
}
}
return count;
}
int main() {
//处理输入
int N;
std::cin >> N;
std::cin.ignore();
std::vector<std::string> words(N);
for (int i = 0; i < N; i ++) {
std::getline(std::cin, words[i]);
}
std::string chars;
std::getline(std::cin, chars);
std::cout << getwords(words, chars) << std::endl;
return 0;
}
Hkj url拼接
拼接URL
题目描述:
给定一个url前缀和url后缀,通过,分割 需要将其连接为一个完整的url
如果前缀结尾和后缀开头都没有/,需要自动补上/连接符
如果前缀结尾和后缀开头都为/,需要自动去重
约束:不用考虑前后缀URL不合法情况
输入描述:
url前缀(一个长度小于100的字符串) url后缀(一个长度小于100的字符串)
输出描述:
拼接后的url
示例
输入: /acm,/bb
输出: /acm/bb
输入: /abc/,/bcd
输出: /abc/bcd
输入: /acd,bef
输出: /acd/bef
输入: ,
输出: /
Hkj字符串切割方法
给定一个由小写字母组成的字符串。请找出两个位置,将字符串分为三部分。这三部分的总和应该是相同的,其中每部分的总和是其字符的ASCII码值的总和。注意,这两个位置的字符不包括在这三部分内。
如果你找到了这两个位置,请输出它们的位置。如果没有找到,请输出0,0。
例子:
输入: acdbbbca
输出: 2,5
这是因为当我们在位置2和5进行分割,我们得到三个部分:ac,bb,ca。它们的ASCII码值的总和都是相同的。
输入: abcabc
输出: 0,0
在这个例子中,我们找不到这样的两个位置。
题目分析
遍历字符串,尝试所有可能的两个位置作为分割点,然后比较这三部分的ASCII值之和。为了高效计算,我们可以首先计算字符串的累积ASCII值之和,这样就可以在常数时间内获取任何子字符串的ASCII值之和。
#include <iostream>
#include <string>
#include <vector>
int main() {
std::string s;
std::getline(std::cin, s);
//定义前缀和
int n = s.size();
std::vector<int> prefixsum(n + 1, 0);
for (int i = 1; i <= s.size(); i++) {
prefixsum[i] = prefixsum[i - 1] + s[i - 1];
}
bool find = false;
for (int i = 0; i < n; i++) {
for (int j = i + 2; j < n; j++) {
int sum1 = prefixsum[i] - prefixsum[0]; // 第一部分的和
int sum2 = prefixsum[j] - prefixsum[i + 1]; // 第二部分的和
int sum3 = prefixsum[n] - prefixsum[j + 1]; // 第三部分的和
if (sum1 == sum2 && sum2 == sum3) {
std::cout << i << "," << j <<std::endl;
find = true;
}
}
}
if (!find) std::cout <<"0,0" << std::endl;
return 0;
}
Hjk回文字符串
什么是"回文串"?就是一个字符串正着读和反着读都一样,而且要注意大小写的区别。
例如:
"leVel"是一个回文串,因为正着反着都一样。
"art"就不是,反过来就变成"tra"了。
"Level"也不是,因为大小写不同。
现在,你要做的就是用给定的一个字符串(只含有大小写字母)来构建一个最长的回文串。有一个小要求:每个字母只能用一次,或者干脆不用。如果最长的回文串有好几个,那就选字母顺序最小的那个返回。
比如:输入"abczcccddzz",你可以构造出"ccdzazdcc"这样一个回文串。
为了构建给定字符串中可能的最长回文串,我们可以遵循以下步骤:
- 计数每个字符的出现次数:首先,我们需要计算字符串中每个字符出现的次数。这可以通过使用一个字符到其出现次数的映射(例如,使用
std::map<char, int>
)来完成。 - 构造回文串:接下来,我们可以使用每个字符的最大偶数出现次数来构造回文串的一半。如果有字符出现了奇数次,我们可以选择其中一个作为中心字符(如果有多个奇数出现的字符,选择字母顺序最小的那个作为中心)。构造过程中,对于每个字符,将它的一半加到回文串的一侧,然后如果有中心字符,将其放在中间,最后按相反顺序将字符加到回文串的另一侧。
- 返回结果:构造完成后,我们得到的就是满足条件的最长回文串。
#include <iostream>
#include <string>
#include <map>
#include <algorithm>
int main() {
std::string s;
std::getline(std::cin, s);
std::map<char, int> charsmap;
for (int i = 0; i < s.size(); i++){
charsmap[s[i]] ++;
}
//构建回文串
char center = '\0';
std::string palindromehalf;
for (auto chars : charsmap) {
if (chars.second % 2 == 1 && (center == '\0' || chars.first < center)) {
center = chars.first;
}
else palindromehalf.append(std::string(chars.second / 2, chars.first));
}
std::string palindrome = palindromehalf;
if (center != '\0') palindrome += center;
std::reverse(palindromehalf.begin(), palindromehalf.end());
palindrome += palindromehalf;
std::cout << palindrome << std::endl;
return 0;
}
Hjk IPV4地址转化为整数
存在一种虚拟IPv4地址,由4小节组成,每节的范围为0~255,以#号间隔,虚拟IPv4地址可以转换为一个32位的整数,例如:
128#0#255#255,转换为32位整数的结果为2147549183(0x8000FFFF)1#0#0#0,转换为32位整数的结果为16777216(0x01000000)
现以字符串形式给出一个虚拟IPv4地址,限制第1小节的范围为1128,即每一节范围分别为(1128)#(0255)#(0255)#(0-255),要求每个IPV4地址只能对应到唯一的整数上。如
果是非法IPV4,返回invalidIP
输入描述
输入一行,虚拟IPv4地址格式字符串
输出描述
输出一行,按照要求输出整型或者特定字符
示例
输入: 100#101#1#5
输出: 1684340997
输入: 1#2#3
输出: invalid IP
分析
split
函数:将输入的字符串按指定的分隔符(在这个例子中是#
)分割成子字符串,并将它们存储在一个vector<string>
中返回。
convertToInteger
函数:将存储有四部分虚拟IPv4地址的字符串数组转换为一个32位的整数。这是通过将每部分解析为整数,然后左移适当的位数(基于它是地址中的哪一部分)并通过位或操作合并到结果中实现的。
isValidIP`函数:验证输入的虚拟IPv4地址是否合法。它检查地址是否有四部分,并且每部分的数值是否在合法范围内(对于第一部分是1到128,其余部分是0到255)。
**main函数**:读取输入,使用
split函数分割输入的虚拟IPv4地址,然后检查它是否合法。如果地址合法,它将调用
convertToInteger`函数来转换地址,并输出结果;否则,输出"invalid IP"。
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
std::vector<std::string> split(std::string& s) {
std::stringstream ss(s);
std::string token;
std::vector<std::string> parts;
while (std::getline(ss, token, '#')) {
parts.push_back(token);
}
return parts;
}
bool isvalid(std::vector<std::string>& parts) {
if (parts.size() != 4) return false;
for (int i = 0; i < parts.size(); i++) {
int num = std::stoi(parts[i]);
if (i == 0 && (num < 1 || num > 128)) {
return false;
}
else if (num < 0 || num > 255) {
return false;
}
}
return true;
}
unsigned long getres(std::vector<std::string>& parts) {
unsigned long res = 0;
for (int i = 0; i < parts.size(); i++) {
res |= std::stoul(parts[i]) << (3 - i)*8;
}
return res;
}
int main() {
std::string s;
std::getline(std::cin, s);
//分割string存入vector
std::vector<std::string> parts = split(s);
//判断IP是否有效
if (!isvalid(parts)) {
std::cout << "invalid IP" << std::endl;
}
// 计算整数
else {
unsigned int res = getres(parts);
std::cout << res << std::endl;
}
return 0;
}
Hjk响应报文时间
假设你正在接收网络报文,并且需要在一定时间内对它们作出响应。每次当你收到一个报文时,它会有一个“最大响应时间”来告诉你最晚需要在什么时候回应。但是,如果在等待回应期间又收到了新的报文,你可能需要更新你的响应时间。
“最大响应时间”是这样计算的:
如果它的代码小于128,那么响应时间就是这个代码。
如果它的代码是128或更大,我们会使用一种特殊的方式来计算。简单来说,我们会把这个代码转换为二进制,然后根据它的某些位来获取两个值: exp 和 mant。响应时间将是 (mant | 0x10) << (exp + 3)。
注:exp最大响应时间的高5~7位mant为最大响应时间的低4位。
现在,你的任务是,根据给定的报文数量、收到报文的时间和最大响应时间代码,计算你应该在什么时候发出响应。
输入
第一行是你收到的报文数量。
接下来的每一行都会有两个数字:收到报文的时间和最大响应时间代码。
输出
你应该在什么时候发送响应。
注意
保证在所有的输入中,你只会发送一次响应,且在你的响应计时结束后,不会再收到新的报文。
示例
输入
3
0 20
1 10
8 20
输出
11
说明
收到3个报文,
第0秒收到第1个报文,响应时间为20秒,则要到0+20=20秒响应;
第1秒收到第2个报文,响应时间为10秒,则要到1+10=11秒响应,与上面的报文的响应时间比较获得响应时间最小为11秒;
第8秒收到第3个报文,响应时间为20秒,则要到8+20=28秒响应,与第上面的报文的响应时间比较获得响应时间最小为11秒;
最终得到最小响应报文时间为11秒
示例2
输入
2
0 255
200 60
输出
260
说明
收到2个报文,
第0秒收到第1个报文,响应时间为255秒,则要到(1510×10)<<(7+3)=31744秒响应;(mant=15,exp=7)
第200秒收到第2个报文,响应时间为60秒,则要到200+60-260秒响应,
与第上面的报文的响应时间比较获得响应时间最小为260秒:
最终得到最小响应报文时间为260秒
这种题纯纯恶心
#include <iostream>
#include <algorithm> // 用于std::max函数
int main() {
int numMessages;
std::cin >> numMessages; // 读取报文数量
int finalResponseTime = 0; // 初始化最终响应时间
for (int i = 0; i < numMessages; ++i) {
int receivedTime, code;
std::cin >> receivedTime >> code; // 读取每个报文的接收时间和代码
int responseTime;
if (code < 128) {
// 如果代码小于128,响应时间就是这个代码
responseTime = receivedTime + code;
} else {
// 如果代码是128或更大,使用特殊方式计算响应时间
int exp = (code >> 5) & 0x07; // 获取高3位作为exp
int mant = code & 0x0F; // 获取低4位作为mant
responseTime = receivedTime + ((mant | 0x10) << (exp + 3));
}
// 更新最终响应时间
if (i == 0 || responseTime < finalResponseTime) {
finalResponseTime = responseTime;
}
}
// 输出最终响应时间
std::cout << finalResponseTime << std::endl;
return 0;
}
Hjk报文重排序
对报文进行重传和重排序是常用的可靠性机制,重传缓冲区内有一定数量的子报文,每个子报文在原始报文中的顺序已知,现在需要恢复出原始报文。
输入描述
输入第一行为N,表示子报文的个数,0 < N <= 1000。
输入第二行为N个子报文,以空格分开,子报文格式为字符串报文内容+后缀顺序索引,字符串报文内容由|a-z,A-Z)组成后缀为整形值,表示顺序。顺序值唯一,不重复。
输出描述:
EN输出恢复出的原始报文。按照每个子报文的顺序的升席排序恢复出原始报文,顺序后缀需要从恢复出的报文中删除掉
用例1
输入:
4
rolling3 stone4 like1 a2
输出:
like a rolling stone
说明:
4个子报文的内容分别为roling,stone,like,a,顺序值分别为3,4,1,2,按照顺序值升序并删除掉顺序后缀得到恢复的原始报文: like a rolling stone
用例2
输入:
8
Lgifts6 and7 Exchanging1 all2 precious5 things8 kinds3 of43
// 注: 这里需要注意:and7与Exchanging1有两个空格
输出:
Exchanging all kinds of precious gifts and things
分析
我们可以把每个子报文的顺序索引作为键,子报文内容作为值。这样,在插入过程中map
会自动根据顺序索引对子报文进行排序,然后我们只需要按顺序遍历map
并输出子报文内容即可。
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cctype>
std::map<int, std::string> splitword(std::vector<std::string>& words) {
std::map<int, std::string> messmap;
for (const auto& word: words) {
std::string mes;
std::string numStr;
//从字符串末尾开始遍历,分离数字和文本
for (int i = word.size() - 1; i >= 0; i--) {
if (std::isdigit(word[i])) {
numStr.insert(numStr.begin(), word[i]);
}
else {
mes = word.substr(0, i + 1);
break;
}
}
int num = std::stoi(numStr);
messmap[num] = mes;
// std::string mes = word.substr(0, word.size() - 1);
// int num = word.back() - '0';
// std::pair<int, std::string> iter = {num, mes};
// messmap.insert(iter);
}
return messmap;
}
int main() {
int N;
std::cin >> N;
std::cin.ignore();
std::string s ;
std::vector<std::string> words(N);
for(int i = 0;i < N; i++) {
std::cin >> words[i];
// std::getline(std::cin, words[i]);
}
std::map<int, std::string> wordmap = splitword(words);
for (auto word:wordmap) {
std::cout << word.second << " ";
}
return 0;
}
Hjk 查找人名
题目有问题
Hjk去除多余的空格
题目
你需要写一个功能,它能处理一段文本,去除其中不必要的空格。但是如果这些空格被一对单引号包围起来,就保留它们不变。同时,你还要调整一些特定词汇的位置,这些词汇的位置会以坐标的方式给出,坐标要基于新的文本。
特别注意:
关键词的位置一定不是空格。
一个关键词的前后不会有额外空格。
如果文本中有单引号,那肯定是成对出现的。
关键词可能会有重复出现。
输入格式
如果文本中有单引号,那一定是成对的。
接下来是关键词的位置。每对关键词的开始和结束位置用空格隔开,不同关键词间用逗号隔开。
输出格式
返回经过处理的文本。
输出关键词的新位置。
范例
输入
Life is painting a picture, not doing ‘a sum’.
8 15,20 26,43 45
输出
Life is painting a picture, not doing ‘a sum’.
[8, 15] [19, 25] [42, 44]
解释:这里“a”和“picture”之间的空格被删去了,但在单引号内的空格保持不变。
shit