Day34

690. Employee Importance
     思路：给定一个id号，计算他和他的所有直接或间接的下属的总价值。我开始单纯的认为只要在employees这个数组里，找到id号为指定id号的雇员，然后计算了他的直接下属的价值，忘记了要深度搜索间接下属。看案例是需要建立字典的，深搜要用递归，dfs(id)计算这个id号的所有价值，划分为一个子问题来考虑。

"""
# Employee info
class Employee(object):
    def __init__(self, id, importance, subordinates):
        # It's the unique id of each node.
        # unique id of this employee
        self.id = id
        # the importance value of this employee
        self.importance = importance
        # the id of direct subordinates
        self.subordinates = subordinates
"""
class Solution(object):
    def getImportance(self, employees, id):
        """
        :type employees: Employee
        :type id: int
        :rtype: int
        """
        emps = {employee.id : employee for employee in employees}
        def dfs(ids):
            subordinates_importance = sum([dfs(idd) for idd in emps[ids].subordinates])
            return emps[ids].importance + subordinates_importance
        return dfs(id)

695. Max Area of Island
     思路：只想到从两个方向上搜索为1的数，想到了用深搜，但是如何去分割这一块一块的岛？案例中用的穷尽的方法，计算每一个格子，如果向四周搜索能得到多大的面积，然后求最大值。

class Solution(object):
    def maxAreaOfIsland(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m = len(grid)
        n = len(grid[0])
        def dfs(i,j):
            if i>=0 and i <m and j >=0 and j <n and grid[i][j]:
                grid[i][j] = 0 #找过的就标为0，做个标记
                return 1+ dfs(i-1,j)+dfs(i+1,j)+dfs(i,j-1)+dfs(i,j+1) #四周深搜
            return 0
        areas = [dfs(i,j) for i in range(m) for j in range(n) if grid[i][j]]
        
        return max(areas) if areas else 0