liyunrui

class Solution:
    def jump(self, nums: List[int]) -> int:
        """
        Greedy Approach
        
        To determine Greedy strategy:
            1.What's our locally optimal solution at each step(index)?
                1.1. if maxi step we can jump befor index i is less than current index i, we need one more jump, and we choose longest jump we can do to minimize the number of jump.
                1.2. keep track max position the one could reach starting from the current index i or before it as longest jump when we needed
            2.How do determine our global solution? 

liyunrui

class Solution:
    def findCheapestPrice(self, n, flights, src, dst, k):
        """
        Approach-Dijkstra's algorithm
        
        We can model this problem as graph problem and use shortest path algorithm to solve it.
        
        Problem formulation:
            Given a directed weighted graph with n nodes, find the shortest path between src (starting node) and dst (ending node) with up to pass k nodes.
        

liyunrui

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        """
        1st approach: BFS + nodes coloring
        
        Graph is already in adjacency list representation
        
        Given n nodes and edge list of undirected graph, to see if nodes in the graph could be colored using two colors so that there are no adjacent nodes with the same color.
        
        seeh hashmap: index is node, corresponding value is color (1: blue, -1: red)

liyunrui

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        """    
        It's all pairs shortest path problems.
        
        Given an undirected and weighted graph with n nodes and path distance threshold, find the city with the smallest number of cities.
        
        Step1: We can simply use Floyd-Warshall algorithm to find the minium distance any two cities.(we need shortest path between any two nodes ih the graph)
        Step2: Calculate number for each city that this city can reach satisfying distance threshold
        Step3: Return city with fewest number from itself to others city and wi

liyunrui

class Solution:
    def treeDiameter(self, edges: List[List[int]]) -> int:
        """
        The problem is to calculate diameter of tree, given a graph with tree characteristics. 
        
        Note:
            1. The path with same diameter is not unique.
            2. The diameter of a tree is the longest length of a path between two nodes.

            

liyunrui

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        """
        BFS for binary tree vs BFS for graph 

liyunrui

class UnionFindSet:
    def __init__(self, n):
        #Initially, all elements are single element subsets.
        self._parents = [node for node in range(n)]
        # it's like height of tree but it's not always equal to height because path compression technique.
        self._ranks = [1 for i in range(n)]
    
    def find(self, u):
        """
        The find method with path compression, return root of node u.

liyunrui

class UnionFindSet:
    def __init__(self, n):
        self._parents = [i for i in range(n)]
        self._ranks = [1 for _ in range(n)]
    
    def find(self, u):
        while u != self._parents[u]:
            self._parents[u] = self._parents[self._parents[u]]
            u = self._parents[u]
        return u

liyunrui

class Solution:
    def minimumCost(self, N: int, connections: List[List[int]]) -> int:
        """
        Problem formulation:
            We could formulate this problem into minimum spanning tree problem. So, our goal turn to if it's possble to construct minimum spanning tree given an undirected graph. If yes, return weight. Otherwise, return -1.

        Thought process:
            We use Prim's algorithm
                Step 0: build the graph adjacency list.
                Step 1: we can choos any arbitrary node as starting node with zero edge. Put the pair into the priority queue. (Here, we take first node as starting node)

liyunrui

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        """
        
        Thought process:
            1. we use backtracking to generate all possible pathes from node 0 to node n-1
            
        Time complexity analysis:
            Except the starting and ending node, each node could be included in the path or not. In an exntrem case, there're goingt to 2^(n-1) pathes from node 0 to node n-1 .So, time complexity could roughly be 2 raise to power of n.