Day30

差不多两周没刷题了，开会一周，咸鱼一周，惭愧惭愧。

463. Island Perimeter

     
     

思路：开始构想的是在map四周扩张一圈water，然后判断每个cell，如果上下左右存在1，那就在4的基础上减一，这样需要重构一个新的二维数组，太复杂。参考方法是假设每个方格，如果上或左存在1，就意味着两个格子减一，即减二。不算最上一行，和最左一列。

class Solution(object):
    def islandPerimeter(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        edge = 0
        for h in range(len(grid)):
            for w in range(len(grid[0])):
                if grid[h][w] == 1:
                    edge += 4
                    if h>0 and grid[h-1][w]:
                        edge -= 2
                    if w>0 and grid[h][w-1]:
                        edge -= 2
        return edge  

496. Next Greater Element I
     思路：理解题意错误，开始认为是在相同位置往后找比它大的数；实际上是在相同数的位置往后找比它大的数。需要建立map映射，找到nums数组里每个数对应的其后比它大的数，建立字典；然后在findNums数组里去找有没有对应的键值。用到get函数。

class Solution(object):
    def nextGreaterElement(self, findNums, nums):
        """
        :type findNums: List[int]
        :type nums: List[int]
        :rtype: List[int]
        """
        st = []
        d = {}
        ans = []
        
        for x in nums:
            while len(st) and st[-1] < x:
                d[st.pop()] = x
            st.append(x)
        
        for y in findNums:
            ans.append(d.get(y,-1))
        return ans