Ugly Numbers

来源：cc150, fgdsb

原帖：http://www.hawstein.com/posts/ctci-ch10-math.html
            http://www.fgdsb.com/2015/01/03/ugly-numbers/

题目：
Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
shows the first 11 ugly numbers. By convention, 1 is included.

Write a program to find and print the 150’th ugly number.

cc150上也有相类似的题目，不过prime factors是3,5,7。

代码：

 int uglyNumber(int n) {  
   vector<int> num(n+1);  
   num[0] = 1;  
   int i3 = 0, i5 = 0, i7 = 0;  
   for (int i = 1; i <= n; ++i) {  
     int next = min({num[i3]*3, num[i5]*5, num[i7]*7});  
     num[i] = next;  
     if (next == num[i3]*3) i3++;  
     else if (next == num[i5]*5) i5++;  
     else i7++;  
   }  
   return num[n];  
 }  
   
 int main() {  
   vector<int> ugly = {1,3,5,7,9,15,21,25,27,35,45,49,63};  
   int k = 5;  
   cout << uglyNumber(k) << endl;  
   return 0;  
 }  

Next Permutation

来源：Leetcode

原帖：http://oj.leetcode.com/problems/next-permutation/

题目：
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place, do not allocate extra memory. Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
 1,2,3 -> 1,3,2
 3,2,1 -> 1,2,3
 1,1,5 -> 1,5,1
Solution: O(n)
Processes: Take A = {1,3,2} as an example:
1. Traverse from back to forth, find the turning point, that is A[i] = 3.
2. Sort from the turning point to the end (A[i] to A[end]), so {3,2} becomes {2,3}.
            3. If i equals to 0, finish! Else, goto 4.
            4. Let j = i, search from A[j] to A[end] to find the first elem which is larger than A[i-1], '2' here.
            5. Swap the elem A[j] with A[i-1].
            Finally, the next permutation is {2,1,3}.

代码：

 class Solution {  
 public:  
   void nextPermutation(vector<int> &num) {  
     int i = num.size() - 1;  
     while (i > 0 && num[i] <= num[i - 1]) i--;        
     sort(num.begin() + i, num.end());  
     if (i == 0) return;        
     int j = i;  
     while (j < num.size() && num[j] <= num[i - 1]) j++;        
     swap(num[j], num[i - 1]);  
   }  
 };  

Climbing Stairs

来源：Leetcode

原帖：http://oj.leetcode.com/problems/climbing-stairs/

题目：
You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Solution: Climd one step from last stair or climb 2 steps from the last last stair.
Fibnacacci number.

代码：

 class Solution {  
 public:  
   int climbStairs(int n) {  
     int last = 1;  
     int lastlast = 1;  
     for (int i = 2; i <= n; i++) {  
       int step = last + lastlast;  
       lastlast = last;  
       last = step;  
     }  
     return last;  
   }  
 };  
   
 // {{1,1}, {1,0}} ^ n = {{f(n), f(n-1)}, {f(n-1), f(n-2)}};  
 class Solution {  
 public:  
   void multiply(int a[2][2], int b[2][2]) {  
     int c[2][2] = {0};  
     for (int i = 0; i < 2; ++i) {  
       for (int j = 0; j < 2; ++j) {  
         for (int k = 0; k < 2; ++k) {  
           c[i][j] += a[i][k] * b[k][j];  
         }  
       }  
     }  
     for (int i = 0; i < 2; ++i) {  
       for (int j = 0; j < 2; ++j) {  
         a[i][j] = c[i][j];  
       }  
     }  
   
   }  
   
   void power(int a[2][2], int n) {  
     if (n <= 1) return;  
     int c[2][2] = {{1,1}, {1,0}};  
     power(a, n/2);  
     multiply(a,a);  
     if (n % 2 == 0) return;  
     multiply(a, c);  
   }  
   
   int climbStairs(int n) {  
     if (n == 1) return 1;  
     int matrix[2][2] = {{1, 1}, {1, 0}};  
     power(matrix, n);  
     return matrix[0][0];  
   }  
 };  
   

