【LeetCode】1232. Check If It Is a Straight Line 解答・解説【Python】

はじめに
問題
1. 原文
2. 内容
方針
解答
補足・参考・感想

はじめに

LeetCodeの問題を解答します。

なるべく、問題の和訳と詳細なコメントを書いています。

余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。

様々なカテゴリの問題をランダムにあたる方法も良いですが、

二分探索、連結リストなど、テーマを絞って集中的に解いた方が練習しやすい方は以下の記事が有用です。

テーマごとに問題を分類しました。

LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。

また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。

はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。

解答前に知っておくと役に立つかもしれない情報

問題

原文

You are given an array coordinates, coordinates[i] = [x, y], where [x, y] represents the coordinate of a point. Check if these points make a straight line in the XY plane.

Example 1:

Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]] Output: true

1
2

Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
Output: true

Example 2:

Input: coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]] Output: false

1
2

Input: coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]
Output: false

Constraints:

2 <= coordinates.length <= 1000

coordinates[i].length == 2

-10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4

coordinates contains no duplicate point.

内容

座標の配列coordinatesが与えられます。coordinates[i]は[x,y]であり、x,y座標を意味します。各点が直線状に並んでいるか確かめてください。

制約

・coordinatesの長さは2~1000

・coordinates[i]にの長さは2

・x,yは、-10^4~10^4の範囲内

・coordinatesは同じ点を持たない

※正しくない可能性があります。

方針

・直線状に並んでいる場合は、2点間の傾きは一致するので、各点に対して確かめる

解答

解答1：Python

#(y-y1)/(y2-y1) = (x-x1)/(x2-x1)　→　(y-y1)*(x2-x1) = (x-x1)*(y2-y1)
class Solution:
    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
　　　　 #1つ目の点を保持
        x1,y1 = coordinates[0]
　　　　 #2つ目の点を保持
        x2,y2 = coordinates[1]
　　　　 #3つ目の点から最後の点まで処理
        for i in range(2,len(coordinates)):
　　　　 　　#i番目の点を保持
            x, y = coordinates[i]
　　　　 　　#i番目の点と1,2番目の点の座標を使って直線状に並んでいるか確認。
            if (y-y1)*(x2-x1) != (x-x1)*(y2-y1):
                return False
　　　　 #最後の点まで直線状に並んでいたならTrueを返す
        return True

#(y-y1)/(y2-y1) = (x-x1)/(x2-x1)　→　(y-y1)*(x2-x1) = (x-x1)*(y2-y1)

class Solution:

def checkStraightLine(self, coordinates: List[List[int]]) -> bool:

　　　　 #1つ目の点を保持

x1,y1 = coordinates[0]

　　　　 #2つ目の点を保持

x2,y2 = coordinates[1]

　　　　 #3つ目の点から最後の点まで処理

for i in range(2,len(coordinates)):

　　　　　　#i番目の点を保持

x, y = coordinates[i]

　　　　　　#i番目の点と1,2番目の点の座標を使って直線状に並んでいるか確認。

if (y-y1)*(x2-x1) != (x-x1)*(y2-y1):

return False

　　　　 #最後の点まで直線状に並んでいたならTrueを返す

return True

2点間が同一直線上にあるかを判定する式を使えます。

(y-y1)/(y2-y1) = (x-x1)/(x2-x1)

ただし、点によっては分母が0になる場合があり、その時の処理を書く必要があるので、

こちら↓の方を使いました。

(y-y1)*(x2-x1) = (x-x1)*(y2-y1)

x1,y1と、x2,y2は1,2個目の点、

x,yは3点目以降の点をfor文で走査しながら、式に当てはめていきます。

3点目以降の点が1つでも上記の式に当てはまらなければその時点でFalseを返します。

全て上記の式に当てはまり、for文が最後まで走査できたらTrueを返します。

解答2：Python

class Solution:
    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
        slope = 0
        for i in range(len(coordinates)-1):
            x1,y1 = coordinates[i]
            x2,y2 = coordinates[i+1]
            if x2-x1==0:
                m = float('inf')
            else:
                m=(y2-y1)/(x2-x1)
            if slope==0:
                slope=m
            else:
                if slope!=m:
                    return False
        return True

class Solution:

def checkStraightLine(self, coordinates: List[List[int]]) -> bool:

slope = 0

for i in range(len(coordinates)-1):

x1,y1 = coordinates[i]

x2,y2 = coordinates[i+1]

if x2-x1==0:

m = float('inf')

else:

m=(y2-y1)/(x2-x1)

if slope==0:

slope=m

else:

if slope!=m:

return False

return True

こちらは、1つ目の式を使ったときの解答です。

※(y-y1)/(y2-y1) = (x-x1)/(x2-x1)

分母が0の時の処理を書いています。

場合分けが少し面倒に感じます。

解答3：Python, 英語でのコメント

#We can check if two point are on the line using following formula.
#(y-y1)/(y2-y1) = (x-x1)/(x2-x1)
#However we need to handle the case where the denominator is 0.
#Therefore, insted of above formula we will use following formula .
#(y-y1)*(x2-x1) = (x-x1)*(y2-y1)
#x and y are the coordinates of each point starting from the third element onwards
class Solution:
    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
        #x1, y1 have first element
        #x2, y2 hvae second element
        x1,y1 = coordinates[0]
        x2,y2 = coordinates[1]
        
        #Travers coordinates from third element onwards
        for i in range(2,len(coordinates)):
            #x,y has i-th elements
            x, y = coordinates[i]
            #Check i-th point is on first point to second point line
            if (y-y1)*(x2-x1) != (x-x1)*(y2-y1):
                #If i-th point isn't on line, return False
                return False
        return True