LeetCode 학습노트

#1. （1，1，2，3，5，8,... ）， （ ， ）


#  。 2**n, n+1， 
def fibnacci(n):
    if n==0 or n==1:
        return 1 # 
    else:
        return fibnacci(n-1)+fibnacci(n-2)# ， 
@cal_time# 
def fib1(n):
    return fibnacci(n)

# 。 n, n,
@cal_time
def fib2(n):
    li=[1,1]
    for i in range(2,n+1):
        li.append(li[-1]+li[-2])
    return li[n]

# 。 n
def fib3(n):
    a=1
    b=1
    c=1
    for i in range(2,n+1):
        c=a+b
        a=b
        b=c
    return c


print(fib1(33))

# 
import time
def cal_time(func):
    def wrapper(*args,**kwargs):
        t1=time.time()
        result=func(*args,**kwargs)
        t2=time.time()
        print("%s running time:%s secs."%(func.__name__,t2-t1))
        return result
    return wrapper

# ， 
def hanoi(n,A,B,C):
    if n>0:
        hanoi(n-1,A,C,B)
        print('%s->%s'%(A,C))
        hanoi(n-1,B,A,C)
hanoi(3,'A','B','C')

# （2 ）： O(n)， O(logn)
li=[1,2,5,67,2,6,7]
6 in li#True
li.index(6)#6 5
# ，O（n）
def line_search(num,li):
    count=0
    for i in li:
        if i==num:
            return count
        else:
            count+=1
    return -1
print(line_search(67,li))
# O(logn), 
def bin_search(li,val):
    low=0
    high=len(li)-1
    while low<=high:
        mid=(low+high)//2
        if li[mid]==val:
            return mid
        elif li[mid]value:
            bin_search_rec[data_set,value,low,mid-1]
        else:
            bin_search_rec[data_set,value,low+1,high]
    else:
        return -1

# 
# 
arr=[1,2,4,1,7,8,3]
def rec_opt(arr,i):
    if i==0:
        return arr[0]
    elif i==1:
        return max(arr[0],arr[1])
    else:
        A=rec_opt(arr,i-2)+arr[i]
        B=rec_opt(arr,i-1)
        return max(A,B)
# 
def dp_opt(arr):
    opt=np.zeros(len(arr))
    opt[0]=arr[0]
    opt[1]=max(arr[0],arr[1])
    for i in rang(2,len(arr)):
        A=opt[i-2]+arr[i]
        B=opt[i-1]
        opt[i]=max(A,B)
    return opt(len(arr)-1)


arr=[3,34,4,12,5,2]
def rec_subset(arr,i,s):
    if s==0:
        return True
    elif i==0:
        return arr[0]==s
    elif arr[i]>s:
        return rec_subset(arr,i-1,s)
    else:
        A=rec_subset(arr,i-1,s-arr[i])
        B=rec_subset(arr,i-1,s)
        return A or B
def dp_subset(arr,S):
    subset=np.zeros((len(arr),S+1),dtype=bool)
    subset[:,0]=True
    subset[0,:]=False
    subset[0,arr[0]]=True
    for i in rang(1,len(arr)):
        for s in range(1,S+1):
            if arr[i]>s:
                subset[i,s]=subset[i-1,s]
            else:
                A=subset[i-1,s-arr[i]]
                B=subset[i-1,s]
                subset[i,s]=A or B
    r,c=subset.shape
    return subset[r-1,c-1]