204 Count Primes

来源：Leetcode

原帖：https://leetcode.com/problems/count-primes/

题目：
Count the number of prime numbers less than a non-negative number, n

代码：

 class Solution {  
 public:  
   int countPrimes(int n) {  
     vector<bool> primes(n-1, true);  
     primes[0] = false;  
     int count = 0;  
     for (int i = 1; i < n-1; ++i) {  
       if (primes[i] == true) {  
         count++;  
         int num = (i+1)*2;  
         while (num < n) {  
           primes[num-1] = false;  
           num = num + i + 1;  
         }  
       }  
     }  
     return count;  
   }  
 };  

202 Happy Number

来源：Leetcode

原帖：https://leetcode.com/problems/happy-number/

题目：
Write an algorithm to determine if a number is "happy". A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

代码：

 class Solution {  
 public:  
   int nextNumber(int n) {  
     int res = 0;  
     while (n) {  
       int rem = n % 10;  
       res += rem * rem;  
       n /= 10;  
     }  
     return res;  
   }  
   bool isHappy(int n) {  
     if (n <= 0) return false;  
     unordered_set<int> set;  
     while (n != 1 && !set.count(n)) {  
       set.insert(n);  
       n = nextNumber(n);  
     }  
     return n == 1;  
   }  
 };  

Gray Code

来源：Leetcode

原帖：http://oj.leetcode.com/problems/gray-code/

题目：
The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0. For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
00 - 0  00 ^ 00
01 - 1  00 ^ 01
11 - 3  01 ^ 10
10 - 2  01 ^ 11
Note:
For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.
3位数情况
000
001
011
010
110
111 //如果按照题意的话，只是要求有一位不同，这里也可以是100
101
100

代码：

 //Iteration  
 class Solution {  
 public:  
   vector<int> grayCode(int n) {    
     vector<int> result;     
     result.push_back(0);   
     for (int i = 0; i < n; i++) {   
       int highestBit = 1 << i;   
       int len = result.size();   
       for (int i = len - 1; i >= 0; i--) {  // reverse  
         result.push_back(highestBit + result[i]); // highest bit  
       }    
     }   
     return result;   
   }  
 };  
   
 //Recursion  
 class Solution {  
 public:  
   vector<int> reverse(const vector<int> & r) {  
     vector<int> rev;  
     for (int i = r.size() - 1; i >= 0; --i) {  
       rev.push_back(r[i]);  
     }  
     return rev;  
   }  
     
   vector<int> grayCode(int n) {  
     vector<int> result;  
     if (n <= 1) {  
       for (int i = 0; i <= n; ++i)  
         result.push_back(i);  
       return result;  
     }  
     result = grayCode(n - 1);  
     vector<int> r1 = reverse(result);  
     for (int i = 0; i < r1.size(); ++i) {  
       int x = 1 << (n - 1);  
       r1[i] += x;  
     }  
   
     for (int i = 0; i < r1.size(); ++i) {  
       result.push_back(r1[i]);  
     }  
     return result;  
   }  
 };  
   

172 Factorial Trailing Zeroes

来源：Leetcode

原帖：https://leetcode.com/problems/factorial-trailing-zeroes/

题目：
Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.

代码：

 class Solution {  
 public:  
   int trailingZeroes(int n) {  
     if (n < 0) return 0;  
     int res = 0;  
     while (n) {  
       n /= 5;  
       res += n;  
     }  
     return res;  
   }  
 };  

Single Number II

来源：Leetcode

原帖：http://oj.leetcode.com/problems/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?
a xor a = 0
a xor 0 = a
0 xor a = a
a xor b = c => a xor c = b => b xor c => a
不进位加法
Solution: Count the number of each bit.

代码：

 class Solution {  
 public:  
   // 3n + 1问题，可以理解为3进制问题  
   int singleNumber(int A[], int n) {  
     int result = 0;  
     for (int i = 0; i < 32; ++i) {  
       int count = 0;  
       int bit = 1 << i;  
       for (int j = 0; j < n; ++j) {  
         if (A[j] & bit) {  
           count++;                    
         }  
       }  
       if (count % 3 != 0) { // count % 3 == 1  
         result |= bit;  
       }  
     }  
     return result;  
   }  
 };  

