力扣hot100_技巧_python版本

一、136. 只出现一次的数字

• 思路：
  • 任何数和 0 做异或运算，结果仍然是原来的数，即 a⊕0=a。
  • 任何数和其自身做异或运算，结果是 0，即 a⊕a=0。
  • 异或运算满足交换律和结合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。
• 代码：

class Solution:def singleNumber(self, nums: List[int]) -> int:return reduce(xor, nums)

二、169. 多数元素

• 代码：

class Solution:def majorityElement(self, nums: List[int]) -> int:n = len(nums)value_counts = defaultdict(int)for i in nums:value_counts[i] += 1for i in value_counts:if value_counts[i] >= n/2:return i

三、75. 颜色分类

• 思路：
  两次遍历，第一次将所有的0归为，第二次将所有的1归为
• 代码：

class Solution:def sortColors(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""def swap(i, j):nums[i], nums[j] = nums[j], nums[i]n = len(nums)ptr = 0for i in range(n):if nums[i] == 0:swap(i, ptr)ptr += 1for i in range(n):if nums[i] == 1:swap(i, ptr)ptr += 1  

四、31. 下一个排列

• 代码：

class Solution:def nextPermutation(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""n = len(nums)i = n-2while i >= 0 and nums[i] >= nums[i+1]:i -= 1if i >= 0:j = n-1while nums[j] <= nums[i]:j -= 1nums[i], nums[j] = nums[j], nums[i]left, right = i+1, n-1while left<right:nums[left], nums[right] = nums[right], nums[left]left += 1right -= 1

五、287. 寻找重复数

class Solution:def findDuplicate(self, nums: List[int]) -> int:n, i = len(nums), 0while i < n:t, idx = nums[i], nums[i] - 1  # t 是当前值，idx 是当前值该放到的位置if nums[idx] == t:             # 如果当前值已经在它该在的位置上if idx != i:               # 表示当前值 t 和它“应该在的位置”的值相等，说明有重复，立即返回return ti += 1else:nums[i], nums[idx] = nums[idx], nums[i]return -1