Number of Islands II

305. Number of Islands II

A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example:

Given m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]].
Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).

0 0 0
0 0 0
0 0 0

Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.

1 0 0
0 0 0   Number of islands = 1
0 0 0

Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.

1 1 0
0 0 0   Number of islands = 1
0 0 0

Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.

1 1 0
0 0 1   Number of islands = 2
0 0 0

Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.

1 1 0
0 0 1   Number of islands = 3
0 1 0

We return the result as an array: [1, 1, 2, 3]

///////////////////////////////////////////////////////////////////////////////////
using a map to keep current islands:

unordered_map<int, vector<pair>> m;


for each coming island, check the four sides of the island,
and see it's connected to which existing island
 
           0
   0    new     0
      island 3

if all sides are 0, push back the new island into m;

otherwise, merge the current islands in the m.

repeat...............

LeetCode 425. Word Squares

Given a set of words (without duplicates), find all word squares you can build from them.

A sequence of words forms a valid word square if the kth row and column read the exact same string, where 0 ≤ k < max(numRows, numColumns).

For example, the word sequence ["ball","area","lead","lady"] forms a word square because each word reads the same both horizontally and vertically.

b a l l
a r e a
l e a d
l a d y

Note:

1. There are at least 1 and at most 1000 words.
2. All words will have the exact same length.
3. Word length is at least 1 and at most 5.
4. Each word contains only lowercase English alphabet a-z.

Example 1:

Input:
["area","lead","wall","lady","ball"]

Output:
[
  [ "wall",
    "area",
    "lead",
    "lady"
  ],
  [ "ball",
    "area",
    "lead",
    "lady"
  ]
]

Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

/////////////////////////////////////////////////////////////////////////////

for (auto word:s)
    vector<vector<string>> res;
    vector<string> tmp;
    tmp.push_back(word);
    for(int i=1;i<word.size();i++)tmp.push_back(word[i]);
    int col=1;
    bt(&s, &res, &tmp, col){
         if(col==word.size())res.push_back(tmp);
         else{
               string subs=tmp[col];
               for(auto w:s){
                    if(word.substr(0, subs.size())==subs){
                         ..update tmp
                         bt(s, res, tmp, col+1);
                         ..de-update tmp
                    }
               }
        }
  }
};

361. Bomb Enemy

Given a 2D grid, each cell is either a wall 'Y', an enemy 'X' or empty '0' (the number zero), return the maximum enemies you can kill using one bomb.
The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since the wall is too strong to be destroyed.
Note that you can only put the bomb at an empty cell.

Example:

For the given grid

0 w 0 0
e 0 e w
0 w 0 e

return 3. (Placing a bomb at (1,1) kills 3 enemies)

using DP:

DP with the same size of matrix mat;

each element is a pair (row, col), row means the sum of enimy in current row based on current position, col means the sum of enimy of column;

fill the DP one by one from left to right, when meet 'e', copy related value; meet 0, using DP or process; meet wall pass.

For the given mat

0 w 0 0
e 0 e w
0 w 0 e

build dp, with '-1' mean not applicable

(-1,-1) (-1,-1) (-1,-1) (-1,-1) 
(-1,-1) (-1,-1) (-1,-1) (-1,-1) 
(-1,-1) (-1,-1) (-1,-1) (-1,-1)

calculation: 

(0,0) (-1,-1) (0, 1) (0, 0) ........

[leetcode] 269. Alien Dictionary

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

For example,
Given the following words in dictionary,

