检测网站打开速度,怎么制作公司的网站,不用vip也能看的黄台的app,怎样提高网站的点击率1.翻转字符串里的单词
题目#xff1a;
给你一个字符串 s #xff0c;请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意#xff1…1.翻转字符串里的单词
题目
给你一个字符串 s 请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中单词间应当仅用单个空格分隔且不包含任何额外的空格。
示例 1
输入s the sky is blue
输出blue is sky the示例 2
输入s hello world
输出world hello
解释反转后的字符串中不能存在前导空格和尾随空格。
思路
这题归档为中等等会strStr归档为简单真是不理解。。。
题目思路就是先去除多余空格然后全部翻转然后一个个翻转单词
代码
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;}
}; 这里有个弱智问题我是弱智我解释下
为什么有些用string s有些用string s
参数类型传递方式是否修改原字符串性能特点string s值传递否修改副本复制整个字符串开销大string s引用传递是直接修改原对象不复制字符串开销小const string s常量引用否禁止修改不复制字符串开销小
一句话不改s就引用一下要改s本身就无。
其实是三个函数一个先把字符串里面多余的空格删掉一个是定义翻转函数最后一个调用前俩再把单词一个个翻转。难点在于边界条件的控制。
2.右旋转字符串、
题目:
字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k请编写一个函数将字符串中的后面 k 个字符移到字符串的前面实现字符串的右旋转操作。
例如对于输入字符串 abcdefg 和整数 2函数应该将其转换为 fgabcde。
思路 思路简单选全部翻转再分段翻转跟上一题有点像但边界条件简单的多且不用删除空格
代码
#includeiostream
#includealgorithm
using namespace std;
int main() {int n;string s;cin n;cin s;int len s.size(); //获取长度reverse(s.begin(), s.end()); // 整体反转reverse(s.begin(), s.begin() n); // 先反转前一段长度nreverse(s.begin() n, s.end()); // 再反转后一段cout s endl;}
reverse函数上大分
3.实现strStr()
题目
给你两个字符串 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 。
思路
说实话我是真没看懂这题特别是KMP只能说硬着头皮敲了。。还分类为简单nnd
代码
class Solution {
public:void getNext(int* next, const string s) {int j -1;next[0] j;for(int i 1; i s.size(); i) { // 注意i从1开始while (j 0 s[i] ! s[j 1]) { // 前后缀不相同了j next[j]; // 向前回退}if (s[i] s[j 1]) { // 找到相同的前后缀j;}next[i] j; // 将j前缀的长度赋给next[i]}}int strStr(string haystack, string needle) {if (needle.size() 0) {return 0;}vectorint next(needle.size());getNext(next[0], needle);int j -1; // // 因为next数组里记录的起始位置为-1for (int i 0; i haystack.size(); i) { // 注意i就从0开始while(j 0 haystack[i] ! needle[j 1]) { // 不匹配j next[j]; // j 寻找之前匹配的位置}if (haystack[i] needle[j 1]) { // 匹配j和i同时向后移动j; // i的增加在for循环里}if (j (needle.size() - 1) ) { // 文本串s里出现了模式串treturn (i - needle.size() 1);}}return -1;}
};
只从代码结构来看的话先定义一个next数组这个是当匹配到不同字符时候高效回调的不用每次都要重头再匹配后面的strStr()分两种情况第一种是不匹配了就用 j next[j]找之前的匹配位置第二种情况是匹配的那么就j继续往下匹配。最后找到长度等于模式串的子字符串就返回此子字符串开始的下标。
4.重复的子字符串
题目
给定一个非空的字符串 s 检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s abab
输出: true
解释: 可由子串 ab 重复两次构成。示例 2:
输入: s aba
输出: false示例 3:
输入: s abcabcabcabc
输出: true
解释: 可由子串 abc 重复四次构成。 (或子串 abcabc 重复两次构成。)
思路
这题也是要用KMP我只能说后面再看一遍吗现在不能卡这里了。
代码
class Solution {
public:void getNext (int* next, const string s){next[0] -1;int j -1;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[s.size()];getNext(next, s);int len s.size();if (next[len - 1] ! -1 len % (len - (next[len - 1] 1)) 0) {return true;}return false;}
}; 和上题一样先创建next数组后面就基于一个类似于数学中的定理的东西证明出来的用此定理去判断。
