leetcode 180週目

2431 ワード

5307.整数をゼロのない2つの和に変換
「ゼロなし整数」は、10進数表示に0を含まない正の整数です.
整数nを与えて、2つの整数からなるリスト[A,B]を返してください.
AとBはいずれもゼロ整数A+B=n問題のないデータであり、少なくとも1つの有効な解決策が保証される.
class Solution(object):
    def getNoZeroIntegers(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        def check(num):
            for i in str(num):
                if i == "0":
                    return False
            return True
        arr = []
        for i in range(n):
            if check(i):
                if check(n-i):
                    return [i,n-i]

5308.または演算の最小反転回数
正の整数a、b、cを3つあげます.
aとbのバイナリ表現をビット反転操作し、a OR b==cをビット単位または演算できる最小反転回数を返すことができます.
「ビット反転動作」とは、1つの数のバイナリ表現のいずれかの単一のビットの1を0または0にして1にすることを意味する.
各ビットを比較すると、cが1であればa、b対応ビットのいずれかを1とし、cが0であればa、b対応ビットを0とする必要があります.
class Solution(object):
    def minFlips(self, a, b, c):
        """
        :type a: int
        :type b: int
        :type c: int
        :rtype: int
        """
        ans = 0
        while a or b or c:
            if c%2==1:
                ans += (a|b)%2 == 0
            else:
                ans += a%2!=0
                ans += b%2!=0
            
            a//=2
            b//=2
            c//=2
        return ans

5309.ネットワークに接続する操作回数
n台のコンピュータをイーサネットケーブルでネットワークに接続し、コンピュータの番号は0からn-1までです.ケーブルはconnectionsで表され、connections[i]=[a,b]はコンピュータaとbを接続している.
ネットワーク内の任意のコンピュータは、ネットワークを介して同じネットワーク内の他の任意のコンピュータに直接または間接的にアクセスすることができる.
このコンピュータネットワークの初期配線connectionsをあげると、任意の2台の直結コンピュータ間のケーブルを抜いて、直結していないコンピュータのペアを接続することができます.すべてのコンピュータを接続するために必要な最小限の操作回数を計算して返してください.不可能な場合は-1を返します.
class Solution(object):
    def makeConnected(self, n, connections):
        """
        :type n: int
        :type connections: List[List[int]]
        :rtype: int
        """
        if len(connections) < n-1:
            return -1
        edge = [[] for i in range(n)]
        for (a,b) in connections:
            edge[a].append(b)
            edge[b].append(a)
        vis = [0]*n
        def dfs(x):
            if vis[x]:
                return 
            vis[x] = 1
            for out in edge[x]:
                dfs(out)

        ans = 0
        for i in range(n):
            if not vis[i]:
                ans += 1
                dfs(i)
        return ans-1