【算法题解】 Day28 双指针
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
题目
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 难度：easy
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
示例：
输入： nums = [1,2,3,4]
输出： [1,3,2,4]
注： [3,1,2,4] 也是正确的答案之一。提示：
0 <= nums.length <= 500000 <= nums[i] <= 10000
方法一：两次遍历
思路
新建一个数组 res用来保存调整完成的数组。遍历两次 nums，第一次遍历时把所有奇数依次追加到 ress 中，第二次遍历时把所有偶数依次追加到 res 中。
解题
Python：
class Solution:
def exchange(self, nums: List[int]) -> List[int]:
return [num for num in nums if num % 2 == 1] + [num for num in nums if num % 2 == 0]Java：
class Solution {
public int[] exchange(int[] nums) {
int n = nums.length, index = 0;
int[] res = new int[n];
for (int num : nums) {
if (num % 2 == 1) {
res[index++] = num;
}
}
for (int num : nums) {
if (num % 2 == 0) {
res[index++] = num;
}
}
return res;
}
}方法二：双指针
思路
记数组 nums的长度为 nnn。先从 nums左侧开始遍历，如果遇到的是奇数，就表示这个元素已经调整完成了，继续从左往右遍历，直到遇到一个偶数。然后从 nums右侧开始遍历，如果遇到的是偶数，就表示这个元素已经调整完成了，继续从右往左遍历，直到遇到一个奇数。交换这个偶数和奇数的位置，并且重复两边的遍历，直到在中间相遇，nums 调整完成。
解题
Python：
class Solution:
def exchange(self, nums: List[int]) -> List[int]:
left, right = 0, len(nums) - 1
while left < right:
while left < right and nums[left] % 2 == 1:
left += 1
while left < right and nums[right] % 2 == 0:
right -= 1
if left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
return numsJava：
class Solution {
public int[] exchange(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
while (left < right && nums[left] % 2 == 1) {
left++;
}
while (left < right && nums[right] % 2 == 0) {
right--;
}
if (left < right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
return nums;
}
}剑指 Offer 58 - I. 翻转单词顺序
题目
剑指 Offer 58 - I. 翻转单词顺序 难度：easy
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。
示例 1：
输入: "the sky is blue"
输出: "blue is sky the"示例 2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。示例 3：
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。说明：
- 无空格字符构成一个单词。
- 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
- 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
方法一：双指针
思路
- 倒序遍历字符串 s，记录单词左右索引边界 i , j ；
- 每确定一个单词的边界，则将其添加至单词列表 res ；
- 最终，将单词列表拼接为字符串，并返回即可。
解题
Python：
class Solution:
def reverseWords(self, s: str) -> str:
s = s.strip() # 删除首尾空格
i = j = len(s) - 1
res = []
while i >= 0:
while i >= 0 and s[i] != ' ': i -= 1 # 搜索首个空格
res.append(s[i + 1: j + 1]) # 添加单词
while s[i] == ' ': i -= 1 # 跳过单词间空格
j = i # j 指向下个单词的尾字符
return ' '.join(res) # 拼接并返回Java：
class Solution {
public String reverseWords(String s) {
s = s.trim(); // 删除首尾空格
int j = s.length() - 1, i = j;
StringBuilder res = new StringBuilder();
while(i >= 0) {
while(i >= 0 && s.charAt(i) != ' ') i--; // 搜索首个空格
res.append(s.substring(i + 1, j + 1) + " "); // 添加单词
while(i >= 0 && s.charAt(i) == ' ') i--; // 跳过单词间空格
j = i; // j 指向下个单词的尾字符
}
return res.toString().trim(); // 转化为字符串并返回
}
}
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-10-27，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录