回溯 《数据结构和算法应用》

下面是一道阿里的面试题:

个高矮不同的12个人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?

网友给出的解决方案,大多是通过Catalan数来解决的,有万能解题法的回溯法当然也可以解决这个问题,下面是我用回溯法来解决这个问题的java代码:

[java] view plain copy
package com.soft;

import java.util.Arrays;

/**
* 张猛
* 2014年8月20日
* description:
* 个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?
*/
public class LineUp {
// 不变信息
static int n;
// 动态改变信息
static int front;// 记录前排的数目
static int back;// 记录后排的数目
static int count;// 记录解数目

/**
* @author zhangmeng
*@param i 表示第i层,此时决定第i+1个人的位置
*/
private static void trackback(int i) {
// 更新front
if (i < n) { // 如果满足约束条件,搜索左子树 if (front < 6 && front >= back) {
// 搜索左子树
front++;
LineUp.trackback(i + 1);
//清理现场
front–;
}
// 如果 满足上界函数,搜索右子树
if (back < 6 && front >back) {
// 更新cx
back++;
trackback(i + 1);
//清理现场
back–;
}
}else{//处理第n层
count++;
return;
}
}

public static int LineUpCount() {
LineUp.n = 12;
LineUp.back = 0;
LineUp.front = 0;
LineUp.count = 0;
trackback(0);
return LineUp.count;
}

public static void main(String[] args) {

System.out.print(LineUp.LineUpCount());

}
}
运行结果:132

分析:这是一个子集树问题,这里的子集指的是站在前排人的集合。

约束条件:front < 6 && front >= back

限界条件:back < 6 && front >back

排列组合
排列组合通常用于在字符串或序列的排列和组合中,其特点是固定的解法和统一的代码风格。通常有两种方法:第一种是类似动态规划的分期摊还的方式,即保存中间结果,依次附上新元素,产生新的中间结果;第二种是递归法,通常是在递归函数里,使用for循环,遍历所有排列或组合的可能,然后在for循环语句内调用递归函数。
回溯
回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来
,换一条路再试。用回溯算法解决问题的一般步骤为:
1、定义一个解空间,它包含问题的解。
2、利用适于搜索的方法组织解空间。
3、利用深度优先法搜索解空间。
4、利用限界函数避免移动到不可能产生解的子空间。
问题的解空间通常是在搜索问题的解的过程中动态产生的,这是回溯算法的一个重要特性。

方案一
对于长度为n的数组,我们需要依次确认每个位置上的元素。初始问题:从a[0]开始依次确认n个元素。如果我们确认a[0]之后,问题就变成从a[1]开始从剩余元素中选择一个元素确定a[1]。每次选择都有多种可能性,我们依次尝试(尝试后还原),并递归解决选择之后的产生的子问题,并定义出口。
[java] view plain copy
public List> permute(int[] nums) {
ArrayList numsArray=new ArrayList();
for(int i:nums){
numsArray.add(i);
}
Collections.sort(numsArray);
List> res=new ArrayList>();
solve(res,numsArray,0);
return res;
}
private void solve(List> res,ArrayList nums,int index){
if(index>=nums.size()){
List permutation=new ArrayList(nums);
res.add(permutation);
[java] view plain copy
}
for(int i=index;i<=nums.size()-1;i++){ Collections.swap(nums, i, index); solve(res,nums,index+1); Collections.swap(nums, i, index); } } 方案二 用一个标记数组标记元素是否已经使用过,每次从剩余元素中尝试添加新元素到临时解中,当没有新的元素可添加时,临时解就为最终的一个解。此方案比方法一要更加直观。 [java] view plain copy public List> permute(int[] nums) {
ArrayList numsArray=new ArrayList();
for(int i:nums){
numsArray.add(i);
}
boolean[] used=new boolean[numsArray.size()];
Collections.sort(numsArray);
List> res=new ArrayList>();
ArrayList subSet=new ArrayList();
solve(res,numsArray,subSet,used);
return res;
}
private void solve(List> res,ArrayList nums,ArrayList subSet,boolean[] used){
if(subSet.size()==nums.size()){
ArrayList clone=new ArrayList(subSet);
res.add(clone);
return;
}
for(int i=0;i> permuteUnique(int[] nums) {
ArrayList numsArray=new ArrayList();
for(int i:nums){
numsArray.add(i);
}
boolean[] used=new boolean[numsArray.size()];
Collections.sort(numsArray);
List> res=new ArrayList>();
ArrayList subSet=new ArrayList();
solve(res,numsArray,subSet,used);
return res;
}
private void solve(List> res,ArrayList nums,ArrayList subSet,boolean[] used){
if(subSet.size()==nums.size()){
ArrayList clone=new ArrayList(subSet);
res.add(clone);
return;
}
for(int i=0;i0&&!used[i-1]&&nums.get(i).equals(nums.get(i-1)))) continue;
subSet.add(nums.get(i));//加入新元素,并递归调用下一个元素
used[i]=true;
solve(res,nums,subSet,used);
subSet.remove(subSet.size()-1);//还原
used[i]=false;
}
}

