[LeetCode] First Bad Version

The question can be found https://leetcode.com/problems/first-bad-version/

Note: if we use m = (e+s)/2, it might cause overflow.

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
    
public:
    int firstBadVersion(int n) {
        int s = 1;
        while(s < n)
        {
            int m = s + (n-s)/2;
            if(isBadVersion(m)) n = m;
            else s = m+1;
        }
        return s;
    }
};

[LeetCode] Summary Ranges

Given a sorted integer array without duplicates, return the summary of its ranges.

For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].

Note: Overflow.

class Solution {
    string getRange(int start, int end)
    {
        if(start == end) return to_string(start);
        return to_string(start) + "->" + to_string(end);
    }
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> res;
        if(nums.empty()) return res;
        
        long start = nums[0];
        long end = start;
        
        for(int i=1;i<nums.size();i++)
        {
            if(nums[i] - end >1)
            {
                res.push_back(getRange(start, end));
                start = nums[i];
                end = start;
            }
            else
            {
                end = nums[i];
            }
        }
        res.push_back(getRange(start, end));
        return res;
    }
};

[LintCode] Hash Function

In data structure Hash, hash function is used to convert a string(or any other type) into an integer smaller than hash size and bigger or equal to zero. The objective of designing a hash function is to "hash" the key as unreasonable as possible. A good hash function can avoid collision as less as possible. A widely used hash function algorithm is using a magic number 33, consider any string as a 33 based big integer like follow:

hashcode("abcd") = (ascii(a) * 333 + ascii(b) * 332 + ascii(c) *33 + ascii(d)) % HASH_SIZE 

                              = (97* 333 + 98 * 332 + 99 * 33 +100) % HASH_SIZE

                              = 3595978 % HASH_SIZE

here HASH_SIZE is the capacity of the hash table (you can assume a hash table is like an array with index 0 ~ HASH_SIZE-1).

Given a string as a key and the size of hash table, return the hash value of this key.f

Example

For key="abcd" and size=100, return 78

Clarification

For this problem, you are not necessary to design your own hash algorithm or consider any collision issue, you just need to implement the algorithm as described.

class Solution {
public:
    /**
     * @param key: A String you should hash
     * @param HASH_SIZE: An integer
     * @return an integer
     */
    long fastPower(int a, int b, int n) {
        // write your code here
        if(1 == b) return 0;
        if(0 == n) return 1;
        long c = fastPower(a, b, n/2);
        if(n%2)
        {
            return (((c*c)%b)*(a%b))%b;   
        }
        return (c*c)%b;
    }
    
    int hashCode(string key,int HASH_SIZE) {
        // write your code here
        long res = 0;
        int len = key.length();
        for(int i=0;i<len;i++)
        {
            res += key[i]*fastPower(33, HASH_SIZE, len-i-1);
        }
        return res % HASH_SIZE;
    }
};

[LintCode] Fast Power

Calculate the an % b where a, b and n are all 32bit integers.

Example

For 231 % 3 = 2

For 1001000 % 1000 = 0

Challenge

O(logn)

Note the nature of MOD and overflow

class Solution {
public:
    /*
     * @param a, b, n: 32bit integers
     * @return: An integer
     */
    int fastPower(int a, int b, int n) {
        // write your code here
        if(1 == b) return 0;
        if(0 == n) return 1;
        long c = fastPower(a, b, n/2);
        if(n%2)
        {
            return (((c*c)%b)*(a%b))%b;   
        }
        return (c*c)%b;
    }
};

[LeetCode] Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

For the function int divide(int dividend, int divisor), overflow will have happen when
1) divisor is 0
2) dividend is -INT_MAX -1 and divisor is -1. for the range of 32 bit integer is from −(2³¹) to 2³¹ − 1

class Solution {
public:
    int divide(int dividend, int divisor) 
    {      
        if(0 == divisor) return INT_MAX;
        if(-1 == divisor && dividend == -INT_MAX - 1) return INT_MAX;
        long longDividend = abs((long)dividend);   
        long longDivisor = abs((long)divisor);   

        long div = longDividend;
        long res = 0;
        while(div >= longDivisor )
        {
            int i =0;
            while(div >= longDivisor)
            {
                i++;
                div >>= 1;
            }
            if(i == 0) i = 1;
            res += (1 << (i-1));
            div = longDividend - (longDivisor << (i-1));
            longDividend = div;
        }
        return ((dividend<0)^(divisor<0)?-1:1)* res;
    }
};

[LeetCode] Sqrt(x)

Implement int sqrt(int x).
It can be solved through Newton's method.

Compute and return the square root of x.

class Solution {
public:
    int sqrt(int x) {
    if (x == 0) return 0;
    double last = 0;
    double res = 1;
    while (res != last)
    {
        last = res;
        res = (res + x / res) / 2;
    }
    return int(res);
}
};

[LeetCode] Pow(x, n)

Implement pow(x, n).

class Solution {
public:
    double myPow(double x, int n) 
    {
        if (n==0) return 1;
        double t = pow(x,n/2);
        if (n%2) 
        {
            return n<0 ? 1/x*t*t : x*t*t;
        } 
        else 
        {
            return t*t;
        }
    }
};

[LeetCode] Reverse Integer

Reverse digits of an integer.

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

class Solution {
public:
    int reverse(int x) {
        long res = 0;
        while(x)
        {
            res *= 10;
            int y = x % 10;
            res += y;
            x /= 10;
        }
        if(abs(res) & (0x1111<<31)) return 0;
        return res;
    }
};