菜鸟的Leetcode（02）

系列文章目录

第1章  求和

第2章  回文

文章目录

• 系列文章目录
• 前言
• 一、题目
• 二、知识点
• 三、解题步骤
  • 1.思路
  • 2.实现
  • 3.演示
  • 4.其他
• 总结

一、题目

给你一个整数 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的解题步骤。