扩展：
// Given an array of integers, every element appears twice except for two. Find the two singles.

代码：

 vector<int> singleNumber(int A[], int n) {  
   vector<int> num(2, 0);  
   int twoNums = 0; // compute two numbers xor  
   for (int i = 1; i < n; ++i) {  
     twoNums ^= A[i];  
   }  
   int bit = 0; // find which bit is different from lowest bit  
   for (int i = 0; i < 32; ++i) {  
     bit = 1 << i;  
     if (twoNums & bit) break;  
   }  
   // find two integers  
   for (int i = 0; i < n; ++i) {  
     if (A[i] & bit) {  
       num[0] ^= A[i];  
     } else {  
       num[1] ^= A[i];  
     }  
   }  
   if (num[0] > num[1]) swap(num[0], num[1]);  
   return num;  
 }  

Single Number I

来源：Leetcode

原帖：http://oj.leetcode.com/problems/single-number/

题目：
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?

代码：

 class Solution {  
 public:  
   int singleNumber(int A[], int n) {  
       int result = 0;  
     for (int i = 0; i < n; ++i) {  
       result ^= A[i];          
     }  
     return result;  
   }  
 };  

Integer to Roman

来源：Leetcode

原帖：http://oj.leetcode.com/problems/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. Conversion range from high bit to low bit.

代码：
1]

 class Solution {  
 public:  
   const string rom[4][10] = {{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"},  
                 {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"},  
                 {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"},  
                 {"", "M", "MM", "MMM"}};  
   
   string intToRoman(int num) {  
     string res;  
     int i = 3;  
     while (num > 0) {  
       int divisor = (int)pow(10, i);  
       res += rom[i][num / divisor];  
       num %= divisor;  
       i--;  
     }  
     return res;  
   }  
 };  

2]

 class Solution {  
 public:  
   string intToRoman(int num) {  
     vector<int> value = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};  
     unordered_map<int, string> map = {{1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"},  
                     {100, "C"}, {90, "XC"}, {50, "L"}, {40, "XL"}, {10, "X"},  
                     {9, "IX"}, {5, "V"}, {4, "IV"}, {1, "I"}};  
     int i=0;  
     string res;  
     while (num) {  
       if (num >= value[i]) {  
         num -= value[i];  
         res += map[value[i]];  
       } else {  
         i++;  
       }  
     }  
     return res;  
   }  
 };  

Roman to Integer

来源：Leetcode

原帖：http://oj.leetcode.com/problems/roman-to-integer/

题目：
Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

代码：

 class Solution {  
 public:  
   int romanToInt(string s) {  
     unordered_map<char, int> roman = {{'M', 1000}, {'D', 500}, {'C', 100},   
                     {'L', 50}, {'X', 10}, {'V', 5}, {'I', 1}};  
     int res = 0, N = s.size();  
     for (int i = 0; i < N; ++i) {  
       if (i < N - 1 && roman[s[i]] < roman[s[i + 1]]) {  
         res -= roman[s[i]];  
       } else {  
         res += roman[s[i]];  
       }  
     }     
     return res;  
   }  
 };  

Multiply Strings

来源：Leetcode

原帖：https://oj.leetcode.com/problems/multiply-strings/

题目：
Given two numbers represented as strings, return multiplication of the numbers as a string. Note: The numbers can be arbitrarily large and are non-negative.
Solution: Just like what we do when multiplying integers.

代码：

 class Solution {  
 public:  
   string multiply(string num1, string num2) {  
     int N = num1.size(), M = num2.size();  
     string res(N + M, '0');  
     for (int i = N - 1; i >= 0; --i) {  
       int carry = 0;  
       for (int j = M - 1; j >= 0; --j) {  
         int sum = carry + (res[i + j + 1] - '0') +   
              (num1[i] - '0') * (num2[j] - '0');  
         res[i + j + 1] = sum % 10 + '0';  
         carry = sum / 10;  
       }  
       res[i] += carry; // add carry ; 不要忘记进位  
     }  
     while (res.size() > 1 && res[0] == '0') { // remove extra '0'  
       res.erase(res.begin());  
     }  
     return res;  
   }  
 };  

Reverse Integer

来源：Leetcode

原帖：http://oj.leetcode.com/problems/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.
例-8%3=-2; -8%-3=-2; 8%-3=2
负数求余主要看的是被除数，与除数无关。
如果被除数是负数那么其结果一定为负。如果被除数和除数都为负则结果还是为负。
如果被除数为正，除数为负，结果为正。

代码：
1] 考虑INT_MAX

 class Solution {  
 public:  
   int reverse(int x) {  
       if (x == 0) return 0;  
       if (x > 0) return -reverse(-x);  
     int res = 0;  
     while (x) {  
         if (res < INT_MIN / 10 || res == INT_MIN / 10 && x % 10 < INT_MIN % 10) {  
             //throw invalid_argument("reverse integer overflows");  
             return 0;  
         }  
       res = res * 10 + (x % 10);  
       x /= 10;  
     }  
     return res;  
   }  
 };  

2] 考虑long long

 class Solution {  
 public:  
   int reverse(int x) {  
     long long res = 0; // long long  
     while (x) {  
       res = res * 10 + x % 10;  
       x /= 10;  
     }  
     assert( res >= INT_MIN && res <= INT_MAX); // overflow and assert usage.  
     return res;  
   }  
 };  
   

