Compare Version Numbers

Problem:
 Compare two version numbers version1 and version2.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

Solution:
/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class Solution {
public:
    int maxPoints(vector<Point> &points) {
        int max_count = 0;
        int size = points.size();
        
        if (size < 3)
            return size;
        
        for (int i = 0; i < size; i++) {
            for (int j = i + 1; j < size; j++) {
                int slope;
                bool slope_inf = false;
                if (points[j].x - points[i].x != 0)
                    slope = (points[j].y - points[i].y)/(points[j].x - points[i].x);
                else {
                    slope_inf = true;
                }
                int count = 0;
                for (int k = 0; k < size; k++) {
                    int temp_slope;
                    bool temp_slope_inf = false;
                    if (points[k].x - points[i].x != 0)
                        temp_slope = (points[k].y - points[i].y)/(points[k].x - points[i].x);
                    else {
                        temp_slope_inf = true;
                    }
                    if (same(points[k], points[i]) ||
                        (temp_slope == slope) ||
                        ((temp_slope_inf == true) && (slope_inf == true)) ) {
                        count++;
                    }
                }
                max_count = max(max_count, count);
                count = 0;
            }
        }
        return max_count;
    }
    
    bool same(Point i, Point j) {
        if ((i.x == j.x) && (i.y == j.y))
            return true;
        return false;
    }
};



================= Real easy one ===============

int compareVersion(string version1, string version2) {

  for (int i = 0, j = 0; i < version1.size() || j < version2.size(); ++i, ++j) {

    int num1 = 0, num2 = 0;

 

    while (version1[i] != '.' && i < version1.size())

      num1 = num1 * 10 + (version1[i++] - '0');

 

    while (version2[j] != '.' && j < version2.size())

      num2 = num2 * 10 + (version2[j++] - '0');

 

    if (num1 > num2)

      return 1;

    

    if (num1 < num2)

      return -1;

  }

 

  return 0;

}

Excel Sheet Column Title

Problem:

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 

Solution:
class Solution {
public:
     // Solution 1:
    /*string convertToTitle(int n) {
        string sol;
        int factor = 26;
        while (n > 0) {
            if (n%factor == 0) {
                sol += 'Z';
                n = (n/factor) - 1; 
            } else {
                sol += 'A' + (n%factor) - 1;
                n = n/factor;
            }
        }
        reverse(sol.begin(), sol.end());
        return sol;
    }

    // Solution 2: Without string reverse.
    string convertToTitle(int n) {
        string sol;
        int factor = 26;
        while (n > 0) {
            if (n%factor == 0) {
                sol.insert(0, 1, 'Z');
                n = (n/factor) - 1; 
            } else {
                sol.insert(0, 1, 'A' + (n%factor) - 1);
                n = n/factor;
            }
        }
        return sol;
    }*/

    //Solution 3: Make string from char and insert.
    string convertToTitle(int n) {
        string ans;
        do {
            n--;
            char c = 'A' + (char)(n % 26);
            ans = string(1, c) + ans;
            n/=26;
        } while(n);
        
        return ans;
    }
};

===== Another attempt ====
string convertToTitle(int n) {
        string ans;
        while (n > 0) {
            char to_append;
            if (n % 26 == 0) {
                to_append = 'Z';
                n = (n / 26) - 1;
            } else {
                to_append = (n % 26) + 'A' - 1;
                n = n / 26;
            }
            ans = string(1, to_append) + ans;
        }
        return ans;
    }

Excel Sheet Column Number

Problem:

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 

Solution:
class Solution {
public:
    int titleToNumber(string s) {
        int size = s.size();
        int sol = 0, factor = 1;
        for (int i = size -1; i >= 0; i--) {
            sol += (s[i] - 'A' + 1)*factor;
            factor *= 26;
        }
        return sol;
    }
};

Factorial Trailing Zeroes

Problem:

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

Solution:
class Solution {
public:
    int trailingZeroes(int n) {
        long int result = 0;
        long int k = 5;
        while (n/k != 0) {
            result += n/k;
            k *= 5;
        }
        return result;
    }
};

House Robber

Problem:

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Solution:

Recursive:
class Solution {
public:
    int rob(vector<int> &num) {
        int size = num.size();
        
        if (size == 0)
            return 0;
        else if (size == 1)
            return num[0];
        else if (size == 2)
            return max(num[0], num[1]);
        else if (size == 3)
            return max(num[0] + num[2], num[1]);
        else {
            vector<int> temp1 = num;
            vector<int> temp2 = num;
            
            temp1.erase(temp1.begin(), temp1.begin() + 2);
            temp2.erase(temp2.begin(), temp2.begin() + 3);
            
            return max(num[0] + rob(temp1), num[1] + rob(temp2));
        }
    }
};

Optimal one:
class Solution {
public:
    int rob(vector<int> &num) {
       vector<int> result;
       int size = num.size();
       if (size == 0)
            return 0;
        result.push_back(num[0]);
        if (size > 1)
            result.push_back(max(num[0], num[1]));
        
        for (int i = 2; i < size; i++) {
            int temp = num[i] + result[i - 2];
            result.push_back(max(result[i-1], temp));
        }
        return result[result.size() - 1];
    }
};

===== No extra space =====

class Solution {
public:
    int rob(vector<int>& nums) {
        int size = nums.size();
        if (size == 0) {
            return 0;
        } else if (size == 1) {
            return nums[0];
        } else {
            for (int i = 1; i < size; i++) {
                if (i == 1) {
                    nums[1] = max(nums[0], nums[1]);
                } else {
                    nums[i] = max(nums[i - 2] + nums[i], nums[i - 1]);
                }
            }
        }
        return nums[size - 1];
    }
};

Rotate Array

Prob:

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Sol:
class Solution {
public:
    void rotate(int nums[], int n, int k) {
        int rotate_by = k % n;
        reverse(nums, 0, n);
        reverse(nums, 0, rotate_by);
        reverse(nums, rotate_by, n);
    }
    void reverse(int nums[], int start, int end) {
        while (start < end) {
            swap(&nums[start++], &nums[--end]);
        }
    }
    void swap(int *a, int *b) {
        int temp = *a;
        *a = *b;
        *b = temp;
    }
};

Reverse Bits

Prob:

Sol:
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t output = 0;
        for (int i = 0; i < 32; i++) {
            output <<= 1;
            output |= (n & 1);
            n >>= 1;
        }
        return output;
    }
};

Other solution:

unsigned int reverseBits(unsigned int num)

{

    unsigned int count = sizeof(num) * 8 - 1;

    unsigned int reverse_num = num;

     

    num >>= 1;

    while(num)

    {

       reverse_num <<= 1;      

       reverse_num |= num & 1;

       num >>= 1;

       count--;

    }

    reverse_num <<= count;

    return reverse_num;

}

Method 3 – Lookup Table:
We can reverse the bits of a number in O(1) if we know the size of the number. We can implement it using look up table.




Method 4:

class Solution { public: uint32_t reverseBits(uint32_t n) { n = (n & 0xffff0000) >> 16 | (n & 0x0000ffff) << 16; n = (n & 0xff00ff00) >> 8 | (n & 0x00ff00ff) << 8; n = (n & 0xf0f0f0f0) >> 4 | (n & 0x0f0f0f0f) << 4; n = (n & 0xcccccccc) >> 2 | (n & 0x33333333) << 2; n = (n & 0xaaaaaaaa) >> 1 | (n & 0x55555555) << 1; return n; } };