[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

The correct order is: "wertf".

Note:

1. You may assume all letters are in lowercase.
2. If the order is invalid, return an empty string.
3. There may be multiple valid order of letters, return any one of them is fine.

Topological sorting:

1. Build the AOV
 using above fig. as example:

  unordered_map <char, int> m1;
m1[v1]=0;
m1[v2]=2;
m1[v3]=1;
...v4..=2;
...v5..=3;
....v6.=0;

  unordered_mpp <char, multisets<char>> m2;
m2[v1]={v2, v3, v4};
m2[v2]={}
......v3..={v2,v5}
.....v4...={v5}
......v6...={v4,v5}

2. extract the value inside 

1. class Solution {  
2. public:  
3.     string alienOrder(vector<string>& words) {  
4.         if(words.size()==0) return "";  
5.         unordered_map<char, int> indegree;  
6.         unordered_map<char, multiset<char>> hash;  
7.         for(auto word: words)  
8.             for(auto ch: word) indegree[ch] = 0;  
9.         for(int i = 1; i < words.size(); i++)  
10.         {  
11.             int k =0, len1 = words[i-1].size(), len2 = words[i].size();  
12.             while(words[i-1][k] == words[i][k]) k++;  
13.             if(k >= min(len1, len2)) continue;  
14.             indegree[words[i][k]]++;  
15.             hash[words[i-1][k]].insert(words[i][k]);  
16.         }  
17.         string ans;  
18.         for(int i = 0; i< indegree.size(); i++)  
19.         {  
20.             char ch = ' ';  
21.             for(auto val: indegree) if(!val.second) { ch = val.first; break; }  
22.             if(ch == ' ') return "";  
23.             ans += ch, indegree[ch]--;  
24.             for(auto val: hash[ch]) indegree[val]--;  
25.         }  
26.         return ans;  
27.     }  
28. };  

ref: http://blog.csdn.net/qq508618087/article/details/50981000

Top K points

// using priority queue

#include <iostream>
#include <vector>
#include <queue>
#include <utility>      // std::pair

using namespace std;


struct point{
  int x;
  int y;
  int dis;
};

  //order of priority queue
//put this outside of class
  bool operator<(const point& a, const point& b) {
  return a.dis > b.dis; // '>' is mini heap; '<' is max heap (max the most important one)
  };




class solution{
  public:
  vector<pair<int, int>> topkPoints(vector<pair<int,int>> &pairs, int k){
 
  //using priority queue
  priority_queue<point> pq;

  //build the queue with k ele.
  for(int i=0;i<pairs.size();i++){
    int dis=pairs[i].first*pairs[i].first + pairs[i].second*pairs[i].second;
    point pTmp;
    pTmp.x=pairs[i].first;
    pTmp.y=pairs[i].second;
    pTmp.dis=dis;
    pq.push(pTmp);
    if(pq.size()>k)pq.pop();
  }
 
  //find the k top points
  vector<pair<int, int>> res;
  for(int i=0;i<k;i++){
    pair<int, int> tmp =make_pair(pq.top().x, pq.top().y);
    pq.pop();
    res.push_back(tmp);
  }
  return res;
  }
};
 


// To execute C++, please define "int main()"
int main() {
 
 
  vector<pair<int, int>> test;
  for(int i=0;i<10;i++){
    pair<int, int> p=make_pair(i,i);  
    test.push_back(p);
  }
 
  solution s;
  vector<pair<int,int>> res=s.topkPoints(test, 2);
  for(int i=0;i<res.size();i++){
    cout<<res[i].first<<' '<<res[i].second;
   
  }
 


  return 0;
}

142. Linked List Cycle II

1. using map, but this will use extra space:(26ms)

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_map<ListNode*, int> m;
        ListNode* p=head;
        int cnt=0;
        while(p!=NULL){
            if(++m[p] == 2)return p;
            p=p->next;
        }
        return NULL;
    }
};



2. find out there is a circle first;
    then swipe each node to check whether there are in circle, the first in circle is the head of the circle.



3. using the 'find intersection in a merging lists' in http://xiamenhai.blogspot.com/2015/10/leetcode-intersection-of-two-linked.html.

Leetcode: Pascal's Triangle II

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

----------------------------

Note: O(k) means we can only use in-place way:

method: from right to left

eg.:

1   4   6  4  1 0 previous line

                            

0   0  0  0   0  1 now calculate in place from right to left 

0   0  0  0   5  1

0   0  0  10  5  1

0   0  10  10  5  1

0   5  10  10  5  1

1   5  10  10  5  1