前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >BAT面试算法进阶(7)- 反转整数

BAT面试算法进阶(7)- 反转整数

作者头像
iOSSir
发布2023-03-19 12:00:08
2050
发布2023-03-19 12:00:08
举报

题目

给定一个 32 位有符号整数,将整数中的数字进行反转。

  • 例如:

输入: 123 输出: 321

输入: 120 输出: 21

输入: -123 输出: -321

  • 注意

假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−2^31, 2^31 − 1]。根据这个假设,如果反转后的整数溢出,则返回 0。

解决方案

  • 方法:弹出和推入数字 & 溢出前进行检查
  • 思路: 我们可以一次构建反转整数的一位数字。在这样做的时候,我们可以预先检查向原整数附加另一位数字是否会导致溢出。
  • 算法 反转整数可以和反转字符串一起类比实现. 在没有辅助的堆栈/数组的帮助下,"弹出"和"推入"数字,可以尝试有用数学的方式.

但是,当因为当 temp = rev*10+pop时,有可能会造成溢出.

  • 解决溢出
  • 假设rev,为正数
  • 如果temp = rev*10+pop,导致溢出.那么一定rev >= INTMAX/10;
  • 如果rev > INTMAX / 10;那么temp = rev*10+pop 一定会溢出
  • 如果rev == INTMAX / 10,那么只要pop > 7 ,temp = rev*10+pop 就会溢出
  • 代码实现 C++ Code
  • 复杂度
  • 时间复杂度:O(log(x))
  • 空间复杂度:O(1)

算法面试系列文章:

BAT面试算法进阶(1)--两数之和 BAT面试算法进阶(2)- 无重复字符的最长子串(暴力法) BAT面试算法进阶(3)- 无重复字符的最长子串(滑动窗口法) BAT面试算法进阶(4)- 无重复字符的最长子串(滑动法优化+ASCII码法) BAT面试算法进阶(5)- BAT面试算法进阶(5)- 最长回文子串(方法一) BAT面试算法进阶(6)- BAT面试算法进阶(6)-最长回文子串(方法二) BAT面试算法进阶(8)- 删除排序数组中的重复项 BAT面试算法进阶(9)- 三维形体投影面积 BAT面试算法进阶(10)- 最长的斐波那契子序列的长度(暴力法) BAT面试算法进阶(11)- 最长的斐波那契子序列的长度(动态规划法) BAT面试算法进阶(12)- 环形链表(哈希表法)

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-02-23,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Python课后小剧场 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目
  • 解决方案
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档