杂七杂八二

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:
        break
    else:
        N1 = N % R
        N = R
        R = N1
        continue
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 = True
        list_s1.sort()
        list_s2.sort()
        i = 0
        while i < len(list_s1) and matches:
            if list_s1[i] == list_s2[i]:
                i = i + 1
            else:
                matches = False
    else:
        matches = False

    return matches

print(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 = 0
    while index < len(symbolString):
        symbol = symbolString[index]
        if symbol == '(':
            s.push(symbol)
        else:
            if s.isEmpty():
                return False
            else:
                s.pop()
        index = index + 1

    if s.isEmpty():
        return True
    else:
        return False

print(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 = 0
    while index < len(symbolString):
        symbol = symbolString[index]
        if symbol in '([{':
            s.push(symbol)
        else:
            if s.isEmpty():
                return False
            else:
                top = s.pop()
                if not matches(top,symbol):
                    return False

        index = index + 1

    if s.isEmpty():
        return True
    else:
        return False