• 基本结构回顾练习题
• 递归
  • 要点：
  • 递归作图：
  • 经典问题
  • 练习题
  • 优化问题和贪心策略

基本结构回顾练习题

1. 实现一个MyQueue类，该类用两个栈来实现一个队列。

queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false
你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size 和 is empty 操作是合法的。

2. 请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。

3. 用队列实现，给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值

## 1.用两个栈实现队列
class myQueue:
    def __init__(self):
        self.items = []
        self.tmp = []
    
    def isEmpty(self):
        return self.items == []
    
    def enqueue(self, item):    # 只能从队尾加入
        return self.items.append(item)
    
    def dequeue(self):          # 只能从队首出去
        for i in range(len(self.items)):
            self.tmp.append(self.items.pop())
        self.items = self.tmp
        return self.items.pop() 
    
## 测试
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"   
duilie = myQueue()
duilie.items = [1,2,3]
duilie.isEmpty()
duilie.enqueue(2)
duilie.items
duilie.dequeue()
duilie.items

False






[1, 2, 3, 2]






1






[2, 3, 2]

## 2.设计一个栈支持min函数
class myStack:
    def __init__(self):
        self.items = []
        self.min_item = []

    def push(self, item):
        self.items.append(item)
        if self.min_item==[] or self.min_item[-1]>=item:
            self.min_item.append(item)
        
    def pop(self):
        if self.min_item[-1]==self.items.pop():
            self.min_item.pop()
        
            
    def getMin(self):
        return self.min_item[-1]

## 测试
zhan = myStack()
zhan.push(2.2)
zhan.items,zhan.min_item
zhan.push(3.4)
zhan.items,zhan.min_item
zhan.push(1.8)
zhan.items,zhan.min_item
zhan.getMin()
zhan.pop()
zhan.items,zhan.min_item,zhan.getMin()

([2.2], [2.2])






([2.2, 3.4], [2.2])






([2.2, 3.4, 1.8], [2.2, 1.8])






1.8






([2.2, 3.4], [2.2], 2.2)

## 3.滑动窗口的最大值，输入num和窗宽k，用队列实现
def maxK(k,nums):
    maxnum = []
    while len(nums)>=k:
        maxnum.append(nums[0])
        for i in range(1,k):
            if maxnum[-1] < nums[i]:
                maxnum.pop()
                maxnum.append(nums[i])
        nums.pop(0)
    return maxnum

# 测试
maxK(k=5, nums = [1, 3, -1, 3.2, -5, 4, 3, 6, 7.5, 2, 6.8, 9])

[3.2, 4, 4, 6, 7.5, 7.5, 7.5, 9]

递归

要点：

• 把问题分解为更小规模相同问题
• 调用自身
• 要有一个基本结束条件

#### 递归理解小故事：
def tell_story(i):
    if i > 0:      # 结束条件
        i = i-1 
        print('从前有座山，山里有座庙，庙里有个老和尚，他在讲：')
        return tell_story(i)   # 调用自身

# 测试
tell_story(3)

从前有座山，山里有座庙，庙里有个老和尚，他在讲：
从前有座山，山里有座庙，庙里有个老和尚，他在讲：
从前有座山，山里有座庙，庙里有个老和尚，他在讲：

#### list累加
num=[1,3,5,7,9]
def listSum(num):
    if len(num)==1:   # 基本结束条件
        return num[0]
    else:
        return num[0]+listSum(num[1:])   # 第一次：a0+a1，第二次a0+a1+a2，第三次...直到len=1

# 测试
listSum(num)

25

