DFS回溯题：奇偶交错排列

末蓝、 2023-10-06 19:26 25阅读 0赞

## DFS回溯题：奇偶交错排列 ##

#### 问题： ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_13_color_FFFFFF_t_70_g_se_x_16]

#### 思路： ####

使用DFS回溯法解决  
关于DFS回溯法，它并不是一种具体的算法，应该说是一种思想  
DFS的基本思想：  
1：一条路走到底。  
2：只有当前状态不存在任何后继状态时，才返回至上一层状态(也就是从哪来回哪去)  
3：一旦从该状态返回，说明该状态及其后继状态都已经访问过，故无需再次访问。

对于本题，要求求解相邻数字奇偶性不同的全排列。我们可以使用dfs函数逐位遍历所有情况，由于每个数字在排列中只能出现一次，因此我们使用visit\[\]数组保存一个数字是否出现过。又因为相邻数字要求奇偶性不同，我们需保存上一位数字的奇偶性，以决定当前位可选哪些数字。  
选取当前位数字时，从1~n中选择满足条件的数字，之后调用下一位的dfs函数，dfs函数返回，即表示当前分支已走完，将当前位数字的visit重置，即回溯到上一层状态

dfs函数的参数有保存每位数字的数组array，当前位的下标now，上一位数字的奇偶性last，题目给定的n，以及visit数组。设now从1开始，当now == n+1时，表示已经得到一个排列，dfs返回

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
**需注意的点**：

*  判断i的奇偶性使用( i & 1 )，即i和1相与，若i为奇数，和1相与得到1，否则得0

#### 代码： ####

import java.util.*;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            int n;
            int[] array = new int[12];
            int[] visit = new int[12];
            while (scanner.hasNextInt()) {
        
                Arrays.fill(visit, 0);
                n = scanner.nextInt();
                dfs(array, 1, -1, n, visit);
            }
    
        }
    
        static void dfs(int[] array, int now, int last, int n, int[] visit) {
        
            int i;
            if (now == n + 1) {
        
                for (i = 1;i <= n;i++) {
        
                    System.out.print(array[i] + " ");
                }
                System.out.print('\n');
            }
            for (i = 1;i <= n;i++) {
        
                if (visit[i] == 0 && last != (i & 1)) {
        
                    array[now] = i;
                    visit[i] = 1;
                    dfs(array, now + 1, i & 1, n, visit);
                    visit[i] = 0;
                }
            }
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/90fa27cf84ff46ac91d8418d7aa4d321.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_13_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/a205c009c7084aa0ae7e4203c22af548.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_13,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/62288edc3cf34c71a49045275bc957e6.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16