【0027.移除元素】
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int fast = 0;
int slow = 0;
for (int fast = 0; fast < nums.size(); fast++) {
if (nums[fast] == val) {
continue;
}
nums[slow] = nums[fast];
slow++;
}
return slow;
}
};
- 超快，一遍过
- 不过，对比下卡哥标准代码我的略显冗余
// 时间复杂度：O(n)
// 空间复杂度：O(1)
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slowIndex = 0;
for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
if (val != nums[fastIndex]) {
nums[slowIndex++] = nums[fastIndex];
}
}
return slowIndex;
}
};
- 既然 我的if是当两者相等就啥也不做 直接continue跳出本次循环进入下次循环 否则两者不行等执行某某代码 那为什么不换成if两者不相等执行某某代码 简而言之 不写continue那段 自己品吧
【0344.反转字符串】
class Solution {
public:
void reverseString(vector<char>& s) {
for (int i = 0, j = s.size() - 1; i < j; i++, j--) {
swap(s[i], s[j]);
}
}
};
- 算是 超快，一遍过
- 把swap函数名字记错了 以后可别写错哦
- j 想的是从字符串数组末尾开始-- 结果一不小心顺手写成跟i一样从0开始++了 以后遇到下标时手脑要同步哦
【剑指Offer05.替换空格】
class Solution {
public:
int findSpace(string &s) {
int count = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == ' ') {
count++;
}
}
return count;
}
string replaceSpace(string s) {a
int countSpace =findSpace(s);
int fast = s.size() - 1;
s.resize(s.size() + countSpace * 2);
int slow = s.size() - 1;
for (; fast >= 0; fast--) {
if (s[fast] == ' ') {
s[slow--] = '0';
s[slow--] = '2';
s[slow--] = '%';
}
else {
s[slow] = s[fast];
slow--;
}
}
return s;
}
};
- 算是 超快，一遍过
- 只是把 resize()即扩充后的数组大小写错了 不应该是空格个数*3 而应该是原数组大小+空格个数 *2
- 对比卡哥 我觉得自己写的更清楚直白（其实没差多少）
class Solution {
public:
string replaceSpace(string s) {
int count = 0; // 统计空格的个数
int sOldSize = s.size();
for (int i = 0; i < s.size(); i++) {
if (s[i] == ' ') {
count++;
}
}
// 扩充字符串s的大小，也就是每个空格替换成"%20"之后的大小
s.resize(s.size() + count * 2);
int sNewSize = s.size();
// 从后先前将空格替换为"%20"
for (int i = sNewSize - 1, j = sOldSize - 1; j < i; i--, j--) {
if (s[j] != ' ') {
s[i] = s[j];
} else {
s[i] = '0';
s[i - 1] = '2';
s[i - 2] = '%';
i -= 2;
}
}
return s;
}
};
【0151.翻转字符串里的单词】
class Solution {
public:
void handleExtraSpace(string &s) {
int slow = 0;
for (int fast = 0; fast < s.size() - 1; ) {
if (s[fast] != ' ') {
s[slow++] = s[fast];
if (s[fast + 1] == ' ') {
s[slow++] = ' ';
}
}
}
if (s[slow] == ' ') {
s.resize(slow - 1);
}
s.resize(slow);
}
void reverseString(string &s, int yesBegin, int noEnd) {
for (int i = yesBegin, j = noEnd - 1; i < j; i++, j--) {
swap(s[i], s[j]);
}
}
string reverseWords(string s) {
handleExtraSpace(s);
reverseString(s, 0, s.size());
int begin = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == ' ') {
reverseString(s, begin, i);
begin = i + 1;
}
}
return s;
}
};
- 整道题 思路上是对的
- 从主函数的步骤：调用handleExtraSpace()去除多余空格》》》调用reverseString()反转整个字符串》》》调用reverseString()反转每个单词
- 到写子函数handleExtraSpace()和子函数reverseString(左闭右开)
- 但是 子函数handleExtraSpace() 思路完全不对
- 此外 主函数 中的for循环结束后 还需要加上一句话：reverseString()实现对最后一个单词的反转
- 那么 现在把焦点放在handleExtraSpace()上
class Solution {
public:
void handleExtraSpace(string &s) {
int slow = 0;
for (int fast = 0; fast < s.size(); fast++) {
if (s[fast] != ' ') {
s[slow++] = s[fast];
if (s[fast + 1] == ' ') {
s[slow++] = ' ';
}
}
}
if (s[slow - 1] == ' ')
s.resize(slow - 1);
else
s.resize(slow);
}
// 版本二
void removeExtraSpaces(string& s) {//去除所有空格并在相邻单词之间添加空格, 快慢指针。
int slow = 0; //整体思想参考https://programmercarl.com/0027.移除元素.html
for (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的大小即为去除多余空格后的大小。
}
- 上面分别是 我的思路（改正后） 和 卡哥思路
- 关于我的思路：
- 之前忘了给for循环里的fast++ 这个是低级错误
- 之前也没考虑到 按照我写的for循环 给slow慢指针所指元素赋值 必然会给最后1个元素赋值空格 因此我还需要进行一个if else操作 如果最后一个是空格 我需要去掉 也就是返回数组大小减1即可 如果不是空格 那么就可以直接返回slow大小
- 改正上述两点之后 我的思路运行成功
- 关于卡哥思路：
- 还需要再看看