连续成对可除以3

问题描述 投票:0回答:1

为一个整数作为输入,数组的大小为n.

执行循环中的以下步骤,直到列表中的第一个N-1项目为3。

对于数组i的索引,从i = 0开始,然后继续直到

i=n-2

:
乘以
array[i]
array[i+1]
,如果产品可以除以3,则用产品替换
array[i]
,否则请勿更改。
列表中的最后一项不能有一对,因此无需处理。 return循环在列表中制作N-1项目的次数是3.

示例:

Input: [34, 56, 20, 90, 100] Output: 3

解释:

Iteration 1: {34 56 1800 9000 100} Iteration 2: {34 100800 16200000 900000 100} Iteration 3: {3427200 100800 16200000 90000000 100} 因此,迭代次数为3.

示例#2

Input: [1, 333, 222, 22] Output: 1 解释: 第1轮:{333 333 222 22} 前3个数字是3的倍数。因此,迭代次数为1.

我的代码是我的代码:
public class Main {

   public static int solve(int[] a) {
        int n = a.length;
        int rounds = 0;

        while (true) {
            boolean allMultiplesOfThree = true;

            // Check if the first n-1 elements are already multiples of 3
            for (int i = 0; i < n - 1; i++) {
                if (a[i] % 3 != 0) {
                    allMultiplesOfThree = false;
                    break;
                }
            }

            // If all first n-1 elements are multiples of 3, return the rounds count
            if (allMultiplesOfThree) {
                return rounds;
            }

            // Increment rounds and update the array in place
            rounds++;
            for (int i = 0; i < n - 1; i++) {
                int product = a[i] * a[i + 1];
                if (product % 3 == 0) {
                    a[i] = product;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] input1 = {34, 56, 20, 90, 100};
        System.out.println(solve(input1)); // Expected: 3

        int[] input2 = {1, 333, 222, 22};
        System.out.println(solve(input2)); // Expected: 1
    }
}

在面试中提出了这个问题,有8个测试用例,我的代码仅用于2个测试用例,所有的测试案例都失败了(失败的测试用例被隐藏了,所以我看不到它们)

解决此问题的正确方法是什么。
	
您可以在一次迭代中做到这一点。

我们可以观察到,如果我们执行乘法并存储产品,我们在数组中又有一个元素3的倍数。如果下一个元素是3个倍数,则只能制作3个元素。这意味着如果我们有几个连续的3个非数字3,我们需要尽可能多的迭代来“修复”并使它们全部倍增3。因此,返回的数字是此类非媒介的最大连续序列的大小3.

有一个例外:如果输入阵列的最后两个元素不是3的倍数,则无法使一个但持久的元素成为3个倍数,因此没有解决方案。应在挑战中提及在这种情况下应退还的内容。

可以像这样对该算法进行编码(如果没有解决方案,我返回-1):
java algorithm time-complexity
1个回答
0
投票
public static int solve(int[] a) { if (a.length < 2) return 0; // Nothing to do if (a[a.length - 2] % 3 != 0 && a[a.length - 1] % 3 != 0) return -1; // No solution int nonMultiplesOf3 = 0; int result = 0; for (var value : a) { if (value % 3 != 0) { nonMultiplesOf3++; result = Math.max(result, nonMultiplesOf3); } else { nonMultiplesOf3 = 0; } } return result; }

© www.soinside.com 2019 - 2024. All rights reserved.