本文主要是介绍5455. 最多 K 次交换相邻数位后得到的最小整数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目
给你一个字符串 num 和一个整数 k 。其中,num 表示一个很大的整数,字符串中的每个字符依次对应整数上的各个 数位 。
你可以交换这个整数相邻数位的数字 最多 k 次。
请你返回你能得到的最小整数,并以字符串形式返回。
leecode 运行的效果;
解题思路:
以“4321” 为例
第一次排序开始 : start = 0 ; num = “4321” , k = 4(最多可以移动的次数) ;
“4321” 长度最大 为 4 的字符串 为 “4321”
最小字符‘1’的位置 为 3 ; 3 - start = 3 ;
第一次排序后: “1432” ,排序后 k = 1 ;
第一次排序开始 : start = 1 ; num = “4321” , k = 1 ;
第 0 位 已经完成排序 ,所以要从 下标为1的位置寻找长度为 2的字符串 即为 “43” ;
“43”最小的字符是‘3’位置为 下标 2 ; k = k -( 2 - start ) = 0
第二次排序结束:“1342” , k = 0 ; 结束排序。
class Solution {
public:
/*
在字符串的长度为k的前提下找到最小的字符的位置
因为都是数字,所以实在‘0’ 到 ‘9’ 之间,为了减少寻找最小值得时间;
*/int minK (string num , int start , int k, vector<int>& ink ){char note ;int i ;/** 为了减少查询从**(起始位 移动 k 次 范围内)** 最小的字符的位置*/for (i = '0' ; i <= '9' ; i ++){if(ink[i] != 0){note = char(i) ;break ;}}int maxlen = (num.length() - 1) > (start + k) ? (start + k) : (num.length() - 1) ;char minNum = num[start] ;int local = start ;
/*
*寻找可操作范围内,最小的字符的位置,找到第一位即可退出寻找,节约计算时*间
*/for (i = start ; i <= maxlen ; i ++ ){if (minNum > num[i]){minNum = num[i] ;local = i ;}if (minNum == note)break ;}ink[minNum] -- ;return local ;}/*
更新每一轮的排序后的num值
*/string minInteger(string num, int k) {int ret ;int i = 0 , j ;vector<int> ink = vector<int>(128, 0) ;char tmp ;for (char cf : num)ink[cf] ++ ;while(k != 0){ret = minK(num , i , k, ink) ;//cout << ret << endl ;if (ret != i){k -= (ret - i) ;tmp = num[ret] ;num.erase(num.begin() + ret) ;num.insert(num.begin() + i, tmp) ;}i ++ ;if (i == num.length())break ;//cout << ret << " : " << k << " i: " << i << " : " << num << endl ;}return num ;}
};
这篇关于5455. 最多 K 次交换相邻数位后得到的最小整数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!