1. Reverse Integer
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).
Solution: Use % and / iteratively.
1 class Solution { 2 public: 3 int reverse(int x) { 4 long long res = 0; 5 while (x) { 6 res = res * 10 + (x % 10); 7 x /= 10; 8 } 9 assert(res <= INT_MAX && res >= INT_MIN); 10 return res; 11 } 12 };
2. Palindrome Number
Determine whether an integer is a palindrome. Do this without extra
space.
Some hints:
Could negative integers be palindromes? (ie, -1)
(No!)
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.
Solution: 1. Count the number of digits first (traverse once) then check the
digits from both sides to center.
2. Reverse the number, then
check to see if x == reverse(x).
3. Recursion (interesting but a
little hard to understand).
1 class Solution { 2 public: 3 bool isPalindrome(int x) { 4 if(x < 0) return false; 5 int d = 1; 6 while(x / d >= 10) d *= 10; 7 while(d > 1) { 8 if(x % 10 != x / d) return false; 9 x = x % d / 10; 10 d /= 100; 11 } 12 return true; 13 } 14 };
3. Single Number I
Given an array of integers, every element appears twice except for one.
Find that single one.
Your algorithm should have a linear runtime
complexity.
Could you implement it without using extra memory?
Solution: XOR.
1 class Solution { 2 public: 3 int singleNumber(int A[], int n) { 4 int single = 0; 5 for(int i = 0; i < n; i++) { 6 single ^= A[i]; 7 } 8 return single; 9 } 10 };
4. Single Number II
Given an array of integers, every element appears three times except for one.
Find that single one.
Your algorithm should have a linear runtime
complexity. Could you implement it
without using extra memory?
Solution: Count the number of each bit.
1 class Solution { 2 public: 3 // assume that integers are 32bits 4 int singleNumber(int A[], int n) { 5 int res = 0; 6 for(int i = 0; i < 32; i++) { 7 int count = 0; 8 int bit = 1 << i; 9 for(int j = 0; j < n; j++) { 10 if(A[j] & bit) { 11 count++; 12 } 13 } 14 if(count % 3) { 15 res = res | bit; 16 } 17 } 18 return res; 19 } 20 };
5. Divide Two Integers
Divide two integers without using multiplication, division and mod operator.
1 class Solution { 2 public: 3 int divide(int dividend, int divisor) { 4 assert(divisor != 0); 5 int res = 0; 6 bool flag = (dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0); 7 long long dividend1 = abs((long long)dividend); 8 long long divisor1 = abs((long long)divisor); 9 while(divisor1 <= dividend1) { 10 long long div = divisor1; 11 int quote = 1; 12 while((div << 1) <= dividend1) { 13 div <<= 1; 14 quote <<= 1; 15 } 16 dividend1 -= div; 17 res += quote; 18 } 19 return flag ? res : -res; 20 } 21 };
6. Integer to Roman
Given an integer, convert it to a roman numeral.
Input is guaranteed to
be within the range from 1 to 3999.
Solution: Buffer the roman numbers.
1 class Solution { 2 public: 3 string rome[4][10] = {{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}, 4 {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"}, 5 {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"}, 6 {"", "M", "MM", "MMM"}}; 7 string intToRoman(int num) { 8 string res; 9 int i = 3; 10 while(num > 0) { 11 int div = (int)pow(10,i); 12 res += rome[i][num/div]; 13 i--; 14 num %= div; 15 } 16 return res; 17 } 18 };
7. Roman to Integer
iven a roman numeral, convert it to an integer.
Input is guaranteed to be
within the range from 1 to 3999.
Solution: use <map> or <unordered_map> (clean)
1 class Solution { 2 public: 3 int romanToInt(string s) { 4 unordered_map<char,int> map; 5 map[‘M‘] = 1000; 6 map[‘D‘] = 500; 7 map[‘C‘] = 100; 8 map[‘L‘] = 50; 9 map[‘X‘] = 10; 10 map[‘V‘] = 5; 11 map[‘I‘] = 1; 12 13 int res = 0; 14 for(int i = 0; i < s.size(); i++) { 15 if(i != s.size()-1 && map[s[i]] < map[s[i+1]]) 16 res -= map[s[i]]; 17 else res += map[s[i]]; 18 } 19 return res; 20 } 21 };
8. Pow(x, n)
Implement pow(x, n).
Solution: recursion.
1 class Solution { 2 public: 3 double pow(double x, int n) { 4 if(x < 0) return n % 2 == 0 ? pow(-x, n) : -pow(-x, n); 5 if(x == 0 || x == 1) return x; 6 if(n == 0) return 1.0; 7 if(n < 0) return 1.0/pow(x, -n); 8 9 double half = pow(x, n/2); 10 if(n % 2 == 0) return half * half; 11 else return x * half * half; 12 } 13 };
Leetcode个人总结12 数字和数学题(8),布布扣,bubuko.com
原文：http://www.cnblogs.com/zhengjiankang/p/3631694.html