为一个整数作为输入,数组的大小为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.
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): 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;
}