LEETCODE 1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits Analysis of problem-solving ideas
The main idea of the topic:
The smallest integer obtained by exchanging adjacent digits at most K times
You are given a string num and an integer k . Among them, num represents a large integer, and each character in the string corresponds to each digit on the integer in turn .
You can swap the digits of adjacent digits of this integer up to number of times . k
Please return the smallest integer you can get, and return it as a string.
Example 1:
Input: num = "4321", k = 4
Output: "1342"
Explanation: 4321 The steps to obtain the smallest integer by exchanging adjacent digits 4 times are shown in the figure above.
Example 2:
Input: num = "100", k = 1
Output: "010"
Explanation: The output can contain leading 0s, but the input is guaranteed not to have leading 0s.
Example 3:
Input: num = "36789", k = 1000
Output: "36789"
Explanation: No swap required.
Example 4:
Input: num = "22", k = 22
Output: "22"
Example 5:
Input: num = "9438957234785635408", k = 23
Output: "0345989723478563548"
hint:
- 1 <= num.length <= 30000
- num Contains only numbers and no leading 0's .
- 1 <= k <= 10^9
Analysis of problem-solving ideas:
This problem requires the use of a greedy algorithm. Just imagine that if we want to make the integer smaller, we should try to move the smaller number to the high position, and the cost of moving from the current position to the high position should be the distance difference between the two positions, so this difference cannot be greater than k, otherwise You will not be able to complete the movement within the specified number of steps. Based on this principle, when solving the problem, we loop backwards from the highest bit to find the smallest number and its subscript minIndex. Note that the distance between the number and the highest bit must be less than or equal to k. Then we move the number to the highest position, and move the numbers from the second highest position to minIndex-1 backward by one bit (equivalent to bubble sort). At this point we have determined the highest digit, and the k value has consumed minIndex units. Next, we follow the above logic to determine the next highest number, and so on, until the so-called position is determined or the current k value is 0 and the operation ends. The above operations can be done using loops, and different can be done using recursion.
Implementation code:
public String minInteger(String num, int k) {
char [] arr= num.toCharArray () ; // Convert the string to an array for easy calculation
return String.valueOf ( help ( arr ,k, 0 )) ; // recursive solution
}
// arr: array
// k: current remaining steps
// index: current high position
char[] help(char[] arr,int k, int index){
// If the subscript is out of bounds or k is 0, return
if(index==arr.length||k==0) return arr;
// Find the smallest number after the current high and its subscript
char min=arr[index];
int minIndex=index;
for(int i=index;i<arr.length&&i-index<=k;i++){
if(arr[i]<min){
min=arr[i];
minIndex=i;
}
}
// Move the numbers between the current high bit and minIndex-1 backward by one bit
for(int i=minIndex;i>index;i--){
arr[i]=arr[i-1];
}
// Set the highest bit to the minimum value (equivalent to bubble sort)
arr[index]=min;
// Recursively find the next highest bit
return help(arr,k-(minIndex-index),index+1);
}
The execution time of this solution is 929ms.
Runtime: 929 ms, faster than 33.33% of Java online submissions for Minimum Possible Integer After at Most K Adjacent Swaps On Digits.
Memory Usage: 43.8 MB, less than 100.00% of Java online submissions for Minimum Possible Integer After at Most K Adjacent Swaps On Digits.
The articles on this website are all original content and can be reproduced at will, but please indicate the link of this article.
If you have any questions, please leave a message at the bottom of the article. In order to prevent malicious comments, this blog has now enabled the message review function. But the blogger will see your message at the first time in the background, and will reply to your message at the first time! Welcome to exchange!
