【0151.翻转字符串里的单词】
-
class Solution { public: string reverseWords(string s) { int slow = 0; int fast = 1; while (fast < s.size()) { if (s[slow] == ' ' && s[fast] == ' ') { fast++; } if (s[slow] == ' ' && s[fast] != ' ') { slow++; fast++; } } } }; -
看懂了 本题是要分三步走 但第一步 移除多余空格 两种方法我都想不通 目前只打算看第二种方法
class Solution {
public:
void cleanExtraSpace(string &s) {
int slow = 0;
for (int fast = 0; fast < s.size(); fast++) {
while (s[fast] == ' ' && s[++fast] == ' ') {
slow = fast
}
}
}
string reverseWords(string s) {
cleanExtraSpace(s);
}
};
- 步骤一：删除多余空格元素 我写的思路是找到多余空格处 进行删除操作 但其实卡哥的思路是 去除所有空格（即先忽略所有空格） 同时在相邻单词之间添加空格 以下三段代码 分别是 标准答案--我的---我的---都是我的
void removeExtraSpaces(string& s) {
int slow = 0;
for (int i = 0; i < s.size(); ++i) {
if (s[i] != ' ') {
if (slow != 0)
s[slow++] = ' ';
while (i < s.size() && s[i] != ' ') {
s[slow++] = s[i++];
}
}
}
s.resize(slow);
}
void removeExtraSpaces(string& s) {
int slow = 0;
while(i < s.size()) {
while (s[i] != ' ' && i < s.size()) {
s[slow++] = s[i++];
}
s[slow++] = ' ';
}
s.resize(slow);
}
-
- 我的1 这段代码 溢出 我就把while改成了for 就解决了 但为什么我i还需要再看看。
void removeExtraSpaces(string& s) {
int slow = 0;
for (int i = 0; i < s.size(); i++) {
while (s[i] != ' ' && i < s.size()) {
s[slow++] = s[i++];
}
s[slow++] = ' ';
}
s.resize(slow);
}
-
- 我的2 这段代码 运行结果"blue方框 is sky the" 预期结果"blue is sky the" 我知道是因为在for循环里 我每while记录一个单词 最后都slow赋值为空格 那么就意味着我给最后一个单词的结尾也赋了空格 而这是不需要的 经过之后的整串---整个单词的反转 这个空格就会从串末尾---串开头----第一个单词的末尾 这个结果 所以我打算 把最后传的数组大小由slow改成slow-1
void removeExtraSpaces(string& s) {
int slow = 0;
for (int i = 0; i < s.size(); i++) {
while (s[i] != ' ' && i < s.size()) {
s[slow++] = s[i++];
}
s[slow++] = ' ';
}
s.resize(slow-1);
}
-
- 上个问题解决了 但 输入" hello world " 我的输出"world hello " 预期输出"world hello" 表示原本串开头的那个空格我没删除 那是因为 如果串原本开头是空 那么我进入for 不执行while 却还要执行slow赋值空格这一操作 所以 在for循环里 while循环之前 需要添加一个判断 if操作
void removeExtraSpaces(string& s) {
int slow = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] != ' ') {
while (s[i] != ' ' && i < s.size()) {
s[slow++] = s[i++];
}
s[slow++] = ' ';
}
}
s.resize(slow-1);
}
- 步骤二：反转整串 和 步骤三：反转每个单词 调用的子函数一样 较简单
- 但是 关于步骤三 主函数里 先要确定出每个单词的左右区间 然后才能调用子函数进行区间内反转 下面注释掉的 是原标准答案 对应部分代码是我的
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;
for (int i = 0; i < s.size(); ++i) {
if (s[i] != ' ') {
if (slow != 0) s[slow++] = ' ';
while (i < s.size() && s[i] != ' ') {
s[slow++] = s[i++];
}
}
}
s.resize(slow);
}
string reverseWords(string s) {
removeExtraSpaces(s);
reverse(s, 0, s.size() - 1);
//int start = 0;
//for (int i = 0; i <= s.size(); ++i) {
// if (i == s.size() || s[i] == ' ') {
// reverse(s, start, i - 1);
// start = i + 1;
// }
//}
int start = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == ' ') {
reverse(s, start, i - 1);
start = i + 1;
}
if (i == s.size() - 1) {
reverse(s, start, i);
}
}
return s;
}
};
- 不知道为什么 我的代码可以简写成卡哥那样的 把局部代码拎出来 以下三段代码是等价的 但不知道怎么能写出来后者。还需要再看看。
int start = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == ' ') {
reverse(s, start, i - 1);
start = i + 1;
}
if (i == s.size() - 1) {
reverse(s, start, i);
}
}
for (int i = 0; i <= s.size(); ++i) {
//for (int i = 1; i <= s.size(); i++) {
if (i == s.size() || s[i] == ' ') {
reverse(s, start, i - 1);
start = i + 1;
}
}
【剑指Offer58-II.左旋转字符串】
class Solution {
public:
string reverseLeftWords(string s, int n) {
int oldSize = s.size();
s.resize(oldSize + n);
for (int i = 0; i < n; i++) {
s[i + oldSize] = s[i];
}
for (int i = n; i < s.size(); i++) {
s[i - n] = s[i];
}
s.resize(oldSize);
return s;
}
};
- 运行成功 但我做的没有意义 因为申请了额外空间 想想不申请有什么办法没
class Solution {
public:
void reverseStr(string &s, int left, int right) {
for (; left < right; left++, right--) {
swap(s[left], s[right]);
}
}
string reverseLeftWords(string s, int n) {
reverseStr(s, 0, n-1);
reverseStr(s, n, s.size() - 1);
reverseStr(s, 0, s.size() - 1);
return s;
}
};
- 不额外开辟空间的话 能想到这个思路 的话 代码是很简单的 但关键是这个思路妙啊 不容易想到啊 》》》局部反转 然后整体反转
- 卡哥代码用的reverse 要注意 一般系统编写好可直接调用的函数 常常是左闭右开原则 就是说 左端点值可以取到 右端点值不可以取到 所以要注意传参
- 比如你要传的下标范围是 0到7（预期） 假设你代码写的是 reverse(0,7)
- 拿去对照标准reverse(0,7)的话因为是左闭右开原则即意思是反转下标范围是0到6 （标准）
- 标准不符合预期 那么你应该应该修改之前的reverse(0,7)为reverse(0,8) 才是正确的
class Solution {
public:
string reverseLeftWords(string s, int n) {
reverse(s.begin(), s.begin() + n);
reverse(s.begin() + n, s.end());
reverse(s.begin(), s.end());
return s;
}
};
【problems/0028.实现strStr】
class Solution {
public:
int strStr(string haystack, string needle) {
int result = -1;
for (int i = 0; i <= haystack.size() - needle.size(); i++ ) {
int count = 0;
int j = 0;
while (j < needle.size()) {
if (haystack[i] == needle[j]) {
i++;
count++;
j++;
}
}
if (count == needle.size()) {
result = i - count;
break;
}
}
return result;
}
};
- 一些用例不通过 这其实就是暴力解法了
class Solution {
public:
void getNext(int* next, const string& s) {
int j = 0;
next[0] = 0;
for(int i = 1; i < s.size(); i++) {
while (j > 0 && s[i] != s[j]) {
j = next[j - 1];
}
if (s[i] == s[j]) {
j++;
}
next[i] = j;
}
}
int strStr(string haystack, string needle) {
if (needle.size() == 0) {
return 0;
}
int next[needle.size()];
getNext(next, needle);
int j = 0;
for (int i = 0; i < haystack.size(); i++) {
while(j > 0 && haystack[i] != needle[j]) {
j = next[j - 1];
}
if (haystack[i] == needle[j]) {
j++;
}
if (j == needle.size() ) {
return (i - needle.size() + 1);
}
}
return -1;
}
};
- 标准答案
明天继续：）