1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits.md

leetcode 1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits

题目

Given a string num representing the digits of a very large integer and an integer k.

You are allowed to swap any two adjacent digits of the integer at most k times.

Return the minimum integer you can obtain also as a string.

Example 1:

Input: num = "4321", k = 4
Output: "1342"
Explanation: The steps to obtain the minimum integer from 4321 with 4 adjacent swaps are shown.

Example 2:

Input: num = "100", k = 1
Output: "010"
Explanation: It's ok for the output to have leading zeros, but the input is guaranteed not to have any leading zeros.

Example 3:

Input: num = "36789", k = 1000
Output: "36789"
Explanation: We can keep the number without any swaps.

Example 4:

Input: num = "22", k = 22
Output: "22"

Example 5:

Input: num = "9438957234785635408", k = 23
Output: "0345989723478563548"

思路

• 递归，index 从最左（最高位）开始，找到从 index 往后（包括 num[index] 在内）的最小值，用 min_index 记录最小值的下标。因为有 k 的限制，所以我们还要计算 min_index 到最高位 (index) 之间的距离，如果超出 k，说明无法在 k 次内完成移动。若不超出，则用类似冒泡排序的方法，把最小值移动到最前面。
• 在下一次递归 helper() 函数中， 把移动后更新的 num，剩余次数： k - 移动距离 = k - (min_index - index)，以及 index++ 传入参数，代表我们对次高位（从左往右第2位）往后的 num 做处理。

代码

class Solution {
    public String minInteger(String num, int k) {
        char[] arr = num.toCharArray(); // 为了方便计算，将字符串转为数组
        return String.valueOf(helper(arr, k, 0)); // 递归求解
    }

    // char helper()定义：
    // arr：数组
    // k：当前剩余步数
    // index：当前高位，从下标0开始

    private char[] helper(char[] arr, int k, int index) {
        // 如果下标越界，或者剩余次数k用光
        if (index == arr.length || k == 0) return arr;
        // 找出当前高位之后最小的数字以及所在下标
        char min = arr[index];
        int min_index = index;
        for (int i = index; i < arr.length && i - index <= k; i++) {
            if (arr[i] < min) {
                min = arr[i];
                min_index = i;
            }
        }
        // 将当前高位index到min_index-1间的的数字分别向后移动一位
        for (int i = min_index; i > index; i--) {
            arr[i] = arr[i - 1];
        }
        // 将最高位设置为最小值（相当于冒泡排序）
        arr[index] = min;
        // 递归求解次高位
        return helper(arr, k - (min_index - index), index + 1);
    }
}