はじめに
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:
Example 2:
Constraints:
2 <= coordinates.length <= 1000coordinates[i].length == 2-10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4coordinatescontains 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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#(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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
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, 英語でのコメント
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#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 |
解答1と同じ内容です。どのように解くかを英語でコメントしました。
実際の面接では入力や出力、入力のデータサイズ、解法について英語でやりとりしながら進めていけるようにしたいです。
まずは、英語でコメントを書き、次回解くときには英語で話しながら解けるようになりたいです。
補足・参考・感想
参考
前：1290. Convert Binary Number in a Linked List to Integer
コメント