DFS(深度优先搜索算法)——Java实现(含例题）
基本概念
深度优先搜索算法（Depth First Search，简称DFS）：一种用于遍历或搜索树或图的算法。
沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。
回溯法
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
基本模版
int check(参数)
{
if(满足条件)
return 1;
return 0;
}
void dfs(int step)
{
判断边界
{
相应操作
}
尝试每一种可能
{
满足check条件
标记
继续下一步dfs(step+1)
恢复初始状态（回溯的时候要用到）
}
}
-
水域大小
你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。
示例：
输入：
[
[0,2,1,0],
[0,1,0,1],
[1,1,0,1],
[0,1,0,1]
]
输出： [1,2,4]
提示：
0 < len(land) <= 1000
0 < len(land[i]) <= 1000
class Solution {
public int[] pondSizes(int[][] land) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < land.length; i++) {
for (int j = 0; j < land[i].length; j++) {
if (land[i][j] == 0) {
list.add(dfs(land, i, j));
}
}
}
int[] arr = new int[list.size()];
for (int i = 0; i < arr.length; i++) {
arr[i] = list.get(i);
}
Arrays.sort(arr);
return arr;
}
public int dfs(int[][] land, int i, int j) {
if (i < 0 || j<0 || i>=land.length || j>=land[i].length || land[i][j] != 0) {
return 0;
}else {
land[i][j] = 1;
int count = 1;
count += dfs(land, i+1, j);
count += dfs(land, i-1, j);
count += dfs(land, i, j+1);
count += dfs(land, i, j-1);
count += dfs(land, i-1, j-1);
count += dfs(land, i-1, j+1);
count += dfs(land, i+1, j-1);
count += dfs(land, i+1, j+1);
return count;
}
}
}
- 字符串的全排列
public static void permutation(char[] chars , int index , List<String> res) {
if (index == chars.length - 1) {
String string = new String(chars);
res.add(string);
}else {
for (int i = index; i < chars.length; i++) {
//去重
if (isSwap(chars, index, i)) {
swap(chars, index, i);
permutation(chars, index+1, res);
//回溯,恢复到初始状态
swap(chars, index, i);
}
}
}
}
public static boolean isSwap(char[] chars, int begin, int end) {
for (int i = begin; i < end; i++) {
if (chars[i] == chars[end]) {
return false;
}
}
return true;
}
public static void swap(char[] chars, int i, int j) {
char temp = chars[j];
chars[j] = chars[i];
chars[i] = temp;
}
- 带分数
题目：
100 可以表示为带分数的形式：100 = 3 + 69258 / 714。
还可以表示为：100 = 82 + 3546 / 197。
注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。
类似这样的带分数，100 有 11 种表示法。
输入格式
从标准输入读入一个正整数N (N<1000*1000)
输出格式
程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。
注意：不要求输出每个表示，只统计有多少表示法！
样例输入1
11
样例输出1
14
样例输入2
105
样例输出2
6
static int n, res;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
sc.close();
int[] data = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
getQuanpailie(data, 0);
System.out.println(res);
}
/**
* 得到三部分的十进制数
* @param data
* @param begin
* @param end
* @return
*/
public static int getNum(int[] data, int begin, int end) {
int num = 0;
for (int i = begin; i < end; i++) {
num = num * 10 + data[i];
}
return num;
}
/**
* 实现全排列后，分成三部分进行计算
* @param data
* @param k
*/
public static void getQuanpailie(int[] data, int k) {
if (data.length - 1 == k) {
//把全排列好的数，分成三部分，进行计算
System.out.println(Arrays.toString(data));
for (int i = 1; i < data.length; i++) {
for (int j = i+1; j < data.length; j++) {
int pre = getNum(data, 0, i);
int mid = getNum(data, i, j);
int fon = getNum(data, j, 9);
if (mid % fon != 0) {
continue;
}
if (pre + mid/fon == n) {
res ++;
}
}
}
}else {
//全排列
for (int i = k; i < data.length; i++) {
swap(data, k, i);
getQuanpailie(data, k+1);
swap(data, k, i);
}
}
}
public static void swap(int[] data, int i, int j) {
int t = data[i];
data[i] = data[j];
data[j] = t;
}
- 素环圈
环由N个圈组成，如图所示。将自然数1, 2、…、n分别放在每个圆中，两个相邻圆中的数字之和应该是素数。
注意：第一个圈的数字应该总是1。
输入:
n (0<n<20)
输出:
输出格式如下所示。每行代表环中的一系列圆数，从1顺时针和逆时针开始。数字的顺序必须满足上述要求。按词典顺序打印解决方案。
Sample Input:
6
Sample Output:
1 4 3 2 5 6
1 6 5 2 3 4
Sample Input:
8
Sample Output:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
sushuquan(n);
}
public static void sushuquan(int n) {
int[] data = new int[n];
for (int i = 0; i < data.length; i++) {
data[i] = i+1;
}
dfs(data, 1);
}
public static void dfs(int[] data, int index) {
if (index == data.length -1) {
boolean b = true;
for (int i = 0; i < data.length-1; i++) {
if (!isPrime(data[i]+data[i+1])) {
b = false;
}
}
if (b) {
b = isPrime(data[0] +data[data.length -1]);
}
if (b) {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i]);
System.out.print(" ");
}
System.out.println();
}
}else {
for (int i = index; i < data.length; i++) {
swap(data, index, i);
dfs(data, index+1);
swap(data, index, i);
}
}
}
public static void swap(int[] data, int i, int j) {
int t = data[i];
data[i] = data[j];
data[j] = t;
}
public static boolean isPrime(int num) {
if (num <= 3) {
return num > 1;
}
// 不在6的倍数两侧的一定不是质数, 在6的倍数两侧的不一定是质数， 比如25.
if (num % 6 != 1 && num % 6 != 5) {
return false;
}
int sqrt = (int) Math.sqrt(num);
for (int i = 5; i <= sqrt; i += 6) {
if (num % i == 0 || num % (i + 2) == 0) {
return false;
}
}
return true;
}