网站开发 wecenter,北京做网站哪个好,wordpress标签链接分类目录,wordpress微信公众平台开发文章目录 反转字符串描述题解 反转字符串II描述题解 替换数字描述题解#xff1a;replace函数题解#xff1a;双指针 翻转字符串里的单词描述题解 右旋字符串描述题解 实现 strStr()描述题解#xff1a;暴力算法题解#xff1a;KMP算法(懵懂) 重复的子字符串描述题解题解replace函数题解双指针 翻转字符串里的单词描述题解 右旋字符串描述题解 实现 strStr()描述题解暴力算法题解KMP算法(懵懂) 重复的子字符串描述题解题解暴力题解KMP题解移动匹配 反转字符串
题目链接
描述
编写一个函数其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1 输入[“h”,“e”,“l”,“l”,“o”] 输出[“o”,“l”,“l”,“e”,“h”]
示例 2 输入[“H”,“a”,“n”,“n”,“a”,“h”] 输出[“h”,“a”,“n”,“n”,“a”,“H”]
题解
C库函数 reverse 做题肯定要了解其内部原理
class Solution {
public:void swap(charc1,charc2){char tmp c1;c1c2;c2tmp;}void reverseString(vectorchar s) {size_t left 0,right s.size()-1;while(left right){swap(s[left],s[right]);left;--right;}}
};反转字符串II
题目链接
描述
给定一个字符串 s 和一个整数 k从字符串开头算起, 每计数至 2k 个字符就反转这 2k 个字符中的前 k 个字符。
如果剩余字符少于 k 个则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个则反转前 k 个字符其余字符保持原样。
示例:
输入: s “abcdefg”, k 2 输出: “bacdfeg”
题解
字符串是一段一段的进行反转所以我们在循环的时候可以每次一段
class Solution {
public:string reverseStr(string s, int k) {size_t len s.size();// 对于字符串是一段一段的处理 所以可以一次跳一段for(int i0;ilen;i2*k){if(iklen){reverse(s.begin()i,s.begin()ik);continue;}reverse(s.begin()i,s.end());}return s;}
};替换数字
题目链接
描述
给定一个字符串 s它包含小写字母和数字字符请编写一个函数将字符串中的字母字符保持不变而将每个数字字符替换为number。
例如对于输入字符串 “a1b2c3”函数应该将其转换为 “anumberbnumbercnumber”。
对于输入字符串 “a5b”函数应该将其转换为 “anumberb”
输入一个字符串 s,s 仅包含小写字母和数字字符。
输出打印一个新的字符串其中每个数字字符都被替换为了number
样例输入a1b2c3
样例输出anumberbnumbercnumber
数据范围1 s.length 10000。
题解replace函数
利用string的replace函数
#include iostream
#include string
using namespace std;void change_string(strings){size_t len s.size();for(int i0;ilen;i){if(s[i]9s[i]0){s.replace(s.begin()i,s.begin()i1,number);len5;i5; }}
}
int main(){string s{1das1das25das};change_string(s);couts\n;return 0;
}题解双指针
先将字符串扩充到最后的大小然后从后先前进行填充
#include iostream
#include string
using namespace std;void change_string(strings){size_t old_len s.size();int count{0};for(int i0;iold_len;i){if(s[i]9s[i]0)count;}s.resize(old_len5*count);size_t new_len s.size();for(int front old_len-1,backnew_len-1;front0;--back,--front){if(s[front]0s[front]9){s[back]r;s[back-1]e;s[back-2]b;s[back-3]m;s[back-4]u;s[back-5]n;back-5;}elses[back]s[front];}
}
int main(){string s;cins;change_string(s);couts\n;return 0;
}翻转字符串里的单词
题目链接
描述
给定一个字符串逐个翻转字符串中的每个单词。
示例 1 输入: “the sky is blue” 输出: “blue is sky the”
示例 2 输入: hello world! 输出: “world! hello” 解释: 输入字符串可以在前面或者后面包含多余的空格但是反转后的字符不能包括。
示例 3 输入: “a good example” 输出: “example good a” 解释: 如果两个单词间有多余的空格将反转后单词间的空格减少到只含一个。
题解
分三个步骤 1、去除多余空格 2、全部字符串进行反转 3、字符串中的单词进行一个一个的反转
class Solution {
public:void deleteSpace(string s){int slow{0},fast{0};size_t len{s.size()};//去除多余的前面的空格while(len0fastlens[fast] )fast;while(fastlen){//去除中间if(fast-10s[fast-1] s[fast] ){fast;continue;}elses[slow]s[fast];}//去除尾部if(slow-10s[slow-1] )s.resize(slow-1);elses.resize(slow);}//[beg,end]void reverse(strings,int beg,int end){for(;begend;--end,beg){char tmp s[beg];s[beg] s[end];s[end] tmp;}}string reverseWords(string s) {deleteSpace(s);size_t len s.size();reverse(s,0,len-1);int i,j;for(i0,j0;ilen;i){if(s[i] ){reverse(s,j,i-1);ji1;}}reverse(s,j,i-1);return s;}
};右旋字符串
题目链接
描述
字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k请编写一个函数将字符串中的后面 k 个字符移到字符串的前面实现字符串的右旋转操作。
例如对于输入字符串 “abcdefg” 和整数 2函数应该将其转换为 “fgabcde”。
输入输入共包含两行第一行为一个正整数 k代表右旋转的位数。第二行为字符串 s代表需要旋转的字符串。
输出输出共一行为进行了右旋转操作后的字符串。
样例输入
2 abcdefg
样例输出
fgabcde
数据范围1 k 10000, 1 s.length 10000;
题解
1、整体反转 2、起点到target这一段反转 3、target到结尾这一段反转
#include iostream
#include string
using namespace std;
// [beg,end]
void my_reverse(strings,int beg,int end){for(;begend;beg,--end){int tmp s[beg];s[beg]s[end];s[end]tmp;}
}
void rightHanded(strings,int target){size_t len s.size();my_reverse(s,0,len-1);my_reverse(s,0,target-1);my_reverse(s,target,len-1);
}
int main(){string s;int target;cintargets;rightHanded(s,target);coutsendl;return 0;
}实现 strStr()
题目链接
描述
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在则返回 -1。
示例 1: 输入: haystack “hello”, needle “ll” 输出: 2
示例 2: 输入: haystack “aaaaa”, needle “bba” 输出: -1
说明: 当 needle 是空字符串时我们应当返回什么值呢这是一个在面试中很好的问题。 对于本题而言当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
题解暴力算法
class Solution {
public:int strStr(string haystack, string needle) {if(haystack||needle)return -1;int pLen haystack.size(),sLen needle.size();for(int i 0; i pLen;i){if(haystack[i]needle[0]){int j 1;for(;jsLen;j)if(haystack[ij]!needle[j])break;if(jsLen)return i;}}return -1;}
};题解KMP算法(懵懂)
KMP算法解决字符串匹配的问题
最长相等前后缀得到前缀表 class Solution {
public:void getNext(int *next,const strings){/*初始化i后缀末尾j前缀末尾*/int j{-1};next[0] j;for(int i1;is.size();i){// 前后缀不相同while(j0s[j1]!s[i])jnext[j];//回退// 前后缀相同if(s[j1]s[i])j;// 将j前缀的长度赋给next[i]next[i]j;}}int strStr(string haystack, string needle) {if(!(haystack.size())||!(needle.size()))return -1;int next[needle.size()];getNext(next,needle);int j -1; // // 因为next数组里记录的起始位置为-1for(int i0;ihaystack.size();i){while(j0needle[j1]!haystack[i])j next[j];if(haystack[i]needle[j1])j;if(j(needle.size()-1))return (i-needle.size()1);}return -1;}
};重复的子字符串
题目链接
描述
题解
给定一个非空的字符串判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母并且长度不超过10000。
示例 1:
输入: “abab” 输出: True 解释: 可由子字符串 “ab” 重复两次构成。 示例 2:
输入: “aba” 输出: False 示例 3:
输入: “abcabcabcabc” 输出: True 解释: 可由子字符串 “abc” 重复四次构成。 (或者子字符串 “abcabc” 重复两次构成。
题解暴力
class Solution {
public:bool repeatedSubstringPattern(string s) {string tmp,str;for(int i0;is.size()/2;i){str;tmps[i];while(str.size()s.size())strtmp;if(strs)return true;}return false;}
};题解KMP
class Solution {
public:void getNext(int *next,const string s){int j-1;next[0]j;for(int i1;is.size();i){while(j0 s[i]!s[j1])jnext[j];if(s[i]s[j1])j;next[i]j;}}bool repeatedSubstringPattern(string s) {int len s.size();if(len0)return false;int next[len];getNext(next,s);if(next[len-1]!-1 len % (len - (next[len-1]1))0)return true;return false;}
};题解移动匹配
class Solution {
public:bool repeatedSubstringPattern(string s) {string t ss;t.erase(t.end()-1);if(t.find(s,1)!string::npos)return true;return false;}
};
