Blog Feed – Page 30 – 步步发财

Heaters – Python 3 ( Week 14 – 07)

 class Solution:
    """
    @param houses: positions of houses
    @param heaters: positions of heaters
    @return: the minimum radius standard of heaters
    """
    def findRadius(self, houses, heaters):
        # Write your code here
        houses = sorted(houses)
        heaters = sorted(heaters)
        start = 0
        end = houses[-1] - houses[0]
        
        # O(log(end))*O(n+m)
        while start + 1 < end:
            mid = start + (end - start) // 2
            if self.check(mid, houses, heaters):
                end = mid
            else:
                start = mid
        if self.check(start, houses, heaters):
            return start
        return end
        
    def check(self, mid, houses, heaters):
        now_heater = 0
        for i  in range(len(houses)):
            while now_heater < len(heaters) and abs(houses[i] - heaters[now_heater]) > mid:
                now_heater += 1
            if now_heater == len(heaters):
                return False
        return True

Time O(log(end)*(n+m)). Space O(logend).

Topological Sorting – Python 3 (Week 14 – 06)

Solution 1 BFS

"""
Definition for a Directed graph node
class DirectedGraphNode:
    def __init__(self, x):
        self.label = x
        self.neighbors = []
"""


class Solution:
    """
    @param: graph: A list of Directed graph node
    @return: Any topological order for the given graph.
    """
    def topSort(self, graph):
        # write your code here
        node_in_degree = self.get_in_degree(graph)
        
        queue = collections.deque([node for node in graph if node_in_degree[node] == 0])
        torder = []
        while queue:
            cur_node = queue.popleft()
            torder.append(cur_node)
            for neighbor in cur_node.neighbors:
                node_in_degree[neighbor] -= 1
                if node_in_degree[neighbor] == 0:
                    queue.append(neighbor)
                    
        if len(torder) != len(graph):
            return[]
        
        return torder
        

        
    def get_in_degree(self, graph):
        node_in_degree = {x: 0 for x in graph}
        for node in graph:
            for neighbor in node.neighbors:
                node_in_degree[neighbor] += 1
        return node_in_degree

Time O(n^2). Space O(n).

Knight Shortest Path – Python 3 (Week 14 – 05）

"""
Definition for a point.
class Point:
    def __init__(self, a=0, b=0):
        self.x = a
        self.y = b
"""

class Solution:
    """
    @param grid: a chessboard included 0 (false) and 1 (true)
    @param source: a point
    @param destination: a point
    @return: the shortest path 
    """

    def shortestPath(self, grid, source, destination):
        # write your code here
        DIRECTIONS = [(-2, -1), (-2, 1), (-1, 2), (1, 2),(2, 1), (2, -1), (1, -2), (-1, -2)]
        queue = collections.deque([(source.x, source.y)])
        distance = {(source.x, source.y): 0}
        while queue:
            x, y = queue.popleft()
            if (x, y) == (destination.x, destination.y):
                    return distance[(x, y)]
            for dx, dy in DIRECTIONS:
                next_x, next_y = x + dx, y + dy
                if (next_x, next_y) in distance:
                    continue 
                if self.is_not_valid(next_x, next_y, grid):
                    continue
                distance[(next_x, next_y)] = distance[(x, y)] + 1
                queue.append((next_x, next_y))
          
        return -1
        
    def is_not_valid(self, x, y, grid):
        n, m = len(grid), len(grid[0])
        if x < 0 or x >= n or y < 0 or y >= m:
            return True
        return grid[x][y]

Time, Space O(nm).

Number of Islands – Python 3 (Week 14 – 04)

 class Solution:
    """
    @param grid: a boolean 2D matrix
    @return: an integer
    """
    def numIslands(self, grid):
        # write your code here
        if not grid or not grid[0]:
            return 0
        
        islands = 0
        visited = set()
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] and (i, j) not in visited:
                    self.bfs(grid, i, j, visited)
                    islands += 1
        return islands            
                    
                    
                    
    
    def bfs(self, grid, x, y, visited):
        queue = collections.deque([(x, y)])
        visited.add((x, y))
        while queue:
            x, y = queue.popleft()
            for delta_x, delta_y in [(1, 0), (0, -1), (-1, 0), (0, 1)]:
                next_x = x + delta_x
                next_y = y + delta_y
                if not self.is_valid(grid, next_x, next_y, visited):
                    continue
                queue.append((next_x, next_y))
                visited.add((next_x, next_y))
    
    def is_valid(self,grid, next_x, next_y, visited):
        n, m = len(grid), len(grid[0])
        if not (0 <= next_x < n and 0 <= next_y < m):
            return False
        if (next_x, next_y) in visited:
            return False
        return grid[next_x][next_y]

