LIKE CODING: MJ

Showing posts with label MJ. Show all posts

Sunday, December 20, 2015

MJ [50] Connected Components

Ref
[1] http://www.mitbbs.com/article_t/JobHunting/33111815.html

Wednesday, December 16, 2015

Question:

you have an img data as an array, output the data for upsampling. For example,
[1, 2, 3, 4, 5, 6] as width 3(2 rows) ==> upsample 2 times would be [1 1 2 2 3 3 1 1 2 2 3 3 4 4 5 5 6 6 4 4 5 5 6 6]
================
================
Ref
[1] http://www.mitbbs.com/article_t/JobHunting/33110511.html

LeetCode [318] Maximum Product of Word Lengths

Ref
[1] https://leetcode.com/problems/maximum-product-of-word-lengths/

Monday, December 14, 2015

LeetCode [317] Shortest Distance from All Buildings

317. Shortest Distance from All Buildings

Hard

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:

Each 0 marks an empty land which you can pass by freely.
Each 1 marks a building which you cannot pass through.
Each 2 marks an obstacle which you cannot pass through.

Example:

Input: [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]

1 - 0 - 2 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

Output: 7 

Explanation: Given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2),
             the point (1,2) is an ideal empty land to build a house, as the total 
             travel distance of 3+3+1=7 is minimal. So return 7.

Note:
There will be at least one building. If it is not possible to build such house according to the above rules, return -1.

#define N 100
class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid) {
        int m = grid.size();
        if(m==0) return 0;
        int n = grid[0].size();
        if(n==0) return 0;

        int nb = 0;//count the number of buildings
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(grid[i][j]==1){
                    nb++;
                }
            }
        }

        int ret = INT_MAX;
        bool found = false;//is true of there exists a valid place which can reach all buildings

        //check every cell if it is not an obstacle, grid[i][j]==0 or 1
        //if grid[i][j]==0, this is an potential valid place 
        //if grid[i][j]==1, check if we can reach all other buildings from [i][j]. If not, ie., there exists another buildings [i', j'] 
        //such that grid[i'][j']==1 and [i, j] cannot reach [i', j'], thus, there mush not exist an valid place which can reach all buildings. 
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(grid[i][j]==2) continue;//cannot pass through an obstacle
                bool visited[N][N] = {false};
                queue<vector<int>> que;
                int cnt = 0, dist = 0;
                vector<int> cor={i, j, 0};//row id, column id, current steps
                que.push(cor);
                visited[i][j] = true;
                while(!que.empty()){
                    int x = que.front()[0];
                    int y = que.front()[1];
                    int step = que.front()[2];
                    que.pop();
                    if(grid[x][y]==1){//found an buildings which can be reached from [i, j] in "step" steps
                        cnt++;
                        dist += step;
                    }

                    //continue bfs if 1) current place is empty; 2) current place is the original place
                    if(grid[x][y]==0||(i==x && j==y)){
                        if(x-1>=0 && grid[x-1][y]<2 && !visited[x-1][y]){vector<int> v = {x-1, y, step+1}; que.push(v); visited[x-1][y] = true;};
                        if(x+1<m  && grid[x+1][y]<2 && !visited[x+1][y]){vector<int> v = {x+1, y, step+1}; que.push(v); visited[x+1][y] = true;};
                        if(y-1>=0 && grid[x][y-1]<2 && !visited[x][y-1]){vector<int> v = {x, y-1, step+1}; que.push(v); visited[x][y-1] = true;};
                        if(y+1<n  && grid[x][y+1]<2 && !visited[x][y+1]){vector<int> v = {x, y+1, step+1}; que.push(v); visited[x][y+1] = true;};
                    }
                }

                //[i, j] is a buildings and it cannot reach all other buildings. Return -1.
                if(grid[i][j]==1 && cnt<nb) return -1;

                //[i, j] is an empty place and it can reach all buildings.
                if(cnt==nb && grid[i][j]==0){
                    found = true;
                    ret = min(ret, dist);
                }
            }
        }

        return found?ret:-1;
    }
};

