目次
解いた問題
leetcode 228. Summary Ranges
重複がなく昇順にソートされたnumsを引数に渡すから、0,1,2のように連続している区間を切り出してリストで返してねって問題。
よくわからなかったので具体例を考えてみた。下記。
# 引数で渡されるもののイメージ
nums = [0, 1, 2, 4, 5, 7]
# 連続していたら"->"で区間を指定、連続してなかったら単体でStrとしてリストに入れる
output = ["0->2", "4->5", 7]
上記のoutputの形で返却すればいいらしい。
学び
- 繰り返し処理以外は重ねても問題ない
-
ifの条件は細かく考えたほうが制御しやすい - リストへの追加は
append
最初に考えた解法
2ポインタ法使って今見ている値とその次の値が連続しているか、すなわちnums[i] == nums[i+1] - 1になっているかを確認すればいいのかなと考えた。
見る箇所が2個と固定されているため、前回やったスライディングウィンドウが使えそうとも思ったがいったん最初に思いついた方法で実装してみることに。
スライディングウィンドウは下記参照。
https://zenn.dev/zenn_mita/articles/e47073eec33966
class Solution:
def summaryRanges(self, nums: List[int]) -> List[str]:
if nums is None:
return []
start_num = nums[0]
window_num = nums[0]
next_num = nums[1]
result = []
i = 1
while i > len(nums):
if next_num == window_num + 1:
output = f"{start_num}->{next_num}"
window_num = next_num
else:
result.add(f"{start_num}")
start_num = next_num
window_num = next_num
i += 1
next_num = nums[i]
return result
もちろん不正解。ひどいな、と自分でも思います。
2ポインタ法ってどうやるんだっけ...
どう条件づけたら分岐がスマートになるか分からず、いったん泥臭く書いてみようと思ったのですが思った以上にうまくいかない。
->の左に格納する数値を保持しながら、次の数値が連続しているかを評価する必要があるが勘所がつかめずコードに落とし込めなかった。
正解
泣く泣く答えを見たら下記のようになった。
class Solution:
def summaryRanges(self, nums: List[int]) -> List[str]:
res = []
if not nums:
return res
start = nums[0]
for i in range(1, len(nums)):
# 連続が切れたら区間を確定
if nums[i] != nums[i - 1] + 1:
if start == nums[i - 1]:
res.append(str(start))
else:
res.append(f"{start}->{nums[i - 1]}")
start = nums[i]
# 最後の区間を処理
if start == nums[-1]:
res.append(str(start))
else:
res.append(f"{start}->{nums[-1]}")
return res
この問題は2ポインタ法ではなく「線形走査」「区間集約」と呼ばれるアルゴリズムを使用しているそう。
線形走査とは、配列を左から右へ一度だけ見るアルゴリズムのことで$O(n)$。
区間集約とは、条件に基づいて値を区間としてまとめるアルゴリズムのこと。
回答を見ると分岐を重ねていたりするので、計算量に直接影響のある繰り返し処理以外は細かくせいぎょするほうがよさそうです。
感想
考え方自体はあってたんだけどなぁ（負け惜しみ
よくよく見るとリストへの追加をappendではなくaddしてたりするのでアルゴリズム以前の問題だったり...
最近昔やったアルゴリズムが抜けていることと、それを中途半端に覚えているため新しいアルゴリズムに適応できないことが課題です。
2025年最後の回答が全く締まらずすっきりしませんが、来年は実績を作る年にするつもりなので、今年以上に力を入れていきます！