算法程序题:
该公司笔试题就1个,要求在10分钟内作完。
题目如下:用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;
}
}
分享到:
相关推荐
经典图论算法题的模板实现,包括最短路,宽搜深搜,拓扑序列,二分图等问题。作者参加算法比赛的利器。现在免费送给你。适合参加蓝桥杯、PAT等算法比赛或者面试的图论基础知识。
给大家分享一套课程——算法面试专题课(Java版),Google面试官带你高质量刷题视频教程,希望对大家面试有帮助。
java实现的图论中的经典算法,包括Dijistral和Krustral算法,代码有详尽的注释,直接粘贴就可以运行,适合新手
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
可以直接运行、无bug、图论算法-将.m文件加入MATLAB当前工作目录,打开点击Run即可运行。
算法设计上机题的最后一题,题目不好描述= =
本书系统讲解数据结构...第2版在延续了第1版理论结合实际的风格的同时,在理论上更精深了一层,添加了很多数据结构的经典问题与新的思想,比如NP完整性、图论中的团问题以及结合自动机理论探讨的字符串匹配技术等。...
第11章_图论模型与算法
玩儿转图论算法 - 课程官方代码仓 大家好, 欢迎大家来到我在上的实战课程的官方代码仓。这个代码仓将不仅仅包含课程的所有源代码,还将发布课程的更新相关内容,勘误信息以及计划的更多可以丰富课程的内容,如更多...
8.6 路径压缩和按秩求并的最坏情形 8.7 一个应用 小结 练习题 参考文献第9章 图论算法 9.1 若干定义 9.2 拓扑排序 9.3 最短路径算法 9.3.1 无权最短路径 9.3.2 dijkstra算法 9.3.3 具有负边值的...
8.6 路径压缩和按秩求并的最坏情形 8.7 一个应用 小结 练习题 参考文献第9章 图论算法 9.1 若干定义 9.2 拓扑排序 9.3 最短路径算法 9.3.1 无权最短路径 9.3.2 dijkstra算法 9.3.3 具有负边值的...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
Coursera上的公开课,普林斯顿大学教授Robert Sedgewick主讲《Algorithms》算法 Java实现 课程网站http://algs4.cs.princeton.edu/home/ 视频一个两部分,算法(一)主要集中在基础的数据结构、排序、查找算法。 ...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
Java版本算法练习+笔记总结 按照数组-> 链表-> 哈希表->字符串->栈与队列->树->回溯->贪心->动态规划->图论->高级数据结构进行系统的练习 每道题都有标号和题目链接.zip
leetcode 分类 Learning Play Algorithm by Java 互联网公司面试真题 LeetCode ... 玩转算法面试-- Leetcode真题分门别类讲解 ...玩转算法 ...看得见的算法 ...恋上数据结构与算法1-基础 ...图论算法 经典应用
图论算法及其matlab程序代码.pdf
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...