解决猴子吃桃问题
猴子第一天摘下若干个桃子，当即吃了一半,还不过瘾，又多吃了一个。第二天早上又将剩下的桃子吃掉一半,又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想吃时，只剩下一个桃子了。
求第一天共摘多少个桃子
"""
假设猴子摘了x个桃子
d1= x/2 -1
d2= d1/2 -1
d3= d2/2 -1
d9= d8/2 -1
d10= 1
"""
peach=1
for i in range(9): #9次，10天剩1个了
peach = 2 * (peach +1 )
print("peach num: ",peach)
peach num: 1534
求杨辉三角N行K列
列表法 空间复杂度
n=9
k=2
pre=[1]
for i in range(n):
row= [1] * (i+1)
for j in range(i-1): #0
row[j+1]=pre[j]+pre[j+1]
print(row)
pre=row
print(row[k-1])
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]
[1, 7, 21, 35, 35, 21, 7, 1]
[1, 8, 28, 56, 70, 56, 28, 8, 1]
8
公式 https://baike.baidu.com/item/%E6%9D%A8%E8%BE%89%E4%B8%89%E8%A7%92/215098?fr=aladdin
- 第n行的m个数可表示为 C(n-1，m-1)，即为从n-1个不同元素中取m-1个元素的组合数。
- C(8,2)=8!/[(8-2)! *2!]=28
m=9
k=3
n=m-1
r=k-1
d=m-k
x=1
for i in range(2,n+1):
x*=i
print(i,x)
if i==n:
a=x
if i==r:
b=x
if i == d:
c=x
print(a//b//c)
28
打印重复的次数
用户输入一个数字，打印每一位数字及其重复的次数
dict
#num=input('>>').strip().lstrip('0+-')
num='1223330'
counter={}
for x in num:
# if x not in counter.keys():
# counter[x]=0
# counter[x]+=1
if x not in counter.keys():
counter[x]=1
else:
counter[x]+=1
print(counter)
dict get
num='1223330'
counter={}
for x in num:
counter[x]=counter.get(x,0)+1
print(counter)
dictsetdefault
num='1223330'
counter={}
for x in num:
counter[x]=counter.setdefault(x,0)+1
print(counter)
defaultdict
from collections import defaultdict
num='1223330'
# counter=defaultdict(int)
counter=defaultdict(lambda :0)
for x in num:
counter[x]+=1
print(dict(counter))
随机挑选2个字母组成字符串，共挑选100个
降序输出所有不同的字符串及 重复的次数
# import string
# alphabet=string.ascii_lowercase
# alphabet=bytes(range(0x61,123)).decode()
alphabet="abcdefghijklmnopqrstuvwxyz"
word=[]
for i in range(100):
word.append("".join(random.sample(alphabet,k=2)))
# word.append("".join(random.choices(alphabet,k=2))) #会重复aa
# word.append(random.choice(alphabet)+random.choice(alphabet))
counter={}
for x in word:
counter[x]=counter.get(x,0)+1
print(sorted(counter.items(),reverse=True),len(counter))
集合
X和群里面其他用户没有好友
A:ListA
B:ListB
C:ListC
思路1：
X 去A、B、C找了一遍
X in ListA or X in ListB or X in ListC #O(1)
X not in (ListA | ListB | ListC) ==True #快，但产生巨大并集，占用内存
思路2：更快
A、B、C用户ID，有没在X好友列表
IDs={A,B,C}
IDs & X !=set()
IDs -X < IDs #真子集
IDs.isdisjoint(X) ==False
有一个API,要求权限同时具备A、B、C才能访问，用户权限为B、C、D是否能访问呢
P1={'A','B','C'}
P2={'B','C','D'}
print(P1-P2==set())
print(P1&P2==P1)
print(P1<=P2)
有一个API,要求权限具备A、B、C任一权限即可访问，用户权限为B、C、D是否能访问
P1={'A','B','C'}
P2={'B','C','D'}
print(P1&P2!=set())
print(P1-P2)
print(P1-P2 < P1) #真子集
一个总任务列表，存储所有任务，一个已完成列表。找出未完成的任务
ALL=[1,2,3,4,5,6,7,8,9,10]
COMPLETED=[2,4,6,8,10]
UNCOMPLETED=[]
效率低
for id in ALL:
if id not in COMPLETED:
UNCOMPLETED.append(id)
# 效率高
ALL={1,2,3,4,5,6,7,8,9,10}
COMPLETED={2,4,6,8,10}
print(ALL-COMPLETED)
随机产生2组各10个数字的列表 如下要求: 每个数字取值范围[10,20] 统计20个数字中，-共有多少个不同的数字? 2组之间进行比较，不重复的数字有几个?分别是什么? 2组之间进行比较，重复的数字有几个?分别是什么? 例如，两组数分别是[1,9,5, 7,4]、 [1,5, 6, 8]， 两组数一共有7个不同的数字，两组间不同的数字 有5个，两组间重复的数字有2个 A={1,9,5,7,4} B={1,5,6,8}
import random
L1=[]
L2=[]
for i in range(10):
L1.append(random.randint(10,20))
L2.append(random.randint(10,20))
S1=set(L1)
S2=set(L2)
print(S1)
print(S2)
print(S1|S2)
print(S1^S2)
print(S1&S2)
递归
阶乘
#公式
def factorial(n):
if n< 3:
return n
return n*factorial(n-1)
def factorial(n):
p=1
for i in range(1,n):
p*=i
return p
def factorial(n,p=1):
if n<2:
return p
return factorial(n-1,p*n)
def factorial(n,p=1):
return p if n<2 else factorial(n-1,p*n)
猴子吃桃
def peach():
total=1
for i in range(9):
total=2*(total+1)
return total
print(peach())
def peach(n=9,p=1):
if n==0:
return p
return peach(n-1,2*(p+1))
print(peach(9))
def peach(n=9):
if n==0:
return 1
return 2*(peach(n-1)+1)
print(peach(9))
def peach(n=1):
if n==10:
return 1
return 2*(peach(n+1)+1)
print(peach())
def peach(days=9,p=1):
p=2*(p+1)
if days ==1:
return p
return peach(days-1,p)
print(peach(9))
1234倒序
#1234 -> [4,3,2,1]
a=1234
print(list(reversed(str(a))))
print(list(map(int,reversed(str(a)))))
def revert(data):
if not data:
return []
return [data[-1]] + revert(data[:-1])
x=str(1234)
print(revert(x))
def revert(data,target=[]):
if not data:
return target
target.append(data[-1])
return revert(data[:-1],target)
print(revert('1234'))
x=123045
def revert(data,target=[]):
x,y=divmod(data,10)
target.append(y)
if x==0:
return target
return revert(x,target)
print(revert(x))
x=123045
def revert(data,target=[]):
if data==0:
return target
x,y=divmod(data,10)
target.append(y)
return revert(x,target)
print(revert(x))
x=123045
def revert(data,target=None):
if target is None:
target=[]
if data==0:
return target
x,y=divmod(data,10)
target.append(y)
return revert(x,target)
print(revert(x))