Page tree
Skip to end of metadata
Go to start of metadata
find_bad_version
def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        if isBadVersion(1):
            return 1

        start = 1
        end = n

        while start <= end:
            mid = (start + end) // 2

            if isBadVersion(mid) == False:
                if isBadVersion(mid + 1) == True:
                    return mid + 1
                else:
                    start = mid + 1
            else:
                if mid - 1 > 0 and isBadVersion(mid - 1) == False:
                    return mid
                else:
                    end = mid - 1
find first and last position
def searchRange(self, nums: List[int], target: int) -> List[int]:
        start = 0
        end = len(nums) - 1

        pos = -1

        while start <= end:
            mid = (start + end) // 2

            if nums[mid] == target:
                pos = mid
                break

            if nums[mid] > target:
                end = mid - 1
            else:
                start = mid + 1

        if pos == -1:
            return [-1, -1]

        start_pos = pos
        end_pos = pos

        start_complete = False
        end_complete = False
        while not start_complete or not end_complete:
            if end_pos + 1 < len(nums) and nums[end_pos + 1] == target:
                end_pos += 1
            else:
                end_complete = True

            if start_pos - 1 >= 0 and nums[start_pos - 1] == target:
                start_pos -= 1
            else:
                start_complete = True

        return [start_pos, end_pos]
완전탐색 : 8464 ms
class Solution:
    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
        graph = {}
        for i in range(1, N + 1):
            graph.setdefault(i, [])
        for node in times:
            graph[node[0]].append([node[1], node[2]])
            
        dist = {node: float('inf') for node in range(1, N + 1)}

        def dfs(node, depth):
            if depth >= dist[node]:
                return
            dist[node] = depth
            for n, w in graph[node]:
                dfs(n, depth + w)

        dfs(K, 0)
        ans = max(dist.values())
        return ans if ans < float('inf') else -1
다익스트라 : 452ms
class Solution:
    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
        graph = collections.defaultdict(dict)
        for i in range(1, N + 1):
            graph[i] = {}

        for v, n, w in times:
            graph[v][n] = w

        infinity = float("inf")
        costs = {}
        for e in graph:
            if e not in costs:
                if e == K:
                    costs[e] = 0
                    for se in graph[e]:
                        costs[se] = graph[e][se]
                else:
                    costs[e] = infinity

        visited = []
        node = self.find_lowest_cost_node(costs, visited)
        while node is not None:
            cost = costs[node]
            neighbors = graph[node]
            for n in neighbors.keys():
                new_cost = cost + neighbors[n]
                if costs[n] > new_cost:
                    costs[n] = new_cost
            visited.append(node)
            node = self.find_lowest_cost_node(costs, visited)

        ans = max(costs.values())
        return ans if ans < float('inf') else -1

    def find_lowest_cost_node(self, costs, visited):
        lowest_cost = float("inf")
        lowest_cost_node = None
        for node in costs:
            cost = costs[node]
            if cost < lowest_cost and node not in visited:
                lowest_cost = cost
                lowest_cost_node = node
        return lowest_cost_node
  • No labels