Hard
题目描述
给定一个整数 n。
如果一个数满足以下条件，则称为特殊数：
- 它是一个回文数。
- 数字中的每个数字 k 都恰好出现 k 次。
返回严格大于 n 的最小特殊数。
示例 1：
输入：n = 2
输出：22
解释：22 是大于 2 的最小特殊数，因为它是回文数且数字 2 恰好出现 2 次。
示例 2：
输入：n = 33
输出：212
解释：212 是大于 33 的最小特殊数，因为它是回文数且数字 1 和 2 分别恰好出现 1 次和 2 次。
约束条件：
0 <= n <= 10^15
提示：
- 特殊数的数量很少，可以预处理它们。
- 使用位掩码暴力枚举所有有效的数字 k 选择。
- 生成前半部分数字的所有排列，然后镜像形成完整的回文数。
- 对于每个 n，使用二分查找找到严格大于 n 的最小特殊数。
解题思路
这道题的关键是理解特殊数的性质和预处理的思路。
分析特殊数的特点：
- 必须是回文数
- 每个数字 k 必须恰好出现 k 次
- 数字 0 不能出现（因为 0 出现 0 次意味着不存在）
解题思路：
由于特殊数非常稀少，我们可以采用预处理的方法：
枚举数字组合：使用位掩码枚举所有可能的数字组合。对于数字 1-9，每个数字 k 要么不选，要么选择并出现 k 次。
构造回文数：对于每种有效的数字组合，需要构造回文数。关键是确定前半部分的排列，然后镜像形成完整回文。
排列生成：对于确定的数字组合，生成前半部分的所有可能排列。需要特别处理奇数长度的情况（中间数字只能是奇数次出现的数字）。
预处理所有特殊数：将所有可能的特殊数生成并排序。
二分查找：对于给定的 n，在预处理的特殊数数组中二分查找第一个大于 n 的数。
实现细节：
- 使用回溯生成所有有效的数字排列
- 注意处理奇数长度回文的中间位置
- 确保生成的数字不超过 10^15 的范围
代码实现
class Solution {
public:
vector<long long> specials;
void generateSpecials() {
// 使用位掩码枚举数字1-9的选择
for (int mask = 1; mask < (1 << 9); mask++) {
vector<int> digits;
int totalCount = 0;
// 根据掩码确定选择的数字
for (int i = 0; i < 9; i++) {
if (mask & (1 << i)) {
int digit = i + 1;
for (int j = 0; j < digit; j++) {
digits.push_back(digit);
}
totalCount += digit;
}
}
// 生成回文数
generatePalindromes(digits, totalCount);
}
sort(specials.begin(), specials.end());
}
void generatePalindromes(vector<int>& digits, int totalCount) {
sort(digits.begin(), digits.end());
// 奇数长度的情况
if (totalCount % 2 == 1) {
// 找到可以放在中间的数字（奇数次出现）
map<int, int> count;
for (int d : digits) count[d]++;
for (auto& p : count) {
if (p.second % 2 == 1) {
int middle = p.first;
vector<int> half;
for (auto& q : count) {
for (int i = 0; i < q.second / 2; i++) {
half.push_back(q.first);
}
}
generatePermutations(half, middle);
break;
}
}
} else {
// 偶数长度的情况
vector<int> half;
map<int, int> count;
for (int d : digits) count[d]++;
bool valid = true;
for (auto& p : count) {
if (p.second % 2 != 0) {
valid = false;
break;
}
for (int i = 0; i < p.second / 2; i++) {
half.push_back(p.first);
}
}
if (valid) {
generatePermutations(half, -1);
}
}
}
void generatePermutations(vector<int> half, int middle) {
sort(half.begin(), half.end());
do {
if (half.empty() || half[0] != 0) {
long long num = 0;
// 前半部分
for (int d : half) {
num = num * 10 + d;
}
// 中间数字
if (middle != -1) {
num = num * 10 + middle;
}
// 后半部分（镜像）
vector<int> reversed = half;
reverse(reversed.begin(), reversed.end());
for (int d : reversed) {
num = num * 10 + d;
}
if (num <= 1e15) {
specials.push_back(num);
}
}
} while (next_permutation(half.begin(), half.end()));
}
long long specialPalindrome(long long n) {
if (specials.empty()) {
generateSpecials();
}
auto it = upper_bound(specials.begin(), specials.end(), n);
return it != specials.end() ? *it : -1;
}
};
class Solution:
def __init__(self):
self.specials = []
self.generated = False
def generateSpecials(self):
from itertools import permutations
# 枚举数字1-9的选择
for mask in range(1, 1 << 9):
digits = []
total_count = 0
# 根据掩码确定选择的数字
for i in range(9):
if mask & (1 << i):
digit = i + 1
digits.extend([digit] * digit)
total_count += digit
# 生成回文数
self.generatePalindromes(digits, total_count)
self.specials.sort()
def generatePalindromes(self, digits, total_count):
from collections import Counter
count = Counter(digits)
if total_count % 2 == 1:
# 奇数长度
middle = -1
for digit, cnt in count.items():
if cnt % 2 == 1:
middle = digit
break
if middle != -1:
half = []
for digit, cnt in count.items():
half.extend([digit] * (cnt // 2))
self.generatePermutations(half, middle)
else:
# 偶数长度
valid = True
half = []
for digit, cnt in count.items():
if cnt % 2 != 0:
valid = False
break
half.extend([digit] * (cnt // 2))
if valid:
self.generatePermutations(half, -1)
def generatePermutations(self, half, middle):
from itertools import permutations
seen = set()
for perm in permutations(half):
if not perm or perm[0] != 0:
perm_tuple = tuple(perm)
if perm_tuple not in seen:
seen.add(perm_tuple)
# 构造回文数
num_str = ''.join(map(str, perm))
if middle != -1:
num_str += str(middle)
num_str += ''.join(map(str, reversed(perm)))
num = int(num_str)
if num <= 10**15:
self.specials.append(num)
def specialPalindrome(self, n: int) -> int:
if not self.generated:
self.generateSpecials()
self.generated = True
import bisect
idx = bisect.bisect_right(self.specials, n)
return self.specials[idx] if idx < len(self.specials) else -1
public class Solution {
private List<long> specials = new List<long>();
private bool generated = false;
private void GenerateSpecials() {
// 枚举数字1-9的选择
for (int mask = 1; mask < (1 << 9); mask++) {
List<int> digits = new List<int>();
int totalCount = 0;
// 根据掩码确定选择的数字
for (int i = 0; i < 9; i++) {
if ((mask & (1 << i)) != 0) {
int digit = i + 1;
for (int j = 0; j < digit; j++) {
digits.Add(digit);
}
totalCount += digit;
}
}
// 生成回文数
GeneratePalindromes(digits, totalCount);
}
specials.Sort();
}
private void GeneratePalindromes(List<int> digits, int totalCount) {
var count = new Dictionary<int, int>();
foreach (int d in digits) {
count[d] = count.GetValueOrDefault(d, 0) + 1;
}
if (totalCount % 2 == 1) {
// 奇数长度
int middle = -1;
foreach (var pair in count) {
if (pair.Value % 2 == 1) {
middle = pair.Key;
break;
}
}
if (middle != -1) {
List<int> half = new List<int>();
foreach (var pair in count) {
for (int i = 0; i < pair.Value / 2; i++) {
half.Add(pair.Key);
}
}
GeneratePermutations(half, middle);
}
} else {
// 偶数长度
bool valid = true;
List<int> half = new List<int>();
foreach (var pair in count) {
if (pair.Value % 2 != 0) {
valid = false;
break;
}
for (int i = 0; i < pair.Value / 2; i++) {
half.Add(pair.Key);
}
}
if (valid) {
GeneratePermutations(half, -1);
}
}
}
private void GeneratePermutations(List<int> half, int middle) {
var permutations = GetPermutations(half);
foreach (var perm in permutations) {
if (perm.Count == 0 || perm[0] != 0) {
long num = 0;
// 前半部分
foreach (int d in perm) {
num = num * 10 + d;
}
// 中间数字
if (middle != -1) {
num = num * 10 + middle;
}
// 后半部分（镜像）
for (int i = perm.Count - 1; i >= 0; i--) {
num = num * 10 + perm[i];
}
if (num <= 1000000000000000L) {
specials.Add(num);
}
}
}
}
private HashSet<List<int>> GetPermutations(List<int> list) {
var result = new HashSet<List<int>>(new ListComparer());
var arr = list.ToArray();
Array.Sort(arr);
do {
result.Add(new List<int>(arr));
} while (NextPermutation(arr));
return result;
}
private bool NextPermutation(int[] arr) {
int i = arr.Length - 2;
while (i >= 0 && arr[i] >= arr[i + 1]) i--;
if (i < 0) return false;
int j = arr.Length - 1;
while (arr[j] <= arr[i]) j--;
(arr[i], arr[j]) = (arr[j], arr[i]);
Array.Reverse(arr, i + 1, arr.Length - i - 1);
return true;
}
public long SpecialPalindrome(long n) {
if (!generated) {
GenerateSpecials();
generated = true;
}
int left = 0, right = specials.Count - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (specials[mid] <= n) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left < specials.Count ? specials[left] : -1;
}
}
public class ListComparer : IEqualityComparer<List<int>> {
public bool Equals(List<int> x, List<int> y) {
return x.SequenceEqual(y);
}
public int GetHashCode(List<int> obj) {
return string.Join(",", obj).GetHashCode();
}
}
var specialPalindrome = function(n) {
function isSpecial(num) {
const str = num.toString();
const count = new Array(10).fill(0);
for (let char of str) {
count[parseInt(char)]++;
}
for (let i = 0; i < 10; i++) {
if (count[i] !== 0 && count[i] !== i) {
return false;
}
}
return str === str.split('').reverse().join('');
}
function generateSpecialPalindromes(maxLen) {
const results = [];
function backtrack(digits, remaining) {
if (remaining.every(x => x === 0)) {
const palindrome = createPalindrome(digits);
if (palindrome > n) {
results.push(palindrome);
}
return;
}
for (let digit = 1; digit <= 9; digit++) {
if (remaining[digit] >= 2) {
digits.push(digit);
remaining[digit] -= 2;
backtrack(digits, remaining);
remaining[digit] += 2;
digits.pop();
}
}
for (let digit = 1; digit <= 9; digit++) {
if (remaining[digit] === 1) {
digits.push(digit);
remaining[digit] = 0;
backtrack(digits, remaining);
remaining[digit] = 1;
digits.pop();
break;
}
}
}
function createPalindrome(digits) {
digits.sort((a, b) => a - b);
const left = [];
const right = [];
let middle = -1;
const count = new Array(10).fill(0);
for (let d of digits) count[d]++;
for (let i = 1; i <= 9; i++) {
if (count[i] % 2 === 1) {
middle = i;
}
for (let j = 0; j < Math.floor(count[i] / 2); j++) {
left.push(i);
}
}
const result = left.concat(middle === -1 ? [] : [middle], left.slice().reverse());
return parseInt(result.join(''));
}
for (let len = 1; len <= maxLen; len++) {
for (let mask = 1; mask < (1 << 9); mask++) {
const remaining = new Array(10).fill(0);
let totalDigits = 0;
for (let digit = 1; digit <= 9; digit++) {
if (mask & (1 << (digit - 1))) {
remaining[digit] = digit;
totalDigits += digit;
}
}
if (totalDigits === len) {
backtrack([], remaining);
}
}
}
return results;
}
const nStr = n.toString();
const candidates = generateSpecialPalindromes(nStr.length + 2);
if (candidates.length === 0) {
return generateSpecialPalindromes(20)[0];
}
return Math.min(...candidates);
};
复杂度分析
| 指标 | 复杂度 |
|---|---|
| 时间 | - |
| 空间 | - |