[数据结构与算法]蓝桥杯冲刺——DFS

寻找三位数

链接: 寻找三位数.

像这种找数字的题目肯定就是DFS没得跑了

DFS其实模板还是很公式化的

参数的传递

最基本的参数主要有两个：

• start：该轮全排列的起始坐标
• len：排列数据总体的长度
  这道题我们知道数组长度，我们就不用传入数组长度了

DFS模板

public static void DFS(int start) {
		if(start == 8) {
			//填入排列完成后需要进行的操作
			}
		}
		
		for(int i=start;i<=8;i++) {
			swap(i,start);
			DFS(start+1);
			swap(i,start);//进行操作以后记得还原数据
		}
	}
	
	public static void swap(int i,int j) {
		int tmp = nums[i];
		nums[i] = nums[j];
		nums[j] = tmp;
	}

根据不同的题目，相应的代码肯定会有所变化，但是大致思想肯定是一致的

完整代码

import java.util.Scanner;
public class test {
	public static int[] nums = {1,2,3,4,5,6,7,8,9};
	public static void main(String[] args) {
		DFS(0);
	}
	
	public static void DFS(int start) {
		if(start == 8) {
			int a = 100*nums[0]+10*nums[1]+nums[2];
			int b= 100*nums[3]+10*nums[4]+nums[5];
			int c = 100*nums[6]+10*nums[7]+nums[8];
			if(b==2*a&&c==3*a) {
				System.out.println(a+"  "+b+"  "+c);
			}
		}
		
		for(int i=start;i<=8;i++) {
			swap(i,start);
			DFS(start+1);
			swap(i,start);
		}
	}
	
	public static void swap(int i,int j) {
		int tmp = nums[i];
		nums[i] = nums[j];
		nums[j] = tmp;
	}

}

纸牌三角形

链接: 纸牌三角形.

这题也是全排列问题，只不过是if终止条件里面进行判断条件，也就是功能语句不同而已。

还有就是需要去重，旋转三边加上对称，就是3*2=6。最后count结果除以6就可以输出了。

完整代码

import java.util.Scanner;
public class test {
	public static int[] nums = {1,2,3,4,5,6,7,8,9};
	public static int count=0;
	public static void main(String[] args) {
		DFS(0);
		System.out.println(count/6);
	}
	
	public static void DFS(int start) {
		if(start == 8) {
			int a = nums[0]+nums[1]+nums[2]+nums[3];
			int b= nums[3]+nums[4]+nums[5]+nums[6];
			int c = nums[6]+nums[7]+nums[8]+nums[0];
			if(a==b&&b==c) {
				count++;
				
			}
		}
		
		for(int i=start;i<=8;i++) {
			swap(i,start);
			DFS(start+1);
			swap(i,start);
		}
	}
	
	public static void swap(int i,int j) {
		int tmp = nums[i];
		nums[i] = nums[j];
		nums[j] = tmp;
	}

}

如果还有不清楚的地方，可以参考上面我给出的全排列讲解的链接，里面就是用此题当例题讲解的。