网站静态首页模板,游戏介绍网站模板下载地址,地产网站方案,学校 网站建设 招标【LetMeFly】2048.下一个更大的数值平衡数
力扣题目链接#xff1a;https://leetcode.cn/problems/next-greater-numerically-balanced-number/
如果整数 x 满足#xff1a;对于每个数位 d #xff0c;这个数位 恰好 在 x 中出现 d 次。那么整数 x 就是一个 数值平衡数 。…【LetMeFly】2048.下一个更大的数值平衡数
力扣题目链接https://leetcode.cn/problems/next-greater-numerically-balanced-number/
如果整数 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 的最小数值平衡数。提示
0 n 106
方法一枚举
我们可以很方便地写一个函数用来判断一个数 n n n是否为“数值平衡数”。 只需要取出这个数的每一位并统计出现次数从0到10遍历如果出现次数不等于这个数就返回false否则返回true。 接下来从给定的 n n n的下一个数开始枚举直到枚举到了“数值平衡数”为止。
时间复杂度不易计算但是能过方法二中也可以看出无论给定n是多少枚举量都不超过557778空间复杂度 O ( 1 ) O(1) O(1)
AC代码
C
class Solution {
private:bool isok(int n) {int cnt[10] {0};while (n) {cnt[n % 10];n / 10;}for (int i 0; i 9; i) {if (cnt[i] cnt[i] ! i) {return false;}}return true;}public:int nextBeautifulNumber(int n) {while (!isok(n));return n;}
};Python
class Solution:def ok(self, n: int) - bool:cnt [0] * 10while n:cnt[n % 10] 1n // 10for i in range(10):if cnt[i] and cnt[i] ! i:return Falsereturn Truedef nextBeautifulNumber(self, n: int) - int:while True:n 1if self.ok(n):return n方法二打表
方法一中我们实现了“判断一个数是否为数值平衡数的函数”因此我们可以写一个简单的程序预先将所有可能用到的“数值平衡数”存下来
#include bits/stdc.h
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout #x x endl
#define fi(i, l, r) for (int i l; i r; i)
#define cd(a) scanf(%d, a)
typedef long long ll;bool isok(int n) {int cnt[10] {0};while (n) {cnt[n % 10];n / 10;}for (int i 0; i 9; i) {if (cnt[i] cnt[i] ! i) {return false;}}return true;
}int main() {vectorint ok;int n 0;while (n) {if (isok(n)) {ok.push_back(n);if (n 1000000) {break;}}}for (int t : ok) {cout t , ;}puts();return 0;
}上述代码不重要反正只要能得到下面的这个表就好
1, 22, 122, 212, 221, 333, 1333, 3133, 3313, 3331, 4444, 14444, 22333, 23233, 23323, 23332, 32233, 32323, 32332, 33223, 33232, 33322, 41444, 44144, 44414, 44441, 55555, 122333, 123233, 123323, 123332, 132233, 132323, 132332, 133223, 133232, 133322, 155555, 212333, 213233, 213323, 213332, 221333, 223133, 223313, 223331, 224444, 231233, 231323, 231332, 232133, 232313, 232331, 233123, 233132, 233213, 233231, 233312, 233321, 242444, 244244, 244424, 244442, 312233, 312323, 312332, 313223, 313232, 313322, 321233, 321323, 321332, 322133, 322313, 322331, 323123, 323132, 323213, 323231, 323312, 323321, 331223, 331232, 331322, 332123, 332132, 332213, 332231, 332312, 332321, 333122, 333212, 333221, 422444, 424244, 424424, 424442, 442244, 442424, 442442, 444224, 444242, 444422, 515555, 551555, 555155, 555515, 555551, 666666, 1224444这是从1到1224444的所有“数值平衡数”。有了这张表不论给你的n等于几你都可以通过二分等方式在极短的时间内找到第一个大于n的“数值平衡数”。
时间复杂度 log l e n ( B i a o ) \log len(Biao) loglen(Biao)其中表的大小 l e n ( B i a o ) 110 len(Biao)110 len(Biao)110空间复杂度 O ( l e n ( B i a o ) ) O(len(Biao)) O(len(Biao))
AC代码
C
const int ok[] {1, 22, 122, 212, 221, 333, 1333, 3133, 3313, 3331, 4444, 14444, 22333, 23233, 23323, 23332, 32233, 32323, 32332, 33223, 33232, 33322, 41444, 44144, 44414, 44441, 55555, 122333, 123233, 123323, 123332, 132233, 132323, 132332, 133223, 133232, 133322, 155555, 212333, 213233, 213323, 213332, 221333, 223133, 223313, 223331, 224444, 231233, 231323, 231332, 232133, 232313, 232331, 233123, 233132, 233213, 233231, 233312, 233321, 242444, 244244, 244424, 244442, 312233, 312323, 312332, 313223, 313232, 313322, 321233, 321323, 321332, 322133, 322313, 322331, 323123, 323132, 323213, 323231, 323312, 323321, 331223, 331232, 331322, 332123, 332132, 332213, 332231, 332312, 332321, 333122, 333212, 333221, 422444, 424244, 424424, 424442, 442244, 442424, 442442, 444224, 444242, 444422, 515555, 551555, 555155, 555515, 555551, 666666, 1224444};class Solution {
public:int nextBeautifulNumber(int n) {return *upper_bound(ok, ok sizeof(ok) / sizeof(int), n);}
};Python
# from bisect import bisect_rightok [1, 22, 122, 212, 221, 333, 1333, 3133, 3313, 3331, 4444, 14444, 22333, 23233, 23323, 23332, 32233, 32323, 32332, 33223, 33232, 33322, 41444, 44144, 44414, 44441, 55555, 122333, 123233, 123323, 123332, 132233, 132323, 132332, 133223, 133232, 133322, 155555, 212333, 213233, 213323, 213332, 221333, 223133, 223313, 223331, 224444, 231233, 231323, 231332, 232133, 232313, 232331, 233123, 233132, 233213, 233231, 233312, 233321, 242444, 244244, 244424, 244442, 312233, 312323, 312332, 313223, 313232, 313322, 321233, 321323, 321332, 322133, 322313, 322331, 323123, 323132, 323213, 323231, 323312, 323321, 331223, 331232, 331322, 332123, 332132, 332213, 332231, 332312, 332321, 333122, 333212, 333221, 422444, 424244, 424424, 424442, 442244, 442424, 442442, 444224, 444242, 444422, 515555, 551555, 555155, 555515, 555551, 666666, 1224444]class Solution:def nextBeautifulNumber(self, n: int) - int:return ok[bisect_right(ok, n)]同步发文于CSDN原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/134900679
