xmchxup / kata Goto Github PK

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res = []
        m, n = len(matrix), len(matrix[0])
        visited = [[False for _ in range(n)] for _ in range(m)]
        dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        x, y = 0, 0
        dir_idx = 0

        def is_valid_coordinate(x, y):
            return not (x < 0 or x >= n or y < 0 or y >= m or visited[y][x])

        while len(res) < m * n:
            res.append(matrix[y][x])
            visited[y][x] = True
            delta_x, delta_y = dirs[dir_idx]
            if not is_valid_coordinate(x + delta_x, y + delta_y):
                dir_idx = (dir_idx + 1) % 4
                delta_x, delta_y = dirs[dir_idx]
            x, y = x + delta_x, y + delta_y

        return res

from typing import List
import random


class Solution:
    def findKthLargestV2(self, nums: List[int], k: int) -> int:
        pivot = random.choice(nums)
        left = [x for x in nums if x < pivot]
        mid = [x for x in nums if x == pivot]
        right = [x for x in nums if x > pivot]

        if k <= len(right):
            return self.findKthLargestV2(right, k)
        elif k > len(right) + len(mid):
            return self.findKthLargestV2(left, k - (len(right) + len(mid)))
        return mid[0]

    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quickSelect(lo: int, hi: int, k: int):
            if lo >= hi:
                return nums[lo]
            x = nums[lo]
            i, j = lo - 1, hi + 1
            while i < j:
                i += 1
                while i <= j:
                    if nums[i] >= x:
                        break
                    i += 1
                j -= 1
                while j >= i:
                    if nums[j] <= x:
                        break
                    j -= 1
                if i < j:
                    nums[i], nums[j] = nums[j], nums[i]
            largeCnt = hi - j
            if k <= largeCnt:
                return quickSelect(j + 1, hi, k)
            else:
                return quickSelect(lo, j, k - largeCnt)

        return quickSelect(0, len(nums) - 1, k)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1 for _ in range(n)] for _ in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[m - 1][n - 1]

from typing import List
class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        res = 0
        i, j = len(g) - 1, len(s) - 1
        while i >= 0 and j >= 0:
            if s[j] >= g[i]:
                res += 1
                j -= 1
                i -= 1
            else:
                i -= 1
        return res