主页 / 问题 / 1611084
Accepted
user709676
Asked:2025-05-01 04:17:48 +0000 UTC2025-05-01 04:17:48 +0000 UTC

优化简单代码（String.valueOf）

  • 772

任务如下：

输入输出数据：

数据示例：

我解决了这个问题，但是在我的算法中我使用 String.valueOf 方法将数组的每个元素转换为字符串，这占用了大量的内存。我该如何优化我的代码？

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int k = scanner.nextInt();
    int[] list = new int[n + 1];
    for (int i = 0; i < n; i++) {
        list[i] = scanner.nextInt();
    }
    System.out.println(findMaxDifference(list,k));
}

public static long findMaxDifference(int[] list, int k) {
    long result = 0;
    for (int i = 0; i < k; i++) {
        list = refactorNum(list);
        result += list[list.length - 1]; // увеличиваю результат по последнему индексу массива
        list[list.length - 1] = 0; // обновляю его
    }
    return result;
}

private static int[] refactorNum(int[] list) {
    int prevIndex = -1;
    int prevValue = -1;
    for (int i = 0; i < list.length-1; i++) {
        String stringNum = String.valueOf(list[i]); // (проблема) создаю n*k объектов String
        for (int j = 0; j < stringNum.length(); j++) {
            if (stringNum.charAt(j) != '9') {
                stringNum = stringNum.replaceFirst(String.valueOf(stringNum.charAt(j)),"9");
                int parsedInt = Integer.parseInt(stringNum);
                if (parsedInt - list[i] > list[list.length-1]) {
                    if (prevIndex != -1) {
                        list[prevIndex] = prevValue;
                    }
                    prevIndex = i;
                    prevValue = list[i];
                    list[list.length-1] = parsedInt - list[i]; // ожидаемый результат
                    list[i] = parsedInt;
                }
                break;
            }
        }
    }
    return list;
}

}

java

1 个回答

  1. Best Answer

    是的，您确实进行了nk次操作才得到结果。太多了，不是因为内存，而是因为速度。您可以使用nlogn进行管理。

    假设输入数字为12345。利用他的数字可以获得哪些“增长”？我们从九中减去每个数字，并根据数字中的位置号为其添加零：

    12345→80000、7000、600、50、4。

    我们将把所有输入数字转换成这样的“增加”集合。我们将“增加”收集到一个列表中，按降序排序并计算该列表前k 个元素的总和：

    import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Temp {
    public static void main(String... args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        List<Integer> diffs = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            String s = sc.next();
            int p10 = 1;
            for (int j = s.length() - 1; j >= 0; --j) {
                diffs.add((9 - (s.charAt(j) - '0')) * p10);
                p10 *= 10;
            }
        }
        diffs.sort(Collections.reverseOrder());
        if (k < diffs.size()) {
            diffs = diffs.subList(0, k);
        }
        long sum = 0;
        for (int d : diffs) {
            sum += d;
        }
        System.out.println(sum);
    }
}

    最有可能的是，该任务将以这种形式被接受。但还可以做得更好。请注意，“增加”仅存在形式为d·10 j的增加，其中0 ≤ d ≤ 9。也就是说，不同的选择不超过九十种。这意味着，您无需进行排序，而是可以在n + k时间内安排一个即兴的计数排序，这比nlogn更好。并且仅需要常量内存。

    import java.util.Scanner;

public class Temp {
    public static void main(String... args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        int[] p10 = new int[9];
        for (int j = 0, p = 1; j < 9; ++j, p *= 10) {
            p10[j] = p;
        }

        int[][] diffs = new int[9][10];
        for (int i = 0; i < n; ++i) {
            String s = sc.next();
            for (int j = s.length() - 1; j >= 0; --j) {
                ++diffs[s.length() - j - 1][9 - (s.charAt(j) - '0')];
            }
        }

        long sum = 0;
        for (int j = p10.length - 1; j >= 0; --j) {
            for (int d = 9; d >= 0; --d) {
                int r = Math.min(diffs[j][d], k);
                sum += d * r * p10[j];
                k -= r;
            }
        }
        System.out.println(sum);
    }
}
    • 1

相关问题