23.01.06 Today’s Leetcode

1833. Maximum Ice Cream Bars (medium)

class Solution:
    def maxIceCream(self, costs: List[int], coins: int) -> int:
        costs.sort()
        # print(costs)
        count = 0
        for cost in costs:
            if cost <= coins:
                coins -= cost
                count += 1
            else:
                break
        return count

77. Combinations (medium)

# use itertools.combinations
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        arr = [x for x in range(1, n + 1)]
        return list(itertools.combinations(arr, k))
        

# use backtracking
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def backtrack(first = 1, curr = []):
            if len(curr) == k:
                output.append(curr[:])
            for i in range(first, n + 1):
                curr.append(i)
                backtrack(i+1, curr)
                curr.pop()
        output = []
        backtrack()
        return output

934. Shortest Bridge (medium, solving)

class Solution:

    def spread(self, grid, x, y):
        n = len(grid)
        if x < 0 or x >= n or y < 0 or y >= n:
            return
        if grid[x][y] == 0 or grid[x][y] == 2:
            return
        grid[x][y] = 2
        self.spread(grid, x + 1, y)
        self.spread(grid, x - 1, y)
        self.spread(grid, x, y + 1)
        self.spread(grid, x, y - 1)

    def find_bridge(self, grid, x, y):
        n = len(grid)
        if x < 0 or x >= n or y < 0 or y >= n:
            return 10**9
        if grid[x][y] == 99:
            return 10**9
        if grid[x][y] == 1:
            return 0
        res = 10**9
        origin = grid[x][y]
        grid[x][y] = 99
        res = min(res, self.find_bridge(grid, x + 1, y))
        res = min(res, self.find_bridge(grid, x - 1, y))
        res = min(res, self.find_bridge(grid, x, y + 1))
        res = min(res, self.find_bridge(grid, x, y - 1))
        grid[x][y] = origin
        return res + 1

    def distance(self, grid, point1, point2):
        return abs(point1[0] - point2[0]) + abs(point1[1] - point2[1])
        
    def shortestBridge(self, grid: List[List[int]]) -> int:
        n = len(grid)
        for x in range(n):
            for y in range(n):
                if grid[x][y] == 1:
                    self.spread(grid, x, y)
                    break
        print(grid)
        res = 10**9
        for x in range(n):
            for y in range(n):
                if grid[x][y] == 2:
                    res = min(res, self.find_bridge(grid, x, y))
        return res