当前位置: 首页 > article >正文

有趣的算法实践:整数反转与回文检测(Java实现)

题目描述:整数反转与回文检测

要求实现两个功能

  1. 将输入的整数反转(保留符号,如输入-123返回-321
  2. 判断反转后的数是否为回文数(正反读相同)

示例

输入:123 → 反转结果:321 → 非回文数
输入:-121 → 反转结果:-121 → 是回文数

一、算法实现与解析

方法1:字符串操作法(直观解法)

public class NumberUtils {
    // 整数反转
    public static int reverseByString(int x) {
        String str = Integer.toString(x);
        String reversed = new StringBuilder(str).reverse().toString();
        try {
            return x < 0 ? -Integer.parseInt(reversed.substring(0, reversed.length()-1)) 
                         : Integer.parseInt(reversed);
        } catch (NumberFormatException e) {
            return 0; // 处理溢出情况
        }
    }

    // 回文检测
    public static boolean isPalindromeString(int x) {
        return x == reverseByString(x);
    }
}

特点分析

  • 时间复杂度:O(n),n为数字位数
  • 空间复杂度:O(n),字符串存储额外空间
  • 优点:代码简洁,易于理解
  • 缺点:大数处理可能溢出(需异常捕获)

方法2:数学运算法(高效解法)

public class NumberUtils {
    // 整数反转(数学法)
    public static int reverseByMath(int x) {
        int reversed = 0;
        while (x != 0) {
            int digit = x % 10;
            // 溢出预判
            if (reversed > Integer.MAX_VALUE/10 || 
               (reversed == Integer.MAX_VALUE/10 && digit > 7)) return 0;
            if (reversed < Integer.MIN_VALUE/10 || 
               (reversed == Integer.MIN_VALUE/10 && digit < -8)) return 0;
            reversed = reversed * 10 + digit;
            x /= 10;
        }
        return reversed;
    }

    // 回文检测(无额外空间)
    public static boolean isPalindromeMath(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) return false;
        int reverted = 0;
        while (x > reverted) {
            reverted = reverted * 10 + x % 10;
            x /= 10;
        }
        return x == reverted || x == reverted / 10;
    }
}

核心优势

  • 时间复杂度:O(log₁₀n),每次循环减少一位
  • 空间复杂度:O(1),无需额外存储结构
  • 创新点:通过数学运算实现反转,避免字符串转换的性能损耗

二、性能对比与工程实践建议

方法执行时间(n=123454321)内存消耗适用场景
字符串法0.02ms2KB快速开发/小数据量
数学法0.005ms0.1KB高并发/大数据量

调优建议

  1. 输入校验:处理非数字字符及边界值(如Integer.MIN_VALUE)
  2. 防御式编程:添加溢出检测逻辑(如方法2中的预判)
  3. 单元测试:覆盖正负数、零、回文数与非回文数等场景
  4. 日志监控:记录反转过程中的异常状态

三、举一反三:算法变形练习

  1. 扩展题1:反转字符串中的数字片段(保留其他字符位置)
    输入:"a12b34c" → 输出:"a43b21c"
  2. 扩展题2:找出1-10000之间的所有回文素数
  3. 挑战题:实现支持大数反转的算法(使用BigInteger)

技术彩蛋:回文数检测算法在验证码生成、数据库主键校验等场景有广泛应用。尝试用位运算实现更高效的反转算法(提示:32位整数的二进制反转)!


http://www.kler.cn/a/589621.html

相关文章:

  • java学习总结(六)Spring IOC
  • 基于k3s部署Nginx、MySQL、Golang和Redis的详细教程
  • 一键爬取b站视频
  • lua C语言api学习2 在C语言中使用lua语言
  • 3月17日作业
  • QT中的宏
  • JAVA | 聚焦 String 的常见用法与底层内存原理
  • 无人机吊舱模块更换技术难点分析!
  • UFS Link Startup 介绍
  • 怎么在centos7中搭建一个mqtt服务
  • 设计模式(行为型)-状态模式
  • 【CVPR 2025】局部区域自注意力LASA,用重叠补丁增强区域特征交互,即插即用!
  • 【Mac 从 0 到 1 保姆级配置教程 08】08. 快速配置 Neovim、LazyVim 以及常用开发环境,如果之前有人这么写就好了
  • 【JavaEE】Spring Boot 日志
  • Qt:槽函数与信号
  • 下载 CSS 文件阻塞,会阻塞构建 DOM 树吗?会阻塞页面的显示吗?
  • python项目一键加密,极度简洁
  • 使用Appium的W3C Actions实现多指触控行为
  • C++ STL 之常用拷贝和替换算法①copy();②replace();③replace_if();④swap();
  • C++ STL map