这次是基础版的最后一章，本章的内容是前缀树、贪心算法、递归。本章内容个人认为是基础算法中最重要的内容，欢迎大佬指点！！
# #前缀树和贪心算法
# #前缀树
# class TrieNode(object):
# def __init__(self):
# self.path=0
# self.end=0
# self.thenext=[None]*26
#
# class Trie(object):
# def __init__(self):
# self.root=TrieNode()
#
# def insert(self,word): #加入
# if word==None:
# return
# word=list(word)
# node=self.root
# node.path+=1
# for i in word:
# index=ord(i)-ord("a") #简单起见，只设置了为小写字母的字符串
# if node.thenext[index]!=None:
# node.thenext[index]=TrieNode()
# node=node.thenext[index]
# node.path+=1
# node.end+=1
#
# def search(self,word): #查询word之前加入过几次
# if word==None:
# return 0
# word=list(word)
# node=self.root
# for i in word:
# index=ord(i)-ord("a")
# if node.thenext[index]==None:
# return 0
# node=node.thenext
# return node.end
#
# def prefixNumber(self,pre): #查询以pre为前缀的单词有哪些
# if pre==None:
# return 0
# pre=list(pre)
# node=self.root
# for i in pre:
# index=ord(i)-ord("a")
# if node.thenext[index]==None:
# return 0
# node=node.thenext
# return node.path
#
# def delete(self,word):
# if self.search(word)!=0:
# word=list(word)
# node=self.root
# node.path-=1
# for i in word:
# index=ord(i)-ord("a")
# if node.thenext[index].path-1==0:
# node.thenext[index]=None
# return
# node=node.thenext[index]
# node.path-=1
# node.end-=1
'''
前缀树只是为了引出贪心算法，无需深究
'''
#贪心算法
#在某一个标准以下，优先考虑最满足的样本，最后考虑最不满足的样本，最终得到一个答案的算法，叫做贪心算法。
# #一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。
# # 给你每一个项目开始的时间和结束的时间(给你一个数组，里面是一个个具体的项目)，你来安排宣讲的日程，要求会议室进行宣讲的场次最多。
# #[[start,end],[start,end]]
# def bestArrange(program,start):
# program=sorted(program,key=lambda x:(x[1],x[0]),reverse=False)
# for i in program:
# if i[0]<=start:
# start=i[1]
# print(i)
# #一块金条切一次就要花和长度一样的铜板，给定一个数组将金条分成和数组的大小，求一个花费铜板最少的方法
# def bestArrange(program):
# s=0
# while len(program)>1:
# program=list(program)
# program.sort()
# a,b=program.pop(0),program.pop(0)
# summ=a+b
# s+=summ
# program.append(summ)
# print(summ)
# return s
#
# arr=[10,30,30,35]
# print(bestArrange(arr))
# #输入:数组costs，数组profits，正数k，正数m
# #costs表示每个项目的花费，profits表示每个项目的利润，k表示只能做k各项目，m表示初始资金
# #求一种方法是最后的钱最多
# def bestArrange(costs,profits,k,m):
# arr=[]
# allarr=[]
# for i in range(len(costs)):
# arr.append(costs[i])
# arr.append(profits[i])
# allarr.append(arr)
# arr=[]
# allarr=sorted(allarr,key=lambda x:(x[1],x[0]),reverse=True)
# while k>0:
# for i in range(len(allarr)):
# if allarr[i][0]<=m:
# m+=allarr[i][1]
# print(allarr.pop(i))
# k-=1
# break
# if i==len(allarr)-1:
# return m
# return m
#
# coust=[1,1,2,2,3,4]
# profits=[1,4,3,7,2,10]
# k=4
# m=1
# m=bestArrange(coust,profits,k,m)
# print(m)
# #N皇后问题
# #在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行不同列，也不在同一条斜线上，问有多少种摆法
# #N=0,return 1 ; N=2或3,return 0 ; N=8,return 92
# #从第0行开始，for j in range(n)，判断第i行的j位置是否合规，如果合规把j赋值在i行上
# def procsess(record,i,n):
# if i==n:
# return 1
# res=0
# for j in range(n): #i为纵向与n和k对应，j为横向与record(k)对应
# if isValid(record,i,j):
# record[i]=j
# res+=procsess(record,i+1,n)
# return res
#
# def isValid(record,i,j): #遍历i以前的行，如果i行上的j位置=k行的位置 或者 k行的位置到i行j位置的横向距离=i行到k行的纵向距离 则不合规
# for k in range(i):
# if j==record[k] or abs(record[k]-j)==abs(i-k):
# return False
# return True
#
# def go(n):
# record=[None]*n
# return procsess(record,0,n)
#
# print(go(15))
'''
'''
#暴力递归
#1.把问题转化为规模缩小了的同类问题的子问题
#2.有明确的不需要继续进行递归的条件(base case)
#有当得到了子问题的结果之后的决策过程
#不记录每一个子问题的解
# #汉诺塔问题
# #打印n层汉诺塔从最左边移动到最右边的全部过程:把n层从大到小的圆盘从左移到右，全程不能让大圆盘压住小圆盘
# #3层汉诺塔问题:1、2、3代表三个从小到大的圆盘，[][][]代表三个杆子。
# # [123][][]->[23][][1]->[3][2][1]->[3][12][]->[][12][3]->[1][2][3]->[1][][23]->[][][123]
# #第一步:把左杆的前n-1个移到中杆去
# #第二步:把左杆的第n个移到右杆去
# #第三步:把中杆的n-1移会左杆
#
# def func(n, thefrom, to, other):
# if n==1:
# print ("move 1 form" + thefrom + "to" + to)
# else:
# func(n - 1, thefrom, other, to)
# print("move " + str(n) +" form" + thefrom + "to" + to)
# func(n - 1, other, to, thefrom)
#
# def func2(rest,down,thefrom,to,other):
# if rest==1:
# print("move " + str(down) +" form" + thefrom + "to" + to)
# else:
# func2(rest-1,down-1,thefrom,other,to)
# func2(1,down,thefrom,to,other)
# func2(rest-1,down-1,other,thefrom,to)
#
# func2(3,3,"左","右","中")
# print("//")
# func(3,"左","右","中")
# #打印一个字符串的全部子序列，包括空字符
# #"abc"的子序列为["abc","ab","ac","a","bc","b","c",None]
# def process(word,i,res,helplist):
# if i==len(word):
# helplist.append(res)
# return
# reskeep=res.copy()
# reskeep.append(word[i])
# process(word,i+1,reskeep,helplist)
# resnokeep=res.copy()
# process(word,i+1,resnokeep,helplist)
# return helplist
#
# print(process("abc",0,[],[]))
# #打印一个字符的全排列
# def digui(chs,i,res):
# if i==len(chs):
# res.append(chs)
# # print(chs)
# return
# visit={}
# for j in range(i,len(chs)):
# if chs[j] not in visit:
# visit[chs[j]]=True
# chs2=chs.copy() #因为python底层list的赋值是直接赋值给地址，所以不能简单的交换
# chs[i], chs[j] = chs[j], chs[i]
# digui(chs,i+1,res)
# chs=chs2.copy()
# return res
#
# chs="111"
# chs=list(chs)
# res=digui(chs,0,[])
# print(res)
# # res2=set()
# # for i in res:
# # res2.add("".join(i))
# # print(res2)
# #给定一个数组arr，代表数值不同的纸牌排成一条线。玩家A、B一次拿走每张纸牌，但是每次只能拿走最边上的纸牌。返回胜者的分数
# def f(arr,L,R):
# if L==R:
# return arr[L]
# return max(arr[L]+s(arr,L+1,R),arr[R]+s(arr,L,R-1))
# def s(arr,L,R):
# if L==R:
# return 0
# return min(f(arr,L+1,R),f(arr,L,R-1))
# def win(arr):
# return max(f(arr,0,len(arr)-1),s(arr,0,len(arr)-1))
#
# arr=[1,2,5,6,2,1,100]
# print(win(arr))
# #给你一个栈，请你逆序这个栈，不能申请其他数据结构，只能使用递归函数
# #python没有栈，只需要把它理解为一个先进后出的列表就行
# def f(thelist): #返回最下面的值
# result=thelist.pop()
# if thelist==[]:
# return result
# last=f(thelist)
# thelist.append(result)
# return last
#
# def reverse(thelist):
# if thelist==[]:
# return
# i=f(thelist)
# reverse(thelist)
# thelist.append(i)
# return thelist
# a=[1,2,3,4]
# print(reverse(a))
# #规定1和A对应，2和B对应......
# #那么"111"，可以转化为"AAA"、"AK"、"KA"
# #给定一个字符串，返回有多少种转化结果
# def process(chs,i):
# if i==len(chs):
# return 1
# if chs[i]=="0":
# return 0
# if chs[i]=="1":
# res=process(chs,i+1)
# if i="0"and chs[i+1]<="6":
# res+=process(chs,i+2)
# return res
# return process(chs,i+1)
#
# print(process("111",0))
# #给定两个长度都为N的数组，分别代表物品的重量和价值。给定一个正数bag，via哦是一个载重bag的袋子，问能装下多少价值的东西
# def process(weight,values,i,aweight,bag):
# if aweight>bag:
# return 0
# if i==len(weight):
# return 0
# return max(process(weight,values,i+1,aweight,bag),process(weight,values,i+1,aweight+weight[i],bag)+values[i])
#
# def process2(weight,values,i,aweight,avalue,bag):
# if aweight>bag:
# return 0
# if i==len((weight)):
# return avalue
# return max(process2(weight,values,i+1,aweight,avalue,bag),process2(weight, values, i+1, aweight+weight[i], avalue+values[i], bag))
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）