回溯法总结

Posted 1 CommentPosted in 回溯法

对于某些计算问题而言,回溯法是一种可以找出所有(或一部分)解的一般性算法,尤其适用于约束满足问题(在解决约束满足问题时,我们逐步构造更多的候选解,并且在确定某一部分候选解不可能补全成正确解之后放弃继续搜索这个部分候选解本身及其可以拓展出的子候选解,转而测试其他的部分候选解)。

401.二进制手表

Posted 1 CommentPosted in 回溯法

①画出递归树,找到状态变量(回溯函数的参数),这一步非常重要※
②根据题意,确立结束条件
③找准选择列表(与函数参数相关),与第一步紧密关联※
④判断是否需要剪枝
⑤作出选择,递归调用,进入下一层
⑥撤销选择

46.47.全排列问题

Posted Leave a commentPosted in 回溯法

仅作一个记录,方便n刷整理思路。讲解比我写的详细就不再赘述了。 给定一个 没有重复 数字的序列,返回其所有可能的全排列。 示例: 输入: [1,2,3]输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 详细讲解 47.全排列Ⅱ 给定一个可包含重复数字的序列,返回所有不重复的全排列。 示例: 输入: [1,1,2]输出:[[1,1,2],[1, […]

POJ1128总结

Posted Leave a commentPosted in 回溯法

Consider the following 5 picture frames placed on an 9 x 8 array.
Now place them on top of one another starting with 1 at the bottom and ending up with 5 on top. If any part of a frame covers another it hides that part of the frame below.
Viewing the stack of 5 frames we see the following.

POJ1659总结

Posted Leave a commentPosted in 回溯法

未名湖附近共有N个大小湖泊L1, L2, …, Ln(其中包括未名湖),每个湖泊Li里住着一只青蛙Fi(1 ≤ i ≤ N)。如果湖泊Li和Lj之间有水路相连,则青蛙Fi和Fj互称为邻居。现在已知每只青蛙的邻居数目x1, x2, …, xn,请你给出每两个湖泊之间的相连关系。