分析
我们将排列看成一个n位整数,下一个排列组合就是当前整数增加并且保证增量最小。为了保证增量最小,因此我们需要保证变化的范围尽量限制在低位。因此我们采用如下策略:
1、从后往前寻找第一组相邻元素a[i]=0&&nums[index-1]>=nums[index]) index–;
if(index==0){
reverse(nums,0,nums.length-1);
return;
}
int smallerIndex=index-1,change=index;
//寻找恰当交换元素
while(change+1nums[smallerIndex])change++;
int t=nums[smallerIndex];nums[smallerIndex]=nums[change];nums[change]=t;
reverse(nums,index,nums.length-1);
}
private void reverse(int[] nums,int begin,int end){
int t;
while(begin0){
if(k>=factorial(n-index)){
int change=index+1;
while(arr[change] letterCombinations(String digits) {
String[] strMap={“”,””,”abc”,”def”,”ghi”,”jkl”,”mno”,”pqrs”,”tuv”,”wxyz”};
ArrayList res=new ArrayList();
if(digits.equals(“”)||digits==null) return res;
res.add(“”);
for(int i=0;i t=new ArrayList();
for(int j=0;j> combine(int n, int k) {
List> res=new ArrayList>();
int[] nums=new int[n];
ArrayList r=new ArrayList();
boolean[] used=new boolean[n];
for(int i=0;i> res,ArrayList r,int[] nums,int k,boolean[] used){
if(r.size()==k){
ArrayList clone=new ArrayList(r);
res.add(clone);
return ;
}
int index=r.size();
for(int i=index;i> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
List> res=new ArrayList>();
ArrayList r=new ArrayList();
solve(res,r,candidates,target,0);
return res;
}
public void solve(List> res,ArrayList r,int[] candidates,int target,int index){
if(target==0){
ArrayList clone=new ArrayList(r);
res.add(clone);
return;
}
if(index>=candidates.length||target> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
List> res=new ArrayList>();
ArrayList r=new ArrayList();
solve(res,r,candidates,target,0);
return res;
}
public void solve(List> res,ArrayList r,int[] candidates,int target,int index){
if(target==0){
ArrayList clone=new ArrayList(r);
res.add(clone);
return;
}
if(index>=candidates.length||target> combinationSum3(int k, int n) {
List> res=new ArrayList>();
ArrayList sub=new ArrayList();
solve(res,sub,k,n,1);
return res;
}
private void solve(List> res,ArrayList sub,int k,int n,int start){
if(sub.size()==k&&n==0){
ArrayList clone=new ArrayList(sub);
res.add(clone);
return;
}
if(n<0||start==10||(sub.size()==k&&n!=0)){ return; } //选择当前元素 sub.add(start); solve(res,sub,k,n-start,start+1); sub.remove(sub.size()-1); //不选择当前元素 solve(res,sub,k,n,start+1); } 分析 对于合法的括号表达式,从左边往右边看时,每时每刻左括号的个数大于等于右括号的个数。 我们可以将问题看成是对于长为2 n的字符串,从第一个位置开始我们选择'('或者')',同时要保证左括号个数永远大于右边括号的个数,并且最终左括号和右括号的个数都等于n。当我们做完所有的选择就得到了合法的括号表达式。 因此得到如下递归解法: [java] view plain copy public List generateParenthesis(int n) {
List res=new ArrayList();
if(n==0){
res.add(“”);
return res;
}
StringBuilder r=new StringBuilder();
solve(n,0,0,res,r);
return res;
}
private void solve(int n,int left,int right,List res,StringBuilder r){
if(r.length()==2*n){
System.out.println(r.toString());
res.add(r.toString());
return;
}
if(left> subsets(int[] nums) {
List> res=new ArrayList>();
res.add(new ArrayList());
for(int i=0;i> t=new ArrayList>();
for(List r:res){
t.add(r);
ArrayList clone=new ArrayList(r);
clone.add(nums[i]);
t.add(clone);
}
res=t;
}
return res;
}

分析
因为元素可以重复,并且需要过滤重复的集合,我们需要对生成子集的过程进行进一步的控制。我们将问题理解为,从a[0]开始求所有的子集,该问题可以分为两个问题1、选择a[0],从a[1]开始求所有子集并对每个子集加上a[0];2从a[1]开始求所有的子集。因此得到如下递归解法。
注:由于需要消除重复子集,因此我们在选择当前元素a[i]时,如果a[i-1]等于a[i]且我们没有选择,我们就必定不能选择a[i]。
[java] view plain copy
public List> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
boolean[] used=new boolean[nums.length];
List> res=new ArrayList>();
ArrayList sub=new ArrayList();
solve(res,0,sub,nums,used);
return res;
}
private void solve(List> res,int start,ArrayList sub,int[] nums,boolean[] used){
if(start==nums.length){
ArrayList clone=new ArrayList(sub);
res.add(clone);
return;
}
//选择当前元素
if(start>0&&nums[start]==nums[start-1]&&!used[start-1]){
//do nothing
}else{
used[start]=true;
sub.add(nums[start]);
solve(res,start+1,sub,nums,used);
sub.remove(sub.size()-1);
used[start]=false;
}
//不选择当前元素
solve(res,start+1,sub,nums,used);
}

分析
我们从每一个位置开始回溯,并标记元素是否已经使用过。
[java] view plain copy
public boolean exist(char[][] board, String word) {
boolean used[][]=new boolean[board.length][board[0].length];
for(int i=0;i> partition(String s) {
List> res=new ArrayList>();
List sub=new ArrayList();
solve(res,sub,s,0);
return res;
}
private void solve(List> res,List sub,String s,int start){
if(start==s.length()){
List clone=new ArrayList(sub);
res.add(clone);
return;
}
List ends=new ArrayList();
for(int i=start;i> emptyLocations=
new ArrayList>();
for(int row=0;row<9;row++){ for(int col=0;col<9;col++){ if(board[row][col]=='.'){ ArrayList location=new ArrayList();
location.add(row);location.add(col);
emptyLocations.add(location);
}
}
}
solve(board,0,emptyLocations);
}
private boolean solve(char[][] board,int index,ArrayList> emptyLocations){
if(index==emptyLocations.size()){
return true;
}
ArrayList location=emptyLocations.get(index);
int row=location.get(0),col=location.get(1);
for(char c=’1′;c<='9';c++){ if(isValid(board,row,col,c)){ board[row][col]=c; if(solve(board,index+1,emptyLocations)){ return true; }else{ board[row][col]='.'; } } } return false; } public boolean isValid(char[][] board,int row,int col,char c){ //验证行 for(int i=0;i<9;i++){ if(board[row][i]==c) return false; } //验证列 for(int i=0;i<9;i++){ if(board[i][col]==c) return false; } //验证3*3格子 for(int i=(row/3)*3;i<(row/3)*3+3;i++){ for(int j=(col/3)*3;j<(col/3)*3+3;j++){ if(board[i][j]==c) return false; } } return true; } 分析 我们知道N皇后问题通常采用回溯法求解。 方案一 对于每行每个位置进行尝试,并判断是否合法。 [java] view plain copy public List> solveNQueens(int n) {
ArrayList locations=new ArrayList();
List> res=new ArrayList>();
solve(res,locations,n);
return res;
}
private void solve(List> res,ArrayList locations,int n){
if(n==locations.size()){
addRes(res,locations);
return;
}
for(int i=0;i locations,int location){
for(int i=0;i> res,ArrayList locations){
List r=new ArrayList();
for(int i=0;i> solveNQueens(int n) {
int[] locations=new int[n+1];
for(int i=1;i<=n;i++){ locations[i]=i; } List> res=new ArrayList>();
solve(res,locations,1);
return res;
}
private void solve(List> res,int[] locations,int index){
if(index==locations.length){
addRes(res,locations);
return;
}
for(int i=index;i<=locations.length-1;i++){ if(isValid(locations,index,i)){ int t=locations[index];locations[index]=locations[i];locations[i]=t; solve(res,locations,index+1); t=locations[index];locations[index]=locations[i];locations[i]=t; } } } private boolean isValid(int[] locations,int index,int change){ for(int i=1;i> res,int[] locations){
List r=new ArrayList();
for(int i=1;i<=locations.length-1;i++){ StringBuilder builder=new StringBuilder(); for(int j=1;j<=locations.length-1;j++){ if(locations[i]==j){ builder.append("Q"); }else{ builder.append("."); } } r.add(builder.toString()); } res.add(r); } 注:在统计结果数量时,由于Java本身都是按值传递参数的(对于对象传递的是地址值),因此我们不用用int类型统计结果数量,同时由于Integer是不可变的,因此也不能使用Integer。这里我采用Integer容器来统计数量,此外还可以利用AtomicInteger原子整型或自定义引用类型来进行统计,也可以在方法调用中返回结果数量。如有更好的方法忘指教,谢谢!! [java] view plain copy public int totalNQueens(int n) { ArrayList locations=new ArrayList();
Stack count=new Stack();
count.add(new Integer(0));
solve(locations,n,count);
return count.get(0);
}
private void solve(ArrayList locations,int n,Stack count){
if(n==locations.size()){
count.push(new Integer(count.pop()+1));
return;
}
for(int i=0;i locations,int location){
for(int i=0;i

Leave a Reply

Your email address will not be published. Required fields are marked *