[Leetcode] Find Minimum in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

Analysis:

Since it is sorted array, binary search may be the hint. Let m be the middle index of array num, if num[0] < num[m], then first part is sorted, the minimum element would be either num[0] or the minimum of the second part, which can be computed recursively. Similarly, if num[m] < num[n], second part is sorted, the minimum element would be either num[m] or the minimum of the first part. 

 int findMin(vector<int> &num) {
        int b = 0;
        int e = num.size() - 1;
        int minValue = INT_MAX;
        while(b <= e) {
            int m = b + (e- b)/2;
            //it is sorted from b to m
            if (num[b] <= num[m]) {
                minValue = min(num[b], minValue);
                b = m + 1;
            }
            else {
                minValue = min(num[m], minValue);
                e = m-1;
            }
        }
        return minValue;
    }

[Leetcode] Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

Analysis:

Apparently, we need to use extra space to store the minimum element of the stack. We can use one stack s to store the pushed element and another stack sMin to store minimum elements appearing so far. Whenever an element x is pushed, if it is less than current minimum (at the top of sMin stack), push x to the sMin; otherwise, the top of the sMin is the minimum and we push it to sMin;

class MinStack {
    stack<int> s;
    stack<int> sMin;
public:
    void push(int x) {
        s.push(x);
        if (sMin.empty() || x < sMin.top())
            sMin.push(x);
        else
            sMin.push(sMin.top());
    }

    void pop() {
        s.pop();
        sMin.pop();
    }

    int top() {
        return s.top();
    }

    int getMin() {
        return sMin.top();
    }
};

However, it could not pass Leetcode oj as Memory Limit Exceeded.  By looking at the solution again, we notice that if x is greater than minimum value, there is no need to push the sMin top value. Just do some special handle when popping the element: if the element is greater than minimum, do not pop sMin.

class MinStack {
    stack<int> s;
    stack<int> sMin;
public:
    void push(int x) {
        s.push(x);
        if (sMin.empty() || x <= sMin.top())
            sMin.push(x);
    }

    void pop() {
        if (s.top() <= sMin.top())
            sMin.pop();
        s.pop();
    }

    int top() {
        return s.top();
    }

    int getMin() {
        return sMin.top();
    }
};

In addition, we notice that if all the pushed elements are the same, there are still spaces wasted. It is possible to have a better solution so that few spaces needed for sMin.

[Leetcode] Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

    string addBinary(string a, string b) {
        string ret;
        int i = a.size() - 1;
        int j = b.size() - 1;
        int carry = 0;
        while(i >= 0 || j >= 0 || carry > 0)
        {
            int da = i < a.size() ? a[i] - '0' : 0;
            int db = j < b.size() ? b[j] - '0': 0;
            //the value
            int d = (da + db + carry) % 2;
            //the carry
            carry = (da + db + carry) / 2;
            ret.insert(ret.begin(),1, d + '0');
            i--;
            j--;
        }
        
        return ret;
    }

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

vector<int> plusOne(vector<int> &digits) {
        
        int carry = 0;
        vector<int> nums;
        for(int i=digits.size()-1; i >=0; i--)
        {
            int one = i == digits.size()-1 ? 1 : 0;
            int d = (digits[i] + one + carry) % 10;
            carry =  (digits[i] + one + carry) / 10;
            nums.insert(nums.begin(), d);
        }
        //don't forget carry for case {9}
        if (carry > 0)
            nums.insert(nums.begin(), 1);
        
        return nums;
    }

[Leetcode] Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

<pre class="prettyprint linenums:1"><code class="language-cpp"> int sqrt(int x) { int b = 0; int e = x/2 + 1; while(b <= e) { long long mid= (b+e)/2; long long sl = mid * mid; long long sh = (mid+1) * (mid+1); if (sl <= x && sh > x) return mid; else if (sl < x) b = mid + 1; else e = mid - 1; } return -1; } </code></pre>

[Leetcode] 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?

int climbStairs(int n) {
        vector<int> f(n+1,0);
        for(int i=0; i<=n; i++)
        {
            if (i == 0)
                f[i] = 1;
            else if (i == 1)
                f[i] = 1;
            else
                f[i] = f[i-1] + f[i-2];
        }
        return f[n];
    }

[Leetcode] Simplify Path

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

click to show corner cases.

Corner Cases:

• Did you consider the case where path = "/../"?
  In this case, you should return "/".
• Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
  In this case, you should ignore redundant slashes and return "/home/foo".

vector<string> splitPath(string path)
    {
        vector<string> ret;
        int i=0;
        while(i < path.size())
        {
            while(i < path.size() && path[i] != '/')
                i++;
            int j = i;
            i++;
            while(i < path.size() && path[i] != '/')
                i++;
                
            if (j != path.size())
                ret.push_back(path.substr(j+1, i-(j+1)));
        }
        return ret;
    }

    string simplifyPath(string path) {
        vector<string> paths = splitPath(path);
        stack<string> s;
        for(int i=0; i<paths.size(); i++)
        {
            //case: "/.."
            if (paths[i] == "..")
            {
                if (!s.empty())
                    s.pop();
            }
            //case: "////"
            else if (paths[i] != "." && paths[i].size() > 0)
                s.push(paths[i]);
        }
        
        string outPath;
        while(!s.empty())
        {
            string p = s.top();
            s.pop();
            outPath.insert(0, p);
            outPath.insert(0,"/");
        }
        
        if (outPath.size() == 0)
            outPath = "/";
            
        return outPath;
        
    }