LeetCodeWeekly 239C 1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number next_permutaion と 隣接swapする回数
題意
- 最大1000桁のある数値$num$が与えられる。いま、この数を並び替えて作れる数字を考えたときに、$num$よりも厳密に大きい数字のみを考える。
- このような$k$番目を考えると、$num$の隣接した数字を最小で何回入れ替えればいいか。
こう考えた
この問題は2つのステップに分かれる。
- STEP1: $k$個大きな数字を求める。これを$target$とする
- STEP2: $num$の隣接数字を何回入れ替えると$target$にできるかを判定する
STEP1 1つ目に大きな数値
C++ならnext_permutationを使う。next_permutaionはhttps://cpprefjp.github.io/reference/algorithm/next_permutation.html
にある。通常は、ソートした配列からスタートして、辞書順にすべての順列を得ることに使われる。ここで、next_permutationは毎回、配列を並び替える。つまり、${1,2,3}$を与えると、配列が${1,3,2}$に並び替えられる。この性質を使い、$nums$を配列として$k$回next_permutaionに渡すことで、$target$を求められる。
STEP2 隣接した要素を並び替える回数
$num$が高々1000桁なので愚直にシミュレーションする。STEP1で元の$nums$は並び替えられてしまうので、これを保持してき、$ind=i$の文字が次に出現する位置$j$を探索して、位置$i$まで実際にswapすればよい。
実装
class Solution {
public:
int getMinSwaps(string num, int k) {
int sl = num.size();
int res = 0, j;
vector<int> dat(sl), odat(sl);
REP(i, sl) odat.at(i) = num[i] - 0x30;
REP(i, sl) dat.at(i) = num[i] - 0x30;
REP(i, k) next_permutation(dat.begin(), dat.end()); // k個先を探索する
REP(i, sl){ // すべての文字をチェック
if(dat[i] == odat[i]) continue; // 入れ替える必要がない
j = i + 1;
while(dat[j] != odat[i]) j++; // 文字がある場所jを探す
while(j > i) { // swapをシミュレーション
swap(dat[j-1], dat[j]);
--j;
++res;
}
}
return res;
}
};
class Solution {
public:
int getMinSwaps(string num, int k) {
int sl = num.size();
int res = 0, j;
vector<int> dat(sl), odat(sl);
REP(i, sl) odat.at(i) = num[i] - 0x30;
REP(i, sl) dat.at(i) = num[i] - 0x30;
REP(i, k) next_permutation(dat.begin(), dat.end()); // k個先を探索する
REP(i, sl){ // すべての文字をチェック
if(dat[i] == odat[i]) continue; // 入れ替える必要がない
j = i + 1;
while(dat[j] != odat[i]) j++; // 文字がある場所jを探す
while(j > i) { // swapをシミュレーション
swap(dat[j-1], dat[j]);
--j;
++res;
}
}
return res;
}
};
Author And Source
この問題について(LeetCodeWeekly 239C 1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number next_permutaion と 隣接swapする回数), 我々は、より多くの情報をここで見つけました https://qiita.com/recuraki/items/10f95ce2c82526bcd4fd著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .