Pythonで世界で闘うプログラミング力を鍛える[chap02]
前回kigeso.hatenablog.com
の続きです。
今回は連結リストを扱うということでしたので、はじめに簡単に実装したリストを全ての問題で使用しています。
連結リスト [lib2.py]
from random import randint class MyCell: # シンプルな連結リストを実装しました # initCell関数で初期化できます # printCell関数でリストの要素を表示できます def __init__(self, data=None): self.data = data self.next = None # # MyCellを初期化 # def initCell(x=10): head = MyCell() if type(x) == int: n = head n.data = randint(1, 10) for _ in range(x-1): n.next = MyCell(randint(1, 10)) n = n.next elif type(x) == list: n = head n.data = x[0] for i in x[1:]: n.next = MyCell(i) n = n.next else: return None return head # # MyCellの中身を表示 # def printCell(head, N=None): cnt = 1 n = head while 1: print(n.data, end='') if n.next != None and (N == None or cnt < N): print('->', end='') else: print() break n = n.next cnt += 1 return
重複要素の削除
from lib2 import * # # O(n) 追加領域あり # def delete_duplicate(head): element = set() n = head pre = None while n != None: if n.data in element: pre.next = n.next else: element.add(n.data) pre = n n = n.next # # O(n^2) 追加領域なし # def delete_duplicate2(head): n = head while n.next != None: now = n while now.next != None: if n.data == now.next.data: now.next = now.next.next else: now = now.next n = n.next if __name__ == '__main__': l = [7,8,6,6,7,2,10,2,2] head = initCell(l) print('入力') printCell(head) delete_duplicate(head) printCell(head) head = initCell(l) print('入力') printCell(head) delete_duplicate2(head) printCell(head)
後ろからK番目を返す
from lib2 import * def Kth_from_back(head, k=3): n = head cnt = 0 while n.next != None: cnt += 1 n = n.next if cnt == k-1: break if n == None: print('False') return m = head while n.next != None: m = m.next n = n.next print(m.data) return if __name__ == '__main__': head = initCell() print('入力') printCell(head) Kth_from_back(head, k=5)
間の要素を削除
from lib2 import * def delete_element(node): n = node if n.next == None: node = None else: n.data = n.next.data n.next = n.next.next if __name__ == '__main__': head = initCell() print('入力') printCell(head) k = 5 print(k) node = head cnt = 0 while node.next != None: cnt += 1 if cnt == k: break node = node.next delete_element(node) printCell(head)
リストの分割
from lib2 import * # このコードはkより小さいものと大きいものの中間ノードを記憶している # けど、リストのheadとtailを使った方が簡単だ def divide_list(head, k): n = head out = MyCell() x_node = None #kより小さい値の中で最も後ろのノード while n != None: if x_node == None: # まだ値が入っていない if out.data == None: out.data = n.data # まだk未満の値が入っていない else: tmp = MyCell(n.data) tmp.next = out out = tmp if n.data < k: x_node = out else: # kより小さければ先頭に加える if n.data < k: tmp = MyCell(n.data) tmp.next = out out = tmp # kより大きければx_nodeの後に加える else: tmp = MyCell(n.data) tmp.next = x_node.next x_node.next = tmp n = n.next return out if __name__ == '__main__': head = initCell([3, 5, 8, 5, 10, 2, 1]) print('入力') printCell(head) k = 5 head = divide_list(head, k) printCell(head)
リストで表された2数の和
from lib2 import * # 最後の桁上がりに注意 # 例：5->5 と 5->4 を足すと、0->0->1となるように def list_sum(l1, l2): if l1 == None or l2 == None: return None n1, n2 = l1, l2 flg = False out = MyCell() tail = out while n1 != None or n2 != None or flg: num1 = n1.data if n1 != None else 0 num2 = n2.data if n2 != None else 0 ssum = num1+num2+int(flg) tail.next = MyCell(ssum%10) tail = tail.next flg = ssum >= 10 n1 = n1.next if n1 != None else None n2 = n2.next if n2 != None else None return out.next if __name__ == '__main__': list1 = initCell([7, 1, 6]) list2 = initCell([5, 9, 3]) print('list1') printCell(list1) print('list2') printCell(list2) print('ans') printCell(list_sum(list1, list2))
回文
from lib2 import * def is_palindrome(head): n = head reverse = MyCell() while n != None: reverse.data = n.data tmp = MyCell() tmp.next = reverse reverse = tmp n = n.next printCell(reverse.next) n = head r = reverse.next while n != None or r != None: if n != None and r == None: return False elif n == None and r != None: return False elif n.data != r.data: return False else: n = n.next r = r.next continue return True if __name__ == '__main__': head = initCell([1, 2, 3, 4, 5, 4, 3, 2, 1]) print('入力') printCell(head) print(is_palindrome(head))
共通するノード
from lib2 import * import random def make_common_list(): common = initCell(random.randrange(3, 10)) h1, h2 = initCell(random.randrange(3, 10)), initCell(random.randrange(3, 10)) n1, n2 = h1, h2 while n1 != None: if n1.next == None: n1.next = common break else: n1 = n1.next while n2 != None: if n2.next == None: n2.next = common break else: n2 = n2.next return h1, h2 # 判定のみ def is_common_list(h1, h2): end1, end2 = h1, h2 while end1.next != None: end1 = end1.next while end2.next != None: end2 = end2.next if end1 == end2: return True return False # 共通のノードを返す def is_common_list2(h1, h2): end1, end2 = h1, h2 len1 = 1 while end1.next != None: len1 += 1 end1 = end1.next len2 = 1 while end2.next != None: len2 += 1 end2 = end2.next if end1 != end2: return False n1, n2 = h1, h2 if len1 < len2: len1, len2 = len2, len1 n1, n2 = n2, n1 for _ in range(len1-len2): n1 = n1.next while 1: if n1 == n2: return n1 else: n1 = n1.next n2 = n2.next return False if __name__ == '__main__': h1, h2 = make_common_list() printCell(h1) printCell(h2) print(is_common_list(h1, h2)) printCell(is_common_list2(h1, h2))
ループの検出
from lib2 import * import random def make_roop_list(): h1 = initCell(random.randrange(3, 10)) h2 = initCell(random.randrange(3, 10)) n1, n2 = h1, h2 while 1: if n1.next == None: n1.next = h2 break else: n1 = n1.next while 1: if n2.next == None: n2.next = h2 break else: n2 = n2.next return h1 # フロイドの循環検出アルゴリズムっていう名前らしい def find_roop_head(n): head = n slow, fast = head, head while 1: if slow.next != None: slow = slow.next else: return False if fast.next != None: if fast.next.next != None: fast = fast.next.next else: return else: return False if slow == fast: break slow = head while 1: if slow == fast: return slow if slow.next != None: slow = slow.next else: return False if fast.next != None: fast = fast.next else: return False return False if __name__ == '__main__': n = make_roop_list() printCell(n, N=20) printCell(find_roop_head(n), 15)
