4- 算法练习leetcode.com

0、五大经典算法

动态规划算法----爬楼梯
分治算法--
贪心算法---零钱问题
回溯算法---迷宫问题 --深度优先
分支限界法 ----广度优先

  

1、找出下标范围

4- 算法练习leetcode.com

1、二分法

li = [1,2,3,3,3,4,4,5]

def half_sort(data,value):
low = 0
high = len(li) -1
while low<=high:
mid = (low + high) // 2
if data[mid] == value:
return mid
if data[mid] > value:
# high = mid # mid已经比较过了,可以舍弃掉
high = mid -1
if data[mid] < value:
# low = mid
low = mid + 1 index = half_sort(li,4)
print(index)

2、错误版本

4- 算法练习leetcode.com

3、ok版本

def half_sort(data,value):
low = 0
high = len(li) -1
while low<=high:
mid = (low + high) // 2
if data[mid] == value:
left = mid
right = mid
while data[left] ==value and left>=0: # 左边界
left -= 1
while data[right] == value and right <= len(data): # 右边界
right += 1
return (left+1, right-1) # 稍微调整下标 if data[mid] > value:
high = mid -1
if data[mid] < value:
low = mid + 1
return li = [1,2,3,3,3,4,4,5]
index = half_sort(li,5)
print(index)

2、 返回两个数之和的下标

4- 算法练习leetcode.com

https://leetcode.com/problems/two-sum/?tab=Description

(1)双循环版本:O(n^2)

4- 算法练习leetcode.com4- 算法练习leetcode.com

def findout(li, value):
for i in range(len(li)): # 1,2,5,4
for j in range(i+1,len(li)): # 2,5,4
if li[i] + li[j] == value:
return (i,j) li = [1, 2, 5, 4]
ret = findout(li, 2)
print(ret)

4- 算法练习leetcode.com

 (2)二分法查找:O(nlogn)

li = [1, 2, 5, 4]
target = 5 def bin_search(data_set, val, low, high):
while low <= high:
mid = (low+high) //2
if data_set[mid] == val:
return mid
elif data_set[mid] < val:
low = mid +1
else:
high = mid -1
return def func2():
import copy
li2 = copy.deepcopy(li) # [1, 2, 5, 4]
li.sort() # [1, 2, 4, 5]
for i in range(len(li)):
a = i
b = bin_search(li, target-li[a], i+1, len(li)-1)
if b:
# return (a,b) # 返回的是排序后的li的下标 (0, 2)
return (li2.index(li[a]), li2.index(li[b])) # li.index(4) # 求下标 print(func2())

4- 算法练习leetcode.com

(3)建立下标list

# 建立下标list
li = [1, 2, 5, 4]
target = 5
max_num = 100 def func3():
a = [ None for i in range(max_num+1)]
for i in range(len(li)):
a[li[i]] = i
if a[target-li[i]] != None:
return (a[li[i]],a[target-li[i]]) print(func3())

4- 算法练习leetcode.com  4- 算法练习leetcode.com4- 算法练习leetcode.com4- 算法练习leetcode.com

  (4)dict字典下标表示方式

4- 算法练习leetcode.com  4- 算法练习leetcode.com

3、递归练习1:斐波那契

# 方式1:list写法
def fib(n):
li = []
for i in range(n):
if i == 0 or i ==1:
li.append(1)
else:
li.append(li[i-2]+li[i-1])
return li print(fib(5)) # 方式2:while
def fib2(max):
a, b = 0, 1
count = 0
while count < max:
print(b, end=" ")
b, a = a+b, b
count += 1
fib2(5) # 方式3:yield
def fib2(max):
a, b = 0, 1
count = 0
while count < max:
yield b
b, a = a+b, b
count += 1 for item in fib2(5):
print(item,end=" ")
# 牛逼版本
def fib(n):
if n<=1 :
return 1
else:
return fib(n-2) + fib(n-1) print([fib(n) for n in range(10)])
# 装饰器版本

# 装饰器版本
def cache(func):
cache = {}
def wrap(*args):
if args not in cache:
cache[args] = func(*args)
return cache[args]
return wrap @cache
def fib(n):
if n<=1 :
return 1
else:
return fib(n-2) + fib(n-1) print([fib(n) for n in range(10)])

4、递归问题-爬楼梯

假设你正在爬楼梯,需要n步你才能到达顶部。但每次你只能爬一步或者两步,你能有多少种不同的方法爬到楼顶部?

