wordpress 企业网站 授权费,企业查询信息系统,深圳小程序搭建,wordpress rss 采集2048. 下一个更大的数值平衡数
如果整数 x 满足#xff1a;对于每个数位 d #xff0c;这个数位 恰好 在 x 中出现 d 次。那么整数 x 就是一个 数值平衡数 。
给你一个整数 n #xff0c;请你返回 严格大于 n 的 最小数值平衡数 。
示例 1#xff1a;输入#xff1a;n …2048. 下一个更大的数值平衡数
如果整数 x 满足对于每个数位 d 这个数位 恰好 在 x 中出现 d 次。那么整数 x 就是一个 数值平衡数 。
给你一个整数 n 请你返回 严格大于 n 的 最小数值平衡数 。
示例 1输入n 1
输出22
解释
22 是一个数值平衡数因为
- 数字 2 出现 2 次
这也是严格大于 1 的最小数值平衡数。
示例 2输入n 1000
输出1333
解释
1333 是一个数值平衡数因为
- 数字 1 出现 1 次。
- 数字 3 出现 3 次。
这也是严格大于 1000 的最小数值平衡数。
注意1022 不能作为本输入的答案因为数字 0 的出现次数超过了 0 。
示例 3输入n 3000
输出3133
解释
3133 是一个数值平衡数因为
- 数字 1 出现 1 次。
- 数字 3 出现 3 次。
这也是严格大于 3000 的最小数值平衡数。解题思路
先计算当前n有多少位设为k如果n比拥有k个数位的数值平衡数都要大那么我们就求k1位的最小数值平衡数使用回溯法求出拥有k个数位的所有数值平衡数因为我们只能从1-9中取数字组成数值平衡数并且每个数位的出现次数必须与数位值相同我们尝试组成k个数位的所有可能性并且使用全排列将所有的可能排列遍历一遍找出严格大于 n 的 最小数值平衡数 。
代码
class Solution {
public:int min0x3f3f3f3f,tar;int nextBeautifulNumber(int n) {this-tarn;if(n0) return 1;dfs(vectorint{},0, 1 (int)log10(n));dfs(vectorint{},0, 2 (int)log10(n));return min;}void dfs(vectorint arr,int cur,int len){if (len0){do{int sum0;for (int i 0; i arr.size(); i) {sumsum*10arr[i];}if (sumtarsummin)minsum;}while (next_permutation(arr.begin(),arr.end()));return;}for (int i cur; leni ; i) {for (int j 0; j i; j) {arr.push_back(i);}dfs(arr,i1,len-i);for (int j 0; j i; j) {arr.pop_back();}}}};
