Tuesday, December 30, 2014

LeetCode 59 Spiral Matrix

Problem

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example, Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].


Solution

Code first:

vector<int> spiralOrder(vector<vector<int> > &matrix) {
    vector<int> result;
    if (matrix.size() < 1) 
        return result;
    int top = 0;
    int button = matrix.size() - 1;
    int left = 0;
    int right = matrix[0].size() - 1;
    while (top <= button && left <= right) {
        for (int x = left; x <= right; x++) { //left to right
            result.push_back(matrix[top][x]);
        }
        top++;

        for (int y = top; y <= button; y++) { //top to button
            result.push_back(matrix[y][right]);
        }
        right--;
        if (button >= top) { // check if the button line haven't been pushed
            for (int x = right; x >= left; x--) {
                result.push_back(matrix[button][x]);
            }
            button--;
        }

        if (right >= left) { //check if the left line haven't been pushed
            for (int y = button; y >= top; y--) {
                result.push_back(matrix[y][left]);
            }
            left++;
        }

    }
    return result;
}

The solution is easy to understand, just iterate upper left -> upper right -> lower right -> lower -> left -> upper left. So we need four variable top, button, left, right to shrink to center step by step. The only tricky part is when we move from right to left and button to top, we should check if there are still space for this two operations. In fact, when I implement this, I debugged almost one hour and than find this.


Written with StackEdit.

LeetCode Rotated Sorted Array Problems

There are 4 problems about rotated sorted array, the sorted array is like [0 , 1, 2, 3, 4, 5], and the rotated sorted array is separating the sorted array to two parts and exchange the position of them. So one rotated array of above is [3, 4, 5, 0, 1, 2]. The fist two problems is Search in Rotated Sorted Array and Search in Rotated Sorted Array II. The difference is the first one's array have no duplicate and the second one may have duplicated elements. The method to solve the two question is the same. Here is the code for first question:

int search(int A[], int n, int target) {
    int lo = 0;
    int hi = n - 1;
    int mid;
    while (lo <= hi) {
        mid = lo + (hi - lo) / 2;
        if (target == A[mid]) {
            return mid;
        }
        if (A[lo] < A[mid]) {// target in left part, when no duplicate, change "<" to "<=".
            if (A[lo] <= target && target <= A[mid]) {
                hi = mid - 1;
            }
            else {
                lo = mid + 1;
            }
        }
        else if (A[lo] > A[mid]) { //target in right part. when no duplicate, change to else here.
            if (A[mid] <= target && target <= A[hi]) {
                lo = mid + 1;
            }
            else {
                hi = mid - 1;
            }
        }
        else { // handle duplicated cases
            lo++;
        }
    }
    return -1;
}

In fact, the code above also could handle the cases contain duplicated elements. When there are duplicated elements, we do know target in which part, so just let "lo" increase by one. If there have no duplicates, the time complexity is O(logn), just like binary search for a sorted array. if there are duplicated cases, the worst time complexity is O(n) for a array like [3, 3, 3, 3, 1, 3, 3].

The other two problem is Find Minimum in Rotated Sorted Array and Find Minimum in Rotated Sorted Array II. These two questions also could use binary search to solve, and just like the above two problems, the difference is whether there are duplicated elements. Here is the code:

int findMin(vector<int> &num) {
    int lo = 0;
    int hi = num.size() - 1;
    int mid = 0;

    while(lo < hi) {
        mid = lo + (hi - lo) / 2;

        if (num[mid] > num[hi]) { //minimum in right side
            lo = mid + 1;
        }
        else if (num[mid] < num[hi]) { //mininum in left side
            hi = mid;
        }
        else { // when num[mid] and num[hi] are same
            hi--;
        }
    }
    return num[lo];
}

Just as first two questions, this could handle the duplicated elements. This part of problems compare middle elements with "hi" elements, we also could compare middle and "lo" elements.

Written with StackEdit.

LeetCode 172 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.

This is a newly added problem in LeetCode, just yesterday. As a Chinese, I firstly searched what is "Trailing Zeros". OK, it's just the zeros at the end of a decimal number.
Before a depth thinking, I have known that the number of trailing zeros have a close relationship with the number of "5". So I wrote a small python script to try factorials below 10!. Here is the result:
1  1
2  2
3  6
4  24
5  120
6  720
7  5040
8  40320
9  362880
10 3628800

Looks like the number of trailing zeros is associated with the number of numbers could be divided by 5, so I wrote answer:
int trailingZeroes(int n) { return n / 5; }
While, it's still hard to me to get the right answer just one submit. When the input is 30, the right answer is 7 but my answer is 6. OK, I printed out all the factorials less than 28, something aren't went well after 25:
24 620448401733239439360000
25 15511210043330985984000000
26 403291461126605635584000000

After multiplied by 25, there increased 2 zeros. 25 is the square of 5, so it multiplied two 5 to 24!, so it added 2 zeros. Same thing, 125 means there are three 5 multiplied to last number, added 3 zeros. Looks like for factorial, the result is,
return n / 5 + n / 25 + n / 125 + n / 625 + n / 3125;

This could pass the test in LeetCode, but if n is too large, this is not a universal result. The best is
int trailingZeroes(int n) {
    int c = 0;
    while (n >= 5) {
        n /= 5;
        c += n;
    }
    return c;
}


By the way, StackEdit is a great!!!
Written with StackEdit.