public class Solution {
    public int shortestDistance(int[][] grid) {
        if (grid == null || grid[0].length == 0) return 0;
        final int[] shift = new int[] {0, 1, 0, -1, 0};
        
        int row  = grid.length, col = grid[0].length;
        int[][] distance = new int[row][col];
        int[][] reach = new int[row][col];
        int buildingNum = 0;
        
        for (int i = 0; i < row; i++) {
            for (int j =0; j < col; j++) {
                if (grid[i][j] == 1) {
                    buildingNum++;
                    Queue<int[]> myQueue = new LinkedList<int[]>();
                    myQueue.offer(new int[] {i,j});

                    boolean[][] isVisited = new boolean[row][col];
                    int level = 1;
                    
                    while (!myQueue.isEmpty()) {
                        int qSize = myQueue.size();
                        for (int q = 0; q < qSize; q++) {
                            int[] curr = myQueue.poll();
                            
                            for (int k = 0; k < 4; k++) {
                                int nextRow = curr[0] + shift[k];
                                int nextCol = curr[1] + shift[k + 1];
                                
                                if (nextRow >= 0 && nextRow < row && nextCol >= 0 && nextCol < col
                                    && grid[nextRow][nextCol] == 0 && !isVisited[nextRow][nextCol]) {
                                        //The shortest distance from [nextRow][nextCol] to thic building
                                        // is 'level'.
                                        distance[nextRow][nextCol] += level;
                                        reach[nextRow][nextCol]++;
                                        
                                        isVisited[nextRow][nextCol] = true;
                                        myQueue.offer(new int[] {nextRow, nextCol});
                                    }
                            }
                        }
                        level++;
                    }
                }
            }
        }
        
        int shortest = Integer.MAX_VALUE;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 0 && reach[i][j] == buildingNum) {
                    shortest = Math.min(shortest, distance[i][j]);
                }
            }
        }
        
        return shortest == Integer.MAX_VALUE ? -1 : shortest;
        
        
    }
}

Wednesday, December 9, 2015

LeetCode [315] Count of Smaller Numbers After Self

315. Count of Smaller Numbers After Self

Hard

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example 1:

Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Constraints:

0 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

