剑指offer21.调整数组顺序使得奇数位于偶数前面 57.和为s的两个数字 58.反转单词顺序

本文主要是介绍剑指offer21.调整数组顺序使得奇数位于偶数前面 57.和为s的两个数字 58.反转单词顺序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述
暴力二次遍历（时间复杂度空间复杂度都是n）

class Solution {
public:vector<int> exchange(vector<int>& nums) {vector<int> result(nums.size());int left=0;for(int i=0;i<nums.size();i++){if(nums[i]%2==1) result[left++]=nums[i];}for(int i=0;i<nums.size();i++){if(nums[i]%2==0) result[left++]=nums[i];}return result;}
};

这边有一个问题，就是如果这个vector result(nums.size()) 不知道长度 那插入数组时候只能用result.push_back(nums[i])
只有在我定义里这vector容器长度n的时候。我才能使用result[i]
这是不定义长度的写法

class Solution {
public:vector<int> exchange(vector<int>& nums) {vector<int> result;for(int i=0;i<nums.size();i++){if(nums[i]%2==1) result.push_back(nums[i]);}for(int i=0;i<nums.size();i++){if(nums[i]%2==0) result.push_back(nums[i]);}return result;}
};

方法2：双指针，一次遍历，原地修改
时间n 空间1

class Solution {
public:vector<int> exchange(vector<int>& nums) {int left=0,right=1;while(right<nums.size()){if(nums[left]%2==1||nums[right]%2==1)//left和right至少有一个为奇数{if(nums[left]%2==0)//前偶后奇 调换{int temp=nums[left];nums[left]=nums[right];nums[right]=temp;}//其他情况 比如前奇后偶 前奇后奇 都不需要调换 直接++left++;right++;}else //全为偶数{right++;}}return nums;}
};

在这里插入图片描述
无语写了个哈希集合然后就大无语，耗时耗空间
我想的是先把当前数组放到哈希表里，然后再遍历当前数组的时候，在哈希集合里找有没有和他配对的，有就放进result里面

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_set<int>set;vector<int>result;for(int i=0;i<nums.size();i++) set.insert(nums[i]);for(int i=0;i<nums.size();i++){if(set.count(target-nums[i])!=0){result={nums[i],target-nums[i]};}}return result;}
};

优化哈希表(记住这是一个排过序的所以找到后面大的大的对应的target-x一定是前面已经存储在哈希容器里的。（其实和没优化的差距不大哈哈哈哈）

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_set<int>set;for(auto x:nums){if(set.count(target-x)!=0) return {x,target-x};set.insert(x);}return {};}
};

方法2：双指针和三数之和很像，只是不用去重

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int left=0,right=nums.size()-1;while(left<right){if(nums[left]+nums[right]>target) right--;else if(nums[left]+nums[right]==target) return{nums[left],nums[right]};else left++;}return {};}
};

在这里插入图片描述
调用stringstream

class Solution {
public:string reverseWords(string s) {string res = "",temp;stringstream ss(s);while(ss >> temp){res = temp + " " + res;//temp读取s里每一个单词}res.pop_back();return res;}
};

方法2：暴力解法
整体翻转+局部一个一个翻转（要求每个单词中间只能用一个空格连接）
思路找空格截取当前单词的0到空格拼接直到再也找不到空格
问题：1.要去除字符串前面所有的空格 2.去除字符串整体翻转后所有的空格 3.去除字符串中间单词的空格比如 a good example 。
举例：” a good example “
1.首先去除前面的空格->” a good example “
2.整体翻转->” elpmaxe doog a “，去除前面的空格->” elpmaxe doog a “
3.第一次找空格elpmaxe后面截取出来翻转->“example”,substr=example,result+=example,s截取变成” doog a“去除中间的空格->”doog a“
4.第二次找空格截取翻转”good“,substr=good;result=example good,s变成a,此时其实是找不到空格的，那条件判定就会出现问题，因此要在大循环while (s.find(" ") != s.npos)判断前，去除首位空格后，在s尾部加一个空格，这样到第四步就变成了 s=”a “
5.第三次找空格，a后面，翻转即本身，substr=a，result=a good example s啥也解决不到了
循环结束！！！

class Solution {
public:
string reverseWords(string s) {string result, substr;int len = s.size();int pos = 0;while (s[0] == ' '){len--;s = s.substr(1, len);}//去除前面的空格reverse(s.begin(), s.end());//整个字符串翻转int i = 0;while (s[0] == ' '){len--;s = s.substr(1, len);}//去除翻转后前面的空格s += " ";//后面加个空格cout<<s<<endl;len++;int flag = 0;while (s.find(" ") != s.npos){int j = 0;if (flag != 0) result+= " ";flag=1;//就是指示第一个不用加空格，下面单词拼接都要用的pos = s.find(" ");substr = s.substr(0, pos);reverse(substr.begin(), substr.end());result += substr;s = s.substr(pos+1 , len - pos - 1);len=s.size();while (s[0] == ' '){len--;s = s.substr(1, len);}//去除中间的空格}return result;
}
};