LeetCode Top 50

One problem a day, keep the virus away.

Due to the spreading of the coronavirus, I CANNOT find a job after spending 6 years to purchase my program in CS :(.

So what, let’s LeetCode. One problem a day (rank by frequency), keep the virus away. I will not describe the problem as if you are familiar with the problem, you can recall what the problem is after reading the title of the problem. Enjoy your life and have fun!

1. Two Sum

"""
time complexity: O(n)
space complexity: O(n)
"""
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hist = {}
        for i, num in enumerate(nums):
            if target-num in hist:return [hist[target-num], i]
            hist[num] = i

200. Number of Islands

# time complexity O(V+E)
# space complexity O(E)
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:return 0
        R, C = len(grid), len(grid[0])
        def dfs(i,j):
            grid[i][j] = '0'
            for di, dj in [(0,1),(0,-1),(1,0),(-1,0)]:
                r, c= i+di, j+dj
                if 0<=r<R and 0<=c<C and grid[r][c]=='1':
                    dfs(r,c)
        res = 0
        for i in range(R):
            for j in range(C):
                if grid[i][j]=='1':
                    dfs(i,j)
                    res += 1
        return res

1192. Critical Connections in a Network

class Solution(object):
    def criticalConnections(self, n, connections):
        if not connections:return []
        graph = collections.defaultdict(list)
        for u, v in connections:
            graph[u].append(v)
            graph[v].append(u)
        dfs_num = [None]*n
        dfs_low = [None]*n
        self.num = 0
        def dfs(i, parent):
            # visited, return
            if dfs_num[i] is not None:return
            dfs_num[i] = dfs_low[i] = self.num
            self.num += 1
            for j in graph[i]:
                if dfs_num[j] is None:
                    dfs(j, i)
            dfs_low[i] = min([dfs_low[i]]+[dfs_low[j] for j in graph[i] if j!=parent])
        dfs(0, None)
        res = []
        for u, v in connections:
            if dfs_low[u]>dfs_num[v] or dfs_low[v]>dfs_num[u]:res.append([u,v])
        return res

2. Add Two Numbers

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy_head = ListNode()
        carry = 0
        tail = dummy_head
        while l1 or l2 or carry:
            val = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
            if l1: l1 = l1.next
            if l2: l2 = l2.next
            carry, this_dig = divmod(val, 10)
            tail.next = ListNode(this_dig)
            tail = tail.next
        return dummy_head.next

146. LRU Cache

system design, double linked list, hash map

class Node:
    def __init__(self, key=None, val=None):
        self.key = key
        self.val = val
        self.next = self.prev = None
    
class DLinkedList:
    def __init__(self):
        self.size = 0
        self._nodes = {}
        self.head = self.tail = Node(-1, -1)
        self.head.next = self.tail
        self.tail.prev = self.head
    def pop(self, node=None):
        if node is None:
            node = self.tail.prev
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1
        return node
    def append_left(self, node): 
        self.head.next.prev = node
        node.next = self.head.next
        self.head.next = node
        node.prev = self.head
        self.size += 1
class LRUCache:
def __init__(self, capacity: int):
        self._capacity = capacity
        self.cache = DLinkedList()
        self.nodes = {}
        self.size = 0
    def _update(self, node):
        self.cache.pop(node)
        self.cache.append_left(node)
    def get(self, key: int) -> int:
        if key not in self.nodes:return -1
        self._update(self.nodes[key])
        return self.nodes[key].val
def put(self, key: int, value: int) -> None:
        if self._capacity == 0:return
        if key in self.nodes:
            node = self.nodes[key]
            node.val = value
            self._update(node)
            return
        if self.size == self._capacity:
            node = self.cache.pop()
            del self.nodes[node.key]
            self.size -= 1
        new_node = Node(key, value)
        self.cache.append_left(new_node)
        self.nodes[key] = new_node
        self.size += 1
        
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

42. Trapping Rain Water

# time complexity: O(n)
# space complexity: O(n)
class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height)<=2:return 0
        left = [height[0]]
        for i in range(1, len(height)):
            left.append(max(left[-1], height[i]))
        right = [height[-1]]
        for i in range(len(height)-2, -1, -1):
            right.append(max(right[-1], height[i]))
        right.reverse()
        res = 0
        for i in range(1, len(height)-1):
            this_res = min(left[i-1], right[i+1]) - height[i]
            this_res = max(this_res, 0)
            res += this_res
        return res

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

# time complexity O(n^2)
# space complexity O(n)
class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:return ""
        def helper(i, j):
            while i>=0 and j<len(s) and s[i]==s[j]:
                i -= 1
                j += 1
            return s[i+1:j]
        even = max((helper(i, i+1) for i in range(len(s))), key=len)
        odd = max((helper(i, i) for i in range(len(s))), key=len)
        return max(even, odd, key=len)