LIKE CODING: September 2015

Monday, September 28, 2015

LeetCode [287] Find the Duplicate Number

287. Find the Duplicate Number

Medium

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one duplicate number in nums, return this duplicate number.

Follow-ups:

How can we prove that at least one duplicate number must exist in nums?
Can you solve the problem without modifying the array nums?
Can you solve the problem using only constant, O(1) extra space?
Can you solve the problem with runtime complexity less than O(n2)?

Example 1:

Input: nums = [1,3,4,2,2]
Output: 2

Example 2:

Input: nums = [3,1,3,4,2]
Output: 3

Example 3:

Input: nums = [1,1]
Output: 1

Example 4:

Input: nums = [1,1,2]
Output: 1

Constraints:

2 <= n <= 3 * 104
nums.length == n + 1
1 <= nums[i] <= n
All the integers in nums appear only once except for precisely one integer which appears two or more times.

//C++: 32ms
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for(int i=1; i<nums.size(); ++i){
            if(nums[i]==nums[i-1]) return nums[i];
        }
        return false;
    }
};
//C++: 16ms
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        bool cont = true;
        while(cont){
            cont = false;
            for(int i=0; i<n; ++i){
                if(nums[i]!=i+1 && nums[nums[i]-1]!=nums[i]){
                    swap(nums[i], nums[nums[i]-1]);
                    cont = true;
                }
            }
        }
        for(int i=0; i<n; ++i){
            if(nums[i]!=i+1) return nums[i];
        }
    }
};
//Java
class Solution {
    public int findDuplicate(int[] nums) {
        int s = nums[0], f = nums[nums[0]];
        while(s!=f){
            s = nums[s];
            f = nums[nums[f]];
        }
  //      System.out.println(s +" "+f);
        s = 0;
        while(s!=f){
            s = nums[s];
            f = nums[f];
        }
        return f;
    }
}

Thursday, September 24, 2015

LeetCode [286] Walls and Gates

286. Walls and Gates

Medium

You are given a m x n 2D grid initialized with these three possible values.

-1 - A wall or an obstacle.
0 - A gate.
INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

Example:

Given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        int m = rooms.size();
        if(m==0) return;
        int n = rooms[0].size();
        if(n==0) return;
        
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                stack<pair<int, int>> stk;
                if(rooms[i][j]==0){
                    stk.push(pair<int, int>(i,j));
                    while(!stk.empty()){
                        int x = stk.top().first, y = stk.top().second;
                        stk.pop();
                        if(x-1>=0 && rooms[x-1][y]>rooms[x][y]+1){rooms[x-1][y] = rooms[x][y]+1; stk.push(pair<int, int>(x-1,y));}
                        if(x+1<m  && rooms[x+1][y]>rooms[x][y]+1){rooms[x+1][y] = rooms[x][y]+1; stk.push(pair<int, int>(x+1,y));}
                        if(y-1>=0 && rooms[x][y-1]>rooms[x][y]+1){rooms[x][y-1] = rooms[x][y]+1; stk.push(pair<int, int>(x,y-1));}
                        if(y+1<n  && rooms[x][y+1]>rooms[x][y]+1){rooms[x][y+1] = rooms[x][y]+1; stk.push(pair<int, int>(x,y+1));}
                    }
                }
            }
        }
    }
};

class Solution {
    int[][] dirs = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
    int m, n;
    public void wallsAndGates(int[][] rooms) {
        m = rooms.length;
        if(m==0) return;
        n = rooms[0].length;

        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(rooms[i][j]==0){
                    dfs(rooms, i, j);
                }
            }
        }
    }

    void dfs(int[][] rooms, int i0, int j0){
        for(int[] d : dirs){
            int i = i0+d[0], j = j0+d[1];
            if(i>=0 && i<m && j>=0 && j<n && rooms[i][j]!=-1){
                if(rooms[i][j]>rooms[i0][j0]+1){
                    rooms[i][j] = rooms[i0][j0]+1;
                    dfs(rooms, i, j);
                }
            }
        }
    }
}

MJ [40] Count squares

Question:
Given a set of points, find all squares composed by four points of the set.

Ref
[1] http://www.mitbbs.com/article_t1/JobHunting/32968629_0_1.html
[2] https://www.codechef.com/problems/D6
[3] https://www.quora.com/Given-two-diagonally-opposite-points-of-a-square-how-can-I-find-out-the-other-two-points-in-terms-of-the-coordinates-of-the-known-points

Monday, September 21, 2015

LeetCode [285] Inorder Successor in BST

Ref
[1] https://leetcode.com/problems/inorder-successor-in-bst/
OJ

Sunday, September 20, 2015

LeetCode [284] Peeking Iterator

284. Peeking Iterator

Medium

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation -- it essentially peek() at the element that will be returned by the next call to next().

Example:

Assume that the iterator is initialized to the beginning of the list: [1,2,3].

