LeetCode [320] Generalized Abbreviation

Ref
[1] https://leetcode.com/problems/generalized-abbreviation/

LeetCode [321] Create Maximum Number

Ref
[1] https://leetcode.com/problems/create-maximum-number/
OJ
[2] https://leetcode.com/discuss/75756/share-my-greedy-solution

MJ [50] Connected Components

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

LeetCode [319] Bulb Switcher

Ref
[1] https://leetcode.com/problems/bulb-switcher/

Survey [1] Cycle Detection

Method 1: Union-Find (Detect Cycle in a an Undirected Graph) [1]

Method 2: DFS (Detect Cycle in a an Directed Graph) [2]

Method 3: Coloring (Detect Cycle in a an Directed Graph) [3]

 Ref
[1] http://www.geeksforgeeks.org/union-find/
[2] http://www.geeksforgeeks.org/detect-cycle-in-a-graph/
[3] http://www.cs.cornell.edu/courses/cs2112/2012sp/lectures/lec24/lec24-12sp.html

MJ [49] Upsampling

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/

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

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

LeetCode [316] Remove Duplicate Letters

 316. Remove Duplicate Letters

Medium

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

 

Example 1:

Input: s = "bcabc"
Output: "abc"

Example 2:

Input: s = "cbacdcbc"
Output: "acdb"

 

Constraints:

• 1 <= s.length <= 104
• s consists of lowercase English letters.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

class Solution { public: string removeDuplicateLetters(string s) { if(s.empty()) return s; string ret; while(!s.empty()){ int cnts[26] = {0}; for(char c:s) cnts[c-'a']++; int pos = 0, n = s.size(); for(int i=0; i<n; ++i){ if(s[i]<s[pos]) pos = i; cnts[s[i]-'a']--; //find who's the first to disappear if(cnts[s[i]-'a']==0) break; } ret += s[pos]; string next; for(int i=pos+1; i<n; ++i){ if(s[i]!=s[pos]) next += s[i]; } s = next; } return ret; } };

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

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]
]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

/** * 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; } };