*目次 [#v44acab3]
#contents
#br
*flatten [#b03d7ed3]
再帰を使わない方法
import collections
def flatten(lst):
i = 0
while i < len(lst):
while isinstance(lst[i], collections.Iterable):
if not lst[i]:
lst.pop(i)
i -= 1
break
else:
lst[i:i+1] = lst[i]
i += 1
return lst
print [1, 2, 3, 4, 5, 6, 7] == flatten([1, [2, 3], [4, 5, [6, 7]]])
再帰を使う方法
def flatten(lst):
flatList = []
for e in lst:
if type(e)==list:
flatList.extend(flatten(e))
else:
flatList.append(e)
return flatList
print [1, 2, 3, 4, 5, 6, 7] == flatten([1, [2, 3], [4, 5, [6, 7]]])
*数字からなるリストの各要素をかけ算する [#bbb1b2c5]
以下の例だと、3 x 7 x 11 x 13 x 17 で 51051 になる。
a = [3, 7, 11, 13, 17]
print reduce(lambda x, y: x*y, a)
*2つのリストの要素を交互に連結する [#a25dc2d2]
2つのリストから交互にデータを取り出し1つのリストを作る。
以下の例だと、c は [1, 4, 2, 5, 3, 6] になる。
a = [1, 2, 3]
b = [4, 5, 6]
c = list(sum(zip(a, b), ()))
*リストの重複を排除する [#sf542eaa]
リストの重複した要素を削除する。ただし要素の出現順に並べる。
以下の例では、[2, 0, 3, 4, -1, -2] を出力する。
a = [2, 0, 0, 3, 2, 3, 4, 3, -1, -2, -1]
print list(sorted(set(a), key=a.index))
*二分探索 [#p333c91d]
# -*- coding: utf-8 -*-
# リストaの中にxが含まれている場合、その位置をゼロインデックスで返す。
# xが含まれていない場合は-1を返す。
def binary_search(a, x, lo=0, hi=None):
if hi == None:
hi = len(a)
while lo < hi:
md = (lo+hi) // 2
v = a[md]
if v < x:
lo = md + 1
elif x < v:
hi = md
else:
return md
return -1
a = range(-int(5e7), int(5e7), 2)
xs = [-1, 0, int(1e8), -int(1e8), -int(4e6-1), -int(4e6), -45672108]
for x in xs:
print '%10d: %8d' % (x, binary_search(a, x))
*キュー [#v7a2e824]
dequeによる実装。append/popleftを使う。
# -*- coding: utf-8 -*-
from collections import deque
q = deque('xyz')
print q # deque(['x', 'y', 'z'])
q.append('a')
q.append('f')
print q # deque(['x', 'y', 'z', 'a', 'f'])
print q.popleft() # x
print q.popleft() # y
print q # deque(['z', 'a', 'f'])
print q.popleft() # z
print q.popleft() # a
print q.popleft() # f
if len(q):
print q.popleft() # if文がないとIndexErrorになる。
print q # deque([])
*スタック [#wffca796]
dequeによる実装。append/popを使う。
# -*- coding: utf-8 -*-
from collections import deque
q = deque('xyz')
print q # deque(['x', 'y', 'z'])
q.append('a')
q.append('f')
print q # deque(['x', 'y', 'z', 'a', 'f'])
print q.pop() # f
print q.pop() # a
print q # deque(['x', 'y', 'z'])
print q.pop() # z
print q.pop() # y
print q.pop() # x
if len(q):
print q.pop() # if文がないとIndexErrorになる。
print q # deque([])
