概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインでだそうです。
その対策としてLeetCodeなるサイトで対策を行うようです。
※LeetCodeとは
本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトです。
せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていきます。
未経験のエンジニアなので、基本的に簡単なもの（easyでacceptanceが高い順）から解いていきます。
問題
2475. Number of Unequal Triplets in Array
0から始まるインデックスを持つ正の整数の配列 nums が与えられる。
この配列の中から、以下の条件を満たす3つのインデックスの組 (i,j,k) の数を出力する。
0 <= i < j < k < nums.length-
nums[i],nums[j],nums[k]は互いに異なる -
nums[i] != nums[j],nums[i] != nums[k],nums[j] != nums[k]がすべて成り立つ必要がある。
例1:
入力: nums = [4,4,2,4,3]
出力: 3
説明:
次の三つ組は条件を満たす
・(0, 2, 4) because 4 != 2 != 3
・(1, 2, 4) because 4 != 2 != 3
・(2, 3, 4) because 2 != 4 != 3
三つ組が3つあるので、3を返す。
例2:
入力: nums = [1,1,1,1,1]
出力: 0
説明:
条件を満たす三つ組はないので、0を返す。
制約条件:
3 <= nums.length <= 100
1 <= nums[i] <= 1000
解法
class Solution:
def smallestEqual(self, nums: List[int]) -> int:
n = len (nums)
count = 0
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
if nums[i] != nums[j] and nums[i] != nums[k] and nums[j] != nums[k]:
count += 1
return count
初期化と準備
n = len(nums)
count = 0
n = len(nums)
入力として与えられたリストnumsの要素の数を取得し、その値を変数 n に格納する。
リストの長さは、ループの範囲を決定するために使われる。
count = 0
条件を満たす組の数を数えるためのカウンター変数。
探索と条件チェック
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
if nums[i] != nums[j] and nums[i] != nums[k] and nums[j] != nums[k]:
count += 1
return count
この部分では、まず3つの入れ子になったループを使って、リスト内のすべての可能な3つの要素の組み合わせを順番に選び出す。
例
入力: nums = [4,4,2,4,3]
| インデックス(i, j, k) | 値 (nums[i], nums[j], nums[k]) | 条件 |
|---|---|---|
| (0, 1, 2) | (4, 4, 2) | いいえ (4 と 4 が同じ) |
| (0, 1, 3) | (4, 4, 4) | いいえ (4 と 4 が同じ) |
| (0, 1, 4) | (4, 4, 3) | いいえ (4 と 4 が同じ) |
| (0, 2, 3) | (4, 2, 4) | いいえ (4 と 4 が同じ) |
| (0, 2, 4) | (4, 2, 3) | はい (4 != 2 != 3)→count=1 |
| (1, 2, 3) | (4, 2, 4) | いいえ (4 と 4 が同じ) |
| (1, 2, 4) | (4, 2, 3) | はい (4 != 2 != 3)→count=2 |
| (1, 3, 4) | (4, 4, 3) | いいえ (4 と 4 が同じ) |
| (2, 3, 4) | (2, 4, 3) | はい (2 != 4 != 3)→count=3 |
このループが終了すると結果は、count＝３となり、これが関数の戻り値となる。
別解
for文でネストしすぎで、注意を受けたのでネストしないやり方を考えてみる。
import itertools
class Solution:
def unequalTriplets(self, nums: List[int]) -> int:
count = 0
for triplet in itertools.combinations(nums, 3):
num1, num2, num3 = triplet
## if num1 != num2 and num1 != num3 and num2 != num3:
## count += 1
## ↑は条件分岐がわかりにくいので、下記に修正した
if len(set(triplet)) == 3:
count += 1
return count
for triplet in itertools.combinations(nums, 3):
「itertools.combinations()」で重複なしのすべての組み合わせを生成するイテレータを返す。
例
入力: nums = [4,4,2,4,3]
| triplet 4, 4, 2 | num1 != num2 and num1 != num3 and num2 != num3 | count |
|---|---|---|
| (4, 4, 2) | False | 0 |
| (4, 4, 4) | False | 0 |
| (4, 4, 3) | False | 0 |
| (4, 2, 4) | False | 0 |
| (4, 2, 3) | True | 1 |
| (4, 4, 3) | False | 1 |
| (4, 2, 4) | False | 1 |
| (4, 2, 3) | True | 2 |
| (4, 4, 3) | False | 2 |
| (2, 4, 3) | True | 3 |
countは3となり上記と同様に出力される。
Discussion