时间戳

首页 > 解决方案 > k 次交换中的最大数

java - k 次交换中的最大数

问题描述

给定一个数字 K 和表示正整数的数字字符串 str，通过对 str 的数字执行最多 K 次交换操作来构建可能的最大数字。

示例 1： 输入：K = 4 str = "1234567" 输出：7654321 解释：三个交换可以使输入 1234567 变为 7654321，将 1 与 7 交换，2 与 6 交换，最后将 3 与 5 交换

我正在尝试使用两个循环来解决它。对于每个索引 i，我找到第 (i+1) 个索引到第 (N-1) 个索引之间的最大整数，其中 N 是字符串的大小。如果最大数大于 arr[i]，则交换它。下面是我写的代码。

public static String findMaximumNum(String str, int k) {
        int N = str.length();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.valueOf(str.charAt(i) + "");
        }
        int swaps = 0;
        for (int i = 0; i < N - 1; i++) {
            if(swaps == k)
                break;
            int maxIndex = findMaxInRange(arr, i + 1, N - 1);
            if (arr[i] < arr[maxIndex]) {
                swap(arr, i, maxIndex);
                swaps++;
            }
        }
        String out = "";
        for (int i = 0; i < N; i++) {
            out = out + arr[i] + "";
        }
        return out;
    }

    private static int findMaxInRange(int[] arr, int i, int j) {
        int max = Integer.MIN_VALUE;
        int maxIndex = i;
        for (int k = i; k <= j; k++) {
            if (arr[k] >= max) {
                max = arr[k];
                maxIndex = k;
            }
        }
        return maxIndex;
    }

    private static void swap(int[] arr, int i, int j) {
        System.out.println("swapping "+arr[i]+" and "+arr[j]+" from "+Arrays.toString(arr));
        int ch = arr[i];
        arr[i] = arr[j];
        arr[j] = ch;
    }

    public static void main(String[] args) {
        System.out.println(findMaximumNum("61892795431", 4));

    }

很少有测试用例失败。失败的测试用例之一是输入：4 61892795431

其正确输出为：99876215431

MyCode 的输出是：99876125431

我无法弄清楚输出是“99876215431”以及我的方法有什么问题。请帮我理解。提前非常感谢:)

标签： javaalgorithmdata-structuresdynamic-programmingbacktracking

解决方案

如何解决这个问题的基本步骤： 0. 将字符串转换为整数数组

  1. 循环K次
  2. 在这个循环中，从 i+1 (LOOP VAR) 到集合的末尾并搜索更高的值
  3. 当我们找到比collection[i]更高的值时，我们会记住它的值和它在witch上的索引。需要注意的重要一点是，我们要交换最大的数字，但 i 也必须是最后一个可能的数字。
  4. 在迭代结束时，我们交换元素（具有最佳索引的 i）
  5. 我们完成了，剩下的就是将我们的 int 列表转换回字符串。

代码：（它的python，因为java很痛苦）

def sort(swaps, string):
    l = list(map(int, list(string)))
    print(l)
    for i in range(swaps):
        best = l[i] + 1
        bestIndex = i
        for j in range(i+1, len(l)):
            if best <= l[j]:
                best = l[j]
                bestIndex = j
        print(i, bestIndex)
        l[i], l[bestIndex] = l[bestIndex], l[i]
    return "".join(map(str, l))

print(sort(4, "61892795431"))

推荐阅读