637. 二叉树的层平均值

637. 二叉树的层平均值

import json

from tools import treeGenerate
from typing import List, Optional
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

from collections import deque
class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        queue = deque([None, root])
        count = 0
        total = 0
        ans = []
        while queue:
            node = queue.pop()
            if node is None:
                ans.append(total / count)
                count = 0
                total = 0
                if queue:
                    queue.appendleft(None)
                continue
            count += 1
            total += node.val
            if node.left:
                queue.appendleft(node.left)
            if node.right:
                queue.appendleft(node.right)
        return ans

278. 第一个错误的版本

278. 第一个错误的版本

class Solution:
    def firstBadVersion(self, n: int) -> int:
        end = n
        start = 1
        while start < end:
            mid = start + (end - start) // 2
            if isBadVersion(mid):
                end = mid
            else:
                start = mid + 1
        return start

404. 左叶子之和

404. 左叶子之和

class Solution:
    def __init__(self):
        self.ans = 0

    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        self.dfs(root, False)
        return self.ans


    def dfs(self, node, is_left):
        if node.left is None and node.right is None and is_left:
            self.ans += node.val
        if node.left:
            self.dfs(node.left, True)
        if node.right:
            self.dfs(node.right, False)

827. 最大人工岛

827. 最大人工岛

• 假设原数据为：

  [
      [0, 0, 0, 0, 0, 0, 0],
      [0, 1, 1, 1, 1, 0, 0],
      [0, 1, 0, 0, 1, 0, 0],
      [1, 0, 1, 0, 1, 0, 0],
      [0, 1, 0, 0, 1, 0, 0],
      [0, 1, 0, 0, 1, 0, 0],
      [0, 1, 1, 1, 1, 0, 0]
  ]

• 深度优先遍历找出所有的岛屿及其面积并进行标号（编号从2开始）；

  [
      [0, 0, 0, 0, 0, 0, 0], 
      [0, 2, 2, 2, 2, 0, 0], 
      [0, 2, 0, 0, 2, 0, 0], 
      [3, 0, 4, 0, 2, 0, 0],
      [0, 2, 0, 0, 2, 0, 0], 
      [0, 2, 0, 0, 2, 0, 0], 
      [0, 2, 2, 2, 2, 0, 0]
  ]

• 数据存储在字典中island_area: Dict[int, int]={2: 15, 3: 1, 4: 1}
• 再进行双重循环，找到所有为0的区域（即可以被连接的区域），将上下左右岛屿的面积相加再加1，找到最大值。

from typing import List, Dict

from collections import defaultdict


class Solution:
    def __init__(self):
        self.grid = None
        self.island_number = 2  # 当前正在探测的岛屿的编号
        self.island_area: Dict[int, int] = defaultdict(int) # 岛屿的面积

    def largestIsland(self, grid: List[List[int]]) -> int:
        self.grid = grid
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if self.grid[i][j] == 1:
                    self.dfs(i, j)
                    self.island_number += 1
        if len(self.island_area) == 1 and len(grid) * len(grid[0]) == self.island_area[2]:
            return self.island_area[2]
        max_area = 0
        used = set()
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                now_area = 1
                used.clear()
                if grid[i][j] == 0:
                    if i - 1 >= 0 and grid[i - 1][j] not in used:
                        now_area += self.island_area[grid[i - 1][j]]
                        used.add(grid[i - 1][j])
                    if i + 1 < len(self.grid) and grid[i + 1][j] not in used:
                        now_area += self.island_area[grid[i + 1][j]]
                        used.add(grid[i + 1][j])
                    if j - 1 >= 0 and grid[i][j - 1] not in used:
                        now_area += self.island_area[grid[i][j - 1]]
                        used.add(grid[i][j - 1])

                    if j + 1 < len(self.grid[i]) and grid[i][j + 1] not in used:
                        now_area += self.island_area[grid[i][j + 1]]
                        used.add(grid[i][j + 1])
                if now_area > max_area:
                    max_area = now_area
        return max_area

    def dfs(self, x, y):
        if self.grid[x][y] == 0 or self.grid[x][y] == self.island_number: # 正在探测
            return
        self.island_area[self.island_number] += 1
        self.grid[x][y] = self.island_number
        if x - 1 >= 0:
            self.dfs(x - 1, y)
        if x + 1 < len(self.grid):
            self.dfs(x + 1, y)
        if y - 1 >= 0:
            self.dfs(x, y - 1)
        if y + 1 < len(self.grid[x]):
            self.dfs(x, y + 1)