//C++: 680ms  Sort from the end
class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        vector<int> ret(n, 0);
        for(int i=n-2; i>=0; --i){
            int t = nums[i];
            int j;
            for(j = i+1; j<n; ++j){
                if(nums[j]>=t) break;
            }
            nums.insert(nums.begin()+j, t);
            nums.erase(nums.begin()+i);
            ret[i] = j-i-1;
        }
        return ret;
    }
};
]]></script>
<script class="brush: js" type="syntaxhighlighter"><![CDATA[
//C++: 104ms  binary search
class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {     
     int n = nums.size();
     vector<int> ret(n,0);
     for(int i=n-2; i>=0; --i){
         int l = i+1, r = n-1, m;
         while(l<=r){
          m = (l+r)/2;
          if((nums[m]>=nums[i] && nums[m-1]<nums[i])){
              break;
          }else if(nums[m]>=nums[i]){
              r = m-1;
          }else{
              l = m+1;
          }
         }
         if(r<=i) m = i+1;
         if(l>=n) m = n;
         nums.insert(nums.begin()+m, nums[i]);
         nums.erase(nums.begin()+i);
         ret[i] = m-(i+1);
     }
 return ret;
    }
};
]]></script>
<script class="brush: js" type="syntaxhighlighter"><![CDATA[
//C++: 100ms merge sort
class Solution {
    vector<int> numbers;
    vector<int> ret;
public:

    vector<int> merge(vector<int> leftIndices, vector<int> rightIndices){
        int szl = leftIndices.size();
        int szr = rightIndices.size();
        int i = 0, j = 0, cnt = 0;
        vector<int> sortedIndices;
        while(i<szl && j<szr){
            if(numbers[leftIndices[i]]<=numbers[rightIndices[j]]){
                sortedIndices.push_back(leftIndices[i]);
                ret[leftIndices[i]] += cnt;
                i++;
            }else{
                sortedIndices.push_back(rightIndices[j]);
                j++;
                cnt++;
            }
        }
        while(i<szl){
            sortedIndices.push_back(leftIndices[i]);
            ret[leftIndices[i]] += cnt;
            i++;
        }
        while(j<szr){
            sortedIndices.push_back(rightIndices[j]);
            j++;
        }
        return sortedIndices;
    }
    void divide(vector<int> &indices){
        int n = indices.size();
        if(n<2) return;
        int mid = n/2;
        vector<int> left(indices.begin(), indices.begin()+mid);
        vector<int> right(indices.begin()+mid, indices.end());
        divide(left);
        divide(right);
        indices = merge(left, right);
    }

    vector<int> countSmaller(vector<int>& nums) {
        numbers = nums;
        int sz = nums.size();
        ret.resize(sz, 0);
        vector<int> indices(sz);
        for(int i=0; i<sz; ++i){
            indices[i] = i;
        }
        divide(indices);
        return ret;
    }
};

//Java
class Solution {
    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        List<Integer> list = new ArrayList<Integer>();
        for(int v:nums) list.add(v);
        List<Integer> counts = new ArrayList<Integer>(n);
        for(int i=0; i<n; ++i) counts.add(0);
        //sort nums from right to left;
        for(int i=n-2; i>=0; --i){
            int l = i+1, r = n-1;
            while(l<r){
                int m = (l+r)/2;
                if(list.get(m)<list.get(i)){
                    l = m+1;
                }else{
                    r = m;
                }
            }
            if(list.get(l)<list.get(i)){
                l = n;
            }
            list.add(l, list.get(i));
            list.remove(i);
            counts.set(i, l-i-1);
        }
        return counts;
    }
}

Tuesday, December 8, 2015

LeetCode [314] Binary Tree Vertical Order Traversal

Given a binary tree, return the vertical order traversal of its nodes' values. (ie, from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

Examples 1:

Input: [3,9,20,null,null,15,7]

   3
  /\
 /  \
 9  20
    /\
   /  \
  15   7 

Output:

[
  [9],
  [3,15],
  [20],
  [7]
]

Examples 2:

Input: [3,9,8,4,0,1,7]

     3
    /\
   /  \
   9   8
  /\  /\
 /  \/  \
 4  01   7 

Output:

[
  [4],
  [9],
  [3,0,1],
  [8],
  [7]
]

Examples 3:

Input: [3,9,8,4,0,1,7,null,null,null,2,5] (0's right child is 2 and 1's left child is 5)

     3
    /\
   /  \
   9   8
  /\  /\
 /  \/  \
 4  01   7
    /\
   /  \
   5   2

Output:

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

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> verticalOrder(TreeNode* root) {
        int l = 0, r = 0;
        vector<vector<int>> ret;
        if(!root) return ret;
        
        ret.resize(1);
        queue<pair<TreeNode*, int>> que;//node. column index
        que.push(make_pair(root, 0));
        while(!que.empty())
        {
            TreeNode *node = que.front().first;
            int index = que.front().second;
            que.pop();
            if(index<l)
            {
                l--;
                ret.insert(ret.begin(), vector<int>());
            }
            else if(index>r)
            {
                r++;
                ret.insert(ret.end(), vector<int>());
            }
            ret[index-l].push_back(node->val);
            if(node->left) que.push(make_pair(node->left, index-1));
            if(node->right) que.push(make_pair(node->right, index+1));
        }
        return ret;
    }
};

LeetCode [313] Super Ugly Number

Ref
[1] https://leetcode.com/problems/super-ugly-number/

Friday, December 4, 2015

LeetCode [311] Sparse Matrix Multiplication

Given two sparse matrices A and B, return the result of AB.

You may assume that A's column number is equal to B's row number.

Example:

Input:

A = [
  [ 1, 0, 0],
  [-1, 0, 3]
]

B = [
  [ 7, 0, 0 ],
  [ 0, 0, 0 ],
  [ 0, 0, 1 ]
]

