LcTop5-0215

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

• 差值 索引脚标；用map字典，map[value]=index;*
• 遍历一遍，存字典、或判断差值存在；map[target-nums[i]]=i;

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  

• 当前位：ListNode(carry%10);
  进位：carry//=10; carry+=l.val；
  链表头与新链表：dummy=cur=ListNode(0)；

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)

42. Trapping Rain Water

n: elevation map
width bar is 1
compute trap 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

• 遍历一遍：获取当前柱囤水 & 总囤水；
  参考柱：两端较高柱 & 较低柱；
  当前柱：当前囤水 或更新较小柱；

LRU Cache

# 146. LRU Cache
# Design and implement a data structure for Least Recently Used (LRU) cache. 
# support: get and put.
# get(key) -key exists in the cache: value, otherwise -1.
# put(key, value) - Set or insert the value if key is not present. 
# When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
# initialized: positive capacity.
# O(1) time complexity?

# @des:   LRU(最近最少使用) 缓存机制
# OrderedDict 参看 https://docs.python.org/3/library/collections.html#collections.OrderedDict
# OrderedDict是dict子类，支持dict所有方法，记住了插入key的顺序。
# 如果新条目覆盖现有条目，则原始插入位置保持不变。 删除条目并重新插入它将使其移至最后。详细介绍参见Python官方文档。
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)
                removes a (key, value) pair. 
                LIFO if last true or FIFO if false.
                '''
        self.dic[key] = value 

202. Happy Number

number === sum of the squares of its digits
repeat the process until the number equals 1
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

class Solution:
    def isHappy(self, n: int) -> bool:
        seen = set()
        while n not in seen:  #如果重复 则结束； 
            seen.add(n)   #中间数添加到集合里；
            n = sum([int(x) **2 for x in str(n)]) #中间数的平方和
        return n == 1 #判断是否为 1 

*set集合；
*while not in =>add & sum
*return n==1

Critical Connections in a Network

# 1192. Critical Connections in a Network
import collections
class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        def makeGraph(connections):
            graph = collections.defaultdict(list)
            for conn in connections:
                graph[conn[0]].append(conn[1])
                graph[conn[1]].append(conn[0])
            return graph        
        graph = makeGraph(connections)
        connections = set(map(tuple, (map(sorted, connections))))
        rank = [-2] * n
        
        def dfs(node, depth):
            if rank[node] >= 0:
                # visiting (0<=rank<n), or visited (rank=n)
                return rank[node]
            rank[node] = depth
            min_back_depth = n
            for neighbor in graph[node]:
                if rank[neighbor] == depth - 1:
                    continue  # don't immmediately go back to parent. 
                    # that's why i didn't choose -1 as the special value, in case depth==0.
                back_depth = dfs(neighbor, depth + 1)
                if back_depth <= depth:
                    connections.discard(tuple(sorted((node, neighbor))))
                min_back_depth = min(min_back_depth, back_depth)
            rank[node] = n  # this line is not necessary. see the "brain teaser" section below
            return min_back_depth
            
        dfs(0, 0)  # since this is a connected graph, we don't have to loop over all nodes.
        return list(connections)

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

Longest Palindromic Substring

• 遍历元素 逐一判断 以当前元素为中心回文长度

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

Merge Two Sorted Lists

# 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

53. Maximum Subarray

# 53. Maximum Subarray
# integer array nums, 
# contiguous subarray (containing at least one number)=> largest sum 
class Solution:
    def maxSubArray(self,nums):
        if not nums:
            return 0
        subSum=maxSum=nums[0]
        for num in nums[1:]:
            subSum=max(num,num+subSum)
            maxSum=max(subSum,maxSum)
        return maxSum

Valid Parentheses

# 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 == []   

class Solution:
    # def twoSorted(self,nums1,nums2):
    def findMedianSortedArrays(self, A, B):
        l = len(A) + len(B)
        if l % 2 == 1:
            return self.kth(A, B, l // 2)
        else:
            return (self.kth(A, B, l // 2) + self.kth(A, B, l // 2 - 1)) / 2
    
    def kth(self, a, b, k):
        if not a:
            return b[k]
        if not b:
            return a[k]
        ia, ib = len(a) // 2 , len(b) // 2
        ma, mb = a[ia], b[ib]

        # when k is bigger than the sum of a and b's median indices 
        if ia + ib < k:
            # if a's median is bigger than b's, b's first half doesn't include k
            if ma > mb:
                return self.kth(a, b[ib + 1:], k - ib - 1)
            else:
                return self.kth(a[ia + 1:], b, k - ia - 1)
        # when k is smaller than the sum of a and b's indices
        else:
            # if a's median is bigger than b's, a's second half doesn't include k
            if ma > mb:
                return self.kth(a[:ia], b, k)
            else:
                return self.kth(a, b[:ib], k)