塞进裤子ヾ(≧O≦)〃嗷~

0%

我的函数库

将一些常用函数记录下来,避免重复造轮子

字符串

字符串加1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def addone(mystr):#字符串加1
n = len(mystr)
temp= 1 #进位
for i in range(n-1,-1,-1):
ch = mystr[i]
temp = int(ch) + 1
if temp < 10:
mystr = mystr[0:i] + str(temp) + mystr[i+1:]
return mystr
else:#if之前都要进位,我们直接让本位为0即可
mystr = mystr[0:i] + '0' + mystr[i+1:]
if i == n-1:
continue

if temp!=0:#处理99的情况
mystr = '1' + mystr[:]
return mystr

回溯问题

RE:https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-xiang-jie-by-labuladong-2/

1
2
3
4
5
6
7
8
9
10
#回溯问题模版框架
result = []
def backtrack(当前路径,选择列表)
if 满足结束条件:#比如选择列表为空
result.append(当前路径)
return
for 选择 in 选择列表:
做选择(将此选择从选择列表移除)
backtrack(当前路径,新选择列表)
撤销选择(将上一步做出的选择从路径列表剔除,加入选择列表)

leetcode 797,77

子集问题利用回溯算法,要用 index 参数排除已选择的数字。

组合问题利用回溯思想,结果可以表示成树结构,关键点在于要用一个 index 排除已经选择过的数字。

排列问题利用回溯思想,也可以表示成树结构,关键点在于使用 contains 方法排除已经选择的数字

全排列

—新版—

排列的结束条件是选择列表的每个元素都被选择过一次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
res = []
choices = [1,2,3]
curpath = []
def backtrack(curpath,choices):
if len(choices) == len(curpath):
res.append(curpath.copy())
#需要传递下curpath的拷贝,否则对curpath的修改会影响到res结果
return

for i in range(len(choices)):
if choices[i] in curpath:#跳过已经作出的选择
continue #若是有放回抽样,就注释掉这个if语句
curpath.append(choices[i])
backtrack(curpath,choices)
curpath.pop()
backtrack(curpath,choices)
print(res)
#[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

—旧版—–

两种方式,一种有放回的抽样,另一种是无放回抽样

比如【123】,第一种有27种结果,第二种有6种结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#permutation,

def Permutation(ss):
def helper(ss,resultlist,curpath="",index=0):
#ss:str 采样字符串
#resultlist:list,存储结果【【123】,【132】...】
#curpath:str,当前存储的排列结果(未完成的)
#index:int,已经进行了index位的采样
if index == length:#到了最后一个字符
resultlist.append(curpath)
else:
for i in range(len(ss)):
#有放回抽样
helper(ss,resultlist,curpath+ss[i],index+1)
#无放回抽样
#helper(ss[:i]+ss[i+1:],resultlist,curpath+ss[i],index+1)
#ss[:i]+ss[i+1:]是为例取出当前字符ss[i],因为是不放回采样
#path+ss[i]是将当前字符保留到curpath中
if not ss:
return []
resultlist = []
length = len(ss)
helper(ss,resultlist,curpath="",index=0)#list是可变对象,不必return
return list(set(resultlist))#set()去重

print(Permutation("123"))

子集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
res = []
choices = [1,2,3]
curpath = []
def backtrack(curpath,choices,index):
#当前路径,选择列表,已经选了index个
res.append(curpath.copy())

for i in range(index,len(choices)):
curpath.append(choices[i])
backtrack(curpath,choices,i+1) #注意是i+1
curpath.pop()
backtrack(curpath,choices,index=0)
print(res)
#[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

组合

组合与子集差不多,区别在于结束条件,组合和排列必须是树的叶子结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
res = []
choices = [1,2,3,4]

def backtrack(curpath,choices, index, k):
if len(curpath) == k:
res.append(curpath.copy())
return
for i in range(index, len(choices)):
curpath.append(choices[i])
backtrack(curpath.copy(),choices,i+1, k)
curpath.pop()

backtrack(curpath=[],choices=choices,index=0,k=3)
print(res)
#[[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]
if help:小手一抖点个广告 or 大手一挥资助一下