杂七杂八二

python可视化
https://pythontutor.com/render.html#mode=display

辗转相除法求最大公约数

'''
辗转相除法求最大公约数
'''
M = int(input("请输入M:"))
N = int(input("请输入N:"))
R = M % N
A = N
while True:if R ==0:breakelse:N1 = N % RN = RR = N1continue
print("%s和%s的最大公约数是%s" % (M, A, N))

变位词判断问题

'''
变位词判断问题：
所谓“变位词”是指两个词之间存在组成字母的重新排列关系
如：heart和earth，python和typhon
为了简单起见，假设参与判断的两个词仅由小写字母构成，而且长度相等
解题目标：写一个bool函数，以两个词作为参数，返回这两个词是否变位词
可以很好展示同一问题的不同数量级算法
'''def bianweici(s1,s2):list_s1 = list(s1)list_s2 = list(s2)# 先判断长度是不是相等if len(list_s1) == len(list_s2):matches = Truelist_s1.sort()list_s2.sort()i = 0while i < len(list_s1) and matches:if list_s1[i] == list_s2[i]:i = i + 1else:matches = Falseelse:matches = Falsereturn matchesprint(bianweici('abcde','edcbad'))

用Python实现ADT Stack
栈顶首端的版本（左），其push/pop的复杂度为O(n)，而栈顶尾端的实现（右），其push/pop的复杂度为O(1)

'''
用Python实现ADT Stack
'''
class Stack:def __init__(self):self.items = []def isEmpty(self):return self.items == []def push(self,item):return self.items.append(item)def pop(self):return self.items.pop()def peek(self):return self.items[len(self.items)-1]def size(self):return len(self.items)

检查()括号匹配

'''
用Python实现ADT Stack
'''class Stack:def __init__(self):self.items = []def isEmpty(self):return self.items == []def push(self,item):return self.items.append(item)def pop(self):return self.items.pop()def peek(self):return self.items[len(self.items)-1]def size(self):return len(self.items)

'''
检查()括号匹配
'''
def parChecker(symbolString):# 建立一个空栈s = Stack()index = 0while index < len(symbolString):symbol = symbolString[index]if symbol == '(':s.push(symbol)else:if s.isEmpty():return Falseelse:s.pop()index = index + 1if s.isEmpty():return Trueelse:return Falseprint(parChecker("(()())"))
print(parChecker("(((((((((())))))))))))))))))())"))

结果：
True
False

检查括号匹配升级版：({[)}]
多了一个matches方法：

def matches(open,close):opens = "([{"closers = ")]}"return opens.index(open) == closers.index(close)

修改了parChecker（）

def parCheckerUpdate(symbolString):# 建立一个空栈s = Stack()index = 0while index < len(symbolString):symbol = symbolString[index]if symbol in '([{':s.push(symbol)else:if s.isEmpty():return Falseelse:top = s.pop()if not matches(top,symbol):return Falseindex = index + 1if s.isEmpty():return Trueelse:return False

一些顿悟：

opens = "([{"
closers = ")]}"
open = '('
close = ']'
print(opens.index(open))   #0
print(closers.index(close))  #1

十进制转换为二进制

from learning.stack import Stackdef divideBy2(decNumber):remstack = Stack()while decNumber > 0:rem = decNumber % 2 #求余数remstack.push(rem)decNumber = decNumber // 2  #整数除binString = ""while not remstack.isEmpty():binString = binString + str(remstack.pop())return binStringprint(divideBy2(42))

十进制->十六进制

def baseConverter(decNumber,base):# "0123456789ABCDEF”[0]是一个常用的技巧，它可以快速将一个数字转换为16进制字符digits = '0123456789ABCDEF'remstack = Stack()while decNumber > 0:rem = decNumber % baseremstack.push(rem)decNumber = decNumber // basenewString = ''while not remstack.isEmpty():newString = newString + digits[remstack.pop()]   #pop()出14，则查表得到Ereturn newString
print(baseConverter(25,2))
print(baseConverter(26,16))

后缀表达式

