对一个算法笔试题的注解

对一个算法笔试题的注解

算法程序题：

    该公司笔试题就1个，要求在10分钟内作完。

    题目如下：用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连。

  基本思路：
1 把问题归结为图结构的遍历问题。实际上6个数字就是六个结点，把六个结点连接成无向连通图，对于每一个结点求这个图形的遍历路径，所有结点的遍历路径就是最后对这6个数字的排列组合结果集。
2 显然这个结果集还未达到题目的要求。从以下几个方面考虑：
  1. 3，5不能相连：实际要求这个连通图的结点3，5之间不能连通, 可在构造图结构时就满足改条件，然后再遍历图。
  2. 不能有重复: 考虑到有两个2，明显会存在重复结果，可以把结果集放在TreeSet中过滤重复结果。//TreeSet用于过滤一个集合中相同的东西还真是个挺不错的方法
  3. 4不能在第三位: 仍旧在结果集中去除满足此条件的结果。

采用二维数组定义图结构，最后的代码是：

 1package test;
 2
 3import java.util.Iterator;
 4import java.util.TreeSet;
 5
 6public class TestQuestion {
 7
 8    private String[] b = new String[] { "1", "2", "2", "3", "4", "5" };
 9    private int n = b.length;
10    private boolean[] visited = new boolean[n];
11    private int[][] a = new int[n][n];
12    private String result = "";
13    private TreeSet treeSet = new TreeSet();// 用于保存结果，具有过滤相同结果的作用。
14
15    public static void main(String[] args) {
16        new TestQuestion().start();
17    }
18
19    private void start() {
20        // 创建合法路径标识集合
21        for (int i = 0; i < n; i++) {
22            for (int j = 0; j < n; j++) {
23                if (i == j) {
24                    a[i][j] = 0;
25                } else {
26                    a[i][j] = 1;
27                }
28            }
29        }
30        a[3][5] = 0;
31        a[5][3] = 0;
32        for (int i = 0; i < n; i++) {
33            this.depthFirstSearch(i);// 深度递归遍历
34        }
35        Iterator it = treeSet.iterator();
36        while (it.hasNext()) {
37            String string = (String) it.next();
38
39            if (string.indexOf("4") != 2) {
40                System.out.println(string);
41            }
42        }
43    }
44
45    /**
46     * 深度优先遍历
47     * 
48     * @param startIndex
49     */
50    private void depthFirstSearch(int startIndex) {
51        // 递归的工作
52        visited[startIndex] = true;// 用于标识已经走过的节点
53        result = result + b[startIndex];// 构造结果
54        if (result.length() == n) {
55            treeSet.add(result);// 添加到TreeSet类型中，具有过滤相同结果的作用
56        }
57        // 每走到一个节点，挨个遍历下一个节点
58        for (int j = 0; j < n; j++) {
59            if (a[startIndex][j] == 1 && visited[j] == false) {
60                depthFirstSearch(j);// 深度递归遍历
61            } else {
62                continue;
63            }
64        }
65        // 递归的收尾工作
66        result = result.substring(0, result.length() - 1);
67        visited[startIndex] = false;// 取消访问标识
68    }
69}
70

转载于http://www.blogjava.net/ITdavid/archive/2008/02/27/182483.html


posted on 2008-03-01 10:42 鲁胜迪 阅读(292) 评论(0)  编辑  收藏


只有注册用户登录后才能发表评论。
网站导航:
 
<2008年3月>
日一二三四五六
2425262728291
2345678
9101112131415
16171819202122
23242526272829
303112345

导航

统计

常用链接

留言簿(4)

随笔分类

随笔档案

文章分类

新闻分类

搜索

最新评论

阅读排行榜

评论排行榜