python算法集锦1-10

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]					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5710717.html