java – 所有可能的数组子集的乘积之和

我编写了一个代码来查找所有可能的数组子集的乘积.我得到了预期的输出,但是我无法让它足够快以清除时间相关的测试用例.

任何人都可以帮助我优化代码的速度吗？

第一个输入(testCases)是测试用例的数量.
根据测试用例的数量,我们将具有数组(大小)和数组元素(集合)的大小.

例如,有效输入将是：

1
3
2 3 5

哪里：

1 is the number of testcases. 3 is the size of the test set and 2 3 5 are the elements of the input set.

预期的输出是：

71

上述输出的计算如下：

{2},{3},{5},{2,3},{3,5},3,5}

=>   2    3    5      6      15      10        30

=>   2 + 3 + 5 + 6 + 15 + 10 + 30

=>   71

import java.util.Scanner;

public class Test {
    static int printSubsets(int set[]) {
        int n = set.length;
        int b = 0;

        for (int i = 0; i < (1 << n); i++) {
            int a = 1;
            for (int j = 0; j < n; j++){

                if ((i & (1 << j)) > 0) {

                    a *= set[j];
                }}

            b += a;
        }
        return b;
    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int testCases = scanner.nextInt();

        for (int i = 0; i < testCases; i++) {
            int size = scanner.nextInt();
            int set[] = new int[size];
            for (int j = 0; j < set.length; j++) {
                set[j] = scanner.nextInt();
            }

            int c = printSubsets(set);
            System.out.println((c - 1));

        }
        scanner.close();
    }
}

解决方法

你需要使用一点数学.假设您有3个值,就像您的示例一样,但我们称之为A,B和C.

要获得产品总和,您需要计算：

Result3 = A + B + C + A*B + A*C + B*C + A*B*C
        = A + B + A*B + (1 + A + B + A*B) * C

现在,如果我们先计算A B A * B,称之为Result2,那么你会得到：

Result2 = A + B + A*B
Result3 = Result2 + (1 + Result2) * C

我们重复一遍,所以

Result2 = A + (1 + A) * B
Result1 = A
Result2 = Result1 + (1 + Result1) * B

你能看到这种模式吗？让我们使用4个值：

Result4 = A + B + C + D + A*B + A*C + A*D + B*C + B*D + C*D
        + A*B*C + A*B*D + A*C*D + B*C*D + A*B*C*D
        =      A + B + C + A*B + A*C + B*C + A*B*C
        + (1 + A + B + C + A*B + A*C + B*C + A*B*C) * D
        = Result3 + (1 + Result3) * D

摘要：

Result1 = A
Result2 = Result1 + (1 + Result1) * B
Result3 = Result2 + (1 + Result2) * C
Result4 = Result3 + (1 + Result3) * D

作为代码,这是：

private static long sumProduct(int... input) {
    long result = 0;
    for (int value : input)
        result += (result + 1) * value;
    return result;
}

只有一次迭代,所以O(n).

测试

System.out.println(sumProduct(2,3));
System.out.println(sumProduct(2,5));
System.out.println(sumProduct(2,5,7));

产量

11
71
575

UPDATE

也可以使用带有Lambda表达式的Java 8 Streams使用IntStream.of(int...)或Arrays.stream(int[])(它们执行相同操作)来完成代码.

// Using IntStream with result as int
private static int sumProduct(int... input) {
    return IntStream.of(input).reduce((a,b) -> a + (1 + a) * b).getAsInt();
}

// Using Arrays with result as long
private static long sumProduct(int... input) {
    return Arrays.stream(input)
                 .asLongStream()
                 .reduce((a,b) -> a + (1 + a) * b)
                 .getAsLong();
}

java – 所有可能的数组子集的乘积之和

解决方法

猜你在找的Java相关文章