1. Reverse Integer
Reverse digits of an integer.
Example1:x = 123, return 321
Example2:x = -123, return -321
click to show spoilers.
Have you thought about this?
Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!
If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.
Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?
Throw an exception? Good, but what if throwing an exception is not an option? You would then have to re-design the function (ie, add an extra parameter).
int reverse(int x) {
int result = 0;
while (x)
{
result = result*10 + x%10;
x /= 10;
}
return result;
}
12.9update:之前想复杂了,不应该那样处理,更新一下,使用long long就好了,如下程序:
考虑:
1 溢出
2 + -
3 1000, 10等尾部为零的情况
答案:
1 long long 处理了
2 无需要处理
3 无需要处理
int reverse(int x)
{
long long res = 0;
while (x)
{
res = res*10 + x%10;
x /= 10;
}
if (res >= INT_MAX) return INT_MAX;
if (res <= INT_MIN) return INT_MIN;
return res;
}
2 Palindrome Number
Determine whether an integer is a palindrome. Do this without extra space.
click to show spoilers.
Some hints:
Could negative integers be palindromes? (ie, -1)
If you are thinking of converting the integer to string, note the restriction of using extra space.
You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?
There is a more generic way of solving this problem.
去掉最高位额外处理可能溢出的情况,然后转置整数比较的程序:
class Solution {
public:
bool isPalindrome(int x) {
if(x<0) return false;
else if(x<10) return true;
int y = 0;
int a = x%10;
x /= 10;
while (x >= 10)
{
if(x%10 != 0)
y = 10*y + x%10;
x/=10;
}
if(a != x) return false;
x=y;
int z = 0;
while (y)
{
z = 10*z + y%10;
y/=10;
}
if(z != x) return false;
return true;
}
};
最高位和最小位分别比较的程序:
bool isPalindrome(int x) {
if (x < 0) return false;
int div = 1;
while (x / div >= 10) {
div *= 10;
}
while (x != 0) {
int l = x / div;
int r = x % 10;
if (l != r) return false;
x = (x % div) / 10;
div /= 100;
}
return true;
}
另辟蹊径递归程序:
bool isPalindrome(int x, int &y) {
if (x < 0) return false;
if (x == 0) return true;
if (isPalindrome(x/10, y) && (x%10 == y%10)) {
y /= 10;
return true;
} else {
return false;
}
}
bool isPalindrome(int x) {
return isPalindrome(x, x);
}
截开高位数和低位数的程序:
bool isPalindrome(int x) {
if(x < 0) return false;
int a = x, b = 0;
while(a > b) {
b = b * 10 + a % 10;
a /= 10;
}
if(a == 0) return (x == b);
return (a == b) || a == (b / 10);
}
部分程序出处:LeetCode论坛
//2014-1-24 update
class Solution124
{
public:
bool isPalindrome(int x)
{
int y = 0;
if (x<0) return false;
if (x<10) return true;
if (x%10 ==0 && x%10%10 == 0) return false;
while (x > y)
{
y = y*10 + x%10;
x /= 10;
}
if (x == y || x == y/10) return true;
return false;
}
};
bool isPalindrome(int x)
{
if (x<0) return false;//特殊情况1
if (x<10) return true;//特殊情况2
if (x%10 == 0) return false;//特殊情况3:尾数为零的肯定不是Palindrome
int y = 0;
while (x > y)
{
y = y*10 + x%10;
x /= 10;
}
return x == y || x == y/10;
}
分享到:
相关推荐
LeetCode Palindrome Number解决方案
Determine whether an integer is a palindrome. Do this without extra space. Java AC版本
LeetCode:LeetCode培训&&分享
目录目录计算机系学生为什么要刷算法PAT乙级和甲级是什么考PAT对学习 | 考研 | 工作的作用是什么刷PAT乙级和甲级需要掌握哪些知识关于PAT刷题中编程语言
Given a 32-bit signed integer, reverse digits of an integer. Java AC版本
leetcode 分类 LeetCode LeetCode上的算法题使用golang和c++实现 目录结构 c++ LeetCode [^使用说明]:使用vs2019打开此路径下的sln文件,LeetCode.cpp中main函数用于测试 go src [^分包说明]:按照不同类型的题目建包...
因此在之后的刷题过程中,刻意放慢了脚步,每做完一道题,都去主动思考这种算法的时空复杂度是多少,是否还有更优的解法,能否做到举一反三等。 章节的编排形式参考了leetcode的题型分类,例如二叉树,字符串以及...
leetcode下载 LeetCode-Python-Java zhouzhenping/LeetCode-Python&Java 参考代码来源 力扣(LeetCode) 链接: 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 Github 01 两数之和 给定一...
leetcode中文版 My LeetCode solutions with Chinese explanation. 我的LeetCode中文题解。 每个题目都保证击败超过80%的提交,并尽量给出多种解法并分析算法复杂度。 每日持续更新中,欢迎交流,欢迎star :D 另外,...
leetcode LeetCode Algorithm # Title Solution 146 , 283 11 70 , 1 , 15 , 141 206 24 142 26 189 21 88 20 155 84 239 42 641 50 , 78 , 169 , 51 , 102 , 433 , 242 , 49 , 94 , 144 , 589 , 590 , 429 , 20 , ...
第321题Reversed_Integer Java中的LeetCode逆整数问题解决方案 问题 - 给定一个有符号的 32 位整数 x,返回 x 其数字颠倒。 如果反转 x 导致值超出有符号的 32 位整数范围 [-231, 231 - 1],则返回 0。 假设环境不...
leetcode 2 leetcode 代码包含在文件中,以下链接为问答博客。 # Java C 困难 0001 简单的 0015 中等的 0018 中等的 0035 简单的 0049 中等的 0110 简单的 0149 难的 0172 简单的 0202 简单的 0204 简单的 0205 简单...
Leetcode\ReverseInteger\ReverseInteger.cs 问题: 业绩报告: 回文数 代码: Leetcode\PalindromeNumber\PalindromeNumber.cs 问题: 从排序数组中删除重复项 代码: Leetcode\RemoveDuplicates\RemoveDuplicates....
leetcode卡 leetcode leetcode 每日刷一题 (2019.04.01 ~ forever) 9 / 1553 :rocket: helper top-interview-questions problems
leetcode python 039 Programming-Practice tags: 目录 简介 这篇博客是我平时刷Leetcode,剑指offer题目和牛客网上的招聘题目等的代码、思路。代码和思路都保存在上,我对于每一道题都尽量做到c++和python都进行...
leetcode leetcode 的解决方案 本仓库是 603LZY 的 leetcode 解决方案合集。 最新更新于2018-10-22 22:06:22这里有875个问题的228个解决方案,还有139个被锁定。 完成统计: JavaScript:11 Python:214 C++:40 ...
9. Palindrome Number 11. Container With Most Water 13. Roman to Integer 15. 3Sum 16. 3Sum Closest 17. Letter Combinations of a Phone Number 18. 4Sum 19. Remove Nth Node From End of List 20. Valid ...
leetcode 分类 leetcode 练习 按照数据结构和算法分类对leetcode题型做出解答 主要使用C/C++语言 每道题给出算法思路,示例,分析时间、空间复杂度,争取做到最优解 暂时就想到这么多,以后再添加吧^_^
The solution of LeetCode in python&C++&java&JavaScript(leetcode题解,有python,C++,Java,JavaScript等解法)
Solutions collection of LeetCode submissions in JavaScript & TypeScript (LeetCode 解题集之 JavaScript & TypeScript 版).zip