こちらは「Summary Ranges」のPythonによる解答例となっております。この問題は、整数の配列が与えられたとき、連続する数値をまとめて、範囲の形で表現する問題です。
問題
整数の配列 nums が与えられたとき、以下の規則に従って、配列内の数値をまとめて表現します。最終的に、まとめられた数値を文字列のリストとして返します。
- 数値
aが数値bの直後に続く場合、数値aと数値bを “a->b” のような形式でまとめます。 - 数値
aが数値bの直後に続かない場合、数値aを単独で表現します。
解法
この問題は、Pythonのitertoolsモジュールを用いた1つのアプローチがあります。itertools.groupby()関数は、連続する数値をグループ化することができます。また、reモジュールを用いて、正規表現を用いた文字列操作で解決することもできます。
アルゴリズムの概要を以下に述べます。
- itertools.groupby()関数を使用して、連続する数値をグループ化します。
- グループ化された数値を、範囲の形式で表現します。
- 結果をリストとして返します。
Pythonコード
以下のコードが、「Summary Ranges」を解くためのPythonプログラムとなります。
### Function ##################################################################
def solve(num=0):
solver = Solution().summaryRanges
if 1 <= num <= Input().input: id_LIST = [num]
else: id_LIST = [id+1 for id in range(Input().input)]
for id in id_LIST:
data = Input(id)
ans = solver(data.nums)
result = "OK" if ans==data.ans else "NG"
print(f"[{str(id).zfill(3)}] {result}")
### Class #####################################################################
import itertools
import re
class Solution:
def summaryRanges(self, nums):
"""
:type nums: List[int]
:rtype: List[str]
"""
return [re.sub("->.*>", "->", "->".join([str(n) for i, n in g])) for _, g in itertools.groupby(enumerate(nums), key=lambda x: x[1]-x[0])]
#==============================================================================
class Input:
def __init__(self, num=0):
if num == 1:
self.nums = [0,1,2,4,5,7]
self.ans = ["0->2","4->5","7"]
elif num == 2:
self.nums = [0,2,3,4,6,8,9]
self.ans = ["0","2->4","6","8->9"]
else:
self.input = 2
### Main ######################################################################
if __name__ == "__main__":
solve()
###############################################################################