283. Move Zeroes
https://leetcode.com/problems/move-zeroes/
solution
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
slow = 0 # 有效位置,本题存放第一个0的位置. 类似quick sort中的partition
for i in range(len(nums)):
if nums[i] != 0:
nums[slow], nums[i] = nums[i], nums[slow]
slow += 1
时间复杂度:O(n) 空间复杂度:O(1)
follow up
位运算:异或
class Solution:
def missingNumber(self, nums: List[int]) -> int:
s = 0
for i in nums:
s = s ^ i
for i in range(len(nums)+ 1):
s = s ^ i
return s
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
for i in range(n):
# 注意这里是while
while nums[i] >= 0 and nums[i] < n and nums[nums[i] - 1] != nums[i]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
maxpos = 0
for num in nums:
if num > maxpos:
maxpos = num
minpos = maxpos
for num in nums:
if num < minpos and num > 0:
minpos = num
if minpos > 1:
return 1
for i in range(minpos + 1,maxpos + 1):
if i in nums:
continue
else:
return i
return maxpos + 1
# 两障碍物之间的区间, 加到前后. 注意题目条件: nums元素的取值范围为[lower,upper]
class Solution:
def findMissingRanges(self, nums, lower, upper):
nums = [lower - 1] + nums + [upper + 1]
res = []
for i in range(1, len(nums)):
if nums[i] - nums[i-1] > 1:
l = nums[i-1] + 1
h = nums[i] - 1
res.append(str(l) if l == h else '{}->{}'.format(l, h))
return res
287. Find the Duplicate Number
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
slow = nums[0]
fast = nums[0]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
Last updated