8000 New Problem Solution - "1850. Minimum Adjacent Swaps to Reach the Kth… · royeLin/leetcode_cpp@fb308ad · GitHub
[go: up one dir, main page]
Skip to content

Commit fb308ad

Browse files
haoelhaoel
committed
New Problem Solution - "1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number"
1 parent 83fa31a commit fb308ad

File tree

2 files changed

+115
-0
lines changed

2 files changed

+115
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,7 @@ LeetCode
99

1010
| # | Title | Solution | Difficulty |
1111
|---| ----- | -------- | ---------- |
12+
|1850|[Minimum Adjacent Swaps to Reach the Kth Smallest Number](https://leetcode.com/problems/minimum-adjacent-swaps-to-reach-the-kth-smallest-number/) | [C++](./algorithms/cpp/minimumAdjacentSwapsToReachTheKthSmallestNumber/MinimumAdjacentSwapsToReachTheKthSmallestNumber.cpp)|Medium|
1213
|1849|[Splitting a String Into Descending Consecutive Values](https://leetcode.com/problems/splitting-a-string-into-descending-consecutive-values/) | [C++](./algorithms/cpp/splittingAStringIntoDescendingConsecutiveValues/SplittingAStringIntoDescendingConsecutiveValues.cpp)|Medium|
1314
|1848|[Minimum Distance to the Target Element](https://leetcode.com/problems/minimum-distance-to-the-target-element/) | [C++](./algorithms/cpp/minimumDistanceToTheTargetElement/MinimumDistanceToTheTargetElement.cpp)|Easy|
1415
|1847|[Closest Room](https://leetcode.com/problems/closest-room/) | [C++](./algorithms/cpp/closestRoom/ClosestRoom.cpp)|Hard|

‎algorithms/cpp/minimumAdjacentSwapsToReachTheKthSmallestNumber/MinimumAdjacentSwapsToReachTheKthSmallestNumber.cpp

Lines changed: 114 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,114 @@
1+
// Source : https://leetcode.com/problems/minimum-adjacent-swaps-to-reach-the-kth-smallest-number/
2+
// Author : Hao Chen
3+
// Date : 2021-05-03
4+
5+
/*****************************************************************************************************
6+
*
7+
* You are given a string num, representing a large integer, and an integer k.
8+
*
9+
* We call some integer wonderful if it is a permutation of the digits in num and is greater in value
10+
* than num. There can be many wonderful integers. However, we only care about the smallest-valued
11+
* ones.
12+
*
13+
* For example, when num = "5489355142":
14+
*
15+
* The 1^st smallest wonderful integer is "5489355214".
16+
* The 2^nd smallest wonderful integer is "5489355241".
17+
* The 3^rd smallest wonderful integer is "5489355412".
18+
* The 4^th smallest wonderful integer is "5489355421".
19+
*
20+
* Return the minimum number of adjacent digit swaps that needs to be applied to num to reach the k^th
21+
* smallest wonderful integer.
22+
*
23+
* The tests are generated in such a way that k^th smallest wonderful integer exists.
24+
*
25+
* Example 1:
26+
*
27+
* Input: num = "5489355142", k = 4
28+
* Output: 2
29+
* Explanation: The 4^th smallest wonderful number is "5489355421". To get this number:
30+
* - Swap index 7 with index 8: "5489355142" -> "5489355412"
31+
* - Swap index 8 with index 9: "5489355412" -> "5489355421"
32+
*
33+
* Example 2:
34+
*
35+
* Input: num = "11112", k = 4
36+
* Output: 4
37+
* Explanation: The 4^th smallest wonderful number is "21111". To get this number:
38+
* - Swap index 3 with index 4: "11112" -> "11121"
39+
* - Swap index 2 with index 3: "11121" -> "11211"
40+
* - Swap index 1 with index 2: "11211" -> "12111"
41+
* - Swap index 0 with index 1: "12111" -> "21111"
42+
*
43+
* Example 3:
44+
*
45+
* Input: num = "00123", k = 1
46+
* Output: 1
47+
* Explanation: The 1^st smallest wonderful number is "00132". To get this number:
48+
* - Swap index 3 with index 4: "00123" -> "00132"
49+
*
50+
* Constraints:
51+
*
52+
* 2 <= num.length <= 1000
53+
* 1 <= k <= 1000
54+
* num only consists of digits.
55+
******************************************************************************************************/
56+
57+
class Solution {
58+
private:
59+
// Refer to:
60+
// https://leetcode.com/problems/next-permutation/solution/
61+
void nextPermutation(string& num) {
62+
int i = num.size() - 2;
63+
while (i >= 0 && num[i + 1] <= num[i]) {
64+
i--;
65+
}
66+
if (i >= 0) {
67+
int j = num.size() - 1;
68+
while (j >= 0 && num[j] <= num[i]) {
69+
j--;
70+
}
71+
swap(num[i], num[j]);
72+
}
73+
reverse(num, i + 1);
74+
}
75+
76+
void reverse(string& num, int start) {
77+
int i = start, j = num.size() - 1;
78+
while (i < j) {
79+
swap(num[i], num[j]);
80+
i++;
81+
j--;
82+
}
83+
}
84+
85+
86+
public:
87+
int getMinSwaps(string num, int k) {
88+
string pnum = num;
89+
while(k--) {
90+
nextPermutation(pnum);
91+
}
92+
//cout << num << endl << pnum << endl;
93+
int result = 0;
94+
for(int i = 0; i < num.size(); i++) {
95+
if (num[i] == pnum[i]) continue;
96+
for(int j = i + 1; j < num.size(); j++) {
97+
if(num[i] != pnum[j]) continue;
98+
//cout << "j=" << j << ", i=" << i << endl;
99+
result += j - i;
100+
101+
//shift the string
102+
char c = pnum[j];
103+
for (int k = j; k > i; k--) {
104+
pnum[k] = pnum[k-1];
105+
}
106+
pnum[i] = c;
107+
//cout << pnum << endl;
108+
break;
109+
}
110+
}
111+
//cout << endl;
112+
return result;
113+
}
114+
};

0 commit comments

Comments
 (0)
0