Time, Space O(n). n is number of grids

Word Ladder – Python 3 (Week 14 – 03)

Solution 1 分层

class Solution:
    """
    @param: start: a string
    @param: end: a string
    @param: dict: a set of string
    @return: An integer
    """
    def ladderLength(self, start, end, dict):
        # write your code here
        dict.add(end)
        queue = collections.deque([start])
        visited = set([start])
        
        distance = 0
        while queue:
            distance += 1
            for i in range(len(queue)):
                word = queue.popleft()
                if word == end:
                    return distance
                
                for next_word in self.get_next_words(word):
                    if next_word not in dict or next_word in visited:
                        continue
                    queue.append(next_word)
                    visited.add(next_word)
            
        return 0
        
    # O(26 * L^2) : not forget the complexity of word[:i]
    # L is the length of word    
    def get_next_words(self, word):
        words = [] 
        for i in range(len(word)):
            left, right = word[:i], word[i+1:]
            for char in 'abcdefghijklmnopqrstuvwxyz':
                if char == word[i]:
                    continue
                words.append(left + char + right)
        return words

Time O(n*l + l^2). Space O(n*l). n is total number of words. l is the max length of word.

Solution 2 不分层

class Solution:
    """
    @param: start: a string
    @param: end: a string
    @param: dict: a set of string
    @return: An integer
    """
    def ladderLength(self, start, end, dict):
        # write your code here
        dict.add(end)
        queue = collections.deque([start])
        
        distance = {start: 1}

        while queue:
            word = queue.popleft()
            if word == end:
                return distance[word]
                
            for next_word in self.get_next_words(word):
                if next_word in distance or next_word not in dict:
                    continue
                queue.append(next_word)
                distance[next_word] = distance[word] + 1
                
            
        return 0
        
    # O(26 * L^2) : not forget the complexity of word[:i]
    # L is the length of word    
    def get_next_words(self, word):
        words = [] 
        for i in range(len(word)):
            left, right = word[:i], word[i+1:]
            for char in 'abcdefghijklmnopqrstuvwxyz':
                if char == word[i]:
                    continue
                words.append(left + char + right)
        return words

Time O(n*l + l^2). Space O(n*l). n is total number of words. l is the max length of word.

Solution 3 Bidirectional Breadth First Search

class Solution:
    """
    @param: start: a string
    @param: end: a string
    @param: dict: a set of string
    @return: An integer
    """
    def ladderLength(self, start, end, dict):
        # write your code here
        dict.add(end)
        queue1, queue2 = collections.deque([start]), collections.deque([end])
        visited1, visited2 = set([start]), set([end])
        distance = 1

        while queue1 or queue2:
            
            distance += 1
            for _ in range(len(queue1)):
                word = queue1.popleft()
                for next_word in self.get_next_words(word):
                    if next_word not in dict or next_word in visited1:  
                        continue
                    if next_word in visited2: 
                        return distance
                    visited1.add(next_word)
                    queue1.append(next_word)

            distance += 1
            for _ in range(len(queue2)):
                word = queue2.popleft()
                for next_word in self.get_next_words(word):
                    if next_word not in dict or next_word in visited2:  
                        continue
                    if next_word in visited1:  
                        return distance
                    visited2.add(next_word)
                    queue2.append(next_word)
    
        return 0
        
        
        
   
        
    # O(26 * L^2) : not forget the complexity of word[:i]
    # L is the length of word    
    def get_next_words(self, word):
        words = [] 
        for i in range(len(word)):
            left, right = word[:i], word[i+1:]
            for char in 'abcdefghijklmnopqrstuvwxyz':
                if char == word[i]:
                    continue
                words.append(left + char + right)
        return words