'''
后缀表达式456*+     78+32+/
'''
from learning.stack import Stackdef postfixEval(postfixExpr):operandStack = Stack()tokenList = postfixExpr.split()for token in tokenList:if token in '0123456789':operandStack.push(int(token))else:operand2 = operandStack.pop()operand1 = operandStack.pop()result = doMath(token,operand1,operand2)operandStack.push(result)return operandStack.pop()def doMath(op,op1,op2):if op == '*':return op1 * op2elif op == '/':return op1 / op2elif op == '+':return op1 + op2else:return op1 - op2print(postfixEval(' 4 5 6 * + ' ))
# print(postfixEval('7 8 + 3 2 + /'))

双端队列

class Deque:def __init__(self):self.items = []def isEmpty(self):return self.items == []def addFront(self, item):self.items.append(item)def addRear(self, item):self.items.insert(0, item)def removeFront(self):return self.items.pop()def removeRear(self):return self.items.pop(0)def size(self):return len(self.items)

回文词

from learning.deque import Dequedef palchecker(aString):chardeque = Deque()for ch in aString:chardeque.addRear(ch)stillEqual = Truewhile chardeque.size() > 1 and stillEqual:first = chardeque.removeFront()last = chardeque.removeRear()if first != last:stillEqual = Falsereturn stillEqualprint(palchecker("lsdkjfskf"))
print(palchecker("radar"))

节点Node

'''
链表实现：节点Node
'''class Node:def __init__(self,initdata):self.data = initdataself.next = Nonedef getData(self):return self.datadef getNext(self):return self.nextdef setData(self,newdata):self.data = newdatadef setNext(self,newnext):self.next = newnext# temp = Node(93)
# print(temp.getData())

无序表UnorderedList

'''
无序表UnorderedList
'''
from learning.node import Node
class UnorderedList:def add(self, item):temp = Node(item)temp.setNext(self.head)self.head = tempdef size(self):current = self.headcount = 0while current != None:count = count+1current = current.getNext()return countdef search(self,item):current = self.headfound = Falsewhile current != None and not found:if current.getData() == item:found = Trueelse:current = current.getNext()return founddef remove(self,item):current = self.headprevious = Nonefound = Falsewhile not found and current != None:if current.getData() == item:found = Trueelse:previous = currentcurrent = current.getNext()if previous == None:self.head = current.getNext()else:previous.setNext(current.getNext)

有序表orderedList

from learning.node import Node
'''
有序表orderedList
'''
class OrderreadList:def add(self, item):current = self.headprevious = Nonestop = Falsewhile current != None and not stop:if current.getData() > item:   #发现插入位置stop = Trueelse:previous = currentcurrent = current.getNext()temp = Node(item)# 插入在表头if previous == None:temp.setNext(self.head)self.head = temp# 插入在表中else:temp.setNext(current)previous.setNext(temp)def size(self):current = self.headcount = 0while current != None:count = count+1current = current.getNext()return countdef search(self,item):current = self.headfound = Falsestop = False  #标志变量while current != None and not found and not stop:if current.getData() == item:found = Trueelse:if current.getData() > item:stop = Trueelse:current = current.getNext()return founddef remove(self,item):current = self.headprevious = Nonefound = Falsewhile not found and current != None:if current.getData() == item:found = Trueelse:previous = currentcurrent = current.getNext()if previous == None:self.head = current.getNext()else:previous.setNext(current.getNext)

递归

def listsum(numList):if len(numList) == 1:return numList[0]else:return numList[0]+listsum(numList[1:])print(listsum([1,3,5]))

递归实现整数转换为任意进制

'''
整数转换为任意进制
'''
def toStr(n,base):converString = '0123456789ABCDEF'if n < base:return converString[n] # 最小规模else:return toStr(n//base,base)+converString[n%base]  # 减小规模，调用自身print(toStr(1453,16))
print(toStr(769,10))

python中的递归深度限制

import sysprint(sys.getrecursionlimit())
sys.setrecursionlimit(1000)
print(sys.getrecursionlimit())

顺序查找

'''
顺序查找，无序表查找列表
'''
def sequentialSearch(alist,item):pos = 0found = Falsewhile pos<len(alist) and not found:if alist[pos] == item:found = Trueelse:pos = pos+1return found,postestlist = [1,2,32,8,17,19,42,13,0]
print(sequentialSearch(testlist,3))
print(sequentialSearch(testlist,13))

二分查找法

def binarySearch(alist,item):first = 0last = len(alist)-1found = Falsewhile first<last and not found:midpoint = (first+last)//2if alist[midpoint] == item:found = Trueelse:if midpoint<item:first = midpoint+1else:last = midpoint-1return foundtestlist = [0,1,2,8,13,17,19,32,42]
print(binarySearch(testlist,3))
print(binarySearch(testlist,13))

