无法找到我的程序查找可被 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
...

希望您可以使用上述例程来帮助跟踪代码中的问题。

无法找到我的程序查找可被 3 整除的最大整数出错的测试用例

Unable to find the test case where my program to find largest integer divisible by 3 goes wrong

java

linked-list

testcase