長跑排名預測

參考代碼

 1 public class yucepaiming {
 2     //存盤運動員數量與圍觀黨數量
 3     private static int n,m;
 4     //存盤圍觀黨預測結果
 5     private static String[][] s;
 6     //存盤運動員排名順序
 7     private static int[] list;
 8     //存盤滿足預測的結果總和
 9     private static int sum;
10     private static List<int[]> alist = new ArrayList<>();
11     public static void main(String[] args) {
12         String str = new Scanner(System.in).nextLine();
13         n = Integer.parseInt(str.split(" ")[0]);
14         m = Integer.parseInt(str.split(" ")[1]);
15         s = new String [m][];
16         for(int i=0;i<m;i++){
17             str = new Scanner(System.in).nextLine();
18             s[i]=str.split(" ");
19         }
20         //初始化排名，1號第一名，2號第二名...
21         list = new int[n];
22         for(int i=0;i<n;i++){
23             list[i]=i;
24         }
25         //使用回溯演算法，引數為運動員排名，0為第一名
26         dg(0);
27         System.out.println(sum);
28         for(int[] a : alist){
29             str = Arrays.toString(a);
30             str = str.replace("[", "");
31             str = str.replace("]", "");
32             System.out.println(str);
33         }
34     }
35     private static void dg(int index) {
36         //當最后一個順序已經排好并且滿足預測條件的話
37         if(index == n && filter(list)){
38             sum++;
39             //注意必須重新復制陣列，因為存入集合中的只是陣列地址，如果沒有復制，當陣列改變時，集合的元素也會改變
40             alist.add(Arrays.copyOf(list, list.length));
41         }else{
42             /*交換順序->排下一個運動員->還原順序,注意當前交換順序的運動員只能交換他后面的運動員的順序，
43             這樣交換的兩個運動員在遞回程序中才不會重復交換，產生錯誤的資料，所以i=index，而不是0 */
44             for(int i=index;i<n;i++){
45                 //交換順序
46                 int t = list[i];
47                 list[i] = list[index];
48                 list[index] = t;
49                 //排下一個運動員
50                 dg(index+1);
51                 //還原順序
52                 t = list[i];
53                 list[i] = list[index];
54                 list[index] = t;
55             }
56         }
57     }
58     private static boolean filter(int[] data) {
59         boolean falg = true;
60         for(int i=0;i<m;i++){
61             //這個預測是錯誤的
62             if(s[i][s[i].length-1].equals("0")){
63                 //當所以運動員都滿足預測則預測錯誤
64                 for(int j=0,k=1;j<n;j++){
65                     if(Integer.parseInt(s[i][k])==list[j]&&++k==s[i].length-1){
66                         falg = false;
67                     }
68                 }
69             }else{//這個預測是正確的                
70                 falg = false;
71                 //當所以運動員都滿足預測則預測正確
72                 for(int j=0,k=1;j<n;j++){
73                     //原理同錯誤預測
74                     if(Integer.parseInt(s[i][k])==list[j]&&++k==s[i].length-1){
75                         falg = true;
76                     }
77                 }
78             }
79         }
80         return falg;
81     }
82 }

運行結果

 注意：

1                 for(int j=0,k=1;j<n;j++){
2                     if(Integer.parseInt(s[i][k])==list[j]&&++k==s[i].length-1){
3                         falg = false;
4                     }
5                 }

這段代碼意思是當所以運動員都滿足預測則預測錯誤

別看這個if陳述句只有一行，邏輯還是特別復雜的
首先要明白&&，當左邊不滿足，右邊就不會執行了
當第一次執行Integer.parseInt(s[i][k])==list[j]滿足條件時，會把第i個圍觀黨預測的第一個人從已經排好的陣列list中找出來
這時k為圍觀黨預測的人在s[i][]中的下標,j為list陣列中的下標，他們指的同一個運動員
當第一個條件滿足會執行++k==s[i].length-1，這句話的意思是如果++k超過了存預測部分的長度，換句話說就是當前k下標是最后一個預測
因為s陣列最后還存了一個狀態，這句話的對錯與否，所以s[i].length-1
所以這個回圈加上if判斷的運行程序就是：
在排名中找到第一個預測，判斷這個預測是不是最后一個預測（當預測只有一個人會判斷為預測錯誤，當然這樣的預測是無意義的），
如果是則判斷為預測錯誤，否則判斷下一個預測(k++)，然后找到運動員排名位置(Integer.parseInt(s[i][k])==list[j])，
注意回圈是j++,也就是找到的運動員必須在上一個運動員后面的，這樣才能滿足預測
如果找不到k則在回圈結束都不可能滿足++k==s[i].length-1，則說明預測正確，否則判斷當前是否為最后一個，若是，則說明所有預測都成立，
則回傳預測錯誤，若不是最后一個，則判斷下一個預測

標籤：其他

上一篇：二分查找

下一篇：演算法題--最長回文子串