一.变位词判断问题

变位词是指相同字母的不同排列方式。 1.逐字检查法（直接比较）

def anagramSolution_first(s1,s2): n = 0 if len(s1) == len(s2): for i in s1: for j in s2: if i == j: n += 1 if n == len(s1): result = True else: result = False else: result = False return result print(anagramSolution_first('typhon','python'))

时间复杂度：O(n**2) 2.逐字检查法（标记）

def anagramSolution1(s1,s2): alist = list(s2) pos1 = 0 stillOK = True while pos1 < len(s1) and stillOK: pos2 = 0 found = False while pos2 < len(alist) and not found: if s1[pos1] == s2[pos2]: found = True else: pos2 = pos2 + 1 if found: alist[pos2] = None else: stillOK = False pos1 = pos1 + 1 return stillOK print(anagramSolution1('typhon','python'))

时间复杂度：O(n**2) 3.排序比较法

def anagramSolution2(s1,s2): if len(s1) == len(s2): alist1 = list(s1) alist2 = list(s2) alist1.sort() alist2.sort() result = True i = 0 while i < len(s1) and result: if alist1[i] == alist2[i]: i += 1 else: result = False else: result = False return result print(anagramSolution2('typhon','python'))

时间复杂度：O(nlogn) 4.计数比较法（ord计数）

def anagramSolution3(s1,s2): ''' 将每个出现的字母进行计数然后比较次数 使用到ord（Unicode编码） 26字母表示为数字ord('c')-ord('a')=2 ''' # 1.list+ord alist1 = [0] * 26 alist2 = [0] * 26 result = False if len(s1) == len(s2): for i in s1: number = ord(i) - ord('a') alist1[number] += 1 for i in s2: number = ord(i) - ord('a') alist2[number] += 1 if alist1 == alist2: result = True return result print(anagramSolution3('typhon','python'))

时间复杂度：O(n**2) 5.计数比较法（dict计数）

def anagramSolution4(s1,s2): alist1 = list(s1) alist2 = list(s2) result = False count_dict1 = {} count_dict2 = {} if len(s1) == len(s2): for item in alist1: if item in count_dict1: count_dict1[item] += 1 else: count_dict1[item] = 1 for item in alist2: if item in count_dict2: count_dict2[item] += 1 else: count_dict2[item] = 1 if count_dict1 == count_dict2: result = True return result print(anagramSolution4('typhon','python'))

时间复杂度：O(n)

二、数据结构的性能

三、栈与栈的应用

栈：

# 列表的尾作为栈顶 class Stack_End: def __init__(self): self.item = [] def push(self,x): return self.item.append(x) def pop(self): return self.item.pop() def peek(self): return self.item[-1] def size(self): return len(self.item) def isEmpty(self): return self.item == [] # 列表的头作为栈顶 class Stack_First: def __init__(self): self.item = [] def push(self,x): return self.item.insert(0,x) def pop(self): return self.item.pop(0) def peek(self): return self.item[0] def size(self): return len(self.item) def isEmpty(self): return self.item == []

1.简单括号匹配 只有严格按照对称结构的括号才能匹配成功 eg: False:<>()，{(<}>) True:<()>，{(<>)}

from pythonds.basic.stack import Stack_End ipt = input('请输入要匹配的式子') def eq_bracket(ipt): s = Stack_End() result = True bra_l = '(（{[<《' bra_r = ')）}]>》' for i in range(0,len(ipt)): if ipt[i] in bra_l: s.push(ipt[i]) elif ipt[i] in bra_r: a = s.peek() b = ipt[i] if s.isEmpty() or bra_r.index(b) != bra_l.index(a): result = False else: s.pop() if s.isEmpty() and result: result = True else: result = False return result print(eq_bracket(ipt))

时间复杂度:O(n)

2.十进制转化为x进制(x<=16)

from pythonds.basic.stack import Stack_End def ten_trans_x(num,x): ''' 将十进制的数字转化为x进制的数字（x<=16） :param num: 输入的十进制数字 :param x: 目标进制 :return: 输出的x进制数字 ''' s = Stack_End() a = '' num = int(num) x = int(x) digits = '0123456789ABCDEF' while num > 0: num_last = num % x s.push(num_last) num = int(num / x) while not s.isEmpty(): a += digits[s.pop()] return a print(ten_trans_x('125',16))

时间复杂度：O(n)

3.表达式转化 3.1全括号中缀表达式转换为后缀表达式

def full_bre_tran(exp,format): ''' 全括号中缀表达式转化为后缀表达式 :param exp: 输入的表达式（为str） :return: format表达式（前缀或者后缀） ''' ope_stack = Stack_End() ope = '+-*/' exp_list = list(exp) if eq_bracket(exp): if format == 'end': for i in range(0,len(exp)): if exp[i] in ope: ope_stack.push(exp_list[i]) exp_list[i] = '' elif exp[i] == ')': exp_list[i] = ope_stack.pop() elif exp[i] == '(': exp_list[i] = '' else: left_bra = Stack_End() for i in range(0,len(exp)): if exp[i] in ope: ope_stack.push(exp_list[i]) exp_list[i] = '' elif exp[i] == '(': left_bra.push(i) elif exp[i] == ')': exp_list[i] = '' if not ope_stack.isEmpty(): exp_list[left_bra.pop()] = ope_stack.pop() result = [i for i in filter(None,exp_list)] return ''.join(result) # print(full_bre_tran('((A+B)*C)','end')) # print(full_bre_tran('(A+(B*C))','end')) # print(full_bre_tran('(((A+B)*C)-((D-E)*(F+G)))','first')) # print(full_bre_tran('(((A+B)*C)-((D-E)*(F+G)))','end'))

3.2通用中缀表达式转化为后缀

def trans(exp,format): opstack = Stack_End() postfixList = [] if format == 'end': for i in exp: if i == '(': opstack.push(i) elif i == ')': while opstack.peek() != '(': postfixList.append(opstack.pop()) opstack.pop() elif i in '*/': opstack.push(i) elif i in '+-': if not opstack.isEmpty(): if opstack.peek() in '*/': postfixList.append(opstack.pop()) else: opstack.push(i) else: postfixList.append(i) while not opstack.isEmpty(): postfixList.append(opstack.pop()) return ''.join(postfixList) print(full_bre_tran('(A+(B*C))','end')) print(trans('A+B*C','end'))

4.后缀表达式求值

def solve_end(exp): wostack = Stack_End() for i in exp: if i not in '+-*/': wostack.push(i) elif i in '+*': value1 = wostack.pop() value2 = wostack.pop() if i == '*': value = int(value1) * int(value2) else: value = int(value1) + int(value2) wostack.push(int(value)) elif i in '-/': value1 = wostack.pop() value2 = wostack.pop() if i == '/': value = int(value2) / int(value1) else: value = int(value2) - int(value1) wostack.push(int(value)) return wostack.peek() print(solve_end('78+32+/'))