【LeetCode】1007. Minimum Domino Rotations For Equal Row解題報告(Python)

作者:負雪明ろうそくid:fuxuemingzhu個人ブログ:http://fuxuemingzhu.cn/
目次

タイトル説明

テーマ大意

解題方法

を繰り返します

日付

タイトルアドレス:https://leetcode.com/problems/minimum-domino-rotations-for-equal-row/
タイトルの説明
In a row of dominoes, A[i] and B[i] represent the top and bottom halves of the i -th domino. (A domino is a tile with two numbers from 1 to 6 - one on each half of the tile.)
We may rotate the i -th domino, so that A[i] and B[i] swap values.
Return the minimum number of rotations so that all the values in A are the same, or all the values in B are the same.
If it cannot be done, return -1 .
Example 1:

Input: A = [2,1,2,4,2,2], B = [5,2,6,2,3,2]
Output: 2
Explanation: 
The first figure represents the dominoes as given by A and B: before we do any rotations.
If we rotate the second and fourth dominoes, we can make every value in the top row equal to 2, as indicated by the second figure.

Example 2:

Input: A = [3,5,1,2,3], B = [3,6,3,3,4]
Output: -1
Explanation: 
In this case, it is not possible to rotate the dominoes to make one row of values equal.

Note:

1 <= A[i], B[i] <= 6

2 <= A.length == B.length <= 20000

テーマの大意
ドミノの骨牌が並んでいて、A、Bはそれぞれ各札の表裏を表しています.今、その中の一部の骨牌を反転させて、表裏を合わせて、AかBに全く同じ点数を出すことができますか?できれば、最も少ない反転回数を返す必要があります.できない場合は-1に戻る必要があります.
解題方法
一度遍歴する
私たちはこの問題を分析する必要があります:まずA、Bの両面の数字を統計して、もし最も多い点数の札の個数が現れたら、すべての札が少なくとも1面がこの数字であることを保証する必要があります.この時、両面がこの数字であれば、反転しなくてもいいです.
したがって、
両面が等しい場合は、最も多くの数字targetが表示されます.反転する必要はありません.
この面に反転した回数をそれぞれ2つの数字で表す必要があります.一方だけがtargetに等しい場合は、他方に反転する回数+1とする.
いつでも、このカードの表裏に最も多くの数字が現れない限り、必ず-1に戻ります.
最終的には、2つの方向が反転した回数の最小値を返すだけです.
なぜ統計だけで最も多くの数字が現れるのか、なぜ2番目に多くの回数が現れるのはチャンスがないのかについて議論します.
1.最も多くの数字が現れる回数2.最も多くの回数=長さが現れる場合、このとき第2の回数がNに等しい場合、両者の効果は同じであり、第2の回数がNより小さい場合、不可能である.3.最も多く出現した回数>Nであれば、このとき必ずあるカードの表裏が最も多く出現します.このとき2番目に多い数字はチャンスがありません.
つまり、最も多くの数字が出ていると判断するだけです.
Pythonコードは以下の通りです.

class Solution(object):
    def minDominoRotations(self, A, B):
        """
        :type A: List[int]
        :type B: List[int]
        :rtype: int
        """
        N = len(A)
        count = collections.Counter(A + B)
        if count.most_common(1)[0][1] < N:
            return -1
        target = count.most_common(1)[0][0]
        a_swap = 0
        b_swap = 0
        for i in range(N):
            if A[i] == B[i]:
                if A[i] == target:
                    continue
                else:
                    return -1
            elif A[i] == target:
                b_swap += 1
            elif B[i] == target:
                a_swap += 1
            else:
                return -1
        return min(a_swap, b_swap)

日付
2019年3月10日-週間試合は第1ページに入った!