算法-快速排序及优化

快速排序及优化

快速排序基础

148. 排序链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        slow = head
        fast = head.next
        while fast and fast.next:
            fast, slow = fast.next.next, slow.next
        mid, slow.next = slow.next, None
        left, right = self.sortList(head), self.sortList(mid)
        tmp = res = ListNode(0)
        while left and right:
            if left.val < right.val:
                tmp.next, left = left, left.next
            else:
                tmp.next, right = right, right.next
            tmp = tmp.next
        tmp.next = left if left else right
        return res.next

912. 排序数组

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if len(nums) <= 1:
            return nums
        mid = nums[len(nums) // 2]
        left, right = [], []
        nums.remove(mid)
        for i in nums:
            if i < mid:
                left.append(i)
            else:
                right.append(i)
        return self.sortArray(left) + [mid] + self.sortArray(right)

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

class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        queue = collections.deque()
        for i in nums:
            if i % 2 == 0:
                queue.append(i)
            else:
                queue.appendleft(i)
        return list(queue)

快速排序扩展

面试题 17.14. 最小K个数

class Solution:
    def smallestK(self, arr: List[int], k: int) -> List[int]:
        if k == 0:
            return []
        result = []
        heapq.heapify(arr)
        for i in range(len(arr)):
            result.append(heapq.heappop(arr))
            if i == k-1:
                break
        return result

75. 颜色分类

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

95. 不同的二叉搜索树 II

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        if not n:
            return []
        return self.get_help(1, n)

    def get_help(self, left, right):
        if left > right:
            return [None]
        result = []
        for i in range(left, right + 1):
            left_tree = self.get_help(left, i - 1)
            right_tree = self.get_help(i + 1, right)
            for  l in left_tree:
                for r in right_tree:
                    Tree = TreeNode(i)
                    Tree.left = l
                    Tree.right = r
                    result.append(Tree)
        return result

394. 字符串解码

class Solution:
    def decodeString(self, s: str) -> str:
        stack =[]
        result = ''
        num = 0
        for i in s:
            if '0' <= i <= '9':
                num = num * 10 + int(i)
            elif i == '[':
                stack.append([result,num])
                result, num = '', 0
            elif i == ']':
                res, n = stack.pop()
                result = res + n * result
            else:
                result += i
        return result

附加题

11. 盛最多水的容器

class Solution:
    def maxArea(self, height: List[int]) -> int:
        result = []
        left = 0
        right = len(height) - 1
        while left != right:
            water_v = (right - left) * min(height[left], height[right])
            result.append(water_v)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return max(result)

470. 用 Rand7() 实现 Rand10()

# The rand7() API is already defined for you.
# def rand7():
# @return a random integer in the range 1 to 7

class Solution:
    def rand10(self):
        """
        :rtype: int
        """
        while 1:
            m = rand7()
            n = rand7()
            num = (m-1) * 7 + n
            if num <= 40:
                return num % 10 + 1

239. 滑动窗口最大值

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        queue = collections.deque()
        ans = []
        for i in range(len(nums)):
            while queue and nums[queue[-1]] < nums[i]: queue.pop()
            queue.append(i)
            if queue[0] == i - k: queue.popleft()
            if i + 1 < k: continue 
            ans.append(nums[queue[0]])
        return ans