流量与网站,网站开发中怎么样对接接口,访问网页的流程,上海装修设计公司排名字符串 基础知识双指针法344# 反转字符串541# 反转字符串II54K 替换数字151# 反转字符串中的单词55K 右旋字符串 KMP 字符串匹配算法28# 找出字符串中第一个匹配项的下标#459 重复的子字符串 基础知识
字符串的结尾#xff1a;空终止字符00
char* name hello; … 字符串 基础知识双指针法344# 反转字符串541# 反转字符串II54K 替换数字151# 反转字符串中的单词55K 右旋字符串 KMP 字符串匹配算法28# 找出字符串中第一个匹配项的下标#459 重复的子字符串 基础知识
字符串的结尾空终止字符00
char* name hello; // 字符串不可拓展由于是一个固定分配的内存块有些地方必须加const
char name2[5] {h, e, l, l, o}; // 字符数组没有空终止字符非字符串
char name2[6] {h, e, l, l, o, \\0}; // 或 0
//strlen()计算到空终止字符std::string基本是baseString类模板类的模板版本模板参数是char
cplusplus_std::string
#include string
std::string name Hello; // 默认const
std::cout name std::endl;
// .size(), .find() (不存在std::string::npos)
// 没有contains函数实现
bool contains name.find(no) ! std::string::npos宽字符wchar_t
const char* name u8Hello; // 1字节utf8 std::string
const char16_t* name2 uHello; // 2字节utf16 std::u16string
const char32_t* name3 UHello; // 4字节utf32 std::u32string
const wchar_t* name4 LHello; // 2字节由编译器决定在大多数Unix/Linux系统上通常是32位std::wstring更多用法
// 遍历字符串数组s如char s[5] asd;
for (int i 0; s[i] ! \0; i) { }
// 遍历字符串s
for (int i 0; i s.size(); i) { }string.resize(new_length, \0); // 截断/扩充 O(1)~O(n)
string.erase(index, len); // 删除字符O(n)删除后需前移不传参数相当于clear()
string.erase(first, last); // 删除字符参数为迭代器不包含lastlast非必须参数
string.clear(); // 清空字符串
getline(cin, string); // 读取一整行包含空格
reverse(string.begin(), string.end()); // 原地反转字符串 O(n)algorithm中的泛型函数
string.find(substring, pos0); // 寻找子串 O(mn)pos为起始查找位置没有找到返回std::string::npos
string.substr(pos0, lennpos); // 从字符串中提取子串 O(m)pos为起始位置len为字串长度双指针法
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]提示 1 s.length 105s[i] 都是 ASCII 码表中的可打印字符 // 首尾指针
// O(n) 0ms; O(1) 26.59MB
class Solution {
public:void reverseString(vectorchar s) {int left 0, right s.size() - 1;while (left right) {swap(s[left], s[right--]);}}
};// swap()的两种实现
int tmp s[i];
s[i] s[j];
s[j] s[i];s[i] ^ s[j];
s[j] ^ s[i];
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提示 1 s.length 10^4s 仅由小写英文组成1 k 10^4 当需要固定规律一段一段去处理时考虑在for循环上做调整
// 344衍生处理for循环条件
// O(n) 0ms; O(1) 9.43MB
class Solution {
public:string reverseStr(string s, int k) {for (int i 0; i s.size(); i 2 * k) {if (i k s.size()) {reverse(s.begin() i, s.begin() i k); // reverse不包括last} else {reverse(s.begin() i, s.end());}}return s;}
}; 54K 替换数字
题目链接 题目描述 给定一个字符串 s它包含小写字母和数字字符请编写一个函数将字符串中的字母字符保持不变而将每个数字字符替换为number。 例如对于输入字符串 “a1b2c3”函数应该将其转换为 “anumberbnumbercnumber”。 输入描述 输入一个字符串 s,s 仅包含小写字母和数字字符。 输出描述 打印一个新的字符串其中每个数字字符都被替换为了number 输入示例 a1b2c3输出示例 anumberbnumbercnumber提示信息 数据范围 1 s.length 10000。 首先扩充数组到每个数字字符替换成 number之后的大小
再用双指针法从旧尾向新尾替换字符
// 双指针法从后向前扩充数组
// O(n) 35ms; O(1) 2.18MB
#includeiostreamusing namespace std;int main() {string s;while (cin s) {int n s.size();int count 0; // 统计数字for (int i 0; i n; i) {if (s[i] 0 s[i] 9) count;}// 扩充字符串s.resize(n count * 5);int s_oldTail n - 1, s_newTail s.size() - 1;while (s_oldTail s_newTail s_oldTail 0) {if (s[s_oldTail] 0 s[s_oldTail] 9) {s[s_newTail--] r;s[s_newTail--] e;s[s_newTail--] b;s[s_newTail--] m;s[s_newTail--] u;s[s_newTail--] n;s_oldTail--;}else {s[s_newTail--] s[s_oldTail--];}}cout s endl;}return 0;
}151# 反转字符串中的单词 给你一个字符串 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
解释如果两个单词间有多余的空格反转后的字符串需要将单词间的空格减少到仅有一个。提示 1 s.length 10^4s 包含英文大小写字母、数字和空格 s 中 至少存在一个 单词 在不追求空间复杂度的情况下可以使用使用split库函数分隔单词再定义一个新的string字符串把单词倒序相加
空间复杂度O(1)的解法1. 移除多余空格2. 反转字符串 3. 反转单词
移除多余空格类似移除元素的思想快慢指针法
// 移除多余空格
// 快慢指针
void removeExtraSpaces(string s) {int slowIndex 0, fastIndex 0;int n s.size();// 去除字符串首部空格while (n 0 fastIndex n s[fastIndex] ) fastIndex;// 去除字符串中间冗余空格while (fastIndex n) {if (fastIndex 0 s[fastIndex] s[fastIndex] s[fastIndex - 1]) {fastIndex;} else {s[slowIndex] s[fastIndex];}}// 去除字符串尾部空格if (slowIndex 0 s[slowIndex - 1] ) s.resize(slowIndex - 1);else s.resize(slowIndex);
}// 移除多余空格优化版对整个单词操作去除所有空格再添加
// 快慢指针
void removeExtraSpaces(string s) {int slowIndex 0, fastIndex 0;while (fastIndex s.size()) {if (s[fastIndex] ! ) {if (slowIndex ! 0) s[slowIndex] ;while (s[fastIndex] ! fastIndex s.size()) s[slowIndex] s[fastIndex];} else {fastIndex;}}s.resize(slowIndex);
}// 双指针法
// O(n) 0ms; O(1) 9.89MB
class Solution {
public:void reverse(string s, int start, int end) {int i start, j end;while (i j) {swap(s[i], s[j--]);}}string reverseWords(string s) {// 去除多余空格int slowIndex 0, fastIndex 0;while (fastIndex s.size()) {if (s[fastIndex] ! ) {if (slowIndex ! 0) s[slowIndex] ;while (s[fastIndex] ! fastIndex s.size()) s[slowIndex] s[fastIndex];} else {fastIndex;}}s.resize(slowIndex);// 反转字符串reverse(s, 0, s.size() - 1);// 反转单词int start 0;for(int i 0; i s.size(); i) {if (s[i] || i s.size()) {reverse(s, start, i - 1);start i 1;}}return s;}
};55K 右旋字符串
题目链接 题目描述 字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k请编写一个函数将字符串中的后面 k 个字符移到字符串的前面实现字符串的右旋转操作。 例如对于输入字符串 “abcdefg” 和整数 2函数应该将其转换为 “fgabcde”。 输入描述 输入共包含两行第一行为一个正整数 k代表右旋转的位数。第二行为字符串 s代表需要旋转的字符串。 输出描述 输出共一行为进行了右旋转操作后的字符串。 输入示例 2
abcdefg输出示例 fgabcde提示信息 数据范围 1 k 10000, 1 s.length 10000; 把字符串看成两个部分size-n | n反转两个部分先整体反转所有字符再两个部分分别反转两个操作可交换先后顺序
// 反转字符段整体局部
// O(n) 31ms; O(1) 2.18MB
#includeiostream
#includealgorithmusing namespace std;int main() {int n;string s;while (cin n) {cin s;reverse(s.begin(), s.end());reverse(s.begin(), s.begin() n);reverse(s.begin() n, s.end());cout s endl;}return 0;
}KMP 字符串匹配算法
当出现字符串不匹配时记录一部分之前已经匹配的文本内容利用这些信息避免从头再去做匹配
前缀表子串的最大匹配前后缀长度用于记录模式串与主串(文本串)不匹配时模式串应该从哪里开始重新匹配
前缀函数的计算判断与最大匹配前后缀长度prefix[i-1]处的下一个字符是否相等若相等则prefix[i] prefix[i-1] 1若不相等则回退数次直至相等或不存在
回退方式找次长的匹配前后缀长度即prefix[prefix[i - 1] - 1]
推荐教学视频六分钟学会KMP
28# 找出字符串中第一个匹配项的下标 给你两个字符串 haystack 和 needle 请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标下标从 0 开始。如果 needle 不是 haystack 的一部分则返回 -1 。 示例 1 输入haystack sadbutsad, needle sad
输出0
解释sad 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 所以返回 0 。示例 2 输入haystack leetcode, needle leeto
输出-1
解释leeto 没有在 leetcode 中出现所以返回 -1 。提示 1 haystack.length, needle.length 10^4haystack 和 needle 仅由小写英文字符组成 // 前缀函数
vectorint getNext(const string s) {vectorint prefix(s.size(), 0);for (int i 1, pre 0; i s.size(); i) {while (pre 0 s[i] ! s[pre]) {pre prefix[pre - 1];}if (s[i] s[pre]) prefix[i] pre;}return prefix;
}一种方法启发式方法利用前缀函数将模式串与主串合并只需找到所需的该字符串的最大匹配前后缀的值前缀函数模式串长度 // 合并模式串与主串找最大匹配前后缀
// O(nm) 0ms; O(nm) 8.96MB
class Solution {
public:int strStr(string haystack, string needle) {int n haystack.size(), m needle.size();string s needle # haystack;vectorint prefix(s.size(), 0);for (int i 1; i s.size(); i) {int pre prefix[i - 1];while (pre 0 s[i] ! s[pre]) {pre prefix[pre - 1];}if (s[i] s[pre]) {prefix[i] pre 1;if (prefix[i] m) {return i - m * 2;}}}return -1;}
};优化只需生成模式串的前缀表后匹配
// KMP
// O(nm) 0ms; O(m) 8.61MB
class Solution {
public:int strStr(string haystack, string needle) {int n haystack.size(), m needle.size();// 生成前缀表vectorint prefix(m, 0);for (int i 1, pre 0; i m; i) {while (pre 0 needle[i] ! needle[pre]) {pre prefix[pre - 1];}if (needle[i] needle[pre]) prefix[i] pre;}// 匹配for (int i 0, j 0; i haystack.size(); i) {while (j 0 haystack[i] ! needle[j]) {j prefix[j - 1];}if (haystack[i] needle[j]) {j;if (j needle.size()) {return i - j 1;}}}return -1;}
};时间复杂度当前位的前缀函数至多比前一位增加一每当回退一次当前位的前缀函数的最大值都会减少。前缀函数的总减少次数不会超过总增加次数 KMP 算法虽然有着良好的理论时间复杂度上限但大部分语言自带的字符串查找函数并不是用 KMP 算法实现的。这是因为在实现 API 时我们需要在平均时间复杂度和最坏时间复杂度二者之间权衡。普通的暴力匹配算法以及优化的 BM 算法拥有比 KMP 算法更为优秀的平均时间复杂度 #459 重复的子字符串 给定一个非空的字符串 s 检查是否可以通过由它的一个子串重复多次构成。 示例 1: 输入: s abab
输出: true
解释: 可由子串 ab 重复两次构成。示例 2: 输入: s aba
输出: false示例 3: 输入: s abcabcabcabc
输出: true
解释: 可由子串 abc 重复四次构成。 (或子串 abcabc 重复两次构成。)提示 1 s.length 10^4s 由小写英文字母组成 移动匹配法对字符串sss内若能找到s那么s一定可以由子串构成反之亦然可从充分必要性的角度证明
// 移动匹配法
// O(n) 7ms; O(n) 13.33MB
class Solution {
public:bool repeatedSubstringPattern(string s) {string t s s;t.erase(t.begin());t.erase(t.end() - 1);if (t.find(s) ! std::string::npos) return true;return false;}
};KMP法如果字符串s是由重复子串组成那么最大匹配前后缀不包含的子串一定是s的最小重复子串反之亦然可从充分必要性的角度证明
若s是由最小重复子串p组成那么最大匹配前后缀一定由数个p组成反证法从而推出充分性
根据以上陈述只需要判断不包含的子串是否是重复子串且若是重复子串那么一定是最小重复子串
不包含的子串长度若被s的长度整除那么不包含的子串一定是最小重复子串反之亦然
因此若要判断s是否由重复子串构成只需判断最大匹配前后缀不包含的子串长度是否被s的长度整除
// 最大匹配前后缀
// O(n) 0ms; O(n) 15.18MB
class Solution {
public:bool repeatedSubstringPattern(string s) {int n s.size();vectorint prefix(n, 0);for (int i 1, pre 0; i n; i) {while (pre 0 s[i] ! s[pre]) {pre prefix[pre - 1];}if (s[i] s[pre]) prefix[i] pre;}if (prefix[n - 1] n % (n - prefix[n - 1]) 0) return true;return false;}
};本文参考 LeetCode官方题解 、 代码随想录 及 六分钟学会KMP