Time O(n*l + l^2). Space O(n*l). n is total number of words. l is the max length of word.

Clone Graph – Python 3 (Week 14 – 02)

"""
# Definition for a Node.
class Node:
    def __init__(self, val, neighbors):
        self.val = val
        self.neighbors = neighbors
"""

class Solution:

    def cloneGraph(self, node: 'Node') -> 'Node':
        root = node
        if not node:
            return root
        
        #get all nodes
        nodes = self.getNodes(node)
        
        #creat corresponding nodes
        mapping = {}
        for node in nodes:
            mapping[node] = Node(node.val, [])
            
        
        #copy neighbors
        for node in nodes:
            #mapping[node]
            for neighbor in node.neighbors:
                new_neighbor = mapping[neighbor]
                mapping[node].neighbors.append(new_neighbor)
                
        return mapping[root] 
        
    def getNodes(self, node):
        results = {node}
        queue = collections.deque([node])
        
        while queue:
            cur = queue.popleft()
            for neighbor in cur.neighbors:
                if neighbor not in results:
                    results.add(neighbor)
                    queue.append(neighbor)
        return results

Time O(n +m). Space O(n). n is number of nodes, m is number of edges.

Binary Tree Level Order Traversal – Python 3 (Week 14 – 01)

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if root is None:
            return []
            
        queue = collections.deque([root])
        result = []
        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level)
        return result

Time, Space: O(n).

Rotate String II – Python 3 (Week 13 – 12)

Solution 1

class Solution:
    """
    @param str: An array of char
    @param left: a left offset
    @param right: a right offset
    @return: return a rotate string
    """
    def RotateString2(self, s, left, right):
        # write your code here
        if not s:
            return ''
        result = ''
        
        n = len(s)
        offset = (left - right) % n
        #if left - right < 0:  right offset x
        #x % n = (x % n) + n in python
        result = s[offset : ] + s[ : offset]
    
        return result

Time O(n). Space O(n).

Subarray Sum Closest – Python 3 (Week 13 – 11)

class Solution:
    """
    @param: nums: A list of integers
    @return: A list of integers includes the index of the first number and the index of the last number
    """
    def subarraySumClosest(self, nums):
        
        # write your code here
        if not nums:
            return []
            
        nowsum = 0
        sumindex = [[0, -1]]
        for i in range(len(nums)):
            nowsum += nums[i]
            sumindex.append((nowsum, i))
        
        sumindex.sort(key=lambda x : x[0])
        
        dis = float('inf')
        start, end = 0, 0
        
        for i in range(len(sumindex) - 1):
           if sumindex[i + 1][0] - sumindex[i][0] < dis:
                start = sumindex[i + 1][1]
                end = sumindex[i][1]
                dis = sumindex[i + 1][0] - sumindex[i][0]
                
        if start == end:
            return [start, end]
        elif start < end:
            return [start + 1, end]
        else:
            return [end + 1, start]

Time O(nlogn). Space O(n).

Subarray Sum – Python 3 (Week 13 – 10)

class Solution:
    """
    @param nums: A list of integers
    @return: A list of integers includes the index of the first number and the index of the last number
    """
    def subarraySum(self, nums):
        # write your code here
        
        if not nums:
            return []
        prefixsum = {0: -1}
        nowsum = 0
        
        for i in range(len(nums)):
            nowsum += nums[i]
            if nowsum in prefixsum:
                return [prefixsum[nowsum] + 1, i]
            prefixsum[nowsum] = i

            
        return[]

Time O(n). Space O(1).