系列文章目录
第1章 求和
第2章 回文
文章目录
一、题目
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
例如，121 是回文，而 123 不是。
（Leetcode编号:09）
二、知识点
1.运算
2.栈
3.双指针
三、解题步骤
1.思路
大方向
（1）数学
设x等于abcdefg，逆x为rex
1.x % 10 => x的最后一位取出，g + 条件1 ：x / 10 > 1 //判断循环结束
2.g * 10 = g0
3.x = abcdef % 10 = f
4.g0 + f =gf
法1.完全循环
rex ?= x
bool isPalindrome(int x) {
if(x < 0)
return false;
long int rex = 0;
long int n = x;
while(n!=0) //n为整型，n<1时，取整为0
{
rex = rex * 10 + n % 10;
n = n / 10;
}
if(rex == x)
return true;
else
return false;
}法2.循环一半（x / 10,同时变化）
1.rex < x 时，循环ing
2.3.rex = x 时，循环结束，真
3.rex > x 时，循环结束，假
【1】末尾为0时，可判断为x ?= 0,提前结束
【2】x = abcde时，即以中间数，左右对称
class Solution {
public boolean isPalindrome(int x) {
if(x < 0||(x % 10 == 0 && x != 0)){
return false;
}
int rex = 0;
while(x > rex){
rex = rex * 10 + x % 10;
x = x / 10; //x也变化
}
return x == rex ||x == rex/10; //[2] x = abcde
}
}法0：给变量 i 记录 x % 10 的次数(多余）
法1：std::string str = std::to_string(x)后，int i = strlen(str)(多余）
在C中，gpt表示有
//在C语言中，可以使用snprintf函数将数字转换为字符串。
//这个函数允许你指定一个最大长度，以防止溢出。这是一个示例：
#include <stdio.h>
int main() {
int num = 123456789;
char str[20];
snprintf(str, sizeof(str), "%d", num);
printf("数字转化为字符串： %s", str);
return 0;
}
//在这个例子中，我们使用snprintf函数将整数num转换为字符串，并将结果存储在字符数组str中。
//sizeof(str)用于确定最大转换长度，防止溢出。（2）字符串&栈
1.数字转化字符串，std::string str = std::to_string(x)后，strlen(str)
2.push一半栈
（2.5）字符串&双指针
1.数字转化字符串，std::string str = std::to_string(x)后，strlen(str)
2.双指针头尾
#include <string>
class Solution {
public:
bool isPalindrome(int x) {
if (x < 0) return false; // 如果数字是负数，则不是回文数
std::string str = std::to_string(x); // 将整数转换为字符串
int len = str.length(); // 获取字符串的长度
int left = 0, right = len - 1; // 初始化左右指针
// 从两端向中间遍历字符串，比较字符是否相等
while (left < right) {
if (str[left] != str[right]) {
return false;
}
left++;
right--;
}
return true; // 如果所有字符都相等，则是回文数
}
};2.实现
（2）字符串&栈(有<stack>)
#include <string>
#include <stack>
class Solution {
public:
bool isPalindrome(int x) {
if (x < 0) return false; // 如果数字是负数，则不是回文数
std::string str = std::to_string(x); // 将整数转换为字符串
int len = str.length(); // 获取字符串的长度
std::stack<char> s; // 创建一个栈来存储一半的字符
for (int i = 0; i < len / 2; ++i) {
s.push(str[i]);
} // 将字符串的前半部分字符压入栈中
// 检查数字是否有奇数个字符
int start = (len % 2 == 0) ? len / 2 : (len / 2) + 1;
//str的中间为开始比较的位置start
for (int i = start; i < len; ++i) {
if (s.empty() || s.top() != str[i]) {
// 从栈中弹出字符并与字符串的后半部分进行比较
return false;
}
s.pop();
}
return s.empty(); // 如果栈为空，则是回文数
}
};(无<stack>)
#include <string>
class Stack {
private:
std::string elements; // 用于存储栈元素的字符串
public:
void push(char c) {
elements += c; // 将字符添加到字符串的末尾，相当于入栈操作
}
bool empty() const {
return elements.empty(); // 检查栈是否为空
}
char pop() {
char topElement = elements.back(); // 获取栈顶元素（字符串的最后一个字符）
elements.pop_back(); // 移除栈顶元素（从字符串中删除最后一个字符）
return topElement; // 返回栈顶元素
}
};
class Solution {
public:
bool isPalindrome(int x) {
if (x < 0) return false; // 如果数字是负数，则不是回文数
std::string str = std::to_string(x); // 将整数转换为字符串
int len = str.length(); // 获取字符串的长度
Stack s; // 创建一个栈来存储一半的字符
// 将字符串的前半部分字符压入栈中
for (int i = 0; i < len / 2; ++i) {
s.push(str[i]); // 将当前字符压入栈中
}
// 检查数字是否有奇数个字符
int start = (len % 2 == 0) ? len / 2 : (len / 2) + 1;
// 从栈中弹出字符并与字符串的后半部分进行比较
for (int i = start; i < len; ++i) {
if (s.empty() || s.pop() != str[i]) {
// 如果栈为空或栈顶元素与当前字符不匹配
return false; // 不是回文数
}
}
return s.empty(); // 如果栈为空，则是回文数
}
};3.演示
4.其他
1.栈
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int top;
} Stack;
// 初始化栈
void init(Stack *s) {
s->top = -1;
}
// 判断栈是否为空
int isEmpty(Stack *s) {
return s->top == -1;
}
// 入栈操作
void push(Stack *s, int value) {
if (s->top >= MAX_SIZE - 1) {
printf("栈已满，无法添加元素");
return;
}
s->data[++(s->top)] = value;
}
// 出栈操作
int pop(Stack *s) {
if (isEmpty(s)) {
printf("栈为空，无法弹出元素");
return -1;
}
return s->data[(s->top)--];
}
// 获取栈顶元素
int peek(Stack *s) {
if (isEmpty(s)) {
printf("栈为空，无法获取栈顶元素");
return -1;
}
return s->data[s->top];
}栈是特殊的数组或链表，先进后出，这个栈是由数组变化而来
总结
以上就是今天要讲的内容，本文仅仅简单介绍了Leetcode编号:09的解题步骤。
