Go语言视频零基础入门到精通

javalearner

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

不是特别难的题目，暴力算和用图论算（深度遍历）都可以，结果是198。

1. import java.util.Iterator;  
   
2. import java.util.TreeSet;  
   
3. public class CharSequence {  
   
4.    private String[] c = {"1","2","2","3","4","5"};  
   
5.    private int n = c.length;  
   
6.    private boolean[] visited = new boolean[n];  
   
7.    private int[][] g = new int[n][n];  
   
8.    private TreeSet< String> ts = new TreeSet< String>();  
   
9.    private String result = "";  
   
10.   public CharSequence(){  
    
11.     for(int i=0; i< n;i++){
    
12.      for(int j=0; j< n;j++){
    
13.       if(i == j) g[i][j] = 0;  
    
14.        else g[i][j] = 1;  
    
15.       }  
    
16.     }  
    
17.     g[3][5] = 0;  
    
18.     g[5][3] = 0;  
    
19.    }  
    
20. public void depthFirst(int index){  //搜索以index开头的排列
    
21.    visited[index] = true;  
    
22.    result += c[index];  
    
23.    if(result.length() == n){  
    
24.      ts.add(result);  
    
25.      result = result.substring(0,result.length()-1);  
    
26.      visited[index] = false;  
    
27.    }  
    
28.    else{  
    
29.      for(int i=0; i< n;i++){
    
30.       if(!visited[i] && g[index][i] == 1){  
    
31.        depthFirst(i);  
    
32.       }else continue;  
    
33.      }  
    
34.    result = result.substring(0,result.length()-1);  
    
35.    visited[index] = false;  
    
36.    }  
    
37. }  
    
38. public void graphicGet(){  
    
39.    for(int i=0; i< n;i++){
    
40.      depthFirst(i);  
    
41.    }  
    
42.    int count = 0;  
    
43.    System.out.print("搜索的结果：");  
    
44.    Iterator< String> it = ts.iterator();  
    
45.    while(it.hasNext()){  
    
46.      String tmp = it.next();  
    
47.      //(tmp.contains("35")) continue;  
    
48.      //(tmp.contains("53")) continue;  
    
49.      if(tmp.charAt(3) == "4") continue;  
    
50.      System.out.println(tmp);  
    
51.      count++;  
    
52.     }  
    
53.   System.out.println("共计："+count+"个");  
    
54. }  
    
55. public void bruteForce(){  
    
56.    System.out.println("暴力搜的结果：");  
    
57.    int count = 0;  
    
58.    for(int i = 122345; i< 543222; i++){  
    
59.     String tmp = ""+i;  
    
60.     if(tmp.charAt(3) == "4") continue;  //"4"不能在第三位
    
61.     if(tmp.contains("35")) continue;  //"3"与"5"不能相连。
    
62.     if(tmp.contains("53")) continue;  //"3"与"5"不能相连。
    
63.     //必需同时含5、4、3、1
    
64.     if(tmp.contains("5") && tmp.contains("4") && tmp.contains("3") && tmp.contains("1")){  
    
65.      int index = tmp.indexOf("2");  
    
66.      if(index == -1) continue;  //没有2
    
67.      if(index == tmp.length()-1)  continue;  //只有一个2
    
68.      if(tmp.substring(index+1).contains("2")){  
    
69.        System.out.println(tmp);  
    
70.        count++;  
    
71.      }  
    
72.     }  
    
73.    }  
    
74.    System.out.print("共计："+count+"个");  
    
75. }  
    
76. public void recrusive(){  
    
77. }  
    
78. public static void main(String[] args) {  
    
79.    CharSequence cs = new CharSequence();  
    
80.    //图论的方法  
    
81.    cs.graphicGet();  
    
82.    //暴力搜索  
    
83.   // cs.bruteForce();  
    
84. }  
    
85. }

复制代码

C:java>javac CharSequence.java C:java>java CharSequence
搜索的结果：122345
122543
123245
123254
124325
124523
125234
125243
132245
132254
132524
132542
134225
134252
134522
142325
142523
143225
143252
145223
145232
152234
152243
152324
152342
154223
154232
154322
212345
212543
213245
213254
214325
214523
215234
215243
221345
221543
223145
223154
224315
224513
225134
225143
231245
231254
231524
231542
232145
232154
232514
232541
234125
234152
234215
234251
234512
234521
241325
241523
242315
242513
243125
243152
243215
243251
245123
245132
245213
245231
251234
251243
251324
251342
252134
252143
252314
252341
254123
254132
254213
254231
254312
254321
312245
312254
312524
312542
314225
314252
314522
315224
315242
321245
321254
321524
321542
322145
322154
322514
322541
324125
324152
324215
324251
324512
324521
325124
325142
325214
325241
341225
341252
341522
342125
342152
342215
342251
342512
342521
345122
345212
345221
412325
412523
413225
413252
415223
415232
421325
421523
422315
422513
423125
423152
423215
423251
425123
425132
425213
425231
431225
431252
431522
432125
432152
432215
432251
432512
432521
451223
451232
451322
452123
452132
452213
452231
452312
452321
512234
512243
512324
512342
513224
513242
514223
514232
514322
521234
521243
521324
521342
522134
522143
522314
522341
523124
523142
523214
523241
524123
524132
524213
524231
524312
524321
541223
541232
541322
542123
542132
542213
542231
542312
542321
543122
543212
543221
共计：198个 C:java>

   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/11/30/000655390.zip