您在真实的面试中是否遇到过这个题? yes

比如n=3,1+1+1=1+2=2+1=3,共有3中不同的方法

返回 3

题目分析:

**设f(n)为n阶台阶的情况下,所有不同的跳法方法的总和!**
1.如果起始跳一阶的话,剩余的n-1阶就有 f(n-1) 种跳法;
2.如果起始跳二阶的话,剩余的n-2阶就有 f(n-2) 种跳法;
所以f(n) = f(n-1) + f(n-2),实际结果即为斐波纳契数。

def fib(n):
if n<=1 :
return 1
else:
return fib(n-2) + fib(n-1) print(fib(3))
 
一次性走1步,2步,3步???是否正确
def climb(n,steps):
count = 0
if n<=1:
count = 1
else:
for step in steps:
count += climb(n-step, steps)
return count print(climb(3,(1,2,3))) # 一次性走 1,2,3
def fib(n):
if n<=1 :
return 1
else:
return fib(n-2) + fib(n -1) + fib(n-3) # 一次性走 1,2,3
print(fib(3))

5、递归练习2:汉诺塔问题

  汉诺(Hanoi)塔问题:古代有一个梵塔,塔内有三个座A、B、C,A座上有64个盘子,盘子大小不等,大的在下,小的在上(如图)。
有一个和尚想把这64个盘子从A座移到B座,但每次只能允许移动一个盘子,并且在移动过程中,3个座上的盘子始终保持大盘在下,小盘在上。
在移动过程中可以利用B座,要求打印移动的步骤。如果只有一个盘子,则不需要利用B座,直接将盘子从A移动到C。

解决思路:

我们可以倒着想: 
也就是说,

  当有n个时,由于游戏规则,最终必定将第n块由A搬到C,因为这一块最大,无法进行中转;

  同时,当移动n时,A塔只有n,C塔空,则B塔有1~n-1,且按唯一顺序(由小到大)排列。

接下来的问题是:

  1~n-1是怎么从A到B的?此时将B看作目标塔,C作为辅助塔。这个问题就变成了n-1时的情况。。 
  接着刨下去,我们就能够得到仅需解决n=1的情况,由此解决1~n-1运到B的问题

然后别忘了还要把这n-1块从B借A搬到C。而这不过是上述问题把初始塔和辅助塔互换而已。

假设有n个盘子:

  • 1.把n-1个圆盘从A经过C移动到B
  • 2.把第n个圆盘从A移动到C
  • 3.把n-1个小圆盘从B经过A移动到C

总结:汉诺塔移动次数的递推式:h(x)=2h(x-1)+1

4- 算法练习leetcode.com   4- 算法练习leetcode.com  4- 算法练习leetcode.com

    

代码实现

def hanno(n,a,b,c):
if n ==1 :
move(a,c)
else:
hanno(n-1,a,c,b) # 将n-1个盘子从a经过c移动到b
move(a,c) # 将剩余的最后一个盘子从a移动到c
hanno(n-1,b,a,c) # #将n-1个盘子从b经过a移动到c
def move(a,c):
print(a,'-->',c) hanno(3,'柱子A','柱子B','柱子C')

6、贪心算法:零钱

     所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。
 

找零问题:假设商店老板需要找零n元钱,钱币的面额有:100元、50元、20元、5元、1元,如何找零使得所需钱币的数量最少?

def change_money(x):
money = [100, 50, 20, 5, 1]
change = [0,0,0,0,0] for index,item in enumerate(money):
change[index] = x //money[index]
x = x % money[index] # 总钱数除 100 取余 56
if x>0:
print('还剩下',x)
return change print(change_money(456))
1.找零钱问题:假设只有1分、2分、五分、1角、二角、五角、1元的硬币。
在超市结账时,如果需要找零钱,收银员希望将最少的硬币数找给顾客。
那么,给定需要找的零钱数目,如何求得最少的硬币数呢
def change_money2(x):
money = [1, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01]
change = [0, 0, 0, 0, 0, 0, 0]
for index,item in enumerate(money):
change[index] = x // money[index]
x = x % money[index]
if x > 0 :
print('还剩下',x)
new_change = dict(zip(money,change)) # zip拉链
return new_change print(change_money2(12.125))

4- 算法练习leetcode.com

上一篇:Valid Perfect Square


下一篇:深入学习C#匿名函数、委托、Lambda表达式、表达式树类型——Expression tree types