TopFreq0210

# 1. Two Sum
# Given nums = [2, 7, 11, 15], target = 9,
# Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
class Solution:
    def twoSum(self,nums,target):
        map={}
        for i in range(len(nums)):
            if nums[i] not in map:
                map[target-nums[i]]=i
            else:
                return i,map[nums[i]]
        return -1,-1

# 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       

42. Trapping Rain Water
class Solution:
    def trap(self,height):
        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:
                    ans+=l_max-height[l]
                else:
                    l_max=height[l]
                l+=1
            else:
                if height[r]<r_max:
                    ans+=r_max-height[r]
                else:
                    r_max=height[r]
                r-=1                
        return ans

# 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)

# 20. Valid Parentheses
# string containing just the characters '(', ')', '{', '}', '[' and ']'
# determine if the input string is valid.
# correct order&same type 
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        dict = {"]":"[", "}":"{", ")":"("}
        for char in s:
            if char in dict.values():  # 开口
                stack.append(char)
            elif char in dict.keys():  # 闭口 查看字典开口 同时pop出内部对
                if stack == [] or dict[char] != stack.pop():  
                    return False
            else:
                return False
        return stack == []

# Merge Two Sorted Lists
# Input: 1->2->4, 1->3->4
# Output: 1->1->2->3->4->4
class Solution:
        # iteratively
    def mergeTwoLists(self, l1, l2):
        dummy = cur = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        cur.next = l1 or l2
        return dummy.next

# Merge Two Sorted Lists
# Input: 1->2->4, 1->3->4
# Output: 1->1->2->3->4->4
class Solution:
        # iteratively
    def mergeTwoLists(self, l1, l2):
        dummy = cur = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        cur.next = l1 or l2
        return dummy.next

# 5. Longest Palindromic Substring
# string s, find the longest palindromic substring in s.
class Solution:
    def longestPalindrome(self, s: str) -> str:
        res = ""
        for i in range(len(s)):
            # odd case, like "aba"
            tmp = self.helper(s, i, i)
            if len(tmp) > len(res):
                res = tmp
            # even case, like "abba"
            tmp = self.helper(s, i, i+1)
            if len(tmp) > len(res):
                res = tmp
        return res
    # get the longest palindrome, l, r are the middle indexes   
    # from inner to outer
    def helper(self, s, l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1; r += 1
        return s[l+1:r]