LeetCode 2020-11-11: Valid Square

LeetCode daily challenge の問題 Valid Square (medium) の挑戦メモです。

問題の概要

• 与えられた二次元平面上の四点をいい感じに結んだときに正方形が構成できるか否かを判断する

考え方

• これは (0, 1), (1, 0), (2, 1), (1, 2) みたいな正方形も考えなきゃいけないので、結構面倒な問題ですね… 🤔
• ひとまず「ある点から始めて反時計回り (or 時計回り) に点を辿っていく」的な方法を考えてみよう
  1. ある点から、反時計回りの隣に当たる点に向かうベクトル v を求める
  2. その「反時計回りの隣に当たる点」を起点とし、さらに反時計方向に隣の点にある点に向かうベクトルが、v を左に 90° 回転させたものと等しいかをチェックする
  3. 同様に、最後に残った点も似たようなやり方でチェックする
• この方法であれば、四点をいい感じにソートする方法を考えればあとは簡単に実装できそう
  • 四点を int[] の配列に詰めつつ、Comparator.comparingInt((int[] o) -> o[0]).thenComparingInt(o -> o[1]) こんな感じの comparator を用意して、int[] の配列をソートしてみたらいいのかな？
• 実装して submit → wrong answer を挟んで 💦 accept
  • Runtime 3ms で Your runtime beats 7.03 % of java submissions. だった 😫
• int[][] を Arrays.sort(Object[]) でソートするのが明らかにオーバーヘッド大きめなので、代替手段を考えよう
  • ある点を固定して、その点から他の三点に向かうベクトル同士の関係を考えてみよう
  • ある点の隣同士になる点のベクトルは、ちょうど 90° 右 or 左に回転させると重なるはず
  • さらに、ある点から対角上に位置する点は、ある点の隣同士のベクトルを足し合わせたものに重なるはず
  • ある点と他の三点の位置関係を明らかにするのが面倒なので、対角上に位置する点のパターンをすべて試行してみればいいかな？
• というわけで再度実装 → submit → accept 👍
  • めでたく runtime 0ms 達成 🎉

コード

ソートを用いる方法

class Solution {
    static final Comparator<int[]> COMPARATOR = Comparator.comparingInt((int[] o) -> o[0]).thenComparingInt(o -> o[1]);

    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        int[][] array = {p1, p2, p3, p4};
        Arrays.sort(array, COMPARATOR);

        int xd, yd;
        int[] pa = array[0], pb = array[1], pc, pd;

        if (pa[1] > pb[1]) {
            xd = pa[0] - pb[0];
            yd = pa[1] - pb[1];

            int[] t = pa;
            pa = pb;
            pb = t;

            pc = array[2];
            pd = array[3];

        } else {
            xd = pb[0] - pa[0];
            yd = pb[1] - pa[1];

            pc = array[3];
            pd = array[2];
        }

        if (xd == 0 && yd == 0) {
            return false;
        }

        if (pc[0] != pb[0] + yd
                || pc[1] != pb[1] - xd) {
            return false;
        }

        return pd[0] == pa[0] + yd
                && pd[1] == pa[1] - xd;
    }
}

ソートを用いない力技的な方法

class Solution {
    boolean check(int xd2, int yd2, int xd3, int yd3, int xd4, int yd4) {
        return (xd2 == -yd3 && yd2 == xd3 || xd2 == yd3 && yd2 == -xd3)
                && (xd2 + xd3) == xd4 && (yd2 + yd3) == yd4;
    }

    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        int xd12 = p2[0] - p1[0];
        int yd12 = p2[1] - p1[1];
        int xd13 = p3[0] - p1[0];
        int yd13 = p3[1] - p1[1];
        int xd14 = p4[0] - p1[0];
        int yd14 = p4[1] - p1[1];

        if (xd12 == 0 && yd12 == 0
                || xd13 == 0 && yd13 == 0
                || xd14 == 0 && yd14 == 0) {
            return false;
        }

        if (check(xd12, yd12, xd13, yd13, xd14, yd14)) {
            return true;
        }
        if (check(xd13, yd13, xd14, yd14, xd12, yd12)) {
            return true;
        }
        if (check(xd14, yd14, xd12, yd12, xd13, yd13)) {
            return true;
        }

        return false;
    }
}