知乎 0916 iOS A 卷

笔试三道题，不用动脑子。

1 堆排序

import heapq

class Solution:
    def viewFrames(self , views: List[int], columnCount: int) -> List[List[int]]:
        result = []
        h = [[0, i] for i in range(columnCount)]
        heapq.heapify(h)

        for i in views:
            t = heapq.heappop(h)
            result.append([t[1] * 100, t[0], 100, i])
            heapq.heappush(h, [t[0] + i, t[1]])

        return result

2 计数排序

class Solution:
    def bestSell(self , dealFlow: List[int], minPrice: int, maxPrice: int) -> int:
        # write code here
        t = [0 for _ in range(400000)]
        for i in dealFlow:
            t[i] += 1
        count = 0
        index = -1
        for i in range(minPrice, maxPrice + 1):
            if t[i] > count or (t[i] != 0 and t[i] == count and i > index):
                count = t[i]
                index = i
        return index

3 DFS

class Solution:
    def dfs(self, grid: List[List[int]], x: int, y: int) -> int:
        if x < 0 or x >= len(grid):
            return 0
        if y < 0 or y >= len(grid[0]):
            return 0
        if grid[x][y] == 0:
            return 0
        result = grid[x][y]
        grid[x][y] = 0
        result += self.dfs(grid, x - 1, y)
        result += self.dfs(grid, x + 1, y)
        result += self.dfs(grid, x, y + 1)
        result += self.dfs(grid, x, y - 1)
        return result
    def bigestMine(self , grid: List[List[int]]) -> int:
        result = 0
        for x in range(len(grid)):
            for y in range(len(grid[x])):
                result = max(result, self.dfs(grid, x, y))
        return result