0,1背包问题:我写笔记风格就是想到哪里写哪里,有很多是旧的也没删除,代码内部可能有很多重复的东西,但是保证能运行出最后效果
'''学点高大上的遗传算法'''
'''首先是Np问题的定义:
npc:多项式复杂程度的非确定性问题,
首先是基本的0-1背包问题。 '''
'''给定N个物品和一个背包，物品i的质量是Wi，其价值位Vi，背包的容量为C，问应该
如何选择装入背包的物品，使得转入背包的物品的总价值为最大？
在选择物品的时候，对每种物品i只有两种选择，即装入背包或不装入背包。不能将
物品i装入多次，也不能只装入物品的一部分。因此，该问题被称为0-1背包问题。'''
'''如果穷举就有2^n个需要测试,很大'''
'''其实，0-1背包是DP的一个经典实例，可以用动态规划求解。 DP求解过程可以这样理解：对于前i件物品，背包剩余容量为j时，所取得的最大价值（此时称为状态3）只依赖于两个状态。 状态1：前i-1件物品，背包剩余容量为j。在该状态下，只要不选第i个物品，就可以转换到状态3。 状态2：前i-1件物品，背包剩余容量为j-w[i]。在该状态下，选第i个物品，也可以转换到状态3。 因为，这里要求最大价值，所以只要从状态1和状态2中选择最大价值较大的一个即可。'''
'''算法复杂度基本是O(N)'''
bag_weight=
stone=[]
#stone[i] means (weight, value)
stone.append((,))
stone.append((,))
stone.append((300.9,))
stone.append((400.56,900.56))
stone.append((,1000.598)) stone=sorted(stone) #default sorted by first column of stone ,very convinient
print (stone)
#creat a two-dim list,row i means using the first i stone
#column j means the bag_weight
'''只想到用递归来写,递推还不知道怎么弄'''
#网上说法是不能用递推来写,因为不知道重量的变化,变化太多,不知道要存多少才行.
#下面写出打印的最好的石头组合的index,现在是这个问题比较难!!!!!!!!!!!因为递归问题很难区分这次和上次
#来的index,反复访问很难弄,下面用函数的双返回值来处理这个问题,但是空间开销也是相当大.目测O(N^)
zuhe=[]*len(stone)
def value(num,tmpbag_weight):
if num==:
if tmpbag_weight>=stone[][]: return
else:
return
firstcase=
if tmpbag_weight>=stone[num-][]: firstcase=
firstcase+=stone[num-][]
firstcase+=value(num-,tmpbag_weight-stone[num-][]) secondcase=value(num-,tmpbag_weight) return max(firstcase,secondcase)
print (value(len(stone),bag_weight))
print (zuhe) ###########
print ('妈的我居然写出来了55555555') def value(num,tmpbag_weight):
if num==:
if tmpbag_weight>=stone[][]:
zuhe=[]
return stone[][],zuhe
else:
return ,[]
firstcase=
if tmpbag_weight>=stone[num-][]: firstcase=
firstcase+=stone[num-][]
a,b=value(num-,tmpbag_weight-stone[num-][])
firstcase+=a
c,d=value(num-,tmpbag_weight)
secondcase=c
if firstcase>secondcase:
b.append(num-)
return max(firstcase,secondcase),b
else:
return max(firstcase,secondcase),d
print (value(len(stone),bag_weight))
2.kmp
'''匹配字符串bf算法'''
def search(a,b):#if a in b :return first index else:return None
for i in range(len(b)):
#直接b切片就行了,记住几个常用计数长度更方便
#range[i,i+len(a)] 标示角标从i一直到i+len(a)-1一共len(a)个元素
#切片也类似b[i:i+len(a)]也表示len(a)个元素
if i+len(a)-==len(b):
return None
if b[i:i+len(a)]==a:
return i
print (search('ffg','qfgsdfgsdffg'))
'''下面是KMP算法--看毛片算法'''
'''把复杂度从O(mn)下降到O(m+n)'''
#这个写的很详细,KMP还是要从例子的图形里面分析出来.注意next[]=-,是一种人为的规定,为了识别,你定义-2也一样.
'''http://www.cnblogs.com/yjiyjige/p/3263858.html''' '''先学一下c语言里面的++'''
'''首先要说：a++ = a 和 ++a = a + 1 并不是两个合法的语句。这两个式子
是说 a++ 的值就是 a 的值，而 ++a 的值等于 a+。 注意：我说的是++a和a++的值。 你的这两个表达式不合法！
在C语言中前置和后置自增运算符返回的结果是右值，不能放在等号左侧。
顺便提一下：在C++中，前置自增的结果是左值，可以放在等号左侧。 .int main() {
int b=;
int a=;
++a=b;
a+=;
return ;
} 答案a是1 .int main() {
int b=;
int a=;
b=++a;
a+=;
return ;
} 答案a是5 .int main() {
int b=;
int a=;
a++=b;
a+=;
return ;
} 第四句话不合法,无法运行'''#c++什么鬼 #要先写获取next数组这个函数
#先用暴力方法实现next数组的求法. '''理解:
待处理数组,也就是我们要配出的字符串,比如一个长串里面找一个短的串,那么待处理数组就是这个短的设为p
'''
'''p=abcaab 那么我们的next数组就是-1,0,0,0,1,1
next[i]的招法是符合下面条件的最大的index
.next[i]<i
.设next[i]=k,有p[:k]=p[i-k:i]'''
'''http://www.cnblogs.com/tangzhengyue/p/4315393.html
这个地址里面有一个长的面试题:说的是给一个字符串求他的next数组,下面我来尝试这个next方法
上面写的对不对.
他给的P:
abcaacbbcbadaabcacbd
答案:-10001100000101123400他给的答案做进一步优化了,不止考虑上面3个条件,
也考虑了当前位置,所以把一些项优化到-1了'''
def next_rough(a):
shuchu=[]
shuchu.append(-)
for i in range(,len(a)):
for j in range(i-,-,-):
#这个j循环测试看哪个是k
if a[:j]==a[i-j:i]:
shuchu.append(j)
break
return shuchu
print (next_rough('abcaacbbcbadaabcacbd'))
#成功得到了上面的next数组
#显然这个方法太慢了,应该是O(N^)的.当然当N非常小的时候还是很快的.
#正确的方法有点复杂的,利用的是动态规划来处理这个next数组
#先用next数组进行最后的kmp出结果把.
def kmp(a,b):
i=
j=
nextshuzu=next_rough(a)
while :
if j==len(a):
return i-len(a) #开始index
if i>len(b)-:
return None
if b[i]==a[j]:
i+=
j+=
else:
if nextshuzu[j]==-:
i+=
j=
else:
j=nextshuzu[j] print (kmp('43aa','3ht54543aa43a4a6'))
print (kmp('',''))
#效果还不错. #最后应该用动态规划来写next数组了.
#http://www.cnblogs.com/yjiyjige/p/3263858.html里面写的真的很详细.
#像这种情况，如果你从代码上看应该是这一句：k = next[k];为什么是这样子？你看下面应该就明白了。
#上面这句话在博客里面的说没说完,其实k=next[k]这个吊代码,把2次匹配next给用一个代码写明白了,确实叼.
#下面只需要改成python实现即可.
def next_true(a):
shuchu=[]
shuchu.append(-)
j=
k=-
while (j<len(a)-):
if (k==- or a[j]==a[k]):
j+=
k+=
shuchu.append(k)
else:
k=shuchu[k]
return shuchu
print (next_true('abcaacbbcbadaabcacbd'))
#从结果看完美解决了.
3.遗传算法解背包问题,一写一个晚上没了,干了200行,我理解是这东西就是个类似随机查找的东西,本质很low,但是实用性强,有点像神经网落,普世通用性强.描述性强
缺陷当然是慢!!写写还挺有意思,复习了很多的random函数的使用.这东西不推荐手写大型的,因为有库直接能调用遗传算法.当然现在还有遗传加神经网络的综合体,有点
强.
'''学点高大上的遗传算法'''
import random
print (random.randint(, ))#python 的这个随机正数是包含收尾的,这点要注意.很特俗
'''首先是Np问题的定义:
npc:多项式复杂程度的非确定性问题,
首先是基本的0-1背包问题。 '''
'''给定N个物品和一个背包，物品i的质量是Wi，其价值位Vi，背包的容量为C，问应该
如何选择装入背包的物品，使得转入背包的物品的总价值为最大？
在选择物品的时候，对每种物品i只有两种选择，即装入背包或不装入背包。不能将
物品i装入多次，也不能只装入物品的一部分。因此，该问题被称为0-1背包问题。'''
'''如果穷举就有2^n个需要测试,很大'''
'''其实，0-1背包是DP的一个经典实例，可以用动态规划求解。 DP求解过程可以这样理解：对于前i件物品，背包剩余容量为j时，所取得的最大价值（此时称为状态3）只依赖于两个状态。 状态1：前i-1件物品，背包剩余容量为j。在该状态下，只要不选第i个物品，就可以转换到状态3。 状态2：前i-1件物品，背包剩余容量为j-w[i]。在该状态下，选第i个物品，也可以转换到状态3。 因为，这里要求最大价值，所以只要从状态1和状态2中选择最大价值较大的一个即可。'''
'''算法复杂度基本是O(N)'''
bag_weight=
stone=[]
stone.append((,))
stone.append((,))
stone.append((,))
stone.append((,))
stone.append((,)) # 举个例子，使用遗传算法解决“-1背包问题”的思路：-1背包的解可以编码为一串0-
#字符串（：不取，：取） ；首先，随机产生M个0-1字符串，然后评价这些0-1字
#符串作为0-1背包问题的解的优劣；然后，随机选择一些字符串通过交叉、突变等操作产生下
#一代的M个字符串，而且#较优的解被选中的概率要比较高。这样经过G代的进化后就可能会产生
#出0-1背包问题的一个“近似最优解”。 #遗传算法的问题
'''1.编码:需要将问题的解编码成字符串的形式才能使用遗传算法。最简单的一种编码方式是二进制编码
，即将问题的解编码成二进制位数组的形式。例如，问题的解是整数，
那么可以将其编码成二进制位数组的形式。将0-1字符串作为0-1背包问题的解就属于二进制编码。
.遗传算法有3个最基本的操作：选择，交叉，变异。
下面处理第一个选择问题:
.问题:有n个物体,他们被选择的概率是p1,...pn.和为1.
求一个函数每次根据这个概率随机出一个物体.
这个用random(,)函数随便写很简单--他们管这个叫轮盘赌算法下面我定义他是rws(Roulette
Wheel Selection )函数.
第二个问题交叉:
http://www.cnblogs.com/heaad/archive/2010/12/23/1914725.html
这里面只写了原理没有实现,最后用一个库包来实现的,我打算还是自己手写一次
根据他里面的思想,手动实现遗传算法.
原理写下来:
交叉(Crossover)：2条染色体交换部分基因，来构造下一代的2条新的染色体。例如：
变异(Mutation)：在繁殖过程，新产生的染色体中的基因会以一定的概率出错，称为
变异。变异发生的概率记为Pm 。例如： '''
import random a=[0.1,0.2,0.3,0.4]#物体被选择的概率,这个概率就是这个物体的效果函数
def rws(a):
#生成累加概率 b=random.random()
for i in range(len(a)):
j=(sum(a[:i+]))
if b<j:
return i #return the index of selection one in a
#效果还可以
import numpy as np
def crossover_and_mutation(a,b,mutation_rate):#代表一次进化,a,b都是二进制的数
#我认为把a,b都转化成2进制然后转化为字符串就容易变化多了.所以初始化的时候就弄成2进制的 #直接字符串操作,很方便.
#生成2个需要变化的开始index和结尾index
kaishi=random.randint(,len(stone))
jieshu=random.randint(,len(stone))
start=min(kaishi,jieshu)
end=max(kaishi,jieshu)
#开始交换
a=a[:start]+b[start:end+]+a[end+:]#切片的角标非常贴心,如果角标超了自动返回空list.
b=b[:start]+a[start:end+]+b[end+:] #继续开始突变mutation
#生成一个突变的index,每一次突变基因的个数=mutation_rate*len(stone)
## np.random.randint(low[, high, size]) 返回随机的整数，位于半开区间 [low, high)。
#下面这行就是闭区间的随机取一个
#再加一行,让mutation_rate变动来模拟是否突变:
mutation_rate=random.random()*mutation_rate
mutation_index=np.random.random_integers(,len(stone)-,int(mutation_rate*len(stone)))
mutation_index=set(mutation_index) #开始突变:
after_mut_a='' for i in range(len(a)):
if i in mutation_index and a[i]=='':
after_mut_a+=''
continue #这地方要加入continue
if i in mutation_index and a[i]=='':
after_mut_a+=''
continue
else:
after_mut_a+=a[i]
#b完全类似
mutation_index=np.random.random_integers(,len(stone)-,int(mutation_rate*len(stone)))
#开始突变:
after_mut_b='' for i in range(len(b)):
if i in mutation_index and b[i]=='':
after_mut_b+=''
continue
if i in mutation_index and b[i]=='':
after_mut_b+=''
continue
else:
after_mut_b+=b[i]
return after_mut_a,after_mut_b print (crossover_and_mutation('','',0.5))
print ('上面是一次进化的结果') c=**len(stone)-
print (c)
def init(n):#初始化n这么多个生物
creature=[]
for i in range(n):
t=random.randint(, c)
t=bin(t)
t=t[:] q=len(stone)-len(t)
t=''*q+t
creature.append(t)
return creature #下面写一个二进制的价值函数,也就是这个二进制是否符合背包的规则,和他的价值
def value_of_pick(a):
weight=
for i in range(len(a)):
weight+=int(a[i])*stone[i][]
value=
for i in range(len(a)):
value+=int(a[i])*stone[i][]
if weight>bag_weight:
value/=
return value
def all_value(a_all):
b=[] for i in range(len(a_all)):
b.append(value_of_pick(a_all[i]))
return b #下面开始跑遗传
a_all=init()
all_the_value=all_value(a_all) he=sum(all_the_value)
for i in range(len(all_the_value)):
all_the_value[i]/=he
#上步是归一化
#先选2个,然后进化
for i in range():#进化50次
first=rws(all_the_value)
second=rws(all_the_value)
#这里假设自己和自己也能繁殖..
a,b=crossover_and_mutation(a_all[first],a_all[second],0.3)
a_all.append(a)
a_all.append(b)
all_the_value=all_value(a_all) he=sum(all_the_value)
for i in range(len(all_the_value)):
all_the_value[i]/=he
jieguo=(all_value(a_all))
print (max(jieguo))
#下面我们找到这个答案的具体的pick方法.
index_final=np.argmax(np.array(jieguo))
print (a_all[index_final])
print ('总结取法',end=''),print(a_all[index_final],end=''),print('价值',end=''),print(max(jieguo))
4.hash表数据结构的实现
'''Hash表'''
'''核心就是hash函数的设计：
特点：在构造Hash函数时应尽量考虑关键字的分布特点来设计函数
使得Hash地址随机均匀地分布在整个地址空间当中。
)直接定址法
取关键字或者关键字的某个线性函数为Hash地址，即address(key)=a*key+b;如
知道学生的学号从2NoneNoneNone开始，最大为4NoneNoneNone，则可以将address(key)=key-2NoneNoneNone作为Hash地址。
)平方取中法
对关键字进行平方运算，然后取结果的中间几位作为Hash地址。假如有以下关
键字序列{，，}，平方之后的结果为{，，19NoneNone96}，那么可以取{，，NoneNone}
作为Hash地址。
)折叠法
将关键字拆分成几部分，然后将这几部分组合在一起，以特定的方式进行转化形
成Hash地址。假如知道图书的ISBN号为89None3--，可以将address(key)=+None3+++3作为Hash地址。
)除留取余法
如果知道Hash表的最大长度为m，可以取不大于m的最大质数p，然后对关键字进
行取余运算，address(key)=key%p。
在这里p的选取非常关键，p选择的好的话，能够最大程度地减少冲突，p一般取不
大于m的最大质数。'''
'''5.Hash表的优缺点 Hash表存在的优点显而易见，能够在常数级的时间复杂度上进行查找，并且插入数据
和删除数据比较容易。但是它也有某些缺点，比如不支持排序，一般比用线性表存储需要更
多的空间，并且记录的关键字不能重复。''' a=[,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,]
class hashnode():
def __init__(self,data):
self.data=data;
self.next=None #下面写的是取mod的方法：一般除数取比len(表)小的最大素数。
#获取除数
import math
b=len(a) if b==:
c=
if b==:
c=
if b==:
c= if b>: def sushu(b):
for i in range(b-,,-):
k=None for j in range(,int(math.sqrt(i))+): if i%j==None:
break if j==int(math.sqrt(i))+:
k= if k==: return i
c=sushu(b)#除数就是c
#下面建立hash 表 hashlist=[None]*c
print (c)
for i in range(len(a)):
hashtmp=a[i]%c if hashlist[hashtmp]==None:
hashlist[hashtmp]=hashnode(a[i])
else:
head=hashlist[hashtmp]
while : if head.next!=None:
head=head.next
continue
else:
head.next=hashnode(a[i])
break
print (hashlist[].next.next.data)
print ()
#然后添加元素。直接复制上面的部分代码即可。都类似的。
def add(one): hashtmp=one%c if hashlist[hashtmp]==None:
hashlist[hashtmp]=hashnode(one)
else:
head=hashlist[hashtmp]
while : if head.next!=None:
head=head.next
continue
else:
head.next=hashnode(one)
break
add()
print (hashlist[]) def delme(two):
hashtmp=two%c if hashlist[hashtmp]==None:
pass
else:
head=hashlist[hashtmp]
while : if head.data==two:
head.data=None
if head.next!=None:
head=head.next
continue
if head.next==None:
break
delme()
print (hashlist[]) #下面写查询,这个写的是全部查询，找到所有等于a的hashlist里面的元素的个数
def search(a):
hashtmp=a%c
b=
head=hashlist[hashtmp]
while :
if head.data==a:
b+=
if head.next!=None:
head=head.next
continue
if head.next==None:
break
return b
print (search())
#曾，删，改，查，建立，都有了
#下面写个修改。这个修改貌似很多数据结构不写这个方法。
def change(two,three):
hashtmp=two%c if hashlist[hashtmp]==None:
pass
else:
head=hashlist[hashtmp]
while : if head.data==two:
head.data=three
if head.next!=None:
head=head.next
continue
if head.next==None:
break
change(,)
#因为把所有的2都改成了3所以下面的搜索会变成0
print (search())
print (search()) #其实这个改有很大问题，因为他没有改变hash的东西，是否需要重新建立改完东西的hash索引，这个
#是需要讨论的，但是本质都不难。这里面写的change只是把原来放2的地方数据都改成了3,。所以你找3还是找不到新修改
#的那8个3，还是最开始的那8个3.ps：出事数据里面是8个2 ，8个3的。
5.位图法的实现
##位图大发好神奇 ''' 1、给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何
快速判断这个数是否在那40亿个数当中
首先，将这40亿个数字存储到bitmap中，然后对于给出的数，判断是否
在bitmap中即可。 位图和位向量
所谓位向量法，其实就是使用一串二进制串来表示一组数字集合的方法。
比如，我们知道一个byte = 8bit，表示成二进制串就是：.这里我们就得到
了八个可用的符号位，假如我们作如下规定
）符号位为1的，说明存在于我们的数字集合中
）符号位为0的，说明不在我们的数字集合中
那么，二进制串01010101，表示的数字集合为{,,,} （注意，计算机通常都是从0
开始计算的）
。。
我们知道位图的数据结构就是一个数组，而位图的操作（算法）基本依赖于下面3个元操作 set_bit(char x, int n); //将x的第n位置1，可以通过x |= (1 << n)来实现 clr_bit(char x, int n); //将x的第n位清0，可以通过x &= ~(1 << n)来实现 get_bit(char x, int n); //取出x的第n位的值，可以通过(x >> n) & 1来实现
''' #下面用python手动实现。python所有的数本质都是2进制，可以直接用位运算。
#举一个例子，一个集合里面有数字1,, 那么我们用二进制010101 来表示。也就是第一个0表示没有数字0，然后1表示
#有数字1，0表示没有2, 1表示有数字3, 下一位0又表示没有数字4，最后一个1表示有数字5.
#这样用一个数字就表示了函数数字1,,5这个信息了。问题是python的二进制是从右边开始算的。所以我们再反转一下
#用101010来表示1,,5存在这个信息就行了。
b=[,,,,,]
def init(a):#首先建立第一个数字存在的信息
return <<a
chushihua=init(b[]) for i in range(len(b)):
if i>=:
chushihua=chushihua |(<<b[i])
print (bin(chushihua))#效果不错
#下面是查询一个数字是否在chushihua里面
def search(chushihua,a):
return (chushihua>>a) &
print (search(chushihua,))
print (search(chushihua,))
print (search(chushihua,))
print (search(chushihua,))
#成功解决这个问题。
#还有一个删除函数。比如我有一个操作把所有等于8的数从集合中删除。下面来给他写出来
#思路也不难，比如删除8：我就做一个011111111，然后跟chushihua取交就完了。这地方有那么一点点的复杂。trick
def delme(chushihua,a):
chushihua=(chushihua &(~(<<a)))
return chushihua
chushihua=delme(chushihua,)
#删除8之后找8
print('删除8之后找8')
print (bin(chushihua))
print (search(chushihua,)) #下面没事闲的测试一下，利用random
import numpy as np #这模块有int32限制。。python 这个东西有问题，太大的数会出现错误。
b=np.random.random_integers(,,)#先弄10万个大数。
b=[,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,]
b=b*
#下面就是上面的代码copy
def init(a):#首先建立第一个数字存在的信息
return <<a
chushihua=init(b[]) for i in range(len(b)):
if i>=:
chushihua=chushihua |(<<b[i])
# python 这个东西有问题，太大的数会出现错误。！！！！！！！
#这地方不太清楚，会不会是数字个数太多，导致误差，然后random时候会bug
#后面我改用自己创造的数据然后*，发现效果很好，这个bug先放着问问别人。
#下面是查询一个数字是否在chushihua里面 print ('先用自带的in测试一下')
print ( in b)
print ('再用我的函数测试一下')
print (search(chushihua,))
print (search(chushihua,))
print (search(chushihua,))
print (search(chushihua,))
#成功解决这个问题。
#还有一个删除函数。比如我有一个操作把所有等于8的数从集合中删除。下面来给他写出来
#思路也不难，比如删除8：我就做一个011111111，然后跟chushihua取交就完了。这地方有那么一点点的复杂。trick
def delme(chushihua,a):
chushihua=(chushihua &(~(<<a)))
return chushihua
chushihua=delme(chushihua,)
#最后很明显的看出来，我写的search比自带的int快99999999呗哈哈
6.最长公共子序列问题
'''最长公共子序列：显然动态规划'''
'''经过画图分析，显然是2阶动态规划问题'''
'''设f(a,b,i,j)表示a从0到i的子串，和b从0到j的子串这2个子串的最长公共序列的长度'''
'''那么f(a,b,i,j)是从f(a,b,i-1,j),f(a,b,i,j-1),f(a,b,i-1,j-1)里面开发出来的'''#具体直接写代码。
def f(a,b,i,j):
if i==:
if a[] in b:
return
else:
return
if j==:
if b[] in a:
return
else:
return
case1=case2=case3=
if a[i]==b[j]:
case1=+f(a,b,i-,j-)
if a[i]!=b[j]:
case2=f(a,b,i-,j)
case3=f(a,b,i,j-)
return max(case1,case2,case3)
a='343242dsfd'
b='dsfds'
print (f(a,b,len(a)-,len(b)-))
#上面很简单，3分钟搞定。男的是要把这个解解出来，而不仅仅是输出一个数字。
#这个跟背包问题很像，递归里面开数组。不是太好写。# 下面开始尝试。keyword:多返回值函数 def f(a,b,i,j):
if i==:
if a[] in b:
return ,a[]
else:
return ,''
if j==:
if b[] in a:
return ,b[]
else:
return ,''
case1=case2=case3=
if a[i]==b[j]:
case1=+f(a,b,i-,j-)[]
case1_data=f(a,b,i-,j-)[]+a[i]
if a[i]!=b[j]:
case2=f(a,b,i-,j)[]
case2_data=f(a,b,i-,j)[]
case3=f(a,b,i,j-)[]
case3_data=f(a,b,i,j-)[]#如果有相同长度的解，应该返回最前面的。那么case2和case3如果相同呢？？？？？？？？
#我认为这个是一个相当男的bug了，弄点诡异数据来测一测。
#然而经过我长时间的分析，这个bug其实是没有的，具体很复杂，不容易说明白，
#结论我先说一下，就是这个代码
if case1>case2 and case1>case3:
return case1,case1_data
if case2>=case1 and case2>=case3: #这个代码case2》=case3为什么这么写可以，也就是说如果相等，我还是
#只需要返回case2即可，舍弃case3.我尝试一下说明白这个取舍问题。
#道理就是你的这种取舍，考虑的前提就是case2里面最后一个元素被使用到了，然而
#你如果发生bug那么就必然发生这种情况，下面再让i+，j+1后，如果用case3里面的情况
#会添加一个元素得到的长度比case2里面的长。但是这是不可能的，原因就是上一步
#已经保证了case2里面最后一个元素使用过了。总之很难说清楚的东西。
return case2,case2_data
if case3>=case1 and case3>=case2:
return case3,case3_data a='babax'
b='bbaxy'
print (f(a,b,len(a)-,len(b)-))
7.最长公共子串
'''最长公共子串'''
'''也是动态规划'''
def com(a,b,i,j): #得到a，b的公共子串并且子串以a[i]和b[j]作为结尾的长度,
#然后把他们保存起来用下面的get函数，然后我们再取这个矩阵最大的就行了
if i==:
if b[j]==a[i]:
return
else:
return
if j==:
if a[i]==b[j]:
return
else:
return
if a[i]==b[j]:
return com(a,b,i-,j-)+
else:
return
def get(a,b):
save=[]
for i in range(len(a)):
for j in range(len(b)):
save.append(com(a,b,i,j))
return max(save)
print (get('aa3232','aaa783232'))
#效果还不错。
#下面还是继续写，把这个最长子串的组合写出来。 def com(a,b,i,j): #得到a，b的公共子串并且子串以a[i]和b[j]作为结尾的长度,
#然后把他们保存起来用下面的get函数，然后我们再取这个矩阵最大的就行了
if i==:
if b[j]==a[i]:
return ,a[i]
else:
return ,''
if j==:
if a[i]==b[j]:
return ,a[i]
else:
return ,''
if a[i]==b[j]:
return com(a,b,i-,j-)[]+,com(a,b,i-,j-)[]+a[i]
else:
return ,''
def get(a,b):
save=[]
for i in range(len(a)):
for j in range(len(b)):
save.append(com(a,b,i,j))
return max(save)
print (get('aa3232','aaa783232'))
#一样轻松写出。
8.全域散列法,随机hash的思想
'''全域散列,随机hash技术'''
'''全域散列法在执行的开始时,就从一组精心设计的函数总,随机的选择一个作为散列函数,
随机化保证了没有哪一个输入会导致最坏性能情况的发生.'''
'''构造这个函数族很复杂,也不是非常复杂:
原范围是p,分类后的曹数是m,也就是把p范围内的数都分布到m个曹当中 h(k)_(a,b)=((ak+b)modp)modm
那么因为p,m去定.a跑遍1到p-,b跑遍1到p就构造了p(p-)这么多个函数.他的性质是Pr(h(k)_(a,b)=h(k)_(a,b)). '''
9.二叉搜索树:
#coding:utf-8
#首先是二叉搜索树的定义:
'''若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的
值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。'''
'''二叉搜索树''''''二叉搜索树里面的元素都是不重复的
所以当插入一个元素时候先搜索他是否在树里面,如果在就不插入了,
不果不在就插入''' class node():
def __init__(self,data):
self.left=None
self.right=None
self.data=data
#不能把类写在另一个类里面
class ercha(): def __init__(self):
self.head=node(None)
def input(self,a):
old_head=self.head
while 1: if self.head.data==None:
self.head.data=a
self.head=old_head
return
if self.chazhao(a)==None:
if a<self.head.data and self.head.left==None:
self.head.left=node(a)
self.head=old_head
return
if a<self.head.data and self.head.left!=None:
self.head=self.head.left
continue
if a>self.head.data and self.head.right==None:
self.head.right=node(a)
self.head=old_head
return
if a>self.head.data and self.head.right!=None:
self.head=self.head.right
continue def chazhao(self,a):
old_head=self.head
while 1:
if self.head==None:
self.head=old_head
return None
if a==self.head.data:
new_head=self.head
self.head=old_head
return new_head
if a>self.head.data:
self.head=self.head.right
continue
if a<self.head.data:
self.head=self.head.left
def delet(self,a):
if self.chazhao(a)==None:
print ('错误')
return None
else:
if self.chazhao(a).left==None and self.chazhao(a).right==None:
t=self.chazhao(a)
# t=None这里面写这个不好使.对象不能直接赋值?
t.data=None
if self.chazhao(a).left==None and self.chazhao(a).right!=None:
pass
def listhua(self,a):#把root=a的子树,中序遍历的结果都转化成list来查询
#这个递归代码不能实际使用,因为速度O(N)了,跟需要logn矛盾.
b=[]
if a==None:
return b
if a!=None:
if a.left==None and a.right==None:
return [a]
else:
a1=self.listhua(a.left)
a2=[a]
a3=self.listhua(a.right)
if a1==None:
a1=[]
if a3==None:
a3=[]
return a1+a2+a3
#删除还是没写明白 shu=ercha()
shu.input(3) shu.input(2) shu.input(6)
shu.input(9)
listhuazhihou=shu.listhua(shu.chazhao(3))
print (listhuazhihou[0].data)
#自己写的不对,还是贴个别人的吧
class TreeNode:
def __init__(self,val):
self.val=val;
self.left=None;
self.right=None;
def insert(root,val):
if root is None:
root=TreeNode(val);
else:
if val<root.val:
root.left=insert(root.left,val); #递归地插入元素
elif val>root.val:
root.right=insert(root.right,val);
return root; def query(root,val):
if root is None:
return ;
if root.val is val:
return ;
if root.val <val:
return query(root.right,val); #递归地查询
else:
return query(root.left,val);
def findmin(root):
if root.left:
return findmin(root.left);
else:
return root; def delnum(root,val):
if root is None:
return ;
if val<root.val:
return delnum(root.left,val);
elif val>root.val:
return delnum(root.right,val);
else: # 删除要区分左右孩子是否为空的情况
if(root.left and root.right): tmp=finmin(root.right); #找到后继结点
root.val=tmp.val;
root.right=delnum(root.right,val); #实际删除的是这个后继结点 else:
if root.left is None:
root=root.right;
elif root.right is None:
root=root.left;
return root; #測试代码
root=TreeNode();
root=insert(root,);
root=insert(root,);
root=insert(root,); #print query(root,);
print (query(root,))
root=delnum(root,)
print (query(root,))