1.递归实现阶乘
def fac(N):
if N==1:
return 1
else:
return N*fac(N-1)
print(fac(3))#6
2.线性搜索与二分搜索实现求平方根
比起线性搜索，二分搜索的计算复杂度更低。
#method1:线性搜索
def sqrt(N):
'''
linear saerch
'''
for i in range(N):
if i*i==N:
return i
#method2:二分法实现搜索
def sqrt1(N):
'''
binary search
'''
low=0
high=N
while lowN:
high=mid
if mid*mid
3.斐波拉契数列
1.method1： 利用递归，涉及到重复计算
2.method2：利用字典，将以前计算的结果保存到字典中去
3.更巧妙的回转方式
ef f(n):
if n==0:
return 0
if n==1:
return 1
return f(n-1)+f(n-2)#f(n) calculate multi-times
#notebook to save the result dic{key,value}
def f2(n,nb={}):
if n in nb:
return nb[n]
if n==0:
return 0
if n==1:
return 1
ans=f2(n-1,nb)+f2(n-2,nb)
nb[n]=ans
return ans
def f3(n):
a=0#n=0
b=1#n=1
for i in range(n):
a, b = b, a + b
return a
print(f3(10))
print(f2(10))
4.栈stack之反转数组
先进先后出 FILO Plates=[ ] plates.append(1) plates.pop() len()
def rev(list):
ans=[]
list1=list.copy()
while len(list1)>0:
element=list1.pop()
ans.append(element)
return ans
list=[1,2,3,4]
print(rev(list))
list.reverse()#调用list自带方法
print(list)
5.队列Queue之求平方
队列FIFO先进先出 pop(-1)
def sqr(list,rev):
list1=list.copy()
ans=[]
while len(list1)>0:
if rev:
ele = list1.pop(-1)
else:
ele = list1.pop(0)
ans.append(ele*ele)
return ans
list=[1,2,3,4,5]
print(sqr(list,1))#[25, 16, 9, 4, 1]
print(sqr(list,0))#[1, 4, 9, 16, 25]
6.判断字符串中a在字符串b前算法
Itertools.groupby()把可迭代对象中相邻的重复元素挑出来放到一起
import itertools
#返回groupby可迭代对象不重复的相邻元素
def check(s):
#如果是空集跟只有‘aaa''bbb'存在则为True
if not s:
return True
list=[i for i,j in itertools.groupby(s)]
if len(list)==1:
return True
if len(list)>2:#肯定b在a前
return False
return list[0]=='a'#判断是否a在前面
a='aaaabbbbbaaaa'
b=''
print(check(b))
7.集合和维式图（利用集合来判断是否存在重复元素)
集合具有互异性、有限性、无序性
Venn Graph &(A interest(B) |(A.union(B) ^A.symmetricdifference(b) A-B(in A but not in B) A<=B(subset) A.add(5) A.remove(5)
def unique(s):
st=set()
for i in s:
if i in st:
return False,st#不包含重复元素
st.add(i)
return True,st
def unique1(s):
st=set(list(s))#利用集合本身的互异性
return len(st)==len(s),st
s='aefgbcdb'
print(unique(s))#(True, {'f', 'd', 'a', 'b', 'e', 'c', 'g'})
print(unique1(s))
8.树和广度优先
Root,leaf,child(left,right),parents,depth 2d-1
Perfect binary tree完全二叉树
Binary search tree 左孩子永远比parent小 右孩子永远比parent大
9.判断是否为回文数Palindrome
method1：利用栈的思想
method2：字符串S[::-1]倒序输出
method3：两边向中间聚合half string（用循环，不用循环）
#判断一个数是否为回文数
def isPalindrome(s):
arr=list(s)#利用栈
for i in s:
x=arr.pop()
if i!=x:
return False
return True
#最简单的方法 利用S[::-1]
def isPalindrome1(s):
return s[::-1]==s
#half of the string
def isPalindrome2(s):
low=0
high=len(s)-1
while low
10.使用三种算法解决two-sum问题
问题描述：给定指定target,求出是集合中哪两个元素之和
method1:2个for;
method2: 字典，set;
method3:排序相加法
ums=[1,4,6,7,1]
t=10
#运用字典/set
def twosum2(nums,t):
nb={}
for i in nums:
if t-i in nb:#key
return True
nb[i]=t-i
return False
def twosum3(nums,t):
nb=set()
for i in nums:
if t-i in nb:#key
return True
nb.add(i)
return False
#运用排序方法,双端比较
def twosum4(nums,t):
nums1=nums.copy()
nums1.sort()
left,right=0,len(nums1)-1
while leftt:
right-=1
if nums1[right] + nums1[left] 
