Tuesday, May 28, 2013

Reverse a integer @ Leetcode

刷题必备书籍Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历:The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍:Introduction to Algorithms
编程珠玑:Programming Pearls (2nd Edition)
C++ 学习:The C++ Programming Language, 4th Edition
经典操作系统书籍,龙书:Operating System Concepts
创业:The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career
Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321
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).

In the very first, I thought to convert the integer to string, then the problem transferred to reverse the string which is familiar to most people. However, we need to consider the problem that, the integer may be ended with 0. In this case, we need to filter the 0 and only keep the digits greater than 0. BUT!!! we have to keep in mind is, a string is a const variable which can not be modified once it is given a value. So if we want to use the string, we may need to copy the digits->chars to a new string which makes problem much more tedious and complicate. Why not change our mind to another way? Yes! We can make problem simple by only adding the digits one by one through end to begin. That's it! Oh, keep in mind there may be overflow after the reverse. If in this place, just return -1.


That's my code. At the first, I set a bool variable to see whether x is positive or not. Actually it's not necessary.

Some basic knowledge I have learnt from this problem:

Convert a integer to a string, we can use
char * itoa(int x, char * str, int base) while this is not a function in library, so it's not wise to use it. We may also use
 std:: stringstream ss;
 ss << number;
 string result = ss.str();

There is a std:: to_string() in c++11 that we can use directly. 

7 comments:

  1. But how to handle the overflow? Can you enlighten me a bit? Thanks!

    ReplyDelete
  2. Why judging x is positive or negative is not necessary? In your code, if x < 0, then the loop does not execute, and it returns y = 0.

    ReplyDelete
  3. Condition should be while (x != 0).
    About the overflow, if we do not judge if the number is positive or not. We should record the original x.

    if ((originalX >0 && y<0) || (originalX< 0 && y>0)) {
    // overflow
    }

    ReplyDelete
  4. 有个问题想请教,就是如果我使用string来做,如何判断溢出?谢谢啦~

    ReplyDelete

Leetcode 316. Remove Duplicate Letters

 这道题表面问的是如何删除重复,实际在问如何从多个字符选取一个保留,从而让整个字符串按升序排列。那么策略就是对于高顺位的字符比如‘a',就要选靠前位置的保留,而低顺位字符如’z'则应该尽量选取靠后位置保留。 算法大概思路:每看到一个字符,我们要决定是否保留 1. ...