Speed

# 1. Two Sum
# array of integers,specific target ==> return indices
class Solution:
    def twoSum(self, num, target):
        map = {}   
        for i in range(len(num)):
            if num[i] not in map:      # 对于{}，用in, 用map[key]
                map[target - num[i]] = i
            else:
                return map[num[i]], i  # 返回的是位置，字典通过“数值”查询“位置”
        return -1, -1 #循环所有都没有 

# # Trapping Rain Water
# # elecation map; width 1; trap??
# # ==>300T/60=>5h
# 输入：height_List；
# 挖掘边界 最外层==>l_index&r_index  
# 挖掘固定参考边界 固定一侧 内层&&l_max&r_max&&ans
# 挖掘具体移动l+=或边界更新 及取值ans+= &&height[l]&height[r]&ans
class Solution:
    def trap(self, height: List[int]) -> int:
#       结果&边界点&边界值
        ans = 0
        l,r = 0 , len(height) -1
        l_max, r_max = 0,0
#       边界点内；
        while l < r:
#           右侧高点
            if height[l] < height[r]:
#               左侧高点置换
                if height[l] >= l_max:
                    l_max = height[l]
#               至左侧积水  
                else:
                    ans += l_max - height[l]
                l += 1            
#            左侧高点
            else:
#               右侧高点置换
                if height[r] >= r_max:
                    r_max = height[r]
                else:
                    ans += r_max - height[r]
                r -= 1   
        return ans

# Add Two Numbers
# given two non-empty linked lists 
# digits are stored in reverse order
# Add the two numbers and return it as a linked list.
class Solution:
    def addTwoNumbers(self,l1,l2):
        dummy=cur=ListNode(0)
        carry=0
        while l1 or l2 or carry:
            if l1:
                carry+=l1.val
                l1=l1.next
            if l2:
                carry+=l2.val
                l2=l2.next
            cur.next=ListNode(carry%10)
            cur=cur.next
            carry//=10
        return dummy.next

# Number of Islands
# Given a 2d grid map of '1's (land) and '0's (water),
# count the number of islands. 
# An island is surrounded by water;
# formed by connecting adjacent lands horizontally or vertically. 
# assume all four edges of the grid are all surrounded by water.
class Solution:
    def numIslands(self, grid):
        if not grid:
            return 0   # grid map=>1s&0s=>islands number=>adjacent lands                                                 
        count = 0
        for i in range(len(grid)):  # 遍历每行
            for j in range(len(grid[0])): # 每列
                if grid[i][j] == '1':  # Islands元素
                    self.dfs(grid, i, j)  # 穷尽Islands路径 并标记元素
                    count += 1 #路径加一
        return count  #Islands总数
    def dfs(self, grid, i, j):
        if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] != '1':
            return                       #边界或路径结束    
        grid[i][j] = '#'                 #遍历的标记
        self.dfs(grid, i+1, j)           
        self.dfs(grid, i-1, j)
        self.dfs(grid, i, j+1)
        self.dfs(grid, i, j-1)

# @des:   LRU(最近最少使用) 缓存机制
# OrderedDict 参看 https://docs.python.org/3/library/collections.html#collections.OrderedDict
class LRUCache:
    def __init__(self, capacity: int):
        self.dic = collections.OrderedDict()    # OrderedDict 记住了字典元素的添加顺序
        self.remain = capacity # 容量 大小
    def get(self, key: int) -> int:
        if key not in self.dic:
            return -1
        v = self.dic.pop(key)
        self.dic[key] = v # 被获取 刷新最近使用
        return v    
    def put(self, key: int, value: int) -> None:
        if key in self.dic:
            self.dic.pop(key) # 如果字典中有先弹出 再加入
        else: # 没有
            if self.remain > 0: # 字典未满
                self.remain -= 1 # 剩余容量 -1
            else: #  字典已满 弹出最近最少使用的，最老的元素
                self.dic.popitem(last = False)
                '''
                popitem(last=True)
                The popitem() method for ordered dictionaries returns and removes a (key, value) pair. 
                The pairs are returned in LIFO order if last is true or FIFO order if false.
                '''
        self.dic[key] = value