题目描述
循环数是一种没有重复数字且不含 0 并具有一些有趣性质的整数。
我们以 81362 为例:
如果从最左边的那个数字(在这里是 8)开始,向右数该数字位(当数到最右边的数字时,若还没有数完,则从左边第一位继续数),你将在一个新的数字处停下(如果没停在新数字上,则这个数不是循环数)。对于本例,从 8 开始右数 8 位:1 3 6 2 8 1 3 6,将停在 6 上。
在新停下的位置,继续重复上一个操作,也就是从 6 开始右数 6 位:2 8 1 3 6 2,将停在 2 上。
再次重复此操作,从 2 开始右数 2 位:8 1,将停在 1 上。
继续重复此操作,从 1 开始右数 1 位:3,将停在 3 上。
最后,从 3 开始右数 3 位:6 2 8,将停在 8 上。
循环数满足在所有的数字上均停留一次后,又能够回到出发点上。如果在所有的数字上均停留一次后,没有回到出发点,则这个数不是循环数。
给定一个数字 M,请你找到第一个比 M 大的循环数是多少。
样例
81361
算法1
(暴力枚举) $O(n)$
这道题我直接一个数一个数枚举的,没想到比y总的dfs优化还快了5倍。不知道为什么。。。
时间复杂度
10^7 * 7
实际复杂度会快很多
C++ 代码
//
// Created by Henry Yi on 2021-02-04.
//
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N = 1e7 + 10, M = 10;
int n, used[M], cnt[M];
bool check(int i)
{
string path = to_string(i);
memset(used, 0, sizeof used);
memset(cnt, 0, sizeof cnt);
for (int i = 0, j = 0; i < path.size(); i ++ )
{
j += path[j] - '0';
j %= path.size();
if (cnt[path[j] - '0']) return false;
cnt[path[j] - '0']++;
if (used[j]) return false;
used[j] = true;
}
return true;
}
int main() {
cin >> n;
for (int i = n + 1; ; i++) {
if (check(i)) {
cout << i << endl;
break;
}
}
}
const int N = 1e7 + 10 not used at all