• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

LeetCode – Medium – 46. Permutations

互联网 diligentman 2周前 (04-07) 7次浏览

Topic

  • Backtracking

Description

https://leetcode.com/problems/permutations/

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

Constraints:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • All the integers of nums are unique.

Analysis

方法一:回溯算法(不使用startIndex)

思路分析

以[1,2,3]为例,抽象成树形结构如下:

LeetCode - Medium - 46. Permutations

回溯三弄

递归函数参数

首先排列是有序的,也就是说[1,2] 和[2,1] 是两个集合,这和之前分析的子集以及组合所不同的地方。

可以看出元素1在[1,2]中已经使用过了,但是在[2,1]中还要在使用一次1,所以处理这里不用使用startIndex了。

但本问题需要一个used数组,标记已经选择的元素,如思路分析图橘黄色部分所示。

代码如下:

private void backtracking(List<Integer> path, int[] nums, boolean[] used, List<List<Integer>> results) {}
递归终止条件

可以看出叶子节点,就是收割结果的地方。

当收集元素的数组path的大小达到和nums数组一样大的时候,说明找到了一个全排列,也表示到达了叶子节点。

if (path.size() == nums.length) {
	results.add(new ArrayList<>(path));
	return;
}
单层搜索逻辑

代码如下:

for (int i = 0; i < nums.length; i++) {
	if (used[i])
		continue;

	used[i] = true;
	path.add(nums[i]);
	backtracking(path, nums, used, results);
	path.remove(path.size() - 1);
	used[i] = false;
}

方法二:回溯算法2(使用startIndex)

同方法一差异不大,不过用到startIndex和数组交换元素。

LeetCode - Medium - 46. Permutations

参考资料

  1. 回溯算法:排列问题!
  2. 剑指Offer 2nd – 字符串的排列

Submission

import java.util.ArrayList;
import java.util.List;

public class Permutations {

	// 方法一:回溯算法
	public List<List<Integer>> permute(int[] nums) {
		List<List<Integer>> results = new ArrayList<>();
		List<Integer> path = new ArrayList<>();
		boolean[] used = new boolean[nums.length];
		backtracking(path, nums, used, results);
		return results;
	}

	private void backtracking(List<Integer> path, int[] nums, boolean[] used, List<List<Integer>> results) {
		if (path.size() == nums.length) {
			results.add(new ArrayList<>(path));
			return;
		}

		for (int i = 0; i < nums.length; i++) {
			if (used[i])
				continue;

			used[i] = true;
			path.add(nums[i]);
			backtracking(path, nums, used, results);
			path.remove(path.size() - 1);
			used[i] = false;
		}
	}

	// 方法二:回溯算法2
	public List<List<Integer>> permute2(int[] nums) {
		List<List<Integer>> results = new ArrayList<>();
		List<Integer> path = new ArrayList<>();
		backtracking2(path, 0, nums, results);
		return results;
	}

	private void backtracking2(List<Integer> path, int startIndex, //
			int[] array, List<List<Integer>> results) {

		if (startIndex == array.length) {
			results.add(new ArrayList<>(path));
			return;
		}

		for (int i = startIndex; i < array.length; i++) {
			swap(array, startIndex, i);
			path.add(array[startIndex]);
			backtracking2(path, startIndex + 1, array, results);
			path.remove(path.size() - 1);
			swap(array, startIndex, i);
		}
	}

	private void swap(int[] num, int i, int j) {
		int temp = num[i];
		num[i] = num[j];
		num[j] = temp;
	}
	
}

Test

import static org.junit.Assert.*;

import java.util.Arrays;
import java.util.List;

import static org.hamcrest.collection.IsIterableContainingInAnyOrder.*;

import org.hamcrest.Matcher;
import org.junit.Test;

@SuppressWarnings("unchecked")
public class PermutationsTest {

	private final Permutations obj = new Permutations();

	private final int[] array = {1, 2, 3};
	private final Matcher<Iterable<? extends List<Integer>>> expected = containsInAnyOrder(Arrays.asList(1, 2, 3), //
			Arrays.asList(1, 3, 2), Arrays.asList(2, 1, 3), Arrays.asList(2, 3, 1),// 
			Arrays.asList(3, 1, 2), Arrays.asList(3, 2, 1));
	
	private final int[] array2 = {0, 1};
	private final Matcher<Iterable<? extends List<Integer>>> expected2 = containsInAnyOrder(Arrays.asList(0, 1), Arrays.asList(1, 0));

	private final int[] array3 = {1};
	private final Matcher<Iterable<? extends List<Integer>>> expected3 = containsInAnyOrder(Arrays.asList(1));
	
	@Test
	public void test() {
		assertThat(obj.permute(array), expected);
		assertThat(obj.permute(array2), expected2);
		assertThat(obj.permute(array3), expected3);
	}
	
	@Test
	public void test2() {
		assertThat(obj.permute2(array), expected);
		assertThat(obj.permute2(array2), expected2);
		assertThat(obj.permute2(array3), expected3);
	}
}

展开阅读全文

© 著作权归作者所有

举报

打赏

0


0 收藏

微信
QQ
微博

分享

作者的其它热门文章

【清华大学】《逻辑学概论》笔记
《Java8实战》笔记(10):用Optional取代null
Kafka学习笔记
Redis学习笔记


程序员灯塔
转载请注明原文链接:LeetCode – Medium – 46. Permutations
喜欢 (0)