In [3]:
def even_odd(A):
"""この関数では，左に偶数の値，右に奇数の値を集めていく．
まだ決まっていない部分がそれらのインデックスに挟まれた領域を示すと考え，
3種類のsubarrayから構成されていると見做すこともできる．
Args:
A: list of integers.
Returns:
Sorted list, with the even numbers are at the left side and odd numbers are at the right side.
"""
next_even, next_odd = 0, len(A) -1
# ポインタみたいな考え方だと思うとわかると思う．左から見ていって，偶数なら次の値を見に行き，奇数なら一番左に値を持っていく．
# これは書けるようにしておくと後々応用ができる(競プロで見たことがある)
while next_even < next_odd:
if A[next_even] % 2 == 0:
next_even += 1
else:
A[next_even], A[next_odd] = A[next_odd], A[next_even]
next_odd -= 1
return A
In [4]:
print(even_odd([i ** 2 for i in range(10)]))
配列のライブラリは把握しておくこと．
In [45]:
# 数列Aとpivotに当たるindexを引数にとり，indexの値よりも大きな値はindexの右側に，小さな値は左側に集める関数．
def single_pivot(pivot_index, A):
"""
Args:
pivot_index: integer, the index of pivot.
A: list of integers.
Returns:
sorted list
"""
pivot = A[pivot_index]
# まずpivotより小さな値をpivotの左に集める．
print(len(A))
for i in range(len(A)):
for j in range(i+1, len(A)):
if A[j] < pivot:
A[i], A[j] = A[j], A[i]
break
print(A)
# 次に，pivotより大きな値をpivotの右に集める．
# reversedは初めて使った．イテレータを逆転させる?リストに対して使っても戻り値はイテレータになる．
# 前提として，pivotより小さな値は全て元のpivotより左に集められている．
# そのため,pivotより小さいもの，pivotと等しいものとより大きいものが混在している状態になる．より大きいものがあれば右端から交換していく．
for i in reversed(range(len(A))):
if A[i] < pivot:
break
for j in reversed(range(i)):
if A[j] > pivot:
A[i], A[j] = A[j], A[i]
break
return A
In [48]:
A = [0,1, 2, 0, 2, 1, 1]
trial_index = 2
print(single_pivot(trial_index, A))
In [28]:
print(A)
print(len(A))
print("----------")
for i in range(len(A)):
for j in range(i+1, len(A)):
print("i+1: ", j)
print(A[j])
print("---------------")
In [1]:
# rangeはこのパターンだと何も生成しない．
for i in range(7,4):
print(i)
In [3]:
# 一つ目のpivotのやり方だとO(n**2)なので改善策を考える．
# 簡単なやり方として，pivotより小さいものを見つけたら一番左に，大きいものを見つけたら一番右におく．
# 作業の時はfirst passとsecond passに分ける．はじめに小さいものを集め，次に大きいものを集める．
def pivot_to_edge(pivot_index, A):
"""
Args:
pivot_index: the index deciding the pivot
A: list of integers
Return:
separeted list of integers according whether the value is less than the pivot or more than the pivot.
"""
pivot = A[pivot_index]
# first pass
# 左から順に，"小さいものを入れるポケット"を準備していく．
smaller = 0
for i in range(A):
if A[i] < pivot:
A[i], A[smaller] = A[smaller], A[i]
smaller += 1
# second pass
larger = len(A) - 1
for i in reversed(range(len(A))):
# 小さいものは左に全て固まっているのでbreakでそこでやめることができる．
if A[i] < pivot:
break
if A[i] > pivot:
A[i], A[larger] = A[larger], A[i]
larger -= 1
return A
In [6]:
# pivot問題の最後のやり方．singleかつsublistをbottom, middle, unclassified, topの4つに分ける
def best_method(pivot_index, A):
pivot = A[pivot_index]
# 次のindexの設定は不変．
# bottom group: A[:smaller]
# middle group: A[smaller:equal]
# unclassified group: A[equal: larger]
# top group: A[larger:]
smaller, equal, larger = 0, 0, len(A)
while equal < larger:
# A[equal]はunclassifiedの一番左端，つまり次に確認するところ．
if A[equal] < pivot:
A[smaller], A[equal] = A[equal], A[smaller]
# ここの2文忘れて無限ループ入ってしまった．
smaller += 1
equal += 1
elif A[equal] == pivot:
equal += 1
else:
larger -= 1
A[larger], A[equal] = A[equal], A[larger]
return A
In [7]:
A = [-3, 0, -1, 1,1, -3, 1,2, 4, 2]
pivot_index = 3
best_method(pivot_index, A)
Out[7]:
In [11]:
# 5.3 listで1桁ずつ与えられた数字に1を足してlistで返す．
# 例えば，<1, 3, 9>に<1, 4, 0>で返す．
# ただし，精度に限界がある言語でも使えるアルゴリズムにすること．
# stringで引っ付けてintegerに変換して1足してstringに戻して分解する方法はだめ
def plus_one(A):
"""やり方: 配列の一番後ろに1を足してそれが10になるかならないかで場合分け"""
A[-1] += 1
# 1桁目に繰り上がりがなければ終わり
if A[-1] != 10:
return A
else:
A[-1] = 0
for i in reversed(range(len(A)-1)):
A[i] += 1
if A[i] == 10:
A[i] = 0
# 最初の桁まで来た時の処理
if i == 0:
A[i] = 1
A.append(0)
return A
else:
return A
In [12]:
A = [1, 3, 9]
B = [9, 9]
print(plus_one(A))
print(plus_one(B))
In [13]:
# もっとスマートな書き方
def better_plus_one(A):
A[-1] += 1
# 一つ手前部分の繰り上がり計算もループ中でやるため，rangeは1スタート
for i in reversed(range(1, len(A))):
if A[i] != 10:
break
A[i] = 0
A[i - 1] += 1
if A[0] == 10:
A[0] = 1
A.append(0)
return A
In [14]:
better_plus_one(A)
Out[14]:
In [28]:
# 同じように二つのlist表記の整数が来た時の掛け算
# 大きな数が来た時用の対策が必要． string to intは使えない．
def multiply(num1, num2):
# 符号の処理
# マイナスの計算にも対応させる．マイナスの時はlistの初めの要素が例えば-7とかになってる前提．
sign = -1 if (num1[0] < 0) ^ (num2[0]) else 1
num1[0], num2[0] = abs(num1[0]), abs(num2[0])
# 長さn*mの[0]のリストを準備する． これ確認いるかも
# 計算の仕方は筆算．resultに順次加算していく．
result = [0] * (len(num1) + len(num2))
for i in reversed(range(len(num1))):
for j in reversed(range(len(num2))):
result[i+j+1] += num1[i]*num2[j]
result[i+j] += result[i + j + 1] //10
result[i + j + 1] %= 10
# このorは，1つ目が 空行列だったときのみ評価されて[0]を入れる．nextの第二引数はdefault値
# next使うとbreakと同じような効果が期待?
result = result[next((i for i, x in enumerate(result) if x!= 0), len(result)):] or [0]
# 配列の一番左側に符号を混ぜて，出力する．
return [sign * result[0]] + result[1:]
In [20]:
A = [1, 9, 3, 7, 0, 7, 7, 2, 1]
B = [-7, 6, 1, 8, 3, 8, 2, 5, 7, 2, 8, 7]
multiply(A,B)
Out[20]:
In [31]:
trial_list = [1,1,1,1, 2,2,2,2]
only2 = trial_list[next(i for i, x in enumerate(trial_list) if x != 2):]
only2
Out[31]:
In [27]:
result
Out[27]: