無法找到測試用例，我的程序找到可被3整除的最大整數出錯

Question

最近，當我嘗試解決一個問題時，我給出了0到9之間的一些數字，並且必須找到可分割的最大整數通過3.

我已經讀過我的代碼，但我無法找到測試用例失敗的地方。如果堆棧溢出的優秀人員能夠幫助我找到測試用例，我將不勝感激。測試用例是一個隱藏的測試用例，所以我不能只打印測試用例的元素。

import java.util.Arrays; 
import java.util.LinkedList; 


public class Main { 
public int answer(int[] l) { 

    int b[] = new int[l.length]; 
    int divb = 0; 
    int div = 0; 
    int t = 0; 
    int mi = 1; 
    int counter = 0; 
    LinkedList<Integer> ab = new LinkedList<Integer>(); 
    Arrays.sort(l); 
    for (int i = 0; i < l.length; i++) { 
     ab.add(l[i]); //adding the elements to linkedlist after sorting them 
     div += l[i]; //adding all the elements in the array 
     b[i] = l[i] % 3;//we use b[i] to find whether we have 0,1,2 as one of the remainders 
     divb += b[i]; 
     if (b[i] == 2) { 
      mi = 0; 
     } 
     if (b[i] == 1) { 
      counter = 1; 
     } 
    } 
    if (div % 3 == 1) { 
     if (counter == 1) {/*if counter is 1 that means we have atleast one element which has remainder 1 where we can remove that element to get a an integer in descending order of its digits which are divisible by 3*/ 
      for (int i = 0; i < l.length; i++) { 
       if (b[i] == 1) { 
        div -= l[i]; 
        ab.remove(i); 
        break; 
       } 
      } 
     } else {//if there is no such digit with remainder 1 but we have a number like 3,6,9 which is divible by 3 then we should return such a number. 
      int tk = 0; 
      for (int i = 0; i < l.length; i++) { 
       if (b[i] != 0) { 
        div-=l[i]; 
        ab.remove(tk); 
        tk--; 
       } 
       tk++; 
      } 
     } 

     if (div % 3 != 0) { 
      return 0; 
     } 
    } 
     int k[] = new int[2]; 
     if (div % 3 == 2) {//if the remainder is 2 then we have to remove oen digit with remainder as 2 or two digits with remainder as one. I tried to use various counters so that they don't effect each other 

      for (int i = 0; i < l.length; i++) { 
       if (b[i] == 2 && mi == 0) { 
        div -= l[i]; 
        ab.remove(i); 
        break; 
       } 
       if (b[i] == 1 && t != 2 && mi == 1) { 
        div -= l[i]; 
        k[t] = i; 
        t++; 
       } 
       if (t == 2) { 
        ab.remove(k[0]); 
        ab.remove(k[1] - 1); 
        break; 
       } 
      } 
      if (div % 3 != 0) { 
       return 0; 
      } 
     } 
     if (ab.size() >= 1) {//Here we will check whether size of result is more than zero just in case there was only element in the array which might have no more elements now. 
      int result = 0; 
      Integer[] res = ab.toArray(new Integer[ab.size()]); 
      for (int i = res.length - 1; i >= 0; i--) { 
       result = 10 * result + res[i]; 
      } 
      return result; 
     } 
     else { 
      return 0; 
     } 
    } 
public static void main(String[] arg) 
{ 
    int a[]={7,7,7,6}; 
    Main d=new Main(); 
    int f=d.answer(a); 
    System.out.print(f); 
} 

Answer 1

當試圖編寫這樣一個棘手的算法時，編寫第二個更簡單的實現來測試它是個好主意。

在這種情況下，明顯的候選人是一種蠻力方法，您可以在其中生成輸入數字的所有可能子集的所有可能排列，測試結果數字是否可以被3整除並跟蹤所遇到的最大數字。

下面是一些代碼實現了這個想法：

public class BruteDiv3 
{ 
    public static int maxDiv3(int[] arr) 
    { 
     return generateSubsets(arr, new BitSet(), 0, 0); 
    } 

    static int generateSubsets(int[] digits, BitSet selected, int pos, int maxDiv3) 
    { 
     if (pos == digits.length) 
     { 
      List<Integer> subset = toSubset(digits, selected); 
      if (!subset.isEmpty()) 
      { 
       maxDiv3 = permuteSubset(subset, 0, maxDiv3); 
      } 
      return maxDiv3; 
     } 

     boolean duplicate = false; 
     for (int i = pos - 1; i >= 0; i--) 
     { 
      if (digits[i] == digits[pos] && !selected.get(i)) 
      { 
       duplicate = true; 
       break; 
      } 
     } 

     if (!duplicate) 
     { 
      selected.set(pos); 
      maxDiv3 = generateSubsets(digits, selected, pos + 1, maxDiv3); 
      selected.clear(pos); 
     } 

     maxDiv3 = generateSubsets(digits, selected, pos + 1, maxDiv3); 

     return maxDiv3; 
    } 

    static int permuteSubset(List<Integer> subset, int pos, int maxDiv3) 
    { 
     if (pos == subset.size()) 
     { 
      int num = toInteger(subset); 
      if (num % 3 == 0 && num > maxDiv3) 
      { 
       maxDiv3 = num; 
      } 
      return maxDiv3; 
     } 

     maxDiv3 = permuteSubset(subset, pos + 1, maxDiv3); 

     for (int i = pos + 1; i < subset.size(); i++) 
     { 
      if (!subset.get(pos).equals(subset.get(i))) 
      { 
       List<Integer> permSubset = new ArrayList<>(subset); 
       Collections.swap(permSubset, pos, i); 
       maxDiv3 = permuteSubset(permSubset, pos + 1, maxDiv3); 
      } 
     } 

     return maxDiv3; 
    } 

    static List<Integer> toSubset(int[] arr, BitSet on) 
    { 
     List<Integer> ss = new ArrayList<>(); 
     for (int i = 0; i < arr.length; i++) 
     { 
      if (on.get(i)) 
       ss.add(arr[i]); 
     } 
     return ss; 
    } 

    static int toInteger(List<Integer> digits) 
    { 
     int num = 0; 
     for (int pow10 = 1, i = digits.size() - 1; i >= 0; i--, pow10 *= 10) 
     { 
      num += digits.get(i) * pow10; 
     } 
     return num; 
    } 
} 

掌握了這些，我們現在就可以編寫一個程序來的數字從數字的蠻力方法從你的日常隨機輸入進行比較。

static void compare(int n) 
{ 
    int[] arr = new int[n]; 
    Random r = new Random(); 
    while (true) 
    { 
     for (int i = 0; i < n; i++) 
      arr[i] = r.nextInt(10); 

     int maxBrute = BruteDiv3.maxDiv3(arr); 
     int maxSO = new Main().answer(arr); 

     if (maxBrute % 3 != 0) 
      System.out.println("Bad Brute: " + maxBrute); 
     if (maxSO % 3 != 0) 
      System.out.println("Bad SO: " + maxSO); 

     if (maxBrute != maxSO) 
     { 
      System.out.println(Arrays.toString(arr) + " " + maxBrute + " " + maxSO); 
     } 
    } 
} 

對於最多n = 4的輸入，似乎沒有問題。

然而，由n = 5，我們得到：

[2, 5, 5, 5, 8] 855 0 
[2, 5, 8, 8, 8] 888 0 
[2, 2, 5, 5, 5] 555 0 
... 

如果你的日常似乎返回0。

對於n = 8，我們

[0, 2, 3, 3, 5, 5, 8, 8] 885330 330 
[2, 2, 3, 5, 5, 5, 9, 9] 995553 993 
[2, 2, 2, 3, 5, 5, 6, 9] 965532 963 
... 

希望你可以使用上面的例程可以幫助跟蹤代碼中的問題。