算法-回溯法-回文

素颜马尾好姑娘i 2023-02-16 14:29 16阅读 0赞

# 算法-回溯法-回文 #

# 1 题目概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/palindrome-number/submissions/

## 1.2 题目描述 ##

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:

输入: 121  
输出: true  
示例 2:

输入: -121  
输出: false  
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。  
示例 3:

输入: 10  
输出: false  
解释: 从右向左读, 为 01 。因此它不是一个回文数。

# 2 除反转法 #

## 2.1 思路 ##

1.  将原数字x每次除以10求余数，当做反转数result\*10的个位，累加到result。
2.  然后每次x置为x/10。
3.  循环1和2，直到x==0
4.  最后比较反转数result和原数字x是否相等，相等就是回文，否则不是。

## 2.2 代码 ##

class Solution { 
        public boolean isPalindrome(int x) { 
            if(x < 0){ 
                // 负数不是回文
                return false;
            }
            // 反转数字
            int result = 0;
            int tmp = x;
            while(tmp != 0){ 
                result = result * 10 + tmp % 10;
                tmp /= 10;
            }
            return result == x;
        }
    }

## 2.3 时间复杂度 ##

![在这里插入图片描述][20200610110848906.png]

## 2.4 空间复杂度 ##

O(1)

[20200610110848906.png]: https://img-blog.csdnimg.cn/20200610110848906.png

发表评论取消回复

表情：

评论列表（有 0 条评论，16人围观）

还没有评论，来说两句吧...

相关阅读

相关回溯——131. 分割回文串

1 题目描述 1. 分割回文串给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。回文串是正着读

冷不防/ 2023年10月08日 16:14/ 0 赞/ 12 阅读

相关 LeetCode回溯算法分割问题——131.分割回文串

一、题目描述： [131. 分割回文串][131.] 给你一个字符串 `s`，请你将`s`分割成一些子串，使每个子串都是回文串。返回 `s` 所有可能的分割方案。

迷南。/ 2023年09月28日 15:33/ 0 赞/ 114 阅读

相关算法-Hash-回文

算法-Hash-回文 1 题目概述 1.1 题目出处 https://leetcode-cn.com/problems/longest-palindrome

谁借莪１个温暖的怀抱￠/ 2023年03月13日 03:17/ 0 赞/ 17 阅读

相关算法：回文数。

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。示例 > 输入: 121 > 输出: true 示例

爱被打了一巴掌/ 2023年03月05日 03:14/ 0 赞/ 4 阅读

相关算法-回溯法-回文

算法-回溯法-回文 1 题目概述 1.1 题目出处 https://leetcode-cn.com/problems/palindrome-number/su

素颜马尾好姑娘i/ 2023年02月16日 14:29/ 0 赞/ 17 阅读

相关回溯皇后算法笔记_[算法笔记] 回溯法总结

本文复习一下回溯法，包括递归型和非递归型，通过下面 2 个例子来解析回溯法：全排列问题 n 皇后问题三着色问题回溯法在许多递归问题当中，我们采取的方法都是穷尽

深藏阁楼爱情的钟/ 2023年01月10日 03:45/ 0 赞/ 225 阅读

相关回溯法-哈密尔顿回路

一、哈密顿回路哈密顿回路的定义： G=(V,E)是一个图，若G中一条路径通过且仅通过每一个顶点一次，称这条路径为哈密顿路径。若G中一个回路通过且仅通过每一个顶点一次，称

野性酷女/ 2022年11月18日 04:48/ 0 赞/ 155 阅读

相关算法 - 回文相关

文章目录 1.判断是否回文 2.最长回文子串 3.分割回文串 4.最短回文串 Manacher 算法 O（n） KMP算法 1.判

快来打我*/ 2022年11月12日 13:54/ 0 赞/ 112 阅读

相关算法训练之回溯法

什么是回溯法题目1 已知完成一个简单的工作需要1天，中等难度，需要2天，困难需要4天，如果未来有n个工作日，请返回所以可能的任务排列数。如输入：3 输出

痛定思痛。/ 2022年09月12日 10:46/ 0 赞/ 196 阅读

相关回溯算法（试探法）

算法思路基本思想：为了求得问题的解，先选择某一种可能情况进行试探，在试探过程中，一旦发现原来选择的假设情况是错误的，就退回一步重新选择，继续向另一个方向试

骑猪看日落/ 2022年09月06日 15:27/ 0 赞/ 225 阅读