java - Java 方法的优化

问题描述

Arthur 和 Alena 正在玩一个包含一些整数的数组的游戏。Arthur 可以取任何整数并将其从数组中删除，他必须将该数字的一半（向上取整）添加回数组。Alena 为 Arthur 分配了固定数量的移动，并挑战他最小化最终数组的总和。作为移动如何工作的示例，从数组 nums = [10, 20, 7] 开始并执行 k = 4 移动。

选择任何元素进行移动，例如 7。执行除法：7/2 = 3.5，并向上取整为 4。将 7 替换为新值 4。此时，数组为 nums = [10 , 20, 4]。所有 4 个动作的执行如下：

Pick    Pick/2    Rounded        Result
---------------------------------------------
Initial array                    [10, 20, 7]
----------------------------------------------
7         3.5        4           [ 10, 20, 4]
10        5          5           [5, 20, 4]
20        10         10          [5, 10, 4]
10        5          5           [5, 5, 4]

最终数组的总和是 5 + 5 + 4 = 14，这个总和是最小的。

功能说明

在下面的编辑器中完成函数 minSum。该函数必须返回一个整数，表示 k 步后数组的最小总和。

minSum 有以下参数：

nums[nums[0],...nums[n-1]]:  an array of integers

k:  an integer

约束

1 ≤ n ≤ 105
1 ≤ numi ≤ 104 (where 0 ≤ i < n)
1 ≤ k ≤ 107

自定义测试的输入格式
示例案例 0自定义测试
的示例输入

1
2
1

样本输出

解释

该数组只有一个整数，即 2，对数组采取的步数为 1。在第一步之后，数字 2 减少到数字 1，因此，经过一个步骤后数组的最小和为 1。

这是昨天对一家公司的配对编码采访：我的想法：

将此列表设为数组列表
也转换成数组
排序这个数组
取这个数组的最后一个元素并除以 2 然后分配回来
迭代移动并对数组求和

我尝试并运行了测试用例，系统显示一些由于超时而未通过。

结果：

TestCase #0: Success
Output:
1

Expected Output:
1

TestCase #1: Success
Output:
4

Expected Output:
4

TestCase #2: Success
TestCase #3: Success
TestCase #4: Success
TestCase #5: Success
TestCase #6: Terminated due to timeout
TestCase #7: Terminated due to timeout
TestCase #8: Terminated due to timeout
TestCase #9: Terminated due to timeout
TestCase #10: Terminated due to timeout
TestCase #11: Terminated due to timeout

/*
 * Complete the 'minSum' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER_ARRAY num
 *  2. INTEGER k
 */

public static int minSum(List<Integer> num, int k)
{
    // Write your code here
    // first of all: will have an arraylist for num
    // do the sanity check
    if(num==null || k<1)
    {
        return -1;
    }

    ArrayList<Integer> arrayList = new ArrayList<>(num);
    int[] convertedArray = new int[arrayList.size()];
    // convertedArray = arrayList.toArray();
    for(int i = 0; i<convertedArray.length; i++)
    {
        convertedArray[i] = arrayList.get(i);
    }

    // after the array implementation: sort the array
    Arrays.sort(convertedArray);  // this will get the sorted array
    int length = convertedArray.length;

    // for K times of movements
    for(int j=1 ; j<=k; j++)
    {
        int halfOfOrigianalNumber = (int)Math.round((double)convertedArray[length-1]/2);
        convertedArray[length-1] = halfOfOrigianalNumber;
        Arrays.sort(convertedArray);
    }

    //to sum up :
    int sumUp = 0;  //to sum up
    for (int i=0; i<convertedArray.length;i++)
    {
        sumUp+=convertedArray[i];
    }
    return sumUp;
}

我的代码可以工作，但不是所有的测试用例。我需要对此方法进行任何优化或修复吗？

谢谢你。

标签： javaarraysoptimization

static int playGame(int turns, List<Integer> numbers) { PriorityQueue<Integer> pq = new PriorityQueue<>(numbers.size(), (left, right) -> right - left ); pq.addAll(numbers); for (int i = 0; i < turns; i++) { int next = pq.remove(); pq.add((next + 1) / 2); } return pq.stream().mapToInt(Integer::intValue).sum(); }

java - Java 方法的优化

问题描述

解决方案

推荐阅读