📚

LeetCoding Challenge Oct. 19: Minimum Domino Rotations For…

2020/10/19に公開

Java

LeetCode

tech

LeetCode October Challenge の 19 日目。

今日の問題は Minimum Domino Rotations For Equal Row。

問題の概要

ドミノの牌を以下の図の上部のように並べ、任意の牌を上下反転 (rotation) をして上もしくは下の行を同じ目で揃える (図の下部の状態) 操作を最小手数で実現し、その手数を解として出力する
- leetcode.com から借用
問題によっては揃えることができないものもあり、その場合は -1 を返す

考え方

この手の問題はビット演算を駆使するのが良さそうな気がするぞ…
まずは、上もしくは下の行を同じ目で揃えられる問題なのかを区別する方法を考えてみよう 🤔
- 目１を 0b10, 目２を 0b100, ... 目６を 0b1000000 とビット値で表現するよ
- 変数 andBits の初期値を 0b1111110 として、左のドミノから右のドミノの順に「ドミノの上の目と下の目のビット値のビット和」を求め、それと andBits の値をビット積にして逐次 andBits を更新してみよう
- この値が 0 になった場合は、同じ目で揃えられない問題であることを意味するよ
これにより、同じ目で揃えられる問題であることが判明した (すなわち andBits > 0 である場合) 場合、さらに andBits の値からどの目が揃えられるのかを Integer.numberOfTrailingZeros() を使って求めることができるね 😮
具体的にどの目が揃えられるのかまでを明らかにできるようになったわけだけど、じゃあ実際に最短何手の上下反転操作で目を揃えられるのかを求める方法を考えてみよう 🤔
- 上・下それぞれについて、各々の目の出現回数を数える頻度表を用意して数え上げよう (揃えられる目・揃えられない目はこのときは気にしないよ)
- 揃えられる目の上・下それぞれの頻度のうち、大きい値を利用するよ
- ドミノの数 - 大きい方の頻度 が、最短手数に相当するね 😆
アルゴリズムを明らかにできたので実装 → submit → 一発 accept 🎉
- Runtime: 4ms で、Your runtime beats 71.97 % of java submissions. らしい。ううむ… 😞
この手の問題は走査方向を前後逆にすると runtime が短くなったりすることがあるので試してみよう
- Runtime: 3ms で Your runtime beats 98.43 % of java submissions. 😇
しかし、ここまでやって beats 100% に到達できないのはなぜなんだ…
- Runtime 2ms のサンプルコード (以下) をみると、結構ナイーブな実装に見える
- うーん、JVM のお気持ちがよくわからない…

コード

class Solution {
    public int minDominoRotations(int[] A, int[] B) {
        if (A.length != B.length) {
            return -1;
        }

        int[] countRowA = new int[7];
        int[] countRowB = new int[7];

        int andBits = 0b111_1110;
        for (int i = A.length - 1; i >= 0; i--) {
            andBits &= (1 << A[i]) | (1 << B[i]);
            if (andBits == 0) {
                return -1;
            }

            countRowA[A[i]]++;
            countRowB[B[i]]++;
        }

        int num = Integer.numberOfTrailingZeros(andBits);
        return A.length - Math.max(countRowA[num], countRowB[num]);
    }
}

問題の概要

考え方

コード

Discussion