Day13 2022.11.19 双指针(简单)
21.调整数组顺序使奇数位于偶数前面
自己实现
初步想法是一个指针从开头向右移动,移动到偶数停止;另一个指针从数组中间位置向右移动, 移动到奇数停止,然后交换,一直到left==length/2 && right==length-1
。后来发现这个题目要求中的样例并不是奇数偶数个数相等,所以这个做法不行。
题解
也是双指针,不过这个做法里left是从0向右移动,right是从length-1向左移动。这个方法就能很好地解决奇数偶数个数不相等的问题了。
代码如下:
class Solution {
public:
vector<int> exchange(vector<int>& nums) {
if (nums.size() < 2)return nums;
int length = nums.size();
int left = 0;
int right = length - 1;
while (left < right)
{
while (left < length && nums[left] % 2 == 1)
left++;
while (right>=0 && nums[right] % 2 == 0)
right--;
if (left >= length)return nums;
if (right < 0)return nums;
if (left<right && nums[left] % 2 == 0 && nums[right] % 2 == 1)
{
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
}
left++;
right--;
}
return nums;
}
};
代码表现
hint:
- 感觉对从后往前的遍历不太容易想到,可以强化一下
57.和为s的两个数字
自己实现
left从开始往后走,right从尾开始往前走。如果nums[left]+nums[right]<target
则left++
;如果nums[left]+nums[right]>target
则right--
;如果==
则代表符合结果。但感觉这样的做法对于有些样例会有错误。
代码如下:
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> res;
int length=nums.size();
int left=0;
int right=length-1;
while(left<right)
{
if(nums[left]+nums[right]<target)left++;
else if(nums[left]+nums[right]>target)right--;
else
{
res.push_back(nums[left]);
res.push_back(nums[right]);
return res;
}
}
return res;
}
};
代码表现
题解
证明了自己实现当中的顾虑是不存在的
hint:
- 双指针放在左右两端称为对撞双指针
58-Ⅰ.翻转单词顺序
自己实现
这个就是用输入流读入的方式循环读入,自动根据空格分割好,然后直接调用reverse(vec.begin(),vec.end())
来逆序,并输出就好
代码如下:
class Solution {
public:
string reverseWords(string s) {
istringstream in(s);
vector<string> vec;
string str;
int flag=0;
while(in>>str)
{
flag=1;
vec.push_back(str);
}
if(!flag)return "";
reverse(vec.begin(),vec.end());
string res=vec[0];
for(int i=1;i<vec.size();i++)res+=" "+vec[i];
return res;
}
};
代码表现
hint:
-
vector的逆序方法:
reverse(vec.begin(),vec.end())
。这个并不是vector的内置方法,而是将vector的迭代器作为参数 -
c++按照空格分割字符串的两个方法
-
使用
strtok
:char *strtok(string s, char *delim)
分解字符串为一组字符串,s
为要分解的字符串,delim
为分隔符字符串。这个函数会将s
中的delim
设置为'\0'
。注意:在第一次调用时,
strtok()
必须给予函数s
字符串,往后的调用则将参数s
设置成NULL
。每次调用成功则返回指向被分割出片段的指针。string str = "hhh ttt ggg jjj"; //方法一: strtok char* s = new char[str.size() + 1]; strcpy(s, str.c_str()); char* p = strtok(s, " "); vector<string> words; while(p) { words.push_back(p); p = strtok(NULL, " "); }
-
使用
istringstream
:是一个类,使用构造函数istringstream s(str)
将字符串绑定成流(stream,和cin等效)。这样就可以用s>>tmp
这样的方法来自动按照空格分割了。string str = "hhh ttt ggg jjj"; //方法二: istringstream istringstream ss(str); vector<string> words; string word; while(ss >> word) { words.push_back(word); }
-
-
string
类转成char *
类用str.c_str()
方法