概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。
と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。
ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
Python3で解いています。
前回
ゼロから始めるLeetCode Day76「3. Longest Substring Without Repeating Characters」A
今はTop 100 Liked QuestionsのMediumを優先的に解いています。
Easyは全て解いたので気になる方は目次の方へどうぞ。
Twitterやってます。
技術ブログ始めました！！
技術はLeetCode、Django、Nuxt、あたりについて書くと思います。こちらの方が更新は早いので、よければブクマよろしくお願いいたします！
問題
1502. Can Make Arithmetic Progression From Sequence
難易度はEasy。
最近追加された新しめの問題です。
Easyっぽくない問題なので是非解いてみてください。
問題としては、数の配列arrが与えられた時、連続する2つの要素間の差が同じであれば，数列は算術進行と呼ばれます。
配列を再編成して算術進行を形成できる場合はtrueを返し,そうでない場合はfalseを返してください。
Example 1:
Input: arr = [3,5,1]
Output: true
Explanation: We can reorder the elements as [1,3,5] or [5,3,1] with differences 2 and -2 respectively, between each consecutive elements.Example 2:
Input: arr = [1,2,4]
Output: false
Explanation: There is no way to reorder the elements to obtain an arithmetic progression.
解法
class Solution:
def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
arr.sort()
length = len(arr)
if length==2:
return True
difference = arr[1] - arr[0]
for i in range(1, length):
if arr[i] - arr[i - 1] != difference:
return False
return True
# Runtime: 32 ms, faster than 100.00% of Python3 online submissions for Can Make Arithmetic Progression From Sequence.
# Memory Usage: 13.9 MB, less than 100.00% of Python3 online submissions for Can Make Arithmetic Progression From Sequence.
新しい問題でかつEasyなので両方100%の解答が出来ました。
最初に配列をソートします。
配列の長さが2の時のみ除外し、それ以外の場合は値の差をとったdifferenceとそれぞれのfor文で回した時の内容が異なる場合にはFalseを、それ以外の場合はTrueを返します。
今回はここまで。お疲れ様でした。