- leetcode之回溯排列系列算法
- 1.字符串的排列
- 1.1回溯使用used数组
- 1.2回溯使用used数组
- 2.下一个排列
- 2.1双指针
var res []string
var path string
func permutation(s string) (ans []string) {
t := []byte(s)
sort.Slice(t, func(i, j int) bool { return t[i] < t[j] })
s = string(t)
res = []string{}
used := make([]bool, len(s))
backTrack(s, used)
return res
}
func backTrack(s string, used []bool) {
if len(path) == len(s) {
res = append(res, path)
}
for i := 0; i < len(s); i++ {
if i > 0 && s[i] == s[i-1] && used[i-1] == false {
continue
}
if used[i] == false {
used[i] = true
path = path + string(s[i])
backTrack(s, used)
path = path[:len(path)-1]
used[i] = false
}
}
}
1.2回溯使用used数组本题是回溯算法经典题目，求全排列+去重，这道题目和" 47.全排列II" 几乎是一样的。
var res []string
var path string
func permutation(s string) (ans []string) {
t := []byte(s)
sort.Slice(t, func(i, j int) bool { return t[i] < t[j] })
s = string(t)
res = []string{}
used := make([]bool, len(s))
backTrack(s, used)
return res
}
func backTrack(s string, used []bool) {
if len(path) == len(s) {
res = append(res, path)
}
for i := 0; i < len(s); i++ {
if i > 0 && s[i] == s[i-1] && used[i-1] == true {
continue
}
if used[i] == false {
used[i] = true
path = path + string(s[i])
backTrack(s, used)
path = path[:len(path)-1]
used[i] = false
}
}
}
2.下一个排列
2.1双指针
func nextPermutation(nums []int) {
n := len(nums)
i := n - 2
for i >= 0 && nums[i] >= nums[i+1] {
i--
}
if i >= 0 {
j := n - 1
for j >= 0 && nums[i] >= nums[j] {
j--
}
nums[i], nums[j] = nums[j], nums[i]
}
reverse(nums[i+1:])
}
func reverse(a []int) {
for i, n := 0, len(a); i < n/2; i++ {
a[i], a[n-1-i] = a[n-1-i], a[i]
}
}
//时间复杂度：O(N)，其中 N 为给定序列的长度。我们至多只需要扫描两次序列，以及进行一次反转操作。
//空间复杂度：O(1)，只需要常数的空间存放若干变量。
理解题
本题要求我们实现一个算法，将给定数字序列重新排列成字典序中下一个更大的排列。
以数字序列 [1,2,3] 为例，其排列按照字典序依次为：
[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]
这样，排列 [2,3,1] 的下一个排列即为 [3,1,2]。特别的，最大的排列 [3,2,1] 的下一个排列为最小的排列 [1,2,3]
我们可以将该问题形式化地描述为：给定若干个数字，将其组合为一个整数。如何将这些数字重新排列，以得到下一个更大的整数。如 123 下一个更大的数为 132。如果没有更大的整数，则输出最小的整数。
以 1,2,3,4,5,6 为例，其排列依次为：
123456
123465
123546
…
654321
可以看到有这样的关系：123456 < 123465 < 123546 < … < 654321。
方法：两遍扫描
思路及解法
注意到下一个排列总是比当前排列要大，除非该排列已经是最大的排列。我们希望找到一种方法，能够找到一个大于当前序列的新序列，且变大的幅度尽可能小。具体地：
1.我们需要将一个左边的「较小数」与一个右边的「较大数」交换，以能够让当前排列变大，从而得到下一个排列。
2.同时我们要让这个「较小数」尽量靠右，而「较大数」尽可能小。当交换完成后，「较大数」右边的数需要按照升序重新排列。这样可以在保证新排列大于原来排列的情况下，使变大的幅度尽可能小。
以排列 [4,5,2,6,3,1] 为例：
1.我们能找到的符合条件的一对「较小数」与「较大数」的组合为 2与 3，满足「较小数」尽量靠右，而「较大数」尽可能小。
2.当我们完成交换后排列变为 [4,5,3,6,2,1]，此时我们可以重排「较小数」右边的序列，序列变为 [4,5,3,1,2,6]。
具体地，我们这样描述该算法，对于长度为 n 的排列 a：
1.首先从后向前查找第一个顺序对 (i,i+1)，满足a[i] 2.如果找到了顺序对，那么在区间 [i+1,n) 中从后向前查找第一个元素 j满足a[i] 3.交换 a[i]与 a[j]，此时可以证明区间[i+1,n) 必为降序。我们可以直接使用双指针反转区间 [i+1,n) 使其变为升序，而无需对该区间进行排序。
注意
如果在步骤 1 找不到顺序对，说明当前序列已经是一个降序序列，即最大的序列，我们直接跳过步骤 2 执行步骤 3，即可得到最小的升序序列。
