回文数判断

c/c++蓝桥杯经典编程题100道-目录-CSDN博客

---

目录

回文数判断

一、题型解释

二、例题问题描述

三、C语言实现

解法1：整数反转比较（难度★）

解法2：字符串双指针法（难度★★）

解法3：仅反转一半数字（难度★★☆）

四、C++实现

解法1：字符串反转比较（难度★）

解法2：双指针法优化（难度★★）

解法3：整数反转（C++模板）（难度★☆）

五、总结对比表

六、特殊方法与内置函数补充

1. C语言 sprintf 函数

2. C++ std::reverse 函数

3. C++ isalnum 和 tolower 函数

---

一、题型解释

回文数（Palindrome）是指正读和反读都相同的数字或字符串。常见题型：

1. 基础回文数：判断整数是否为回文数（如 121 是回文数，-121 不是）。

2. 字符串回文：判断字符串是否为回文（忽略大小写和非字母数字字符，如 "A man, a plan, a canal: Panama"）。

3. 进阶问题：

   • 在特定进制下判断回文（如二进制、十六进制）。

   • 找出某范围内的所有回文数。

---

二、例题问题描述

例题1：输入整数 121，输出 true（是回文数）。
例题2：输入字符串 "A man, a plan, a canal: Panama"，输出 true（忽略非字母数字字符后为回文）。
例题3：输入整数 123，输出 false（不是回文数）。
例题4：输入整数 5，输出 true（单个数字是回文数）。

---

三、C语言实现

解法1：整数反转比较（难度★）

通俗解释：

• 将整数反转，与原数比较是否相等。注意处理负数。

c

#include <stdio.h>
#include <stdbool.h>

bool isPalindrome(int x) {
    if (x < 0) return false; // 负数不是回文数
    long reversed = 0;       // 防止反转溢出
    int original = x;
    while (x > 0) {
        reversed = reversed * 10 + x % 10; // 逐位反转
        x /= 10;
    }
    return original == reversed; // 比较反转后与原数
}

int main() {
    printf("%d\n", isPalindrome(121)); // 输出 1（true）
    printf("%d\n", isPalindrome(-121)); // 输出 0（false）
    return 0;
}

代码逻辑：

1. 处理负数：直接返回 false。

2. 反转整数：通过取余和除法逐位反转。

3. 防止溢出：用 long 存储反转结果。

4. 比较结果：若反转后与原数相等，则是回文数。

---

解法2：字符串双指针法（难度★★）

通俗解释：

• 将整数转为字符串，用左右指针向中间比较字符。

c

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

bool isPalindromeString(int x) {
    if (x < 0) return false;
    char str[20];
    sprintf(str, "%d", x); // 将整数转为字符串
    int left = 0, right = strlen(str) - 1;
    while (left < right) {
        if (str[left] != str[right]) return false;
        left++;
        right--;
    }
    return true;
}

int main() {
    printf("%d\n", isPalindromeString(12321)); // 输出 1（true）
    printf("%d\n", isPalindromeString(123));   // 输出 0（false）
    return 0;
}

代码逻辑：

1. 转为字符串：用 sprintf 将整数转换为字符串。

2. 双指针遍历：left 从头开始，right 从尾开始，向中间移动并比较字符。

---

解法3：仅反转一半数字（难度★★☆）

通俗解释：

• 反转数字的后半部分，与前半部分比较（避免溢出）。

c

#include <stdbool.h>

bool isPalindromeHalf(int x) {
    if (x < 0 || (x % 10 == 0 && x != 0)) return false; // 处理负数和末尾为0的情况
    int reversedHalf = 0;
    while (x > reversedHalf) {
        reversedHalf = reversedHalf * 10 + x % 10; // 反转后半部分
        x /= 10;
    }
    return x == reversedHalf || x == reversedHalf / 10; // 处理奇偶长度
}

int main() {
    printf("%d\n", isPalindromeHalf(12321)); // 输出 1（true）
    printf("%d\n", isPalindromeHalf(1221));  // 输出 1（true）
    return 0;
}

代码逻辑：

1. 特殊情况处理：负数和末位为0的非零数直接返回 false。

2. 反转后半部分：当原数剩余部分大于反转部分时继续反转。

3. 比较条件：

   • 偶数位数：x == reversedHalf。

   • 奇数位数：x == reversedHalf / 10（忽略中间位）。

