Python3刷题系列（三）

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        
        l = 1
        r = x
        
        while l <= x:
            res = (l + r) // 2
            s = res ** 2
            
            if s <= x < (res + 1)**2:
                return res
            if s < x:
                l = res
            if s > x:
                r = res
                

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        i = 0
        j = len(numbers) - 1
        while i < j:
            if numbers[i] + numbers[j] > target:
                j -= 1
            elif numbers[i] + numbers[j] < target:
                i += 1
            else:
                return [i+1, j+1]

# 暴力解法：
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return sorted(nums)[-k]
        

# 快排：时间复杂度-O(N), 空间复杂度-O(1).
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return self.quick_sort(nums, k)
    
    def quick_sort(self, nums, k):
        k = len(nums) -k
        left = 0
        right = len(nums) - 1
        while left < right:
            j = self.partition(nums, left, right)
            if j == k:
                break
            elif j < k:
                left = j + 1
            else:
                right = j -1
        return nums[k]
    
    def partition(self, nums, left, right):
        while True:
            while nums[left] < nums[right]:
                right -= 1
            else:
                nums[left], nums[right] = nums[right], nums[left]
                if left >= right:
                    break
                left += 1
                
            while nums[left] < nums[right]:
                left += 1
            else:
                nums[left], nums[right] = nums[right], nums[left]
                if left >= right:
                    break
                right -= 1
        return left


# 堆排：时间复杂度-O(NlogK), 空间复杂度-O(K).
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return self.heap_sort(nums, k)
    
    def heap_sort(self, nums, k):
        for i in range(len(nums)//2 - 1, -1, -1):
            self.heap_adjust(nums, i, len(nums))
            
        cnt = 0
        for i in range(len(nums) - 1, 0, -1):
            self.heap_swap(nums, 0, i)
            cnt += 1
            if cnt == k:
                return nums[i]
            self.heap_adjust(nums, 0, i)
        return nums[0]
        
    def heap_adjust(self, nums, start, length):
        tmp = nums[start]
        k = start * 2 + 1
        while k < length:
            left = start * 2 + 1
            right = left + 1
            
            if right < length and nums[right] > nums[left]:
                k = right
                
            if nums[k] > tmp:
                nums[start] = nums[k]
                start = k
            else:
                break
            k = k*2 + 1
        nums[start] = tmp
    
    def heap_swap(self, nums, i, j):
        nums[i], nums[j] = nums[j], nums[i]
        return nums

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        frequent_of_number = {}
        for num in nums:
            frequent_of_number[num] = frequent_of_number.get(num, 0) + 1
        buckets = [[] for i in range(len(nums) + 1)]
        for key, value in frequent_of_number.item():
            buckets[value].append(key)
        print(buckets)
        result = []
        for x in range(len(nums), -1, -1):
            if k > 0 and buckets[x]:
                result += buckets[x]
                k -= len(buckets[x])
            if k == 0:
                return result

# 暴力解法：
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums.sort()

# 三向切分快速排序思想：
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        head, now, tail = 0, 0, len(nums) - 1
        while now <= tail:
            if nums[now] == 0:
                nums[now], nums[head] = nums[head], nums[now]
                now += 1
                head += 1
            elif nums[now] == 2:
                nums[now], nums[tail] = nums[tail], nums[now]
                tail -= 1
            else:
                now += 1

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g = sorted(g)
        s = sorted(s)
        cnt_g = 0
        cnt_s = 0
        while cnt_g < len(g) and cnt_s < len(s):
            if g[cnt_g] <= s[cnt_s]:
                cnt_g += 1
            cnt_s += 1
        return cnt_g