题目

In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. For example, 4 can be partitioned in five distinct ways: 4, 3 + 1, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1 We can write: enum(4) -> [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]] and enum(5) -> [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]]. The number of parts in a partition grows very fast. For n = 50 number of parts is 204226, for 80 it is 15,796,476 It would be too long to tests answers with arrays of such size. So our task is the following: 1 - n being given (n integer, 1 <= n <= 50) calculate enum(n) ie the partition of n. We will obtain something like that: enum(n) -> [[n],[n-1,1],[n-2,2],…,[1,1,…,1]] (order of array and sub-arrays doesn’t matter). This part is not tested. 2 - For each sub-array of enum(n) calculate its product. If n = 5 we’ll obtain after removing duplicates and sorting: prod(5) -> [1,2,3,4,5,6] prod(8) -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 15, 16, 18] If n = 40 prod(n) has a length of 2699 hence the tests will not verify such arrays. Instead our task number 3 is: 3 - return the range, the average and the median of prod(n) in the following form (example for n = 5): “Range: 5 Average: 3.50 Median: 3.50” Range is an integer, Average and Median are float numbers rounded to two decimal places (“.2f” in some languages).

Notes: Range : difference between the highest and lowest values.

Mean or Average : To calculate mean, add together all of the numbers in a set and then divide the sum by the total count of numbers.

Median : The median is the number separating the higher half of a data sample from the lower half. (https://en.wikipedia.org/wiki/Median)

Hints: Try to optimize your program to avoid timing out.

Memoization can be helpful but it is not mandatory for being successful.

在数论和组合学中，正整数n的分划，也称为整数分划，是把n写成正整数和的一种方法。只有和的顺序不同的两个和被认为是同一个分区。

例如，4可以用五种不同的方式进行分区： 4, 3 + 1, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1

我们可以写：

枚举（4）->[[4]，[3,1]，[2,2]，[2,1,1]，[1,1,1]]和

枚举（5）->[[5]，[4,1]，[3,2]，[3,1,1]，[2,2,1]，[2,1,1,1]，[1,1,1,1]]。 分区中的部分数量增长非常快。对于n=50，零件数为204226，对于80，零件数为15796476，使用这样大小的数组测试答案太长。因此，我们的任务如下：

1-给定n（n整数，1<=n<=50）计算enum（n）即n的分区。我们将得到如下结果：

枚举（n）->[[n]，[n-1,1]，[n-2,2]，…，[1,1，…，1]]（数组和子数组的顺序无关紧要）。此部件未经测试。

2-对于enum（n）的每个子数组，计算其乘积。如果n=5，我们将在删除重复项并排序后获得：

产品（5）->[1,2,3,4,5,6]

产品（8）->[1、2、3、4、5、6、7、8、9、10、12、15、16、18]

如果n=40 prod（n）的长度为2699，则测试将不会验证此类阵列。相反，我们的任务3是：

3-返回prod（n）的极差、平均值和中位数，格式如下（n=5的示例）：

“极差：5平均值：3.50中位数：3.50”

Range是一个整数，Average和Median是四舍五入到小数点后两位的浮点数（在某些语言中是.2f）。

注：极差：最高值与最低值之差。

平均数或平均数：要计算平均数，将集合中的所有数字相加，然后除以总数。

中位数：中位数是将数据样本的上半部分与下半部分分开的数字。(https://en.wikipedia.org/wiki/Median)

提示：尽量优化你的程序以避免超时。

回忆录是有帮助的，但它不是成功的必要条件。

原题链接

分析

先将整数划分，再进行内积排序得到集合，之后算出极差、中位数、平均数即可。这里需要注意的是如何得到集合，使用递归是比较理想的方法。

我的解法

import java.util.*;
public class IntPart {
  public static String part(long n) {
        TreeSet<Long> set = computeProd(n);
        long Range = set.last()-set.first();
        double Average = (double)set.stream().reduce((x, y) -> x + y).get()/set.size();
        ArrayList<Long> list = new ArrayList<>();
        list.addAll(set);
        double Median;
        int index = list.size()/2;
        if (list.size()%2 == 0){
            Median = (list.get(index-1)+list.get(index))/2.0;
        }else {
            Median = list.get(index);
        }
        return String.format("Range: %s Average: %.2f Median: %.2f", Range, Average, Median);
  }
    static Map<Long, TreeSet<Long>> memo = new HashMap<>();
    public static TreeSet<Long> computeProd(long n) {
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        TreeSet<Long> set = new TreeSet<>();
        set.add(n);
        for (int i = 1; i <= n / 2; i++) {
            Set<Long> computed = computeProd(n - i);
            for (long c : computed) {
                set.add(c * i);
            }
        }
        memo.put(n, set);
        return set;
    }
}

参考解法

import java.util.HashMap;
import java.util.TreeSet;
public class IntPart {
  static HashMap<Long, TreeSet<Long>> prodsO = new HashMap<>();
  public static TreeSet<Long> partp(Long n) {
    if (prodsO.containsKey(n))
      return prodsO.get(n);
    long d = 0;
    TreeSet<Long> prods = new TreeSet<>();
    for (long i = 1; i <= n; i++) {
      if (i <= n)
        prods.add(i);
      final long m = i;
      if ((d = n - i) > 1) {
        partp(d).forEach(P -> {prods.add(P*m);});
      }
    }
    prodsO.put(n, prods);
    return prods;
  }
  public static String part(long n) {
    TreeSet<Long> prods = partp(n);
    long range = prods.last() - prods.first();
        double avg = prods.stream().mapToLong(i->i).sum() / (double) prods.size();
        Long[] x = prods.toArray(new Long[]{});
        double med = 0f;
        if (x.length % 2 == 0) {
          med = ((double) x[x.length/2-1] + x[x.length/2]) /2 ;
        } else {
          med = (double) x[x.length/2];
        }
        return "Range: "+ range + " Average: " + String.format("%.2f", avg) + " Median: " + String.format("%.2f", med);
  }
}

提升

1. 这个问题直接分解整数其实也是可以的，通过动态规划或递归都成，不过我们关注的其实是集合中内积完的东西，所以通过treeset将问题分治递归处理比较妥当，剩下的就比较简单了

2. ArrayList list = new ArrayList<>();

   list.addAll(set);
   可以写成 ArrayList list = new ArrayList<>(set);