Java的递归问题 [英] Java Recursion Problem

问题描述

我在Java中的递归面试问题的问题，需要你对这个帮助。

I had a recursion interview question problem in Java,Need your help on this.

写 **的Java功能** ，使得::鉴于int数组，是否有可能划分整数分成两组，这样的总和两组是相同的，与这些约束：所有多个的5必须是在一组中的值，所有属于3的整数倍的值（而不是5的倍数）必须在其他。 （无环必要的。）

Write a **Java function** such that :: Given an array of ints, is it possible to divide the ints into two groups, so that the sum of the two groups is the same, with these constraints: all the values that are multiple of 5 must be in one group, and all the values that are a multiple of 3 (and not a multiple of 5) must be in the other. (No loops needed.)

split53（{1,1}）→真
split53（{1，1，1}）→假
split53（{2，4,2}）→真

split53({1,1}) → true
split53({1, 1, 1}) → false
split53({2, 4, 2}) → true

PS：这是一个面试问题的惠普

PS:This was a Interview Question for hewlett packard

推荐答案

这个问题可以很容易地减少到以下：给定一个整数集数字和一个整数目标，是有可能找到数字与相加等于一个子集目标？
让我知道，如果转换需要澄清。

The question can be easily reduced to following: given a set of integers numbers and an integer target, is it possible to find a subset of numbers with sum equal to target?
Let me know if transition needs clarification.

它可以与 DP 在 O（numbers.size *目标）的时间。这个想法是继

It can be solved with DP in O(numbers.size * target) time. The idea is following

1. 当 numbers.size 是 0 ，唯一可达总和 0 。
2. 假设我们有数字== {1,3} ，在这种情况下，金额 {0，1，3，4} 可用。如果我们添加其他元素数字， 4 ？现在，所有旧的款项仍然可以达到和一些新的太： {0 + 4，+ 4，3 + 4，4 + 4} 。因此，对于数字== {1，3，4} ，可用金额是 {0，1，3，4，5，7，8 } 。
3. 在这种方式下，通过数量增加数量，你可以建立可达款项的清单。

1. When numbers.size is 0, the only reachable sum is 0.
2. Suppose we have numbers == {1, 3}, in this case sums {0, 1, 3, 4} are available. What if we add another element to numbers, 4? Now, all old sums can still be reached and some new ones too: {0 + 4, 1 + 4, 3 + 4, 4 + 4}. Thus, for numbers == {1, 3, 4}, available sums are {0, 1, 3, 4, 5, 7, 8}.
3. In this fashion, adding number by number, you can build the list of reachable sums.

一个工作示例（它不处理负数，但你可以很容易地解决这个问题）

A working example (it doesn't handle negative numbers, but you can easily fix that)

boolean splittable(int[] numbers, int target) {
    boolean[] reached = new boolean[target + 1];
    reached[0] = true;

    for (int number : numbers) {
        for (int sum = target - 1; sum >= 0; --sum) {
            if (reached[sum] && sum + number <= target) {
                reached[sum + number] = true;
            }
        }
    }

    return reached[target];
}

运行它

System.out.println(splittable(new int[]{3, 1, 4}, 7)); // => true
System.out.println(splittable(new int[]{3, 1, 4}, 6)); // => false

修改
我只注意到的要求递归的一部分。那么，DP可以改写为递归与记忆化的，如果是这样的硬性要求。这将preserve运行的复杂性。

edit
I just noticed the "recursion" part of the requirement. Well, DP can be rewritten as recursion with memoization, if that's the hard requirement. This would preserve runtime complexity.

修改2
在组。你有3或5至各组的 的您继续与算法之前分配要素分割。比方说，所有元素的总和取值元素被3整除的总和 S3 和元素整除的总和5，但不是3 S5 。在这种情况下，您分配这些特殊的元素之后，你必须拆分其余的在一组的总和 S / 2 - S3 和另一个 S / 2 - S5

edit 2
On groups. You have to assign elements divisible by 3 or 5 to respective groups before you proceed with the algorithm. Let's say, sum of all elements is s, sum of elements divisible by 3 is s3 and sum of elements divisible by 5 but not 3 is s5. In this case, after you assigned those 'special' elements, you have to split the rest that sum in one group is s/2 - s3 and in another s/2 - s5.

这篇关于Java的递归问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！