酒店电子商务网站建设,泉州网站建设 首选猴子网络,南京网站搜索排名,家居网站建设定位分析论文算法学习——LeetCode力扣字符串篇 344. 反转字符串
344. 反转字符串 - 力扣#xff08;LeetCode#xff09;
描述
编写一个函数#xff0c;其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间#xff0c;你必须原地…算法学习——LeetCode力扣字符串篇 344. 反转字符串
344. 反转字符串 - 力扣LeetCode
描述
编写一个函数其作用是将输入的字符串反转过来。输入字符串以字符数组 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 码表中的可打印字符
代码解析
中间变量交换
class Solution {
public:void reverseString(vectorchar s) {char temp;for(int i0 ;is.size()/2;i){temp s[i];s[i] s[s.size()-1 - i];s[s.size()-1 - i] temp;}}
};
使用对调函数
void reverseString(vectorchar s) {for (int i 0, j s.size() - 1; i s.size()/2; i, j--) {swap(s[i],s[j]);}
}
使用反转库函数
class Solution {
public:void reverseString(vectorchar s) {reverse(s.begin(),s.end());}
};
541. 反转字符串 II
541. 反转字符串 II - 力扣LeetCode
描述
给定一个字符串 s 和一个整数 k从字符串开头算起每计数至 2k 个字符就反转这 2k 字符中的前 k 个字符。
如果剩余字符少于 k 个则将剩余字符全部反转。 如果剩余字符小于 2k 但大于或等于 k 个则反转前 k 个字符其余字符保持原样。
示例
示例 1
输入s “abcdefg”, k 2 输出“bacdfeg”
示例 2
输入s “abcd”, k 2 输出“bacd”
提示
1 s.length 104s 仅由小写英文组成1 k 104
代码解析
class Solution {
public:void rever(string s ,int left ,int right){while(leftright){char tmp s[right];s[right] s[left];s[left] tmp;left;right--;}return;}string reverseStr(string s, int k) {int i0;int flag1;;for(i0 ; ik s.size() ; ik){if(flag1) flag 0;else if(flag 0) {flag 1;continue;}int left i;int right leftk-1;rever(s,left,right);}if( flag1 ) rever(s,i,s.size()-1);return s;}
};
151. 反转字符串中的单词
151. 反转字符串中的单词 - 力扣LeetCode
描述
给你一个字符串 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 104s 包含英文大小写字母、数字和空格 ’ ’s 中 至少存在一个 单词
进阶
如果字符串在你使用的编程语言中是一种可变数据类型请尝试使用 O(1) 额外空间复杂度的 原地 解法。
代码解析
双指针
class Solution {
public:string reverseWords(string s) {int left0 ,right1;string result , temp;if(s.size()1) return s;//针对单一字母while( left right rights.size() )//找到左指针位置单词第一个字母处{while(s[left] ){left;right;if(right s.size()) %应对单词后面多个空格没有新单词类似“abc ”{result.erase(result.size()-1,1);return result;}}while(s[right]! s[right]!\0)//确定右指针位置在单词最后一个字母后{right;}temp s.substr(left,right-left);//抽取子串temp ;//添加空格result.insert(0, temp);//头插字串left right;right left1;}result.erase(result.size()-1,1);//去除最后一个空格return result;}
};
低空间复杂度反转库函数
首先去除多余空格之后整个字符串反转最后每个单词反转
class Solution {
public:string reverseWords(string s) {int left0 , right0;//去除多余的空格while(right s.size()){if(left0 s[right] ){right;}else if(left ! 0 s[right-1] s[right] ){right;}else{s[left] s[right];left;right;}}if(s[left-1] )left--;//针对最后一个是空格s.resize(left);//反转字符串reverse(s.begin(),s.end());//反转单词left0 , right0;while(right s.size()){while(s[right] ! rights.size()) right;reverse(s.begin() left, s.begin() right);left right1;rightleft1;}return s;}
};
低空间复杂度无库函数
class Solution {
public:void reverse(string s, int start, int end){ //翻转区间写法左闭又闭 []for (int i start, j end; i j; i, j--) {swap(s[i], s[j]);}}void removeExtraSpaces(string s) {//去除所有空格并在相邻单词之间添加空格, 快慢指针。int slow 0; //整体思想参考https://programmercarl.com/0027.移除元素.htmlfor (int i 0; i s.size(); i) { //if (s[i] ! ) { //遇到非空格就处理即删除所有空格。if (slow ! 0) s[slow] ; //手动控制空格给单词之间添加空格。slow ! 0说明不是第一个单词需要在单词前添加空格。while (i s.size() s[i] ! ) { //补上该单词遇到空格说明单词结束。s[slow] s[i];}}}s.resize(slow); //slow的大小即为去除多余空格后的大小。}string reverseWords(string s) {removeExtraSpaces(s); //去除多余空格保证单词之间之只有一个空格且字符串首尾没空格。reverse(s, 0, s.size() - 1);int start 0; //removeExtraSpaces后保证第一个单词的开始下标一定是0。for (int i 0; i s.size(); i) {if (i s.size() || s[i] ) { //到达空格或者串尾说明一个单词结束。进行翻转。reverse(s, start, i - 1); //翻转注意是左闭右闭 []的翻转。start i 1; //更新下一个单词的开始下标start}}return s;}
};
28. 找出字符串中第一个匹配项的下标
28. 找出字符串中第一个匹配项的下标 - 力扣LeetCode
描述
给你两个字符串 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 104haystack 和 needle 仅由小写英文字符组成
代码解析
库函数
class Solution {
public:int strStr(string haystack, string needle) {return haystack.find(needle);}
};
暴力法
class Solution {
public:int strStr(string haystack, string needle) {for(int left0 ; left haystack.size() ;left){if(haystack[left] needle[0]){for(int right left ,i0; right haystack.size() ineedle.size(); right,i){if(haystack[right] needle[i]){if(ineedle.size()-1){return left;}continue;}else break;}}}return -1;}
};
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] )j next[j];if(s[i] s[j1]) j;next[i] j;}}int strStr(string haystack, string needle) {if(needle.size() 0 ) return 0;int next[needle.size()];int j-1;getNext(next , needle);for(int i0 ; ihaystack.size() ;i){while(j0 haystack[i] ! needle[j1])j next[j];if(haystack[i] needle[j1]) j;if( j needle.size() - 1 )return (i-needle.size()1);}return -1;}
};
459. 重复的子字符串
459. 重复的子字符串 - 力扣LeetCode
描述
给定一个非空的字符串 s 检查是否可以通过由它的一个子串重复多次构成。
示例
示例 1:
输入: s “abab” 输出: true 解释: 可由子串 “ab” 重复两次构成。
示例 2:
输入: s “aba” 输出: false
示例 3:
输入: s “abcabcabcabc” 输出: true 解释: 可由子串 “abc” 重复四次构成。 (或子串 “abcabc” 重复两次构成。)
提示
1 s.length 104s 由小写英文字母组成
代码解析
移动匹配 class Solution {
public:bool repeatedSubstringPattern(string s) {string tmp s s;tmp.erase(0,1);tmp.erase(tmp.size()-1,1);if(tmp.find(s) -1) return false;else return true;}
};
KMP
代码随想录
class Solution {
public:void getNext(int* next, const string s){int j -1;next[0] j;for (int i 1; i s.size(); i){while (j 0 s[i] ! s[j 1]){j next[j ];}if (s[i] s[j 1]) j;next[i] j;}}bool repeatedSubstringPattern(string s) {if (s.size() 0) {return false;}int *next new int[substr.size()];//计算整个文字串的next数组如果文字串是循环的一个循环next都是-1之后的从0开始递增。next的最后一位的值循环次数-1*循环体长度 -1getNext(next, s);int len s.size();//文字串的长度减去next数组最后一位1 得到是循环体长度// 如果next数组最后一位不是-1意味着之前匹配成功 并且文字串长度对循环体长度可以整除if (next[len - 1] ! -1 len % (len - (next[len - 1] 1)) 0) {delete[] next;return true;}delete[] next;return false;}
};
