原题如下:用1、2、2、3、4、5这六个数字,用java写一个main函数,打印出所有不同的排列,如:512234、412345等,要求:"4"不能在第三位,"3"与"5"不能相连.
我看了回贴都没有很好解决,主要是没有排除重复。
解决思路:强化题目,用1、2、2、3、4、5这六个数字排列“递增”序列。其他要求不变。
算法思路:显然是递归,初始序列122345,先从末两位(45)变化(45,54),然后末三位(345) ... 直到最后六位.怎样解决重复问题?很简单,由于是递增序列,每生成新序列可与前一生成序列比较,如<放弃当前序列。当然有更好效率,如预先预测。代码如下:
class test
{
// 当前固定部分
private String CurFixPart;
private String PreGenNum;
public static void main(String[] args)
{
test t=new test();
t.GenControll("122345");
}
// 调整字符串s位置pos字符到最前
private String shift(String s, int pos)
{
String newStr;
if (s.length()>pos+1)
newStr=s.substring(pos, pos+1)
+s.substring(0, pos)
+s.substring(pos+1);
else
newStr=s.substring(pos)
+s.substring(0, pos);
return newStr;
}
protected int Validate(String newNum)
{
String newGenNum=CurFixPart+newNum;
if (Integer.valueOf(newGenNum)<=Integer.valueOf(PreGenNum))
return 0;
if (newGenNum.substring(2,3).equals("4") ||
(newGenNum.indexOf("35")!=-1) || (newGenNum.indexOf("53")!=-1))
return 0;
PreGenNum=newGenNum;
System.out.println(newGenNum);
return 0;
}
public void GenControll(String Base)
{
PreGenNum="0";
CurFixPart="";
GenNext(Base, 0);
}
void GenNext(String varPart, int curPos)
{
if (varPart.length()==2)
{
Validate(varPart);
Validate(shift(varPart, 1));
return;
}
// Next Layer
String newGen=shift(varPart, curPos);
String SavedFixPart=CurFixPart;
CurFixPart=CurFixPart+newGen.substring(0,1);
GenNext(newGen.substring(1), 0);
CurFixPart=SavedFixPart;
// 同层递增
if (curPos==varPart.length()-1)
return;
GenNext(varPart, curPos+1);
}
}
序列122345测试通过。
有什么意见请大家多多提点。
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;
}
}
3,5不能相连:实际要求这个连通图的结点3,5之间不能连通, 可在构造图结构时就满足改条件,然后再遍历图。
代码中请注意这几行:
// 3 and 5 can not be the neighbor.
a[3][5] = 0;
a[5][3] = 0;
只要这样定义图,根本不用在代码中写IF ELSE语句。
实际上基于图的算法好处在于,只要你能定义好满足题目要求的图结构,遍历的结果就是你要的结果,不用任何对遍历结果做任何处理。包括本题中的:4不能在第三位置,3,5不能相连,唯一
性要求,其实都可以在体现在构造的图形结构里,然后直接遍历图取得自己要的结果。而不用再次处理结果集。
只是说这里实际上对其它要求要体现在图结构里有困难(理论上是可以的),但起码3,5不能相接是很好构造的,就是上面的代码段来解释的。
关于图形数据结构建议先看看数据结构的书,主要是将如何利用二维数组描述图结构,再看看图的深度遍历实现原理。最后再应用到这个问题上来,自然就不难明白了。
分享到:
相关推荐
Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法...
中山大学遗传算法基本习题
C++面试题笔试题C++ 数据结构算法笔试题资料合集: 50个C、C++面试题.pdf C++ 数据结构、算法笔试题.docx C++基础面试题.docx C++开发工程师面试题库.docx C++技能测试试卷一及答案.docx C++技能测试试卷二及答案....
《程序员的算法趣题》是一本专门为IT从业者和有志于进入这个领域的学习者准备的算法书籍。它通过一系列有趣且富有挑战性的题目,旨在帮助读者深入理解和掌握计算机科学中的核心算法,提升解决实际问题的能力。这本书...
4. **考试**:这部分应该是模拟考试或实际考试的试卷,可能包含了选择题、填空题、编程题等多种题型,旨在测试学生对算法的理解和应用能力。 在学习《算法导论》的过程中,理解并掌握以下知识点至关重要: 1. **...
《程序员算法趣题——随书源码》是一个与算法相关的学习资源,包含了增井敏克著作《程序员算法趣题》中的实例代码。增井敏克是算法领域知名的专家,他的书籍通常深入浅出,旨在帮助程序员提升算法思维和解决实际问题...
"JAVA经典算法90题【含源码】"的资源集合为Java初学者提供了一个绝佳的学习平台,旨在通过实际操作来理解和应用各种基础及进阶算法。下面将详细阐述这些算法题目所涉及的知识点,并建议的学习路径。 首先,"JAVA...
贪心算法 每天一道算法题:分治算法,回归算法,贪心算法,回溯算法.zip
计算机常见算法面试题 本资源摘要信息涵盖了计算机常见算法面试题,主要涉及链表、字符串操作、搜索算法等方面的知识点。下面是对标题、描述、标签和部分内容的详细解释: 标题:计算机常见算法面试题 该标题表明...
全排序、二分查找、冒泡排序、阶乘、最大公约数、最小公倍数、...这是里面包含的算法,本人在准备笔试的时候找的,算法尽量采用最优的。 所有的代码均经过测试,个人觉得没有问题,如果哪位大牛找到错误,欢迎批评指正
Java基础编程练习题和经典算法是提升编程技能和准备面试的关键环节。这50题的基础编程练习涵盖了Java语言的核心概念,如数据类型、控制结构、类与对象、异常处理、集合框架等,旨在帮助学习者巩固基础知识并提高编程...
C语言算法题合集.zipC语言算法题合集.zipC语言算法题合集.zipC语言算法题合集.zipC语言算法题合集.zipC语言算法题合集.zipC语言算法题合集.zipC语言算法题合集.zipC语言算法题合集.zipC语言算法题合集.zipC语言算法...
算法 ,简单 入门 LeetCode网站开放的简单算法题,用于平时检验自己的算法能力,程序设计.
本文总结了五道常见的算法面试题,并对每一道题目进行了详细解答和分析,旨在帮助大家深入理解算法设计的基本原理和方法。 首先,将二元查找树转换为排序双向链表。二元查找树(BST)的性质是:对于任意节点,其左...
Java 算法编程题汇总 Java 算法编程题汇总是本文的主题,本文将对 50 道 Java 算法编程题进行汇总,涵盖了 Fibonacci 序列、素数、水仙花数、质因数分解等多个方面的知识点。 Fibonacci 序列 Fibonacci 序列是...
《吉林大学算法分析习题课答案》是一份与算法分析相关的学习资料,主要针对的是吉林大学算法分析课程的习题解答。这份压缩包文件包含了课件等教学资源,旨在帮助学生理解和掌握算法分析的核心概念、方法和技巧。下面...
北航研究生算法期末考试题是针对北京航空航天大学计算机科学与技术6系研究生的一份重要的学习资源,这份资料包含了历年来的试题,尽管年份较早,但其价值并未因时间流逝而减少。由于近年来该课程的考试内容变化不大...
以下是大疆2019年8月雷达算法工程师笔试题的知识点详细解读。 首先,“DJI大疆2019年8月雷达算法工程师笔试题B卷”这一标题说明这是一次面向特定职位(雷达算法工程师)的招聘考试。大疆(DJI)是一家专门从事民用...
2019年的这份笔试题涵盖了多个相关的知识点,下面我会详细解释。 首先,电磁场与电磁波的知识在这个笔试题中占比不多,但这是雷达技术的基础。电磁波的传播特性、极化效应以及电磁波与物体的相互作用等基础概念,对...