题目如下:用1、2、2、3、4、5这六个数字,用java写一个main函数,打印出所有不同的排列,如:512234、412345等,要求:"4"不能在第三位,"3"与"5"不能相连。
static int[] bits = new int[] { 1, 2, 3, 4, 5 };
/**
* @param args
*/
public static void main(String[] args) {
sort("", bits);
}
private static void sort(String prefix, int[] a) {
if (a.length == 1) {
System.out.println(prefix + a[0]);
}
for (int i = 0; i < a.length; i++) {
sort(prefix + a[i], copy(a, i));
}
}
private static int[] copy(int[] a,int index){
int[] b = new int[a.length-1];
System.arraycopy(a, 0, b, 0, index);
System.arraycopy(a, index+1, b, index, a.length-index-1);
return b;
}
**********************************************************************
基本思路:
1 把问题归结为图结构的遍历问题。实际上6个数字就是六个结点,把六个结点连接成无向连通图,对于每一个结点求这个图形的遍历路径,所有结点的遍历路径就是最后对这6个数字的排列组合结果集。
2 显然这个结果集还未达到题目的要求。从以下几个方面考虑:
1. 3,5不能相连:实际要求这个连通图的结点3,5之间不能连通, 可在构造图结构时就满足改条件,然后再遍历图。
2. 不能有重复: 考虑到有两个2,明显会存在重复结果,可以把结果集放在TreeSet中过滤重复结果
3. 4不能在第三位: 仍旧在结果集中去除满足此条件的结果。
采用二维数组定义图结构,最后的代码是:
import java.util.Iterator;
import java.util.TreeSet;
public class TestQuestion {
private String[] b = new String[]{"1", "2", "2", "3", "4", "5"};
private int n = b.length;
private boolean[] visited = new boolean[n];
private int[][] a = new int[n][n];
private String result = "";
private TreeSet set = new TreeSet();
public static void main(String[] args) {
new TestQuestion().start();
}
private void start() {
// Initial the map a[][]
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
a[i][j] = 0;
} else {
a[i][j] = 1;
}
}
}
// 3 and 5 can not be the neighbor.
a[3][5] = 0;
a[5][3] = 0;
// Begin to depth search.
for (int i = 0; i < n; i++) {
this.depthFirstSearch(i);
}
// Print result treeset.
Iterator it = set.iterator();
while (it.hasNext()) {
String string = (String) it.next();
// "4" can not be the third position.
if (string.indexOf("4") != 2) {
System.out.println(string);
}
}
}
private void depthFirstSearch(int startIndex) {
visited[startIndex] = true;
result = result + b[startIndex];
if (result.length() == n) {
// Filt the duplicate value.
set.add(result);
}
for(int j = 0; j < n; j++) {
if (a[startIndex][j] == 1 && visited[j] == false) {
depthFirstSearch(j);
} else {
continue;
}
}
// restore the result value and visited value after listing a node.
result = result.substring(0, result.length() -1);
visited[startIndex] = false;
}
}
- 浏览: 26547 次
- 性别:
- 来自: 北京
最新评论
java难度大算法
- 博客分类:
- 算法
相关推荐
用java程序编写实现遗传算法的算法包。
java算法题的总结 java中算法的重要部分,算法要注意是基础
java算法 经典算法 各个等级的各个难度程度的都有 适合大多数学习和参考
java经典题目,九十道好题目,经典算法,系统锻炼你的思维能力和编码技术,
java课程设计项目——Java语言编写的一个迷宫小游戏(源码+详细说明文档)java课程设计项目——Java语言编写的一个迷宫小游戏(源码+详细说明文档)java课程设计项目——Java语言编写的一个迷宫小游戏(源码+详细...
java编写的递归算法的经典事例。 代码很短,没有点基础理解起来还真有点难度。很有挑战性。 不是我写的。这里只是分享一下。 功能是实现全排列。
这些算法按照难度和类型进行分类,包括数组、字符串、递归、排序、搜索、动态规划等多个领域。每个算法都提供了详细的解析和代码实现,帮助读者深入理解算法的原理和应用。 对于初学者,这些算法可以帮助他们掌握...
自己用GUI写的一个数独小游戏。。可选择难度,生成一个只有唯一解的数独。。可显示答案,玩家也可以自己做题。代码+算法全在里面
Java算法大全(100种算法)囊括了JAVA高难度算法!!内容丰富~~~
SQL与JAVA算法题目(难度和一般面试笔试差不多).doc
基于java和协同过滤算法实现商品推荐功能的购物电商系统源码(高分项目).zip 已获老师指导并通过的高分毕业设计项目,也可作为期末大作业和课程设计,纯手打高分项目,小白实战没难度。 基于java和协同过滤算法...
本书全面讲述算法和数据结构的必备知识,具有以下几大特色。 ? 算法领域的经典参考书 Sedgewick畅销著作的最新版,反映了经过几十年演化而成的算法核心知识体系 ? 内容全面 全面论述排序、搜索、图处理和字符串处理...
本书全面讲述算法和数据结构的必备知识,具有以下几大特色。 算法领域的经典参考书 Sedgewick畅销著作的最新版,反映了经过几十年演化而成的算法核心知识体系 内容全面 全面论述排序、搜索、图处理和字符...
可以根据设置不同难度生成9x9数独题
本书全面讲述算法和数据结构的必备知识,具有以下几大特色。 算法领域的经典参考书 Sedgewick畅销著作的最新版,反映了经过几十年演化而成的算法核心知识体系 内容全面 全面论述排序、搜索、图处理和字符...
本书全面讲述算法和数据结构的必备知识,具有以下几大特色。 算法领域的经典参考书 Sedgewick畅销著作的最新版,反映了经过几十年演化而成的算法核心知识体系 内容全面 全面论述排序、搜索、图处理和字符...
更新到JAVA 5.0 的版本,有范性 课后题目有难度,适合挑战自己 作者Robernto Tamassia Michael T.Goodrich
《算法(第4版)》全面讲述算法和数据结构的必备知识,具有以下几大特色。 1、 算法领域的经典参考书:Sedgewick畅销著作的最新版,反映了经过几十年演化而成的算法核心知识体系 2、内容全面:全面论述排序、...
因此其分支更多,生成的迷宫更复杂,难度更大,也更自然。 (2).使用深度优先算法生成迷宫,深度优先法生成的迷宫极度扭曲,有着一条明显的主路, (3).使用递归分割算法生成迷宫,递归分割法生成的迷宫较为简单...
java基于蚁群算法路由选择可视化动态模拟(论文+开题报告+翻译+任务书+外文翻译) 摘 要 路由选择是一种基于网络层的协议,而所有流行的网络层路由选择协议都是基于以下两种典型的分布式算法之一:距离向量路由算法和...