黑马程序员技术交流社区

标题: 算法题----真心求帮助 [打印本页]
作者: 中国移动    时间: 2012-7-20 00:48
标题: 算法题----真心求帮助
问题：用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连。

解答的大牛，希望给出思路和给出代码的注释谢谢

作者: 中国移动    时间: 2012-7-20 00:52
自己抢板凳，在线等
作者: 滔哥    时间: 2012-7-20 01:11
谁自己解答此题目，奖励3分技术分
作者: 滔哥    时间: 2012-7-20 01:40
  1. static int[] bits = new int[] { 1, 2, 3, 4, 5 };
  2. /**
  3. * @参数
  4. */
  5. public static void main(String[] args) {
  6. sort("", bits);
  7. }

  9. private static void sort(String prefix, int[] a) {
  10. if (a.length == 1) {
  11. System.out.println(prefix + a[0]);
  12. }

  14. for (int i = 0; i < a.length; i++) {
  15. sort(prefix + a[i], copy(a, i));
  16. }
  17. }

  19. private static int[] copy(int[] a,int index){
  20. int[] b = new int[a.length-1];
  21. System.arraycopy(a, 0, b, 0, index);
  22. System.arraycopy(a, index+1, b, index, a.length-index-1);
  23. return b;
  24. }

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

  4. public class TestQuestion {

  6. private String[] b = new String[]{"1", "2", "2", "3", "4", "5"};
  7. private int n = b.length;
  8. private boolean[] visited = new boolean[n];
  9. private int[][] a = new int[n][n];
  10. private String result = "";
  11. private TreeSet set = new TreeSet();

  13. public static void main(String[] args) {
  14. new TestQuestion().start();
  15. }

  17. private void start() {

  19. // 初始化map a[][]
  20. for (int i = 0; i < n; i++) {
  21. for (int j = 0; j < n; j++) {
  22. if (i == j) {
  23. a[i][j] = 0;
  24. } else {
  25. a[i][j] = 1;
  26. }
  27. }
  28. }

  30. //3和5不能相连
  31. a[3][5] = 0;
  32. a[5][3] = 0;

  34. for (int i = 0; i < n; i++) {
  35. this.depthFirstSearch(i);
  36. }

  38. // 打印结果
  39. Iterator it = set.iterator();
  40. while (it.hasNext()) {
  41. String string = (String) it.next();
  42. //“4”不能在第三的位置
  43. if (string.indexOf("4") != 2) {
  44. System.out.println(string);
  45. }
  46. }
  47. }

  49. private void depthFirstSearch(int startIndex) {
  50. visited[startIndex] = true;
  51. result = result + b[startIndex];
  52. if (result.length() == n) {
  53. //过滤重复的值
  54. set.add(result);
  55. }
  56. for(int j = 0; j < n; j++) {
  57. if (a[startIndex][j] == 1 && visited[j] == false) {
  58. depthFirstSearch(j);
  59. } else {
  60. continue;
  61. }
  62. }

  64. // 恢复
  65. result = result.substring(0, result.length() -1);
  66. visited[startIndex] = false;
  67. }
  68. }
复制代码
作者: 王宝康    时间: 2012-7-20 02:01
我有个想法，就是把随机生成的序列放到一个String类型的ArrayList或者数组中，然后遍历集合或者数组，取出的每个字符串进行正则表达式的判断。
作者: 王宝康    时间: 2012-7-20 02:12
王宝康 发表于 2012-7-20 02:01
我有个想法，就是把随机生成的序列放到一个String类型的ArrayList或者数组中，然后遍历集合或者数组，取出 ...


就凭这一分，我一定要做出来！这是被认同的喜悦，哈哈...
作者: 中国移动    时间: 2012-7-20 02:13
滔哥 发表于 2012-7-20 01:40
基本思路：
1 把问题归结为图结构的遍历问题。实际上6个数字就是六个结点，把六个结点连接成无向连通图，对 ...

{:3_47:}滔哥V5 霸气测漏啊
作者: 中国移动    时间: 2012-7-20 02:14
王艺霖 发表于 2012-7-20 01:35
最简单的就是
                   用外部变量接
1：首先要考虑他们是怎么组合排列的

{:3_46:}羡慕嫉妒恨，你要谢谢我啊，你因为我得了3分啊！算法V5
作者: 韦念欣    时间: 2012-7-20 02:26
本帖最后由 韦念欣 于 2012-7-20 02:28 编辑


这个我的代码！
  1. /*
  2. 问题：        用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，
  3.                 如：512234、212345等，要求："4"不能在第三位，"3"与"5"不能相连。
  4. */
  5. public class Demo
  6. {
  7.         public static long count = 0;
  8.         public static void main(String[] args){
  9.                 final String number = "122345";                        // 自定义N个数字（可以是N个任意字符）
  10.                 arrange(number,                                                 // 调用arrange方法递归遍历所有排列
  11.                                 new char[number.length()],
  12.                                 new boolean[number.length()],
  13.                                 0);
  14.                 System.out.println("符合要求的数据共有："+ count +"个.");
  15.         }

  17.         // 方法：递归遍历所有排列
  18.         // 参数：number        需要排列的字符
  19.         //                 tmp         临时结果数组
  20.         //                 used       每个字符的使用标识（标记是否已经使用）
  21.         //                 n              正在遍历的第n个数据
  22.         public static void arrange(final String number, char[] tmp, boolean[] used, int n){
  23.                
  24.                 // 递归出口：当得到一个与number长度相同的数据
  25.                 if (n == number.length()){
  26.                         String result = new String(tmp);                   // 将char数组转换为String

  28.                         // 判断条件："4"不能在第三位，"3"与"5"不能相连
  29.                         if (tmp[2] != '4' && !result.contains("35") && !result.contains("53")){
  30.                                 System.out.println(result);
  31.                                 ++count;                                                // 统计符合要求的结果
  32.                         }
  33.                         return;
  34.                 }

  36.                 // 递归排列
  37.                 for (int i=0; i<number.length(); i++){
  38.                         // 若当前数据为被使用
  39.                         if (!used[i]){
  40.                                 used[i] = true;                                        // 使用当前数据
  41.                                 tmp[n] = number.charAt(i);                  // 将数据填入临时结果数组中
  42.                                 arrange(number, tmp, used ,n+1);       // 递归遍历下一位数据
  43.                                 used[i] = false;                                       // 已经使用完当前数据
  44.                         }
  45.                 }
  46.         }
  47. }
复制代码




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2