Output:

     |  1 0 0 |   | 7 0 0 |   |  7 0 0 |
AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
                  | 0 0 1 |

class Solution {
public:
    vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
        unordered_map<int, unordered_set<int>> A1, B1;
        int ma = A.size(), na = A[0].size();
        int mb = B.size(), nb = B[0].size();

        for(int i=0; i<ma; ++i){
            for(int j=0; j<na; ++j){
                if(A[i][j]){
                    A1[i].insert(j);
                }
            }
        }

        for(int j=0; j<nb; ++j){
            for(int i=0; i<mb; ++i){
                if(B[i][j]){
                    B1[j].insert(i);
                }
            }
        }

        vector<vector<int>> ret(ma, vector<int>(nb, 0));
        for(int i=0; i<ma; ++i){
            for(int j=0; j<nb; ++j){
                int s = 0;
                if(A1.count(i) && B1.count(j)){
                    for(auto k:A1[i]){
                        if(B1[j].count(k)){
                            s += A[i][k]*B[k][j];
                        }
                    }
                }
                ret[i][j] = s;
            }
        }

        return ret;
    }
};

//Java
class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
        int am = A.length, an = A[0].length;
        int bm = B.length, bn = B[0].length;
        List<Map<Integer, Integer>> mapA = new ArrayList<Map<Integer, Integer>>(am);
        List<Map<Integer, Integer>> mapB = new ArrayList<Map<Integer, Integer>>(bn);

        for(int i=0; i<am; ++i){
            mapA.add(new HashMap<>());
            for(int j=0; j<an; ++j){
                if(A[i][j]!=0){
                    mapA.get(i).put(j, A[i][j]);
                }
            }
        }

        for(int j=0; j<bn; ++j){
            mapB.add(new HashMap<>());
            for(int i=0; i<bm; ++i){
                if(B[i][j]!=0){
                    mapB.get(j).put(i, B[i][j]);
                }
            }
        }

        int[][] ret = new int[am][bn];
        for(int i=0; i<am; ++i){
            for(int j=0; j<bn; ++j){
                int s = 0;
                for(Map.Entry<Integer, Integer> e : mapA.get(i).entrySet()){
                    int k = e.getKey(), v = e.getValue();
                    if(mapB.get(j).containsKey(k)){
                        s += v*mapB.get(j).get(k);
                    }
                }
                ret[i][j] = s;
            }
        }
        return ret;
    }
}

Friday, November 13, 2015

LeetCode [305] Number of Islands II

======================= =====================

Note:
1. differentiate the islands by "id"
2. "islands" records the total number of islands
3, "state" records the ids of the islands
Example:
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

step 1: [0, 1]
0 1 0 0
0 0 0 0
0 0 0 0
0 0 0 0
islands = 1

step 2: [1, 0]
0 1 0 0
2 0 0 0
0 0 0 0
0 0 0 0
islands = 2

step 3: [2, 1]
0 1 0 0
2 0 0 0
0 3 0 0
0 0 0 0
islands = 3

step 4: [1, 1]
at this step, id_t = 1, id_l = 2, id_b = 3 and id_r = 0
thus, id is set to the minimal minimum one, which is 1
since the new island (1,1) connects the other 3 existing islands
merge them into one island and update their ids accordingly
after step 4, "state" becomes:
0 1 0 0
1 1 0 0
0 1 0 0
0 0 0 0
islands = 1

the set "merged" is used to avoid cases like
0 2 0 0 0
2 2 0 1 0
0 2 2 0 0
0 0 0 0 0
0 0 0 0 0
currently, there are two islands 1 and 2.
if a new land [1, 2] is created, both id_l and id_b is 2
but "islands" should be decreased once
so after [1,2] is created
the state becomes:
0 1 0 0 0
1 1 1 1 0
0 1 1 0 0
0 0 0 0 0
0 0 0 0 0

Ref
[1] https://leetcode.com/problems/number-of-islands-ii/
OJ
[2] https://leetcode.com/discuss/69572/easiest-java-solution-with-explanations