好家伙 人家总共31天 我就写了13天 惭愧

Day13.1 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，
使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

排序？— 二分？ — 不需要排序

暴力解法：

开辟一块地址为N ，直接遍历整个数组 判断奇偶，分别放入到中点的两边

时间复杂度：N
空间复杂度：N

空间O(1)解法

最好是能在原地处理
image.png
这个 思路绝绝子
一点补充

  • 截至条件是：i j相等 （用 i > j 判断）
  • 循环的条件是
    • 可以步进
    • 也可以直接找

一层循环的步进写法

  1. class Solution:
  2.     def exchange(self, nums: List[int]) -> List[int]:
  3.         point_even = 0
  4.         point_old = len(nums)-1
  6.         while point_even < point_old :
  8.             if nums[point_even] %2 == 0 and nums[point_old] %2 ==1:
  9.                 temp = nums[point_even]
  10.                 nums[point_even] = nums[point_old]
  11.                 nums[point_old] = temp
  13.                 point_even +=1
  14.                 point_old -=1
  16.             elif nums[point_even] %2 != 0 and nums[point_old] %2 ==1:
  17.                 point_even +=1
  18.             elif nums[point_even] %2 == 0 and nums[point_old] %2 !=1:
  19.                 point_old -=1
  20.             else:
  21.                 point_even +=1
  22.                 point_old -=1
  24.         return nums

执行用时：36 ms, 在所有 Python3 提交中击败了96.18%的用户
内存消耗：18.8 MB, 在所有 Python3 提交中击败了88.63%的用户

二层循环

  1. class Solution:
  2.     def exchange(self, nums: List[int]) -> List[int]:
  3.         point_even = 0
  4.         point_old = len(nums)-1
  6.         while point_even < point_old :
  7.             # 找左边的偶数
  8.             while point_even < point_old:
  9.                 if nums[point_even] %2 == 0:
  10.                     break
  11.                 else:
  12.                     point_even +=1
  13.             # 找右边的奇数
  14.             while point_even < point_old:
  15.                 if nums[point_old] %2 ==1:
  16.                     break
  17.                 else:
  18.                     point_old -=1
  20.             #  交换
  21.             temp = nums[point_old]
  22.             nums[point_old] = nums[point_even]
  23.             nums[point_even] = temp
  25.         return nums

直观上感觉会比第一种好一些 — 时间复杂度和空间复杂度基本一致

同样的思路：人家好简洁

  1. class Solution:
  2.     def exchange(self, nums: List[int]) -> List[int]:
  3.         i, j = 0, len(nums) - 1
  4.         while i < j:
  5.             while i < j and nums[i] & 1 == 1: i += 1
  6.             while i < j and nums[j] & 1 == 0: j -= 1
  7.             nums[i], nums[j] = nums[j], nums[i]
  8.         return nums

Day13.2 剑指 Offer 57. 和为s的两个数字

输入一个递增排序的数组和一个数字s，
在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可

这不是两数之和吗？
用哈希表是比较直接的做法 — 用双指针咋做呢
image.png
卧槽 太酷了！！ 和上面的题思路有点像 这个移动还有点像二分查找

所以 两数之和那个题 也可以排序后用这个方法做

直接撸出答案

  1. class Solution:
  2.     def twoSum(self, nums: List[int], target: int) -> List[int]:
  3.         point_left = 0
  4.         point_right = len(nums) - 1
  6.         while nums[point_left] + nums[point_right] != target:
  7.             if nums[point_left] + nums[point_right] > target:
  8.                 point_right -=1
  9.             else:
  10.                 point_left +=1
  12.         return nums[point_left],nums[point_right]

爽的雅痞