Call next() gets you 1, the first element in the list.
Now you call peek() and it returns 2, the next element. Calling next() after that still return 2. 
You call next() the final time and it returns 3, the last element. 
Calling hasNext() after that should return false.

Follow up: How would you extend your design to be generic and work with all types, not just integer?

// Below is the interface for Iterator, which is already defined for you.
// **DO NOT** modify the interface for Iterator.
class Iterator {
    struct Data;
 Data* data;
public:
 Iterator(const vector<int>& nums);
 Iterator(const Iterator& iter);
 virtual ~Iterator();
 // Returns the next element in the iteration.
 int next();
 // Returns true if the iteration has more elements.
 bool hasNext() const;
};


class PeekingIterator : public Iterator {
    bool peeked;
    int peekV;
public:
 PeekingIterator(const vector<int>& nums) : Iterator(nums) {
     // Initialize any member here.
     // **DO NOT** save a copy of nums and manipulate it directly.
     // You should only use the Iterator interface methods.
     peeked = false;
 }

    // Returns the next element in the iteration without advancing the iterator.
 int peek() {
        if(peeked) return peekV;
        else if(Iterator::hasNext()){
            peeked = true;
            peekV = Iterator::next();
            return peekV;
        }
 }

 // hasNext() and next() should behave the same as in the Iterator interface.
 // Override them if needed.
 int next() {
     if(peeked){ peeked = false; return peekV;}
     else if(Iterator::hasNext()) return Iterator::next();
 }

 bool hasNext() const {
     if(peeked) return true;
     else return Iterator::hasNext();
 }
};

// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html

class PeekingIterator implements Iterator<Integer> {  
    private Integer next = null;
    private Iterator<Integer> iter;

    public PeekingIterator(Iterator<Integer> iterator) {
        // initialize any member here.
        iter = iterator;
        if (iter.hasNext())
            next = iter.next();
    }
    
    // Returns the next element in the iteration without advancing the iterator. 
    public Integer peek() {
        return next; 
    }

    // hasNext() and next() should behave the same as in the Iterator interface.
    // Override them if needed.
    @Override
    public Integer next() {
        Integer res = next;
        next = iter.hasNext() ? iter.next() : null;
        return res; 
    }

    @Override
    public boolean hasNext() {
        return next != null;
    }
}

Saturday, September 19, 2015

MJ [39] Valid Parentheses

Question:
Given a string with parentheses, return a string with balanced parentheses by removing the fewest characters possible. You cannot add anything to the string.
Examples:
balance("()") -> "()"
balance(")(") -> "".
balance("(((((") -> ""
balance("(()()(") -> "()()"
balance(")(())(") -> "(())"
Note：balance(")(())(") != "()()"

Ref
[1] http://www.mitbbs.com/article_t1/JobHunting/32913437_0_1.html

Friday, September 18, 2015

MJ [38] Target Sum

Question:
Given an array A, determine if there is a subarray with sum equal to a given target.
Eg., if A = {4, 7, -5, 6, -2, 1} and target = 8. It should return true because sum{7, -5, 6} = 8. If target = 3, it should return false.

Ref
[1] http://www.mitbbs.com/article_t/JobHunting/32957899.html
[2] http://www.geeksforgeeks.org/find-if-there-is-a-subarray-with-0-sum/

LeetCode [283] Move Zeroes

283. Move Zeroes

Easy

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note:

You must do this in-place without making a copy of the array.
Minimize the total number of operations.

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size(), i = 0, j = 0;
        while(j<n){
            while(j<n && nums[j]==0) j++;
            if(j<n) nums[i++] = nums[j++];
        }
        while(i<n){
            nums[i++] = 0;
        }
    }
};

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        int i = 0, j = 0;
        
        while(j<n){
            while(j<n && nums[j]==0){ 
                j++;
            }
            while(j<n && nums[j]!=0){
                nums[i++] = nums[j++];
            }
        }
        fill(nums.begin()+i, nums.end(), 0);
    }
};

class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length;
        int i = 0, j = 0;
        while(i<n){
            if(nums[i]==0){
                i++;
            }else{
                nums[j] = nums[i];
                i++;
                j++;
            }
        }
        
        while(j<n){
            nums[j] = 0;
            j++;
        }
    }
}

MJ [37] Cross River

Question:
A bug is trying to cross the river start from position 0 to position X. Every time bug can jump no more than the D steps (1 to D steps). Leaves will fall from the tree to the river based on schedule A. A[0] = 1 means a leaf will fall on position 1 at time 0. Need to find the earliest time that the bug can jump from position 0 to X using leaves; If there is no answer, return -1;

Example:
A = [1, 3, 1, 4, 2, 5]
X = 7
D = 3
Answer: 3
Explanation: At time 3, there will be leaves on position 1,3, and 4; bug can jump 1 step, 3 step, and then 3 steps to cross the river;
Ref
[1] http://www.mitbbs.com/article_t/JobHunting/33055941.html
[2] http://www.mitbbs.com/article_t/JobHunting/33058417.html