LeetCode 1232. Check If It Is a Straight Line

プログラミング
Page content

どうも、たくチャレ(@takuchalle)です。

LeetCode 1232Check If It Is a Straight Lineを解きました。

設問

与えられた座標coordinatesが直線状に並んでいるかチェックする問題。

解

愚直な方法として、2点ずつの傾きslopeを求めていけばよさそうです。

まず最初の2点の傾きを求めて、残りの点の傾きと比較して異なる場合はfalseを返すようにしています。0割り算にならないようにxが0の時は極端に大きい値をいれています。

計算量はO(N)で、消費メモリはO(1)です。

class Solution {
   public:
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        const auto n = coordinates.size();

        double y = (coordinates[1][1] - coordinates[0][1]);
        double x = (coordinates[1][0] - coordinates[0][0]);

        double slope = std::numeric_limits<double>::max();
        if (x != 0) {
            slope = y / x;
        }

        for (size_t i = 2; i < n; i++) {
            double y = (coordinates[i - 1][1] - coordinates[i][1]);
            double x = (coordinates[i - 1][0] - coordinates[i][0]);

            double slope2 = std::numeric_limits<double>::max();
            if (x != 0) {
                slope2 = y / x;
            }

            if (slope != slope1) return false;
        }

        return true;
    }
};

また、傾きを求める式を変形すると計算コストの高い割り算を排除することができます。

$$ \frac{(y_1 - y_0)}{(x_1 - x_0)} = \frac{(y_2 - y_1)}{(x_2 - x_1)} $$ $$ (y_1 - y_0)(x_2 - x_1) = (y_2 - y_1)(x_1 - x_0) $$

こちらも、計算量はO(N)で、消費メモリはO(1)です。

class Solution {
   public:
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        const auto n = coordinates.size();

        double delta_y0 = (coordinates[1][1] - coordinates[0][1]);
        double delta_x0 = (coordinates[1][0] - coordinates[0][0]);

        for (size_t i = 2; i < n; i++) {
            double delta_y = (coordinates[i - 1][1] - coordinates[i][1]);
            double delta_x = (coordinates[i - 1][0] - coordinates[i][0]);

            if (delta_y * delta_x0 != delta_y0 * delta_x) return false;
        }

        return true;
    }
};