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

268. Missing Number

• 位运算：异或

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

41. First Missing Positive

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

*163. Missing Ranges

# 两障碍物之间的区间, 加到前后. 注意题目条件: 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