---

四、C++实现

解法1：字符串反转比较（难度★）

通俗解释：

• 将字符串反转后与原字符串比较。

cpp

#include <iostream>
#include <string>
#include <algorithm> // 包含reverse函数
using namespace std;

bool isPalindromeString(const string& s) {
    string filtered;
    // 过滤非字母数字字符并转为小写
    for (char c : s) {
        if (isalnum(c)) { 
            filtered += tolower(c);
        }
    }
    string reversed = filtered;
    reverse(reversed.begin(), reversed.end()); // 反转字符串
    return filtered == reversed;
}

int main() {
    cout << boolalpha; // 输出true/false而非1/0
    cout << isPalindromeString("A man, a plan, a canal: Panama") << endl; // true
    cout << isPalindromeString("race a car") << endl; // false
    return 0;
}

代码逻辑：

1. 过滤字符：使用 isalnum 保留字母和数字，tolower 统一小写。

2. 反转字符串：用 reverse 函数反转处理后的字符串。

3. 比较结果：若反转后与原字符串相同，则是回文。

---

解法2：双指针法优化（难度★★）

通俗解释：

• 直接在原字符串上使用双指针，跳过非字母数字字符。

cpp

#include <iostream>
#include <string>
using namespace std;

bool isPalindromeOptimized(const string& s) {
    int left = 0, right = s.size() - 1;
    while (left < right) {
        // 跳过非字母数字字符
        while (left < right && !isalnum(s[left])) left++;
        while (left < right && !isalnum(s[right])) right--;
        // 比较字符（忽略大小写）
        if (tolower(s[left]) != tolower(s[right])) return false;
        left++;
        right--;
    }
    return true;
}

int main() {
    cout << boolalpha;
    cout << isPalindromeOptimized("A man, a plan, a canal: Panama") << endl; // true
    cout << isPalindromeOptimized("0P") << endl; // false（'0'与'P'不等）
    return 0;
}

代码逻辑：

1. 跳过无效字符：左右指针跳过非字母数字字符。

2. 忽略大小写：用 tolower 统一字符大小写后比较。

3. 双指针遍历：向中间移动直到相遇。

---

解法3：整数反转（C++模板）（难度★☆）

通俗解释：

• 使用模板支持不同整数类型（如 int、long）。

cpp

#include <iostream>
#include <type_traits> // 用于类型检查
using namespace std;

template<typename T>
bool isPalindromeNumber(T x) {
    static_assert(is_integral<T>::value, "T必须是整数类型"); // 确保是整数
    if (x < 0) return false;
    T original = x;
    T reversed = 0;
    while (x > 0) {
        reversed = reversed * 10 + x % 10;
        x /= 10;
    }
    return original == reversed;
}

int main() {
    cout << boolalpha;
    cout << isPalindromeNumber(12321) << endl; // true
    cout << isPalindromeNumber(123) << endl;   // false
    return 0;
}

代码逻辑：

1. 模板定义：支持 int、long 等整数类型。

2. 类型检查：static_assert 确保传入的是整数。

3. 反转比较：与C语言解法类似，但通过模板泛化。

---

五、总结对比表

方法	时间复杂度	空间复杂度	优点	缺点
整数反转比较	O(log n)	O(1)	无需额外空间	需处理溢出
字符串双指针法	O(n)	O(n)	直观易理解	需转换字符串
反转一半数字	O(log n)	O(1)	避免溢出，高效	逻辑较复杂
字符串反转比较	O(n)	O(n)	代码简洁	需要过滤和转换字符
双指针优化法	O(n)	O(1)	无需额外空间，直接操作	需处理字符过滤

---

六、特殊方法与内置函数补充

1. C语言 sprintf 函数

• 作用：将整数格式化为字符串。

• 示例：sprintf(str, "%d", x); 将整数 x 存入字符数组 str。

• 注意：需确保目标数组足够大（如 char str[20] 支持64位整数）。

2. C++ std::reverse 函数

• 作用：反转容器（如字符串、数组）中的元素顺序。

• 示例：reverse(s.begin(), s.end()); 反转字符串 s。

3. C++ isalnum 和 tolower 函数

• isalnum：检查字符是否为字母或数字。

• tolower：将字符转换为小写形式。

c/c++蓝桥杯经典编程题100道-目录-CSDN博客