结束两天的玩耍，回归学习！Day13的题目还是关于双指针的。这三个题目主要用的是一种双撞指针，双指针从两头向中间遍历，在双指针碰到一起时就完成所有的处理。
1.调整数组顺序使奇数位于偶数前面
（1）题目
（2）求解思路
因为存放这些数字的数组，所以还是有简单的解法的。如遍历nums，做两个数组分别存奇数和偶数，然后拼在一起。这是我的想法。
官方的解法则是用到了双撞指针，每次处理两个指针所在位置的数：
看懂了解析就很容易总结其思路了：
（3）代码
我的简单算法的Python代码：
classSolution:defexchange(self,nums:List[int])-List[int]:Odd,Even=[],[]#奇数与偶数列表foriinnums:ifi1==1:#为奇数#ifi%2!=0:#为奇数Odd.append(i)else:Even.append(i)returnOdd+Even
双指针算法的Python代码：
classSolution:defexchange(self,nums:List[int])-List[int]:i,j=0,len(nums)-1whileij:whileijandnums[i]1==1:i+=1whileijandnums[j]1==0:j-=1nums[i],nums[j]=nums[j],nums[i]returnnums
2.和为s的两个数字
（1）题目
（2）求解思路
之前网课上的解法是转化一种思路——在遍历到nums[i]时，判断(target-nums[i])是否在nums中即可。为了这种查找更快，可以采用HashSet或HashMap，Python中将列表转化为set更容易，所以我用的set。
官方则还是用的双撞指针，思路惊奇，值得学习。利用双指针降低了空间复杂度为O(1)，而借助HashSet的空间复杂度是O(N)：
这种方法的可行性证明：
（3）代码
利用set的Python代码：
classSolution:deftwoSum(self,nums:List[int],target:int)-List[int]:nums_set=set(nums)foriinnums:if(target-i)innums_set:return[i,target-i]
双指针的Python代码：
classSolution:deftwoSum(self,nums:List[int],target:int)-List[int]:i,j=0,len(nums)-1whileij:s=nums[i]+nums[j]ifstarget:j-=1elifstarget:i+=1else:returnnums[i],nums[j]return[]
3.翻转单词顺序Ⅰ
（1）题目
（2）求解思路
翻转一个数据结构，可以想到的双指针操作就是从两头开始对称交换数即可，但是这题的一些“注意”需要处理。主要就是空格处理：（1）开头和结尾最多只能有一个空格；（2）单词之间的空格最多只有一个。但是我这种做法不好写代码。
而官方的两个方法的思路都是找到单词，再去翻转，最后按空格连接。这样会很容易写代码了。
方法一：双指针
方法二：分割+倒序（利用Python的特性会很好写，但是C++无法做到这一点）
（3）代码
双指针的Python代码：
classSolution:defreverseWords(self,s:str)-str:s=s.strip()#删除首尾空格i=j=len(s)-1res=[]whilei=0:whilei=0ands[i]!=:i-=1#搜索首个空格res.append(s[i+1:j+1])#添加单词whilei=0ands[i]==:i-=1#跳过单词间空格j=i#j指向下个单词的尾字符return.join(res)#拼接并返回
分割+倒序法的Python代码（这里的s.strip()就是处理字符串头尾的空格）：
classSolution:defreverseWords(self,s:str)-str:s=s.strip()#删除首尾空格strs=s.split()#分割字符串strs.reverse()#翻转单词列表return.join(strs)#拼接为字符串并返回
Python还可以一行完成处理：
classSolution:defreverseWords(self,s:str)-str:return.join(s.strip().split()[::-1])
其他程序员的优秀代码：
classSolution:defreverseWords(self,s:str)-str:l=s.split()#按空格把字符串分成多个子字符串存入列表中m=[]#创建一个新的列表foriinl:#遍历子字符串temp=i.replace(,)#将子字符串中间的空格去掉-处理多空格-空格会变成空子字符串iflen(temp):#去除空字符串的情况m.append(i)#加入最终的结果m.reverse()#子字符串内部顺序和列表中字符串顺序完全翻转return.join(m)#以空格连接子字符串
这个代码的执行用时和内存消耗表现都很好：
预览时标签不可点收录于话题#个上一篇下一篇