2519 回文数字
大约 1 分钟
2519 回文数字
【算法】 枚举、回文判断
【C++】 循环、整数拆分、数位和
【难度】 入门
一、题目简述
找出所有 5 位或 6 位的回文数字(正读反读相同),且各位数字之和等于给定的 ()。按从小到大输出,每行一个。没有则输出 。
二、解题思路
枚举 10000~999999,对每个数判断:
- 是否是回文数
- 各位数字之和是否等于
两个条件都满足才输出。
回文判断:将数字反转,看是否等于原数。也可以用字符串更方便。
使用 to_string() 把数字转成字符串,然后用双指针判断回文。
手算各位和:逐位取模累加。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
// 判断回文
bool isPal(int x) {
string s = to_string(x);
int len = s.length();
for (int i = 0; i < len / 2; i++) {
if (s[i] != s[len - 1 - i])
return false;
}
return true;
}
// 数位和
int digitSum(int x) {
int sum = 0;
while (x > 0) {
sum += x % 10;
x /= 10;
}
return sum;
}
int main() {
int n;
cin >> n;
bool found = false;
for (int i = 10000; i <= 999999; i++) {
if (isPal(i) && digitSum(i) == n) {
cout << i << endl;
found = true;
}
}
if (!found) {
cout << -1 << endl;
}
return 0;
}四、复杂度分析
- 时间:,约 90 万次回文判断,每次约 6 次比较,约 540 万次操作,可以接受。
- 空间:。
