[LeetCode] H-Index

This question can be found https://leetcode.com/problems/h-index/

class Solution {
public:
    int hIndex(vector& citations) {
        sort(citations.begin(), citations.end());
        int j = 0;
        for(int i=citations.size()-1;i>=0;i--)
        {
            j++;
            if(citations[i] == j) return j;
            if(citations[i] < j) return j-1;
        }
        return j;
    }
};

[LeetCode] Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int size = nums.size();
        int total = 0;
        for(int i=0; i<size; i++)
        {
            total += nums[i];
        }
        return size*(size+1)/2 - total;
    }
};

[LeetCode] Add Digits

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Please refer to this formula:

The formula is:

class Solution {
public:
    int addDigits(int num) {
        if(0 == num) return 0;
        if(num % 9 == 0) return 9;
        return num % 9;
    }
};

[LeetCode] Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note: Do not use the eval built-in library function.

Note: What can be done through stl stack, can also be done through stl vector.

class Solution {

public:
    int calculate(string s) {
        vector<int> numbers;
        vector<char> operators;
        int i = 0;
        while(i<s.length())
        {
            char e = s[i++];
            if(e == ' ') continue;
            
            if(isdigit(e))
            {
                int j = i;
                while(j < s.length() && isdigit(s[j]) ) j++;
                int num = stoi(s.substr(i-1, j-i+1));
                i = j;
                if(!operators.empty() && 
                    (operators.back() == '*' 
                    || operators.back() == '/')
                  )
                {
                    char op = operators.back();
                    operators.pop_back();
                    if(op == '*') numbers.back() *= num;
                    else numbers.back() /= num;
                }
                else numbers.push_back(num);
                
            }
            else operators.push_back(e);
        }
        
        if(numbers.empty()) return 0;
        int a = numbers[0];
        int opIndex = 0;
        for(int i = 1;i<numbers.size();i++)
        {
            char op = operators[opIndex++];
            if(op == '+') a += numbers[i];
            else a -= numbers[i];
        }
        return a;
    }
};

[LintCode] Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:

1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.

11 is read off as "two 1s" or 21.

21 is read off as "one 2, then one 1" or1211.

Given an integer n, generate the nth sequence.

Example

Given n = 5, return "111221".

Note

The sequence of integers will be represented as a string.

class Solution {
public:
    string countAndSay(int n) {
        string str = "1";
        for(int i=1;i<n;i++)
        {
            int len = str.length();
            int start = 0;
            string res;
            for(int j=1;j<len;j++)
            {
                if(str[j] != str[j-1])
                {
                    res += to_string(j-start) + str[j-1];
                    start = j;
                }
            }
            res += to_string(len-start) + str[len-1];
            str = res;
        }
        return str;  
    }
};

Maximum K

Let M(k) = true denote there are at least k elements in a given array larger than or equal to k. Find the maximum k such that M(k) = true.

For example:

{1, 3, 2, 6, 9}, there are 3 elements larger than or equal to 3. Maximum k = 3.
{1, 3, 4, 6, 9},  there are 4 elements larger than or equal to 3. Maximum k = 3;
{1,1,1}, there are 3 elements larger than or equal to 1. Maximum k = 1;

Analysis:

Suppose the array A is sorted for largest to smallest.

1) A[i] > i means that all elements from 0 to i are larger than or equal to i. Maximum k >= i.
2) A[i] == i means that A[i+1] < i+1, thus maximum k = i
3) A[i-1] > i-1 && A[i] < i. From A[i-1] > i-1 we know A[i-1] >= i. Maximum k = i;

So, we need to find out the first element smaller than or equal to i.

bool lt(int a, int b){return a>b;}

int findPivotCount(vector<int>& A)
{
    int len = A.size();
    if(0 == len) return 0;
    sort(A.begin(), A.end(), lt);
    for(int i=0;i<len;i++)
    {
        if(A[i] <= i) return i;
    }
    return len;
}

This solution will take O(nlogn). Let's give an O(n) solution.
Note that fact the result is at largest n, which is the length the array. Let b[i] be the count of elements with value i. sum(b[j]), i<=j<=n will be the count of elements whose values are larger than or equal to i.

int findPivotCount(vector<int>& A)
{
    int len = A.size();
    vector<int> b(len+1, 0);
    for(int i=0;i<len;i++)
    {
        if(A[i]<0) continue;
        int t = A[i]>len?len:A[i];
        b[t]++;
    }
    int sum = 0;
    for(int i=len;i>=0;i--)
    {
        sum += b[i];
        if(sum >= i) return i;
    }
    return 0;
}

[LeetCode] Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Analysis:
Just catch each possible trading opportunity.

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int profit = 0;
        for(int i=1;i<prices.size();i++)
        {
            profit += max(0, prices[i] - prices[i-1]);
        }
        return profit;
    }
};

[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;
    }
};

[LintCode] Majority Number

Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it.

Example

Given [1, 1, 1, 1, 2, 2, 2], return 1

Challenge

O(n) time and O(1) extra space

Moore’s Voting Algorithm:

class Solution {
public:
    int majorityNumber(vector<int> nums) {
        int len = nums.size();
        if(0 == len) return 0;
        int maj = nums[0], count = 1;
        for(int i=1;i<len;i++)
        {
            if(nums[i] == maj) count ++;
            else count --;
            if(0 == count) 
            {
                maj = nums[i];
                count = 1;
            }
        }
        return maj;
    }
};

