Menu Close

排列组合之全排列[Macaque]

monkey-1179368_960_720.jpg

欢迎阅读、点赞、转发、订阅,你的举手之间,我的动力源泉。

0.基础框架

  • DFS: Depth First Search 深度优先搜索,简称深搜
  • BFSBreadth First Search 广度优先搜索,简称广搜

0.1.DFS算法框架

0.2.BFS算法框架

举个例子,假如你在学校操场,老师叫你去国旗那集合,你会怎么走? 假设你是瞎子,你看不到周围,那如果你运气差,那你可能需要把整个操场走完才能找到国旗。这便是盲目式搜索,即使知道目标地点,你可能也要走完整个地图。 假设你眼睛没问题,你看得到国旗,那我们只需要向着国旗的方向走就行了,我们不会傻到往国旗相反反向走,那没有意义。 这种有目的的走法,便被称为启发式的

bfs.gif

1.全排列

1591629370557.png

方法1:DFS + visit数组

一般使用visited,used等数组来记录当前元素是否被访问过,

方法2:DFS original

  • 题意说nums数组无重复元素,可以利用levelList.contains(num)来做剪枝,不需要借助visited数组

方法3:回溯

  • 回溯法 是一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认 不是 一个解的话(或者至少不是 最后一个 解),回溯算法会通过在上一步进行一些变化抛弃该解,即 回溯 并且再次尝试。

  • 这里有一个回溯函数,使用第一个整数的索引作为参数backtrack(first)

  • 如果第一个整数有索引 n,意味着当前排列已完成。

  • 遍历索引 first 到索引 n - 1 的所有整数。Iterate over the integers from index first to index n - 1.

    • 在排列中放置第 i个整数, 即swap(nums[first], nums[i]).
    • 继续生成从第i个整数开始的所有排列: backtrack(first + 1).
    • 现在回溯,即通过 swap(nums[first], nums[i]) 还原.

2.全排列II

1591714144264.png

方法1:DFS

  • 由于数字重复,与46题主体代码相似,这里需要做一次剪枝
  • 需要将nums进行排序,在visited[i]true时,需要加上前一个元素被访问过,当前元素与前一个元素相等,这两种情况需要continue
  • 注意条件(i - 1)>=0 注意等于号

关联阅读

发表评论

电子邮件地址不会被公开。 必填项已用*标注

苏ICP备20029284号-1