基于Python数据结构之递归与回溯搜索
作者:haiyu94 发布时间:2022-02-27 01:40:33
目录
1. 递归函数与回溯深搜的基础知识
2. 求子集 (LeetCode 78)
3. 求子集2 (LeetCode 90)
4. 组合数之和(LeetCode 39,40)
5. 生成括号(LeetCode 22)
6. N皇后(LeetCode 51,52)
7. 火柴棍摆正方形(LeetCode 473)
1. 递归函数与回溯深搜的基础知识
递归是指在函数内部调用自身本身的方法。能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。特别地,当规模N=1时,能直接得解。
回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
2. 求子集 (LeetCode 78 Subsets)
2.1题目
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
2.2思路
初始化,[ ]的子集为[ [ ] ]
nums[ : n]的子集为所有nums[ : n-1]的子集 加上所有nums[ : n-1]的子集+元素nums[n-1]
2.3代码
class Solution(object):
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
size = len(nums)
return self.solve(nums, size)
def solve(self, nums, n):
if n == 0:
return [[]]
temp = self.solve(nums[:n-1], n-1)
ans = temp[:]
for i in temp:
ans.append(i + [nums[n-1]])
return ans
3. 求子集2 (LeetCode 90 Subsets II)
3.1题目
Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
3.2思路
在上一题思路的基础上,当nums[i]=nums[i-1]时,添加子集时只需在上一步增加的子集基础上进行添加nums[i],而不需要对所有子集进行添加nums[i]。故在递归返回结果时,返回两个结果,一个是所有子集,还有一个是该步骤中添加的子集的集合。
3.3代码
class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
size = len(nums)
return self.solve(nums, size)[0]
def solve(self, nums, n):
if n == 0:
return [[]],[[]]
if n == 1:
return [[],[nums[n-1]]],[[nums[n-1]]]
temp = self.solve(nums[:n-1], n-1)
ans = temp[0][:]
l = len(ans)
if nums[n-1] == nums[n-2]:
for i in temp[1]:
ans.append(i + [nums[n-1]])
else:
for i in temp[0]:
ans.append(i + [nums[n-1]])
return ans,ans[l:]
4. 组合数之和(LeetCode 39,40 )
4.1题目
LeetCode 39 Combination Sum
Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[
[7],
[2, 2, 3]
]
LeetCode 40 Combination Sum II
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
4.2思路
LeetCode 39 Combination Sum
(1)对给定的数字集合进行排序
(2)target=T,从数组中找一个数n,target= T-n,如果target= 0,则寻找成功添加结果,如果taget比候选数字中的最小值还小,则寻找失败,不添加
(3)注意:按从小到大的顺序进行查找,如果某数已找到,则在找下一个时,不包括该数
LeetCode 40 Combination Sum II
该题与上一题相比,区别在于,给定的集合列表中数字可能重复,目标集合中的数字只能使用给定集合中的数字,并且每个数字只能使用一次。注意,由于存在重复的数字,故需要保证结果中的路径集合没有重复。所以当出现candidates[i]==candidates[i-1],跳过。
4.3代码
LeetCode 39 Combination Sum
class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates.sort()
self.ans = []
self.solve(candidates, target, 0 ,[])
return self.ans
def solve(self, candidates, target, start, path):
if target == 0:
self.ans.append(path)
return
if target < 0:
return
size = len(candidates)
for i in range(start, size):
if candidates[i] > target:
return
self.solve(candidates, target - candidates[i], i, path + [candidates[i]])
LeetCode 40 Combination Sum II
class Solution(object):
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates.sort()
self.ans = []
self.solve(candidates, target, 0, [])
return self.ans
def solve(self, candidates, target, start, path):
if target == 0:
self.ans.append(path)
return
if target < 0:
return
size = len(candidates)
for i in range(start, size):
if i != start and candidates[i] == candidates[i-1]:
continue
self.solve(candidates, target - candidates[i], i + 1, path + [candidates[i]])
5. 生成括号(LeetCode 22 Generate Parentheses)
5.1题目
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]
5.2思路
在任意位置,左括号的个数要大于等于右括号的个数,如果左括号的个数有剩余,则+'(‘,递归,如果右括号有剩余,且小于左括号的的个数,则 +‘)‘,最后左右括号都不剩则排列结束。
5.3代码
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
self.res = []
self.generateParenthesisIter('',n, n)
return self.res
def generateParenthesisIter(self, mstr, r, l):
if r == 0 and l ==0:
self.res.append(mstr)
if l > 0:
self.generateParenthesisIter(mstr+'(', r, l-1)
if r > 0 and r > l:
self.generateParenthesisIter(mstr+')', r-1, l)
6. N皇后(LeetCode 51 ,52)
6.1题目
LeetCode 51 N-Queens
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where ‘Q' and ‘.' both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:
[
[“.Q..”, // Solution 1
“…Q”,
“Q…”,
“..Q.”],[“..Q.”, // Solution 2
“Q…”,
“…Q”,
“.Q..”]
]
LeetCode 52 N-Queens II
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
6.2思路
LeetCode 51 N-Queens
n*n的板上放置n个皇后,n个皇后不能发生攻击,即行/列/斜没有其他皇后,要求给出所有解决方案。每次在棋盘上的当前位置放置一个皇后,当不与前面行的皇后发生冲突时,则可以递归处理下面行的皇后。因为有n行n列,n个皇后,故每行可以放一个皇后,每一列也只能放置一个皇后。通过检查第k个皇后能否被放置在第j列进行判断(不与其他皇后在同行,同列,同斜行)。使用一个长度为n的列表记录第k行皇后放置的列位置。
LeetCode 52 N-Queens II
和上一题思路一样,返回结果的长度即可
6.3代码
LeetCode 51 N-Queens
class Solution(object):
def solveNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
self.ans = []
self.board = [-1 for i in range(n)]
self.dfs(0, [], n)
return self.ans
def isQueen(self, krow, jcolumn):
for i in range(krow):
if self.board[i] == jcolumn or abs(krow-i) == abs(self.board[i] - jcolumn):
return False
return True
def dfs(self, krow, rowlist, n):
if krow == n:
self.ans.append(rowlist)
for i in range(n):
if self.isQueen(krow,i):
self.board[krow] = i
self.dfs(krow + 1,rowlist + ['.' * i + 'Q' + '.' * (n-i-1)],n)
LeetCode 52 N-Queens II
class Solution(object):
def totalNQueens(self, n):
"""
:type n: int
:rtype: int
"""
self.ans = []
self.board = [-1 for i in range(n)]
self.dfs(0, [], n)
return len(self.ans)
def isQueen(self, krow, jcolumn):
for i in range(krow):
if self.board[i] == jcolumn or abs(krow-i) == abs(self.board[i] - jcolumn):
return False
return True
def dfs(self, krow, rowlist, n):
if krow == n:
self.ans.append(rowlist)
for i in range(n):
if self.isQueen(krow,i):
self.board[krow] = i
self.dfs(krow + 1,rowlist + ['.' * i + 'Q' + '.' * (n-i-1)],n)
7. 火柴棍摆正方形(LeetCode 473 Matchsticks to Square)
7.1题目
Remember the story of Little Match Girl? By now, you know exactly what matchsticks the little match girl has, please find out a way you can make one square by using up all those matchsticks. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.
Your input will be several matchsticks the girl has, represented with their stick length. Your output will either be true or false, to represent whether you could make one square using all the matchsticks the little match girl has.
Example 1:
Input: [1,1,2,2,2]
Output: trueExplanation: You can form a square with length 2, one side of the square came two sticks with length 1.
Example 2:
Input: [3,3,3,3,4]
Output: falseExplanation: You cannot find a way to form a square with all the matchsticks.
7.2思路
根据火柴棒的总长度,求正方形的变长,若变长不为整数,则直接判断为False。
先将nums按从大到小的顺序排序,used为和nums等长的列表,用于记录第i位的元素是否被用过。
使用递归判断从第i位元素起始,能否找到这样的组合满足其长度之和等于正方形的边长。
(1)若满足初始条件,则返回结果(True or False)
(2)若不满足条件,则进行递归,在剩下的元素中进行选择,看有没有满足情况的,如果没有满足情况的,used对应位置改为False,结果返回False
(3)对nums中的每个元素进行遍历,看能否满足nums中的每个火柴棒都能找到对应边的组合,其长度和等于正方形边长。
7.3代码
class Solution(object):
def makesquare(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
total = sum(nums)
if total%4 != 0 or len(nums)<4: return False
size = total/4
nums.sort(reverse=True)
used = [False]*len(nums)
def dfs(i, expect):
if i >= len(nums): return expect%size == 0
if used[i]: return dfs(i+1, expect)
used[i] = True
if nums[i] == expect: return True
if nums[i] < expect:
expect -= nums[i]
available = [j for j in range(i+1, len(nums)) if not used[j]]
for x in available:
if dfs(x, expect):
return True
used[i] = False
return False
for i in range(len(nums)):
if not dfs(i, size): return False
return True
来源:https://blog.csdn.net/haiyu94/article/details/79453136
猜你喜欢
- 1 文件'''文件存储文件主名.扩展名'''Python中常有的数据文件类型有文本文件、二进
- 如何在网站上提供音乐下载?为用户提供歌曲下载,一般有两种方式,一是直接通过Http,浏览器下载,二是通过ftp协议下载。我们来用Http和浏
- 备份还原数据库备份数据库企业管理器--或用SQL语句(完全备份):backup database 数据库 to
- 运动模糊:由于相机和物体之间的相对运动造成的模糊,又称为动态模糊Opencv+Python实现运动模糊,主要用到的函数是cv2.filter
- 引用类型(Reference)在许多计算机语言中都被使用,而且是作为一个非常强大而实用的特性存在。它有类似指针(Pointer)的实现,却又
- 就算我们每天在叫嚷着创新经济,设计救国,我们在生活中也无处不在的看到各种设计庸俗、制作粗劣的海报、店面、户外广告、大胸美女和肌肉 * 交相辉映
- 最近有点审美疲劳,以往看起来觉得漂亮的界面现在觉得很一般,以前觉得看来还行的界面现在觉得很丑了。想来是时候休息一下了。唯美觉得上次做的OA登
- 在这里我想有必要再较系统说一下ADO的各种对象的方法、属性。毕竟ADO不仅应用在ASP中,VB,VC都可以用到。在这十天中我想主要提到的对象
- 这个例子可作为一个模式,在你需要的时候套用。<!DOCTYPE HTML PUBLIC &q
- SQL*DBA命令的安全性: 如果您没有SQL*PLUS应用程序,您也可以使用SQL*DBA作SQL查权限相关的命令只能分配给Oracle软
- 缘起最近复习设计模式拜读谭勇德的<<设计模式就该这样学>>该书以java语言演绎了常见设计模式本系列笔记拟采用gol
- 查询效率分析:子查询为确保消除重复值,必须为外部查询的每个结果都处理嵌套查询。在这种情况下可以考虑用联接查询来取代。如果要用子查询,那就用E
- 本文实例讲述了PHP实现网页内容html标签补全和过滤的方法。分享给大家供大家参考,具体如下:如果你的网页内容的html标签显示不全,有些表
- 将表数据生成SQL脚本的存储过程示例:CREATE PROCEDURE dbo.UspOutputData @tablename sysna
- 使用ASP处理XSLT转换XML比较简单,思路如下:创建一个XSLTemplate的对象,再创建一个XMLDOM对象,然后在家Xml文件和X
- 通过Python中的matplotlib绘制百分比堆叠柱状图,并为每一个类别设置不同的填充图案。主要原因是有些论文打印出是黑白色的,不同类别
- isset(PHP 3, PHP 4, PHP 5 )isset -- 检测变量是否设置描述bool isset ( mixed var [
- 1、远程登录到linux上,使用到的模块paramiko#远程登陆操作系统def ssh(sys_ip,username,password,
- 最近在一个python工具中需要实现串口自动触发工作的功能,之前只在winform上面实现,今天使用python试试。这里简单记一下:首先用
- 首先上一段程序:import numpy as nplist_a = list(range(10))print("list_a: