LeetCode7~9 Reverse Integer/String to Integer (atoi)/Palindrome Number

一：Reverse Integer

题目：

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

分析：这题通过不断取余将余数存放在一个vector中，然后乘以相应的10^i次方相加即可，这里主要考虑是否overflow,因此将result设为long long int，当大于int的最大值0x7fffffff或者小于int的最小值0x800000000时，则返回0，否则返回result。

代码：

#define maxInt (int)0x7fffffff       // int中最大值==2147483647     unsigned int 最大值为4294967295
#define minInt (int)0x80000000      // int中最小值2147483648
class Solution {
public:
    int reverse(int x) {
        vector<int> v;
        while(x != 0){
            int a = x%10;
            v.push_back(a);
            x = x/10;
        }
        long long int result = 0;
        
        for(int i = 0; i < v.size(); i++){
            result += v[i]*pow(10.0,v.size()- i - 1);
        }
        if(result > maxInt || result < minInt) return 0;     // 通过long long int来解决溢出问题
        return result;
        
    }
};

题目：Implement atoi to convert a string to an integer.

链接：https://leetcode.com/problems/string-to-integer-atoi/

分析：这道题不难，关键是满足的测试样例比较变态，比如“     123456ab78”，也要返回123456等等

代码：

#define Max (int)0x7fffffff
#define Min (int)0x80000000
class Solution {
public:
    int atoi(string str) {
        if(str.size() <= 0) return 0;

        for(int i = 0; i < str.size(); i++){   // 去除前面的空格
            if(str[i] != ' '){
				str = str.substr(i);
				break;
			} 
        }  
		int c = 1;
		int len = str.size();
		if(isdigit(str[0])) {       // 如果第一个为数字 表示整型 则前面放一个+号 
            str = "+" + str;
            len = len +1;
        }
        if(str[0] == '+') c = 1;
        else if(str[0] == '-')c = -1;
        else return 0;

		for(int i = 1; i < len; i++){  //去除后面字母开头的所有字符
			if(!isdigit(str[i]) || i >= 12) {   //超过了12位的不要了 否则有可能会超过long long 的范围
				str = str.substr(0, i);
				break;
			}
		}
		len = str.size();
       
        
        long long int result = 0;;
        
        for(int i = 1; i < len; i++){
            if(!isdigit(str[i]))return 0;
            stringstream ss;
            int temp;
            ss << str[i];
            ss >> temp;
            result += temp * pow(10.0, len-i-1.0)*c;
        }
        if(result > Max) return Max;
		if(result < Min) return Min;
        return result;
    }
};

题目：

Determine whether an integer is a palindrome. Do this without extra space.

click to show spoilers.

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

分析：这题主要有几个限制：1不能用extra space,所以不能转换成string再求回文  2：先求reverse integer，那么溢出怎么办？ 所以这题是先求出int的位数，然后分别取出最低位和最高位进行比较。

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0) return false;
        int d = 0;
        int y = x;
        while(y != 0){    // 先将x的位数求出来
            y = y/10;
            d++;
        }
        while(x != 0){
            int lowBit = x % 10;   // 求出x的最低位
            int highBit = x / pow(10.0, d-1.0);   // 求出x的最高位
            if(lowBit != highBit) return false;
            x = (x - lowBit - highBit * pow(10.0, d-1.0))/10;
            d = d - 2;
        }
        return true;
        
        
    }
};

LeetCode7~9 Reverse Integer/String to Integer (atoi)/Palindrome Number

原文：http://blog.csdn.net/lu597203933/article/details/44887299