[LeetCode] Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line. Analysis: Just need to handle the duplicate node and vertical lines.

/**
 * 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 size = points.size();
        int maxNum = 0;
        unordered_map<float, int> map;

        for(int i=0;i<size;i++)
        {
            map.clear();
            int dup = 1;
            for(int j=0;j<size;j++)
            {
                if(i == j) continue;
                if(points[j].x == points[i].x && points[j].y == points[i].y) {dup++;continue;}

                float k = points[j].x == points[i].x ? INT_MAX: 
                    (float)(points[j].y-points[i].y)/(float)(points[j].x - points[i].x);

                map[k] ++;
            }
            for(auto itor : map)
            {
                maxNum = max(itor.second + dup, maxNum);    
            }
            if(map.size() == 0) maxNum = max(dup, maxNum);
        }
        return maxNum;
    }
};

[LeetCode] Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Analysis:

Similar with Maximum subarray, we need to maintain an array for the maximum product that ends at index i. To achieve that, we need to know the minimum product that ends at i, because some elements might be negative.

If num[i+1] is negative, Max[i+1] = max(Min[i]*num[i+1], num[i+1]),

else Max[i+1] = max(Max[i]*num[i+1], num[i+1]);

class Solution {
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int len = nums.size();
        if(0 == len) return 0;
        int lastMax = nums[0], lastMin = nums[0];
        int res = lastMax;
        for(int i=1;i<len;i++)
        {
            if(nums[i] >=0 )
            {
                lastMax = max(lastMax*nums[i], nums[i]);
                lastMin = min(lastMin*nums[i], nums[i]);
            }
            else
            {
                int t = max(lastMin*nums[i], nums[i]);
                lastMin = min(lastMax*nums[i], nums[i]);
                lastMax = t;
            }
            res = max(res, lastMax);
        }
        return res;
    }
};

[LeetCode] 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.

class Solution {
public:
    string multiply(string num1, string num2) 
    {
        string res(num1.size()+num2.size(), '0');
        for (int i=num1.size()-1;i>=0;i--) 
        {
            int overflow = 0;
            for (int j=num2.size()-1;j>=0;j--) 
            {
                int sum = res[i+j+1]-'0' + (num1[i]-'0')*(num2[j]-'0') + overflow;
                res[i + j + 1] = sum%10 + '0';
                overflow = sum/10;
            }
            res[i] += overflow;
        }
    
        size_t t = res.find_first_not_of("0");
        if (string::npos == t) return "0";
        return res.substr(t);
    }
    
};

[LeetCode] Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int start = 0;
        int end = nums.size() - 1;
        int mid = -1;
        vector<int> res;
        while(start <= end)
        {
            mid = start + (end-start)/2;
            if(nums[mid] == target) break;
            if(nums[mid] < target) start = mid + 1;
            else end = mid - 1;
        }
        if(start > end) 
        {
            res.push_back(-1);
            res.push_back(-1);
            return res;
        }
        int send = mid;
        while(start <= send)
        {
            int smid = start + (send-start)/2;
            if(nums[smid] < target) start = smid + 1;
            else send = smid - 1;
        }
        res.push_back(start);
        
        start = mid;
        while(start <= end)
        {
            int smid = start + (end-start)/2;
            if(nums[smid] == target) start = smid + 1;
            else end = smid - 1;
        }
        res.push_back(end);
        return 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] Plus One

Given a non-negative 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) 
    {
        for(int i=digits.size()-1; i>=0; --i)
        {
            if(digits[i] ==9)
            {
                digits[i] = 0;
            }
            else
            {
                digits[i] = digits[i] + 1;
                return digits;
            }
        }
        digits.insert(digits.begin(), 1);
        return digits;
    }
};

[LeetCode] 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 lenA = a.length();
        int lenB = b.length();
        
        int i = 0;
        int overflow = 0;
        string res;
        while(i<lenA || i<lenB)
        {
            int a1 = i<lenA ? a[lenA - 1 - i] - '0' : 0;
            int a2 = i<lenB ? b[lenB - 1 - i] - '0' : 0;
            int sum = a1 + a2 + overflow;
            overflow = sum > 1 ? 1: 0;
            char c = sum %2 +'0';
            res = c + res;
            i++;
        }
        if(overflow) res = '1' + res;
        return res;
    }
};

[LeetCode] Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

class Solution {
public:
    void sortColors(int A[], int n) {
        int r = 0, w = 0;
        for(int i=0;i<n;i++)
        {
            if(A[i] == 0)
            {
                A[r++] = A[i];
            }
            else if(A[i] == 1)
            {
                w++;
            }
        }
        for(int i=r;i<r+w;i++)
        {
            A[i] = 1;
        }
        for(int i=r+w;i<n;i++)
        {
            A[i] = 2;
        }
    }
};

Another in-place solution:

class Solution{
public:
    void sortColors(vector<int> &nums) {
        int red = 0;
        int blue = nums.size() - 1;
        int p = red;

        while(p<=blue)
        {
            if(nums[p] == 0)
            {
                if(p != red) swap(nums[red], nums[p]);
                else p++;
                red ++;
            }
            else if(nums[p] == 2)
            {
                if(p!=blue) swap(nums[blue], nums[p]);
                else p++;
                blue --;
            }
            else p++;
        }
    }
};

[LeetCode] Bitwise AND of Numbers Range

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) 
    {
        int temp = m ^ n;
    
        int i = 0;
        while(temp >> i) {
            i++;
        }

        return ((m>>i)<<i);
    }    
};