Palindrome Number

来源：Leetcode

原帖：http://oj.leetcode.com/problems/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).
Take 12321 as an example.
[1] x = 1, y = 12321;
[2] x = 12, y = 1232;
[3] x = 123, y = 123;
[4] x = 1232, y = 12;
[5] x = 12321, y = 1; done!

代码：
1] 对称寻找

 class Solution {  
 public:    
   bool isPalindrome(int x) {  
     if (x < 0) return false;  
     int d = 1;  
     while (x / d >= 10) d *= 10;  
     while (d > 1) {  
       if (x % 10 != x / d) return false;          
       x = x % d / 10;  
       d /= 100;  
     }  
     return true;  
   }  
 };  

2] Reverse integer

 class Solution {  
 public:  
   bool isPalindrome(int x) {  
     if (x < 0) return false;  
     return x == reverse(x);  
   }  
   
   int reverse(int x) {  
     int rev = 0;  
     while (x) {  
       rev = rev * 10 + x % 10; //! consider overflow here  
       x /= 10;  
     }  
     return rev;  
   }  
 };  

3] Recursion

 class Solution {  
 public:  
   bool isPalindrome(int x) {  
     return isPalindromeHelper(x, x);  
   }  
     
   bool isPalindromeHelper(int x, int &y) {  
     if (x < 0) return false;  
     if (x == 0) return true;  
     if (isPalindromeHelper(x / 10, y) && x % 10 == y % 10) {  
       y /= 10;  
       return true;  
     }  
     return false;  
   }  
 };  

Plus One

来源：Leetcode

原帖：http://oj.leetcode.com/problems/plus-one/

题目：
Given a number represented as an array of digits, plus one to the number. The digits are stored such that the most significant digit is at the head of the list.

代码：

 class Solution {  
 public:  
   vector<int> plusOne(vector<int> &digits) {  
     int carry = 1;  
     int N = digits.size();  
     for (int i = N - 1; i >= 0 && carry; --i) {  
       int sum = carry + digits[i];  
       carry = sum / 10;  
       digits[i] = sum % 10;  
     }  
     if (carry == 1) { // insert 'carry = 1'  
       digits.insert(digits.begin(), 1);         
     }  
     return digits;  
   }  
 };  

Add Without Add Operator

来源：cc150

原帖：http://www.hawstein.com/posts/20.1.html

题目：
Implement add without add operator ('+'). Bit operation.

