23.05.19 Today’s Leetcode

785. Is Graph Bipartite? (medium)

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        visited = [0] * n
        def dfs(cur, flip):
            if visited[cur] != 0:
                return flip == visited[cur]
            visited[cur] = flip
            for node in graph[cur]:
                temp = dfs(node, -flip)
                if not temp:
                    return False
            return True

        for i in range(n):
            if visited[i] != 0:
                continue
            temp = dfs(i, 1)
            if not temp:
                return False

        return True

786. K-th Smallest Prime Fraction (medium)

class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
        n = len(arr)
        heap = []
        for i in range(n):
            for j in range(i + 1, n):
                heappush(heap, (arr[i] / arr[j], arr[i], arr[j]))
        
        res = []
        for i in range(k):
            res = heappop(heap)
        print(res)
        return [res[1], res[2]]

class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
        def con(value):
            nb_smallest_fraction = 0
            numer = arr[0]
            denom = arr[-1]

            slow = 0
            for fast in range(1, len(arr)):
                while slow < fast and arr[slow] / arr[fast] < value:
                    if arr[slow] / arr[fast] > numer / denom:
                        numer, denom = arr[slow], arr[fast]

                    slow += 1

                nb_smallest_fraction += slow

            return nb_smallest_fraction, numer, denom

        l = arr[0] / arr[-1]
        r = 1

        while l < r:
            m = (l+r) / 2

            count, numer, denom = con(m)

            if count == k:
                return [numer, denom]

            if count > k:
                r = m
            else:
                l = m
        

788. Rotated Digits (medium)

class Solution:
    def rotatedDigits(self, N: int) -> int:
        count = 0
        for d in range(1, N+1):
            d = str(d)
            if '3' in d or '4' in d or '7' in d:
                continue
            if '2' in d or '5' in d or '6' in d or '9' in d:
                count +=1
        return count