二分查找递归算法

def binarySearch2(alist,item):if len(alist) == 0:return Falseelse:minpoint = len(alist)//2if alist[minpoint]==item:return Trueelse:if alist[minpoint]<item:return binarySearch2(alist[minpoint+1:],item)else:return binarySearch2(alist[:minpoint],item)

冒泡排序

def bubblesort(alist):for passnum in range(len(alist)-1,0,-1):for i in range(passnum):if alist[i]>alist[i+1]:alist[i],alist[i+1] = alist [i+1],alist[i]alist = [54,26,93,17,77,31,44,55,20]
bubblesort(alist)
print(alist)

冒泡排序：性能改进

def shortBubbleSort(alist):exchangs = Truepassnum = len(alist)-1while passnum > 0 and exchangs:exchangs = Falsefor i in range(passnum):if alist[i]>alist[i+1]:exchangs = Truealist[i],alist[i+1] = alist [i+1],alist[i]passnum = passnum - 1

选择排序

'''
选择排序
'''def selectSort(alist):for fillslot in range(len(alist)-1,0,-1):positionOfMax = 0for location in range(1,fillslot+1):if alist[location]>alist[positionOfMax]:positionOfMax = locationalist[fillslot],alist[positionOfMax] = alist[positionOfMax],alist[fillslot]alist = [54,26,93,17,77,31,44,55,20]
selectSort(alist)
print(alist)

插入排序

'''
插入排序
'''
def insertionSort(alist):for index in range(1,len(alist)):currentvalue = alist[index]  # 新项插入项position = indexwhile position > 0 and alist[position-1]>currentvalue:alist[position]=alist[position-1]  # 对比，移动position = position-1alist[position]=currentvalue # 插入新项alist = [54,26,93,17,77,31,44,55,20]
insertionSort(alist)
print(alist)

归并排序

def merge_sort(lst):# 递归结束条件if len(lst)<=1:return lst# 分解问题，并递归调用middle = len(lst)//2# 左半部排好序、右半部排好序left = merge_sort(lst[:middle])right = merge_sort(lst[middle:])# 合并左右半部，完成排序merged = []while left and right:if left[0]<=right[0]:merged.append(left.pop(0))else:merged.append(right.pop(0))merged.extend(right if right else left)return mergedalist1 = [54,26,93,17,77,31,44,55,20]
print(merge_sort(alist1))

谢尔排序

'''
谢尔排序
'''def shellSort(alist):sublistcount = len(alist)//2   #间隔设定while sublistcount>0:for startposition in range(sublistcount):   #子列表排序gapInsertionSort(alist,startposition,sublistcount)print("After increments of size",sublistcount,"The list is",alist)sublistcount = sublistcount//2   #间隔缩小def gapInsertionSort(alist,start,gap):for i in range(start+gap,len(alist),gap):currentvalue = alist[i]position = iwhile position>gap and alist[position-gap]>currentvalue:alist[position] = alist[position-gap]position = position-gapalist[position]=currentvaluealist = [54,26,93,17,77,31,44,55,20]
shellSort(alist)

快速排序

'''
快速排序：分裂和移动
'''
def quickSort(alist):quickSortHelper(alist,0,len(alist)-1)def quickSortHelper(alist,first,last):if first<last:splitpoint = partition(alist,first,last)quickSortHelper(alist,first,splitpoint-1)quickSortHelper(alist,splitpoint+1,last)def partition(alist,first,last):# 选定中值pivotvalue = alist[first]# 左右标初值leftmark = first+1rightmark = lastdone = Falsewhile not done:# 向右移动左标while leftmark <= rightmark and alist[leftmark]<=pivotvalue:leftmark = leftmark +1# 向左移动右标while alist[rightmark] >= pivotvalue and rightmark >= leftmark:rightmark = rightmark -1# 两标相错就结束移动if rightmark < leftmark:done = True# 左右标的值交换else:alist[leftmark],alist[rightmark] = alist[rightmark],alist[leftmark]# 中值就位alist[leftmark], alist[rightmark] = alist[rightmark], alist[leftmark]# 中值点，也是分裂点return rightmarkalist = [54,26,93,17,77,31,44,55,20]
quickSort(alist)
print(alist)

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！