代码：

 int add(int a, int b) {  
   do {  
     int n1 = a ^ b;  
     int n2 = (a & b) << 1;  
     a = n1;   
     b = n2;  
   } while (b != 0);  
   return a;  
 }  

Pow(x,n)

来源：Leetcode

原帖：http://oj.leetcode.com/problems/powx-n/

题目：
Implement pow(x, n).

代码：

 class Solution {  
 public:  
   double epsilon = 1e-6;  
   bool equals(double x, double y) {  
     return abs(x - y) < epsilon;   
   }  
   
   double pow(double x, int n) {  
     if (x < 0) return (n % 2 == 0) ? pow(-x, n) : -pow(-x, n);  
     if (equals(x, 0.0) || equals(x, 1.0)) return x;  
     if (n < 0) return 1.0 / pow(x, -n);  
     if (n == 0) return 1.0;  
     double half = pow(x, n / 2);  
     if (n % 2 == 0) {  
         return half * half;  
     } else {  
         return x * half * half;  
     }  
   }  
 };  

Add Binary

来源：Leetcode

原帖：http://oj.leetcode.com/problems/add-binary/

题目：
Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".

代码：

 class Solution {  
 public:  
   string addBinary(string a, string b) {  
     int N = a.size(), M = b.size(), K = max(N, M);  
     string res(K, ' ');  
     int carry = 0;  
     int i = N - 1, j = M - 1, k = K - 1;  
     while (i >= 0 || j >= 0) {  
       int sum = carry;  
       if (i >= 0) sum += a[i--] - '0';  
       if (j >= 0) sum += b[j--] - '0';  
       carry = sum / 2;  
       res[k--] = sum % 2 + '0';  
     }  
     if (carry == 1) {  
       res.insert(res.begin(), '1');  
     }  
     return res;  
   }  
 };  

Sqrt(x)

来源：Leetcode

原帖：http://oj.leetcode.com/problems/sqrtx/

题目：
Implement int sqrt(int x). Compute and return the square root of x.

思路：
这道题用binary search搞定。需要注意的是函数签名，在面试中遇到过两种。int sqrt(int); double sqrt(double). 如果输入是int，在进行binary search的时候可能会遇到overflow。 输入是double，需要考虑<1, >1的情况，另外需要考虑double精度问题。

代码：
1] int type input

 class Solution {  
 public:  
     int sqrt(int x) {  
         assert(x >= 0);  
         int l = 0, r = x / 2 + 1;  
         while (l + 1 < r) {  
             // long long mid = l + (r - l) / 2; // overflow problem.   
             // long long sq = mid * mid;  
             // if (sq == x) {  
             //   return mid;  
             // } else if (sq < x) {  
             //   l = mid;  
             // } else {  
             //   r = mid;  
             // }  
   
             int mid = l + (r - l) / 2;  
             int quot = x / mid;  
             if (quot == mid) {  
                 return quot;  
             } else if (quot > mid) {  
                 l = mid;  
             } else {  
                 r = mid;  
             }  
         }  
         if (r * r == x) return r;  
         return l;  
     }  
 };  

2] input is double

 class Solution {  
 public:  
     const double eps = 1.0e-12;  
     // 0 means equal, -1 means smaller, +1 means larger  
     int compare(double a, double b) {  
         if (a == 0) a += eps;  
         if (b == 0) b += eps;  
         double diff = (a - b) / b;  
         return diff > eps ? 1 : diff < -eps ? -1 : 0;  
     };  
   
     double square_root(double x) {  
         // Decide the search range according to x  
         double l, r;  
         if (compare(x, 1.0) < 0) { // x < 1.0  
             l = x; r = 1.0;  
         } else { // x >= 1.0  
             l = 1.0; r = x;  
         }  
         // Keep searching if l < r  
         while (compare(l, r) < 0) {  
             double m = l + 0.5 * (r - l);  
             double square_m = m * m;  
             if (compare(square_m, x) == 0) {  
                 return m;  
             } else if (compare(square_m, x) < 0) {  
                 l = m;  
             } else {  
                 r = m;  
             }  
         }  
         return l;  
     }  
 };