#### 任意进制转化
def toStr(n, base):
    converString = "0123456789ABCDEF"  # 最大为16进制
    if n < base:
        return converString[n]
    else:
        return toStr(n//base,base)+converString[n%base]

# 测试
toStr(35,2)
toStr(192345,16)

'100011'






'2EF59'

递归调用的实现：

• 每次调用时，现场数据压入系统调用栈（栈帧）
• 返回时，从栈顶获得返回地址，弹出栈帧，按地址返回。

递归作图：

### 画一个五角星
import turtle
t2 = turtle.Turtle()
t2.pencolor('red')
for i in range(6):
    t2.forward(100)
    t2.right(144)
turtle.done()

#### 画一个螺旋
import turtle
t3 = turtle.Turtle()

def drawS(t,linelen):
    if linelen>0:
        t.forward(linelen)
        t.right(90)
        drawS(t,linelen-5)

drawS(t3,100)

#### 画一个二叉树
import turtle

def plotTree(t,branch):
    if branch>5:
        t.forward(branch)
        t.right(20)
        plotTree(t,branch-15)
        t.left(40)
        plotTree(t,branch-15)
        t.right(20)
        t.backward(branch)
    
t4 = turtle.Turtle()
t4.left(90)
t4.backward(70)
plotTree(t4,80)
turtle.done()

from IPython.display import Image
Image(filename = 'Desktop/快乐研一/python/ercha.jpg', width=300, height=300)

经典问题

1——汉诺塔

## 三柱子汉诺塔实现
def moveTower(n,fromT,withT,toT):
    if n>=1:
        moveTower(n-1,fromT,toT,withT)
        print(f"moving disk{n} from {fromT} to {toT}")
        moveTower(n-1,withT,fromT, toT)

moveTower(3,"#1","#2","#3")

moving disk1 from #1 to #3
moving disk2 from #1 to #2
moving disk1 from #3 to #2
moving disk3 from #1 to #3
moving disk1 from #2 to #1
moving disk2 from #2 to #3
moving disk1 from #1 to #3

2——探索迷宫

### 1.考虑用矩阵实现一个迷宫
### 2.墙壁 + 通道  
### 3.避免死循环，记录走过的路径，避开
### 4.结束条件：①碰到墙②碰到走过的③碰到边界

练习题

• 斐波那契数列
• 青蛙跳台阶
• 跳水台问题
• 井字游戏（稍难）

## 1.斐波那契数列
## 从0和1开始，用前面两项相加得到当前项
def fib(n):   # 第几个数
    if n==0: return 0
    if n==1: return 1
    if n>1:
        return fib(n-1)+fib(n-2)      
#测试
for i in range(10): print(fib(i))
    
    
## 2.青蛙跳台阶问题
## 青蛙一次可以跳上一级台阶，也可以跳两级，问跳上n级台阶总共有几种跳法
def numWays(n):
    if n==1:return(1)
    if n==2:return(2)
    if n-2>=1:return(numWays(n-1)+numWays(n-2))
# 测试
numWays(7)


## 3.跳水板
## 正好使用n块木板（有两种长度）生成所有可能长度：
def boardlen(n,short,longer):
    length = []
    for i in range(n+1):
         length.append((n-i)*short+i*longer)
    return length
# 测试：
boardlen(4,2,3)


## 4.递归乘法——正整数相乘
# 如果写成循环非常简单
A=1;B=10;tmp=0
for i in range(A):
    tmp = tmp+B
print(tmp)
# 如果写成递归呢
def multiply(A:int,B:int) -> int:
    if A==1: 
        return B
    if A>=2: 
        return multiply(A-1,B)+B
## 测试
multiply(3, 9)

0
1
1
2
3
5
8
13
21
34





21






[8, 9, 10, 11, 12]






10






27

井字游戏（递归）

import random
## 井字游戏（递归）
# 结束条件：1.放满了，2.三个相同字符填充行、列、对角线
# 用递归列出所有可能的结束情况，每次递归下一次
def wins(jin):
    ifwin = False
    if jin[0]==jin[4]==jin[8]!=0 or jin[2]==jin[4]==jin[6]!=0: ifwin=True   # 对角
    if jin[0]==jin[1]==jin[2]!=0 or jin[3]==jin[4]==jin[5]!=0 or jin[6]==jin[7]==jin[8]!=0: ifwin = True  # 行
    if jin[0]==jin[3]==jin[6]!=0 or jin[1]==jin[4]==jin[7]!=0 or jin[2]==jin[5]==jin[8]!=0: ifwin=True   # 列
    return ifwin

def xiaqi(jin,jin_num):   # 每一次下棋
    ## 停止条件
    if len(jin_num)>=1 and (not wins(jin)):
        
    ## 递归调用
        locat = random.choice(jin_num)   # 从空位中选出一个位置
        ## 轮到谁下棋
        if len(jin_num)%2==0:
            jin[locat]="乙"
        else:jin[locat]="甲"
        jin_num.remove(locat)
        print("第{}次：\n{}\n{}\n{}".format(len(jin)-len(jin_num),jin[0:3],jin[3:6],jin[6:9]))
        return xiaqi(jin, jin_num)   # 下完之后的棋盘和空位继续下棋

    ##  停止之后，判断局势
    if len(jin_num)==0 and (not wins(jin)): print("平局")
    if wins(jin): 
        if len(jin_num)%2==0:
            print("甲 win!")
        else:
            print("乙 win!")
        
xiaqi(jin = [0]*9, jin_num = list(range(0,9)))

第1次：
[0, 0, 0]
['甲', 0, 0]
[0, 0, 0]
第2次：
[0, 0, 0]
['甲', 0, 0]
[0, '乙', 0]
第3次：
[0, 0, 0]
['甲', 0, '甲']
[0, '乙', 0]
第4次：
[0, '乙', 0]
['甲', 0, '甲']
[0, '乙', 0]
第5次：
[0, '乙', 0]
['甲', '甲', '甲']
[0, '乙', 0]
甲 win!

优化问题和贪心策略

## 硬币找零问题
### 一共有1分，5分，10分，25分四种硬币，寻找兑换硬币最少数量
def coins(coinValue, change):  #输入硬币体系，和需要找零的金额
    min_coins = change   # 最大是change次
    if change in coinValue: min_coins = 1
    else:
        for i in range(len(coinValue)):
            if change > coinValue[i]:
                tmp = coins(coinValue, change - coinValue[i])+1   # 如果先兑换一个一分的
                if tmp < min_coins:
                    min_coins = tmp
    return min_coins

coins([1,5,10,25],53)    
# 超级慢，重复计算太多 

5

## 改进方法
def newcoin(coinValue,change,mychange,mymin_coin):
    min_coins = change
    if change in coinValue:
        min_coins=1
    elif change in mychange:
        return mymin_coin[mychange.index(change)]
    else:
        for i in range(len(coinValue)):
            if change >= coinValue[i]:
                tmp = newcoin(coinValue, change-coinValue[i], mychange, mymin_coin)+1
                if tmp < min_coins:
                    min_coins = tmp
                    mychange.append(change-coinValue[i])
                    mymin_coin.append(tmp)
    return min_coins

## 测试
newcoin([1,5,10,25],53,[],[])

5

### 博物馆盗窃问题
### 假设已经拿了k件，拿第k-1件
### 1.如果前k件的重量和20公斤差值小于2——停止
### 从所有能拿的东西里，选一件拿走-》递归，价值=前k件价值最大值+这一件的价值，在对比计算价值最大值
def max_value(currentkg, maxkg,currentvalue,itemkg,itemvalue):
    maxvalues = 0
    if currentkg+min(itemkg) > maxkg: 
        currenkg = min(itemkg)
        maxvalues = itemvalue[itemkg.index(min(itemkg))]
    else:
        for i in range(len(itemkg)):
            if currentkg + itemkg[i] <= maxkg:
                currentkg, currentvalue = max_value(currentkg+itemkg[i], maxkg, currentvalue,itemkg,itemvalue)
                tmp = currentvalue+itemvalue[i]
                if tmp >= maxvalues:
                    maxvalues = tmp
    return currentkg, maxvalues

# 测试
max_value(0,12,0,[2,4,6],[8,20,32])

(12, 56)

### 分发糖果，有 N 个孩子站成了一条直线
# 每个孩子至少分配到 1 个糖果。
# 相邻的孩子中，评分高的孩子必须获得更多的糖果高
# 老师至少准备多少糖果
# 最少糖果=上一个最少糖果+-1，
def min_candy(grade, number, candy, current_sum):
    if number==1:
        candy=1
        current_sum=1
    else:
        candy,current_sum = min_candy(grade, number-1, candy, current_sum)
        if grade[number-1] > grade[number-2]:
            candy = candy+1
            current_sum = current_sum+candy
        if grade[number-1]==grade[number-2]:
            current_sum = current_sum+candy
        if grade[number-1]<grade[number-2]:
            if candy==1:
                current_sum = current_sum+2
                candy = 1
            else:
                candy = 1
                current_sum = current_sum+candy
    return candy,current_sum
    
print("总糖果数{}".format(min_candy([10,20,30,30,20,10,20,40,50,30,10,20],12,0,0)[1]))
1+2+3+3+2+1+2+3+4+2+1+2

总糖果数26





26