Вопрос:
Ссылка: https://leetcode.com/problems/check-if-it-is-a-straight-line/
Вам дан массив coordinates
, coordinates[i] = [x, y]
, где [x, y]
представляет собой координату точки. Проверьте, образуют ли эти точки прямую линию в плоскости XY.
Пример 1:
Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]] Output: true
Пример 2:
Input: coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]] Output: false
Ограничения:
2 <= coordinates.length <= 1000
coordinates[i].length == 2
-10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4
coordinates
не содержит повторяющихся точек.
Решение:
Подход:
Дело в том, что если мы возьмем точки p1(x, y), p2(x1, y1), p3(x3, y3), наклоны любых двух пар одинаковы, то точки p1, p2, p3 лежат на одной прямой.
наклон от p1 и p2 равен y — y1 / x — x1
наклон от p2 и p3 равен y2 — y1 / x2 — x1
если эти два наклона равны, то p1, p2, p3 лежат на одной прямой .
Код:
class Solution { public boolean onLine(int[] p1, int[] p2, int[] p3){ int x = p1[0], y = p1[1], x1 = p2[0], y1 = p2[1], x2 = p3[0], y2 = p3[1]; return ((y - y1) * (x2 - x1) == (y2 - y1) * (x - x1)); } public boolean checkStraightLine(int[][] coordinates) { for(int i=2;i<coordinates.length;i++){ if(!onLine(coordinates[i], coordinates[0], coordinates[1])) return false; } return true; } }
Я думаю, что код здесь довольно ясен. Пожалуйста, прокомментируйте, если вы не поняли какую-либо часть кода.
Временная сложность: O(N)
Космическая сложность: O(1)
Заключение:
Надеюсь, что решение окажется полезным и вам, ребята, понравилось. Давайте обсудим новые подходы. Пожалуйста, прокомментируйте, если у вас есть какие-либо предложения или какие-либо сомнения.
Удачного кодирования.