class Solution {
public:
int nextBeautifulNumber(int 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 的最小数值平衡数。
提示：
0 <= n <= 106原站题解
javascript 解法, 执行用时: 332 ms, 内存消耗: 47.3 MB, 提交时间: 2023-12-09 00:14:07
/**
* @param {number} x
* @return {boolean}
*/
function isBalance(x) {
const count = new Array(10).fill(0);
while (x > 0) {
count[x % 10]++;
x = Math.floor(x / 10);
}
for (let d = 0; d < 10; d++) {
if (count[d] > 0 && count[d] != d) {
return false;
}
}
return true;
}
/**
* @param {number} n
* @return {number}
*/
var nextBeautifulNumber = function(n) {
for (let i = n + 1; i <= 1224444; i++) {
if (isBalance(i)) {
return i;
}
}
};
php 解法, 执行用时: 12 ms, 内存消耗: 18.7 MB, 提交时间: 2023-09-14 00:32:50
class Solution {
/**
* @param Integer $n
* @return Integer
*/
function nextBeautifulNumber($n) {
$table = [
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
];
foreach ($table as $t) if ($t > $n) return $t;
}
}
java 解法, 执行用时: 97 ms, 内存消耗: 42 MB, 提交时间: 2023-09-14 00:32:24
class Solution {
public boolean check(int num) {
int [] xf = new int [10];
while (num != 0) {
int x = num % 10;
xf[x] ++;
num /= 10;
}
for (int x = 0; x < 10; x ++) {
if (xf[x] != 0 && x != xf[x]) {
return false;
}
}
return true;
}
public int nextBeautifulNumber(int n) {
int num = n + 1;
while (check(num) == false) {
num ++;
}
return num;
}
}
cpp 解法, 执行用时: 84 ms, 内存消耗: 6.1 MB, 提交时间: 2023-09-14 00:31:44
class Solution {
public:
bool check(int num) {
int xf[10];
memset(xf, 0, sizeof(xf));
while (num != 0) {
int x = num % 10;
xf[x] ++;
num /= 10;
}
for (int x = 0; x < 10; x ++) {
if (xf[x] != 0 && x != xf[x]) {
return false;
}
}
return true;
}
int nextBeautifulNumber(int n) {
int num = n + 1;
while (check(num) == false) {
num ++;
}
return num;
}
};
python3 解法, 执行用时: 5332 ms, 内存消耗: 15.9 MB, 提交时间: 2023-09-14 00:30:51
class Solution:
def nextBeautifulNumber(self, n: int) -> int:
def check(num: int) -> bool:
xf = collections.defaultdict(int)
for x in str(num):
xf[int(x)] += 1
for x, f in xf.items():
if x != f:
return False
return True
x = n + 1
while check(x) == False:
x += 1
return x
rust 解法, 执行用时: 24 ms, 内存消耗: 2 MB, 提交时间: 2023-09-14 00:30:04
impl Solution {
pub fn next_beautiful_number(n: i32) -> i32 {
use std::collections::HashSet;
fn shuffle_and_record(set: &mut HashSet<i32>, s:&str, visited: &mut Vec<bool>, cur: &mut String){
if cur.len() == s.len() {
set.insert(cur.parse::<i32>().unwrap());
return;
}
for v in 0..s.len(){
if !visited[v] {
visited[v] = true;
cur.push(s.chars().nth(v).unwrap());
shuffle_and_record(set, s.clone(), visited, cur);
visited[v] = false;
cur.pop();
}
}
}
let mut dict = ["1","22","122","333","1333","4444","14444","22333","55555"
,"122333","155555","224444","666666"];
let mut set = HashSet::new();
for s in dict{
let l = s.len();
shuffle_and_record(&mut set, s, &mut vec![false;l], &mut String::new());
}
set.insert(1224444);
let mut arr = set.into_iter().collect::<Vec<i32>>();
arr.sort_unstable();
match arr.binary_search(&(n+1)){
Ok(i) => arr[i],
Err(i) => arr[i],
}
}
pub fn next_beautiful_number2(n: i32) -> i32 {
let mut v = [0; 10];
let mut j = n + 1;
loop {
let mut i = j;
while i != 0 {
v[(i % 10) as usize] += 1;
i /= 10;
}
let mut k = 0;
while k < 10 {
if v[k] == 0 {
k += 1;
continue;
} else {
if v[k] != k {
break;
}
}
k += 1;
}
if k >= 10 {
return j;
}
v = [0; 10];
j += 1;
}
}
}
python3 解法, 执行用时: 36 ms, 内存消耗: 15.7 MB, 提交时间: 2023-09-14 00:29:00
class Solution:
def nextBeautifulNumber(self, n: int) -> int:
_dic = [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]
return _dic[bisect.bisect(_dic, n)]
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-09-14 00:27:40
// 打表 + 二分
var balanced = []int{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}
func nextBeautifulNumber(n int) int {
return balanced[sort.SearchInts(balanced, n+1)]
}
golang 解法, 执行用时: 28 ms, 内存消耗: 1.8 MB, 提交时间: 2023-09-14 00:26:31
// 暴力枚举
func nextBeautifulNumber(n int) int {
next:
for n++; ; n++ {
cnt := [10]int{}
for x := n; x > 0; x /= 10 {
cnt[x%10]++
}
for x := n; x > 0; x /= 10 {
if cnt[x%10] != x%10 {
continue next
}
}
return n
}
}