Today New -> python | 算法大神左神（左程云）算法课程 第五节(第几节我已经搞不清了，随便吧。。）
针对b站视频左神算法与数据结构，自己练习对应的python代码
相关链接：
1️⃣b站视频地址
2️⃣视频笔记（其实主要是题目截图）
⭐ 复制含有随机指针节点的链表
function 1 -> hash表
# 复制含有随机指针节点的链表
# 用hash表
class Node():
def __init__(self, value=None, next=None, rand=None):
self.value = value
self.next = next
self.rand = rand
def CopyList(head):
hash = {} # key-value
h = head
while h is not None:
hash[h] = Node(h.value) # key=old node; value=new node
h = h.next
h = head
while h is not None:
hash[h].next = h.next # new.next = old.next
hash[h].rand = h.rand # new.rand = old.rand
h = h.next
return hash[head] # hash[old head] -> new head
function 2 -> 不用hash表
难点：rand指针的随机性，如何找到复制的链表各个点的rand指针指定的位置？
先依附于原链表创建新节点，这样新表每个节点与原表各个节点之间就有一一对应位置，则根据原表的rand指针指定的位置就可以找到新表对应的位置，就可以先解决rand指针，再依次将新节点从原表中取下，同时连上next指针。
代码：
def CopyList2(head):
if head is None: return None
# step1 create new nodes
h = head
while h is not None:
next = h.next # next -> save next node
h.next = Node(h.value) # h.next -> new node
h.next.next = next # new node -> next
h = next # h move next
# step2 rand part
h = head
while h is not None:
next = h.next.next # next -> save next node of old list
cur_copy = h.next # cur_copy -> new node
cur_copy.rand = h.rand.next if h.rand is not None else None # find rand space or None
h = next
# step3 next part and split
h = head
res = head.next # new list head node
while h is not None:
next = h.next.next
cur_copy = h.next
cur_copy.next = next.next if next is not None else None # new list
h.next = next # old list
h = next
return res
补充知识：Python中如何自己实现hash表？
其中Array是存储结构
Slot是每一对key-value的记录结构
若干Slot构成一张HashTable
# Python中实现hash表结构
class Array(): # Array -> use to save hash table items
def __init__(self, size=32, init=None):
self._size = size
self._items = [init] * size
def __len__(self):
return self._size
def __getitem__(self, index):
return self._items[index]
def __setitem__(self, index, value):
self._items[index] = value
def clear(self, value=None):
for i in range(len(self._items)):
self._items[i] = value
def __iter__(self):
for item in self._items:
yield item
class Slot(): # Slot -> save each key-value
def __init__(self, key, value):
self.key, self.value = key, value
class HashTable():
Unused = None # Unused -> init (means an unused slot)
Empty = Slot(None, None) # an empty slot
def __init__(self):
self._table = Array(size=8, init=HashTable.Unused)
self.length = 0
@property
def _load_factor(self): # how much space has been used
return self.length / float(len(self._table))
def __len__(self): # num of not empty slot
return self.length
def _hash(self, key):
return abs(hash(key)) % len(self._table)
def _find_key(self, key):
index = self._hash(key)
_len = len(self._table)
while self._table[index] is not HashTable.Unused: # an used slot
if self._table[index] is HashTable.Empty: # this slot's key and value have been removed
index = (index * 5 + 1) % _len # search another slot; cpython解决hash冲突的的一种方式。
continue # while -> next loop
elif self._table[index].key == key: # find it
return index
else:
index = (index * 5 + 1) % _len
return None
def _slot_can_insert(self, index):
return (self._table[index] is HashTable.Unused or self._table[index] is HashTable.Empty) # None or Slot(None, None)
def _find_slot_for_insert(self, key):
index = self._hash(key)
_len = len(self._table)
while not self._slot_can_insert(index): # collision
index = (index * 5 + 1) % _len
return index # Dont't worry, read follow -> add and _rehash
def add(self, key, value):
index = self._find_key(key)
if index is not None: # this key already exists
self._table[index].value = value # refresh value of this slot
return False # not new key
else:
index = self._find_slot_for_insert(key)
self._table[index] = Slot(key, value)
self.length += 1
if self._load_factor >= 0.8: # make sure always have space to add
self._rehash()
return True # new key-vlue
def _rehash(self):
old_table = self._table # save old hash table
newsize = len(self._table) * 2
self._table = Array(newsize, init=HashTable.Unused) # reinit
self.length = 0
for slot in old_table:
if slot is not HashTable.Unused and slot is not HashTable.Empty: # not None and not Slot(None, None)
index = self._find_slot_for_insert(slot.key)
self._table[index] = slot
self.length += 1
def get(self, key, default=None):
index = self._find_key(key)
if index is None:
return default # not find return what you want
else:
return self._table[index].value # find key's value
def remove(self, key):
index = self._find_key(key)
if index is None:
raise KeyError() # no this key to remove, so raise error
value = self._table[index].value # save key's value
self._table[index] = HashTable.Empty # this slot -> Slot(None, None)
self.length -= 1
return value
def __iter__(self):
for slot in self._table:
if slot not in (HashTable.Unused, HashTable.Empty):
yield slot.key
# 示例演示效果
def test_hash_table():
h = HashTable()
h.add('i', 0)
h.add('miss', 1)
h.add('u', 2)
assert len(h) == 3
assert h.get("i") == 0
assert h.get("miss") == 1
assert h.get("him", "No!") == "No!"
h.remove('i')
assert h.get('i') is None
assert len(h) == 2
assert sorted(h) == ["miss", "u"]
n = 50
for i in range(n):
h.add(i, i)
print(len(h)) # 52
for i in range(n):
assert h.get(i) == i
if __name__ == '__main__':
test_hash_table()