Python3刷题系列（七）

# leetcode-241:分治思想
class Solution:  # 使用递归实现分治思想，战胜了 63.59% 
    def diffWaysToCompute(self, input: str) -> List[int]:
        return_list = []
        for i in range(len(input)):
            c = input[i]
            if c in ['+','-','*']:
                left = self.diffWaysToCompute(input[:i])
                right = self.diffWaysToCompute(input[i+1:])
                for l in left:
                    for r in right:
                        if c == '+':
                            return_list.append(l+r)
                        elif c == '-':
                            return_list.append(l-r)
                        elif c == '*':
                            return_list.append(l*r)
        if not return_list:
            return_list.append(int(input))  # return_list为空时，显然input只有一个整数

        return return_list

# leetcode-69: 二分查找, O(lgn), 战胜了 84.44%
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(object):  # 同样是二分查找，这种写法超时
    def mySqrt(self, x):
        if x <= 1:
            return x  # 考虑到0,1的情况
        l = 0
        h = x
        while l <= h:
            m = l + (h - 1) / 2  # 中值：防止溢出，等于（l + h） / 2,后者容易溢出
            if x > m**2:
                l = m+1
            elif x < m**2:
                h = m-1
            elif x == m**2:
                return int(m)
        return int(h)

# keetcode-1：哈希表
class Solution:   # 战胜了87.27%
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict = {}
        for i in range(len(nums)):
            if nums[i] in dict:
                return [dict[nums[i]], i]
            dict[target - nums[i]] = i

# 和上面阶梯思想一致，细节不同而已
class Solution:   # 战胜了87.27%
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        my_dict = {}
        for i in range(len(nums)):
            if target - nums[i] in my_dict:
                return [my_dict[target - nums[i]], i]
            my_dict[nums[i]] = i

# leetcode-347：桶排序
class Solution:  # 战胜了32.06%
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        di = {}
        for num in nums:
            if num not in di:
                di[num] = 1
            else:
                di[num] += 1
        bucket = [[] for _ in range(len(nums) + 1)]
        for key, value in di.items():
            bucket[value].append(key)
        ans = []
        for i in range(len(nums), -1, -1):
            if bucket[i]:
                ans.extend(bucket[i])
            if len(ans) >= k:
                break
        return ans[:k]

class Solution:  # 战胜了24.62%
    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.items():
            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

# leetcode-455：贪心算法
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

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        child = 0
        cookies = 0

        while len(g) > child and len(s) > cookies:
          if g[child] <= s[cookies]:
            child += 1
          cookies += 1
        return child

# leetcode-215：快排：时间复杂度-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 findKthLargest(self, nums: List[int], k: int) -> int:
      if len(nums) == 0:
        return
      nums = self.quicksort(nums)
      return nums[-k]

    def quicksort(self, nums):
      if len(nums) == 0:
        return []
      pivot = nums[0]
      left = self.quicksort([x for x in nums[1:] if x < pivot])
      right = self.quicksort([x for x in nums[1:] if x >= pivot])
      return left + [pivot] + right

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

# 三向切分快速排序思想：
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 sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        zero, two = -1, len(nums)
        i = 0
        while i < two:
          if nums[i] == 1:
            i += 1
          elif nums[i] == 2:
            two -= 1
            nums[two], nums[i] = nums[i], nums[two]
          else:
            zero += 1
            nums[zero], nums[i] = nums[i], nums[zero]
            i += 1

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

# 双指针：
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 twoSum(self, numbers: List[int], target: int) -> List[int]:
        a = 0
        b = len(numbers) -1

        while a < b:
            if numbers[a] + numbers[b] < target:
                a += 1
            elif numbers[a] + numbers[b] > target:
                b -= 1
            elif numbers[a] + numbers[b] == target:
                return [a+1, b+1]
        else:
            return None

class Solution:
  def twoSum(self, numbers: List[int], target: int) -> List[int]:
    length = len(numbers)
    for i in range(0, length-1):
      for j in range(i+1, length):
        a = numbers[i]
        b = numbers[j]
        sum = a +b
        if sum == target:
          break
      if sum == target:
        break
    return i+1, j+1