【LeetCode #1007】Minimum Domino Rotations For Equal Row

はじめに

こんにちは．最近，TypeScript を勉強中で，LeetCode の問題も時々 TypeScript で解いてみたりしています<3<3
さて，今日は #1007 の問題です．

問題概要

与えられた配列 tops と bottoms に対して，いくつかの裏表をひっくり返して，tops または bottoms どちらかを全て同じ値にする．
その時のひっくり返す最小回数を答える．もし不可能な場合は -1 を返す．

カテゴリ

問題難易度：Medium
タグ：Array, Greedy

解法

この問題は，「どちらかの列をすべて同じ値に揃えるために，値 x を揃えるターゲットとしたときどれだけ裏返す必要があるか」を考えるのがポイントです．

tops・bottoms の1つ目の要素 top[0]・bottom[0] を取得する
tops[0]・bottoms[0] それぞれに対して，tops・bottoms 全要素との比較を行う
tops[0] と一致する tops・bottoms 内の要素数をそれぞれカウント
bottoms[0] と一致する tops・bottoms 内の要素数をそれぞれカウント
最小値を返す（ひっくり返す必要のある最小の数）

class Solution:
    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
        def check(x, tops, bottoms):
            bc = 0
            tc = 0
            for i in range(len(tops)):
                if tops[i] != x and bottoms[i] != x:
                    return float('inf')
                if tops[i] == bottoms[i]:
                    continue
                tc += tops[i] == x
                bc += bottoms[i] == x
            return min(tc, bc)
        ans = min(check(tops[0], tops, bottoms), check(bottoms[0], tops, bottoms))
        return ans if ans != float('inf') else -1

もう少し高速にする

もし，tops の1つ目の要素 top と bottoms の1つ目の要素 bottom が同じであれば1度の走査で完了する

class Solution:
    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
        def check(x, tops, bottoms):
            bc = 0
            tc = 0
            for i in range(len(tops)):
                if tops[i] != x and bottoms[i] != x:
                    return float('inf')
                if tops[i] == bottoms[i]:
                    continue
                tc += tops[i] == x
                bc += bottoms[i] == x
            return min(tc, bc)
        res = min(check(tops[0], tops, bottoms), check(bottoms[0], tops, bottoms) if tops[0] != bottoms[0] else float('inf'))
        return res if res != float('inf') else -1

まとめ

今回は #1007 の問題と解法を紹介しました！
この問題は一見比較が多そうに見えますが，実際は tops[0] と bottoms[0] のどちらかが全体を同じ値にするための候補になり得るため，その2つとその他の値との比較で済む問題でした．
パッと見，難しそうでも紐解いてみると意外と簡単な問題が medium には多いですね！
次回もまた daily など解説しようと思います:)

おまけ

TypeScript だとこんな感じです．

function check(x: number, tops: number[], bottoms: number[]): number{
    let tc: number = 0;
    let bc: number = 0;
    for (let i: number = 0; i < tops.length; i++){
        if ((tops[i] !== x) && (bottoms[i] !== x)){
            return Infinity;
        }else if (tops[i] === bottoms[i]){
            continue;
        }
        tc += Number(tops[i] == x);
        bc += Number(bottoms[i] == x);
    }
    return Math.min(tc, bc);
};
function minDominoRotations(tops: number[], bottoms: number[]): number {
    let ans: number = Infinity;
    if (tops[0] == bottoms[0]){
        ans = check(tops[0], tops, bottoms);
    }else {
        ans = Math.min(check(tops[0], tops, bottoms), check(bottoms[0], tops, bottoms));
    }
    if (ans === Infinity){
        return -1;
    }
    return ans;
};