9.14 58同城算法笔试3AC python版代码

全是leetcode原题

1.岛屿最大面积

class Solution:
    def getMaxArea(self , data ):
        # write code here
        if not data or not data[0] : return 0
        m = len(data)
        n = len(data[0])
        max_ = 0
        for i in range(m):
            for j in range(n):
                if data[i][j] == 1: max_ = max(max_, self.dfs(data, i, j))
        return max_

    def dfs(self, data, i, j):
        if i < 0 or i >= len(data) or j < 0 or j >= len(data[0]): return 0
        return 1 + self.dfs(data, i+1, j) + self.dfs(data, i-1, j) + self.dfs(data, i, j+1) + self.dfs(data, i, j-1)

2. 41 缺失的第一个正数

   class Solution:
    def firstMissingPositive(self , nums ):
        # write code here
        n = len(nums)
        for i in range(n):
            while nums[i] > 0 and nums[i] <= n and nums[nums[i]-1] != nums[i]: self.swap(nums, nums[i]-1, i)
        for i in range(n):
            if nums[i] != i+1: return i+1
        return n+1
   
    def swap(self, nums, i, j):
        nums[i], nums[j] = nums[j], nums[i]

3. 层序遍历二叉树

   from queue import Queue
   class Solution:
    def printNode(self , node ):
        # write code here
        if not node : return []
        q = Queue()
        q.put(node)
        res = []
        while not q.empty():
            size = q.qsize()
            lst = []
            while size > 0:
                temp = q.get()
                lst.append(temp.val)
                size -= 1
                if temp.left: q.put(temp.left)
                if temp.right: q.put(temp.right)
            res.append(lst)
        return res