沒事寫兩題，練練思維

• 運算技巧

  N*2+1 --> N<<1|1 L+(R-L)/2 --> L+((R-L)>>1) 6^7 異或運算

鏈表

鏈表反轉(zhuǎn)

• # 單鏈表 class Node:def __init__(self, x):self.value = xself.next = None# 雙鏈表 class DoubleNode:def __init__(self, x):self.value = xself.pre = Noneself.next = None# 單鏈表反轉(zhuǎn) def reverse_link_list(head):pre = Nonecur = Nonewhile head:cur = head.nexthead.next = prepre = headhead = curreturn pre# 雙鏈表反轉(zhuǎn) def reverse_double_link_list(head):pre = Nonecur = Nonewhile head:cur = head.nexthead.next = prehead.pre = curpre = headhead = curreturn pre# 對數(shù)器 def test_reverse_link_list(head):if head is None:return Nonearr = []while head:arr.append(head)head = head.nextarr[0].next = Nonefor i in range(len(arr), 0, -1):arr[i].next = arr[i-1]return arr[-1]def test_reverse_double_link_list(head):if head is None:return Nonearr = []while head:arr.append(head)head = head.nextarr[0].next = Nonepre = arr[0]for i in range(1, len(arr)):cur = arr[i]cur.pre = Nonecur.next = prepre.pre = curpre = curreturn arr[-1]def generate_random_link_list(length, value):import randomsize = int(random.random()*(length+1))if size == 0:return Nonesize -= 1head = Node(int(random.random()*(value+1)))pre = headwhile size:cur = Node(int(random.random()*(value+1)))pre.next = curpre = cursize -= 1return headdef generate_random_double_link_list(length, value):import randomsize = int(random.random()*(length+1))if size == 0:return Nonesize -= 1head = DoubleNode(int(random.random()*(value+1)))pre = headwhile size:cur = DoubleNode(int(random.random()*(value+1)))pre.next = curcur.pre = prepre = cursize -= 1return head# 無環(huán)檢查鏈表是否反轉(zhuǎn)有誤 def check_link_list(head1, head2):while head1 is None and head2 is None:if head1.value != head2.valuereturn Falsehead1 = head1.nexthead2 = head2.nextreturn head1 is None and head2 is Nonedef check_double_link_list(head1, head2):n1 = head1==Nonen2 = head2==Noneif n1 and n2:return Trueif n1 ^ n2:return Falseif head1.pre is not None or head2.pre is not None:return Falseend1 = Noneend2 = Nonewhile head is not None and head2 is not None:if head1.value != head2.value:return Falseend1 = head1end2 = head2head1 = head1.nexthead2 = head2.nextif head1 is not None or head2 is not None:return Falsewhile end1 is not None and end2 is not None:if end1.value != end2.value:return Falseend1 = end1.preend2 = end2.prereturn end1 is None and end2 is Nonedef main():length = 20value = 100times = 10000for i in range(times):node1 = generate_random_link_list(length, value)rev1 = reverse_link_list(node1)rev2 = test_reverse_link_list(node1)if not check_link_list(rev1, rev2):print("false")break

刪除指定結(jié)點

• class Node:def __init(self, x):self.value = xself.next = Nonedef remove_value(head, num):# 刪除頭結(jié)點中包含指定數(shù)字的結(jié)點while head:if head != num:breakhead = head.nextpre = headcur = headwhile cur:if cur.value == num:pre.next= cur.nextelse:pre = curcur = cur.nextreturn head

雙向列表實現(xiàn)雙端隊列

• class Node:def __init__(self, x):self.value = xself.pre = Noneself.next = None# 雙端隊列 class DoubleEndQueue:def __init__(self):self.head = Noneself.tail = Nonedef _addtohead(self, value):cur = Node(value)if head is None:head = curtail = curelse:cur.next = headhead.pre = curhead = curdef _addtobottom(self, value):cur = Node(value)if head is None:head = curtail = curelse:cur.pre = tailtail.next = curtail = curdef _popfromhead(self):if head is None:return Nonecur = headif head == tail:head = Nonetail = Noneelse:head = head.nextcur.next = Nonehead.pre = Nonereturn cur.valuedef _popfrombottom(self):if head is None:return cur = tailif head == tail:head = Nonetail = Noneelse:tail = tail.precur.pre = Nonetail.next = Nonereturn cur.valuedef _isEmpty(self):return head == None# class MyStack:def __init__(self):self.stack = DoubleEndQueue()def push(self, value):self.stack._addtohead(value)def pop(self):return self.stack._popfromhead()def isEmpty(self):return self.stack._isEmpty()class MyQueue:def __init__(self):self.queue = DoubleEndQueue()def push(self, value):self.queue._addtohead(value)def poll(self):return self.queue._popfrombottom()def isEmpty(self):return self.queue._isEmpty()# python 庫中棧 from collections import deque stack = deque import queue que = queue.Queue(3) # 先入先出隊列 que = queue.LidoQueue(3) # 后入先出隊列 que = queue.PriorityQueue(3) # 優(yōu)先級隊列

每日一題

• class WiggleSubsuquence:def __init__(self, nums:list):n = len(nums)out = nums[1] - nums[0] res = 1 if out == 0 else 2for i in range(2, n):dif = nums[i] - num[i-1]if (dif > 0 and out <=0) or (dif <0 and out >= 0):res += 1return res

歸并排序

• # 使用遞歸 class MergeSort:def __init__(self, arr):self.arr = arrdef __call__(self):if self.arr is None and len(self.arr) < 2:retunr self.arrself.sort(0, len(arr)-1)def sort(self, l, r):if l == r:return mid = l+ (r - l) >> 1sort(l, mid)sort(mid+1, r)merge(l, mid, r)def merge(self, l, m, r):mid_arr = []ptr1 = lptr2 = m + 1i = 0while prt1 <= m and ptr2 <= r:mid_arr[i] = self.arr[p1] if self.arr[p1] <= self.arr[p2] else self.arr[p2] i += 1ptr1 += 1ptr2 += 1while ptr1 <= m:mid_arr[i] = self.arr[ptr1]i += 1ptr1 += 1while ptr2 <= r:mid_arr[i] = self.arr[ptr2]i += 1ptr2 += 1for j in range(len(mid_arr)):self.arr[l+i] = mid_arr[i]# 非遞歸版本mergeSort class MergeSort:def __init__(self, arr):self.arr = arrself.length = len(arr)def __call__(self):if self.arr is None and self.length < 2:returnmergeSize = 1while mergeSize < self.length:l = 0while l < self.length:if mergeSize >= self.length-l:breakm = l + mergeSize - 1r = l + min(m, self.length-p1-1)self.merge(l, m, r)l = r + 1# 防止溢出if mergeSize > self.length //2 :breakmergeSize <<= 1# l -> 最左邊, m -> 中間, r -> 最右邊 def merge(self, l, m, r):help_arr = []p1 = lp2 = m + 1i = 0while p1 <= m and p2 <= r:if self.arr[p1] <= self.arr[p2]:help_arr[i] = self.arr[p1]p1 += 1else:help_arr[i] = self.arr[p2]p2 += 1i += 1while p1 <= m:help_arr[i] = self.arr[i]while p2 <= r:help_arr[i] = self.arr[i]for j in range(len(help_arr)):self.arr[l+j] = help_arr[j]

總結(jié)

以上是生活随笔為你收集整理的刷题（一）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。