欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

深度优先搜索_全排列问题

程序员文章站 2022-07-07 22:53:10
...

1 字符串的全排列

给定一组字符串,找出所有的排列组合数(有可能存在重复字符)。
思路:深度优先搜索,依然是套用搜索算法的模板,但是这里面涉及到重复字符,我们需要排除掉重复的字符串。这就涉及到剪枝问题。
上一张图:(借的大佬的)
深度优先搜索_全排列问题
深度优先搜索_全排列问题
对于如何深度搜索,当我们访问到某个节点时,我们以此节点开始,进行向后查找,我们固定住这个字符,然后重新进入。
此时为了避免重复,我们可以用set结构来去重。
依然是按照dfs的模板

class solution{
	// 定义成全局变量,方便dfs的递归
	char[] c;
    List<String> res = new LinkedList<>();
    public String[] permutation(String s) {
		c = s.toString();
		dfs(0);
		return res.toArray(new String[res.size()]);
	}
	private void dfs(int count){
		// DFS 确定停止条件
		if(count == c.length-1){
			// 长度等于字符串长度,说明此时已经拼凑出一种情况,可以返回
			res.add(String.valueOf(c))
			return;
		}
		// 用set存储重复
		Set<Character> set = new HashSet<>();
		for(int i=count; i<c.length; i++){
			// set中存在,跳过,因为说明是重复的,即使现在交换;后面会出现重复情况
			if(set.contains(c[i])){
				continue;
			}
			set.add(c[i]); // 存进去
			// 将该节点定住,
			swap(i,count);
			dfs(count+1);
			// dfs 结束,要恢复成之前的状态
			swap(i,count);
		}
	}
	
	private void swap(int i,int count){
		char tmp = c[i];
		c[i] = c[count];
		c[count] = tmp;
}
}

2 数字的全排列

与上面一题相同,leetcode 还有两道数字的全排列,分别是 LeetCode 46 和 LeetCode 47

LeetCode 46是不含重复数字的情况,会简单一些,那么我们就不需要考虑到去重,所以set结构就用不到

不带重复数字的全排列

class solution{
	List<List<Integer>> res = new ArrayList<>();
    int[] n;
    public List<List<Integer>> permute(int[] nums) {
    	n = num;
    	dfs(0);
    	return res;
    }
	private void dfs(int count){
		// dfs 确定停止条件
		if(count == n.length-1){
			res.add(toList(n));
			return;
		}
		for(int i=count; i<n.length; i++){
			swap(i,count);
			// dfs
			dfs(count+1);
			// 恢复状态
			swap(i,count);
		}
	}
	// 数组转链表
	private void List<Integer> toList(int[] n){
		List<Integer> list = new ArrayList<>();
		for(int num:n){
			list.add(num;)
		}
		return list;
	}
}
相关标签: 算法学习