Day 134, #302 #305 Smallest Rectangle Enclosing Black Pixels, Number of Islands II

Smallest Rectangle Enclosing Black Pixels

An image is represented by a binary matrix with 0 as a white pixel and 1 as a black pixel. The black pixels are connected, i.e., there is only one black region. Pixels are connected horizontally and vertically. Given the location (x, y) of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels.

For example, given the following image:

[
  "0010",
  "0110",
  "0100"
]

and x = 0, y = 2,

Return 6.

----------------------------------------------------------------------
COME_BACK, mid的取值问题
binary search
getTop()和getLeft() 返回的都是包含black，其他2个返回的是不包含black。
稍微简单一点写法：https://leetcode.com/discuss/68246/c-java-python-binary-search-solution-with-explanation

class Solution {
public:
    int getTop(vector<vector<char>>& image, int x) {
        int top = 0, bottom = x, n = image[0].size();
        
        while (top < bottom) {
            int mid = (top + bottom) / 2;
            int k = 0;
            while (k < n && image[mid][k] == '0') {
                k++;
            }
            
            if (k < n) {
                bottom = mid;
            }else {
                top = mid + 1;
            }
        }
        
        return bottom;
    }
    
    int getBottom(vector<vector<char>>& image, int x) {
        int top = x, bottom = image.size(), n = image[0].size();
        
        while (top < bottom) {
            int mid = (top + bottom) / 2;
            int k = 0;
            while (k < n && image[mid][k] == '0') {
                k++;
            }
            
            if (k < n) {
                top = mid + 1;
            }else {
                bottom = mid;
            }
        }
        
        return bottom;
    }
    
    int getLeft(vector<vector<char>>& image, int y) {
        int left = 0, right = y, m = image.size();
        
        while (left < right) {
            int mid = (left + right) / 2;
            int k = 0;
            while (k < m && image[k][mid] == '0') {
                k++;
            }
            
            if (k < m) {
                right = mid;
            }else {
                left = mid + 1;
            }
        }
        return left;
    }
    
    int getRight(vector<vector<char>>& image, int y) {
        int right = image[0].size(), left = y, m = image.size();
        while (left < right) {
            int mid = (left + right) / 2;
            int k = 0;
            while (k < m && image[k][mid] == '0') {
                k++;
            }
            
            if (k < m) {
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        
        return left;
    }

    int minArea(vector<vector<char>>& image, int x, int y) {
        int top = getTop(image,x);
        int bottom = getBottom(image,x + 1);
        int left = getLeft(image,y);
        int right = getRight(image,y + 1);
        
        return (bottom - top) * (right - left);
    }
};

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]

Challenge:

Can you do it in time complexity O(k log mn), where k is the length of the positions?

-------------------------------------------------------
COME_BACK
标准union find, O(k * lg k), k 为 0 - m * n
注意：
#1 2维坐标和1维的来回转换
#2 看清题意，对count的计算

class UnionFind {
public:
    UnionFind(vector<pair<int, int>>& positions, int col) {
        this->col = col;
        count = 0;
    }
    
    void addPoint(pair<int,int> &p) {
        int index = encode(p);
        root[index] = index;
        size[index] = 1;
        count++;
    }
 
    int findRoot(pair<int,int> &p) {
        int index = encode(p);
        if (root.find(index) == root.end()) return -1;
        
        while (root[index] != index) {
            index = root[index];
        }
        return index;
    }

    void unionF(pair<int,int> &p1, pair<int,int> &p2) {
        int root1 = findRoot(p1), root2 = findRoot(p2);
        if (root1 == root2) return;
        
        if (size[root1] > size[root2]) {
            size[root1] += size[root2];
            root[root2] = root1;
        }else {
            root[root1] = root2;
        }
        count--;
    }
    
    int getCount() {
        return count;
    }

private:
    unordered_map<int,int> root;
    unordered_map<int,int> size;
    int count;
    int col;
    
    int encode(pair<int, int> &position) {
        return position.first * col + position.second;
    }
    
    pair<int,int> decode(int index) {
        return make_pair<int,int>(index / col, index % col);
    }
};

class Solution {
public:
    vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
        vector<int> rt;
        UnionFind uf(positions, n);
        
        for (int i = 0; i < positions.size(); i++) {
            uf.addPoint(positions[i]);
            int x = positions[i].first, y = positions[i].second;
            pair<int,int> p = make_pair(x + 1, y);
            if (x + 1 < m && uf.findRoot(p) != - 1) {
                uf.unionF(positions[i], p);
            }
            
            p = make_pair(x - 1,y);
            if (x - 1 >= 0 && uf.findRoot(p) != - 1) {
                uf.unionF(positions[i], p);
            }
            
            p = make_pair(x, y + 1);
            if (y + 1 < n && uf.findRoot(p) != - 1) {
                uf.unionF(positions[i],p);
            }
            
            p = make_pair(x, y - 1);
            if (y - 1 >= 0 && uf.findRoot(p) != - 1) {
                uf.unionF(positions[i], p);
            }
            rt.push_back(uf.getCount());
        }
        
        return rt;
    }
};

Java, ids类似于一个树。注意2处可以优化的地方。 O(k * log m * n), k为插入的次数，log(m*n)为树的深度(find()方法)，完全优化后深度为1
https://blog.csdn.net/dm_vincent/article/details/7655764
https://blog.csdn.net/dm_vincent/article/details/7769159 UnionFind更多应用

 
class Solution {
    
    private int[][] dirs = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
    
    public List numIslands2(int m, int n, int[][] positions) {
        List rt = new ArrayList<>();
        UnionFind uf = new UnionFind(m,n);
        
        for (int[] pos : positions) {
            uf.add(pos);
            int p = uf.getRootId(pos[0], pos[1]);
            for (int[] dir : dirs) {
                int i = pos[0] + dir[0];
                int j = pos[1] + dir[1];
                int q = uf.getRootId(i, j);
                if (q > 0 && q != p) {
                    uf.union(pos[0], pos[1], i, j);
                }
            }   
            
            rt.add(uf.getCount());
        }
        
        return rt;
    }
}

class UnionFind {
    
    private int count;
    private int[] ids;
    private int[] sizes;
    private int m;
    private int n;
    
    public UnionFind(int m, int n) {
        count = 0;
        ids = new int[m * n + 1];
        sizes = new int[m * n + 1];
        this.m = m;
        this.n = n;
    }
    
    public int getRootId(int i, int j) {
        if (i >= 0 && i < m && j >= 0 && j < n) {
            int index = getIndex(i,j);
            if ((ids[index]) == 0) return 0;
            return find(i, j);
        }
        
        return 0;
    }
    
    public void add(int[] pos) {
        int id = getIndex(pos[0], pos[1]);
        ids[id] = id;
        sizes[id] = 1;
        count++;
    }
    
    public int find(int i, int j) {
        int id = getIndex(i,j);
        while (ids[id] != id) {
            ids[id] = ids[ids[id]]; // Optimization
            id = ids[id];
        }
        
        return id;
    }
    
    public void union(int pI, int pJ, int qI, int qJ) {
        int rootP = find(pI, pJ);
        int rootQ = find(qI, qJ);
        
        if (rootP == rootQ) return;
        
        if (sizes[rootP] >= sizes[rootQ]) { // Optimization
            sizes[rootP] += sizes[rootQ];
            ids[rootQ] = rootP;    
        }else {
            sizes[rootQ] += sizes[rootP];
            ids[rootP] = rootQ;    
        }
        
        count--;
    }
    
    public int getCount() {
        return count;
    }
    
    private int getIndex(int i, int j) {
        return i * n + j + 1;
    }
}

Day 133, #297 #299 #300 #301 Serialize and Deserialize Binary Tree, Bulls and Cows, Longest Increasing Subsequence, Remove Invalid Parentheses

Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

----------------------------------------------------------
遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        queue<TreeNode *> que;
        que.push(root);
        string s = "";
        
        while (!que.empty()) {
            TreeNode *t = que.front();
            que.pop();
            if (t == NULL) {
                s += "n";
            }else {
                s += to_string(t->val) + ",";
                que.push(t->left);
                que.push(t->right);
            }
        }
        
        return s;
    }

    int next(string data, int &i) {
        int rt = 0, sign = 1;
        if (data[i] == '-') {
            sign = -1;
            i++;
        }
        while (isdigit(data[i])) {
            rt = rt * 10 + data[i] - '0';
            i++;
        }
        i++;
        return rt * sign;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data == "n") return NULL;
        queue<TreeNode *> que;
        int i = 0;
        TreeNode *root = new TreeNode(next(data,i));
        que.push(root);
        
        while (!que.empty()) {
            TreeNode* t = que.front();
            que.pop();
            
            if (isdigit(data[i]) || data[i] == '-') {
                t->left = new TreeNode(next(data,i));
                que.push(t->left);
            }else {
                i++;
            }
            
            if (isdigit(data[i]) || data[i] == '-') {
                t->right = new TreeNode(next(data,i));
                que.push(t->right);
            }else {
                i++;
            }
        }
        
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "";
        
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        
        while (!que.isEmpty()) {
            TreeNode top = que.poll();
            if (top == null) {
                sb.append("n").append(",");
            } else {
                sb.append(top.val).append(",");
                que.add(top.left);
                que.add(top.right);
            }
        }
        
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) {
            return null;
        }
        List<String> l = Arrays.asList(data.split(","));
        Queue<TreeNode> que = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(l.get(0)));
        que.add(root);
        for (int i = 1; i < l.size(); i += 2) {
            TreeNode node = que.poll();
            if (l.get(i).equals("n")) {
                node.left = null;
            } else {
                TreeNode left = new TreeNode(Integer.parseInt(l.get(i)));
                node.left = left;
                que.add(left);
            }
            if (l.get(i + 1).equals("n")) {
                node.right = null;
            } else {
                TreeNode right = new TreeNode(Integer.parseInt(l.get(i + 1)));
                node.right = right;
                que.add(right);
            }
        }
        
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (root == NULL) {
            return "n";
        }
        string rt = to_string(root->val) + ",";
        rt += serialize(root->left) + serialize(root->right);
        return rt;
    }

    TreeNode *helper(string &s, int &i) {
        if (i == s.length()) return NULL;
        if (s[i] == 'n') {
            i++;
            return NULL;
        }
        
        int sign = 1;
        if (s[i] == '-') {
            sign = -1;
            i++;
        }
        int rt = 0;
        while (isdigit(s[i])) {
            rt = rt * 10 + s[i] - '0';
            i++;
        }
        i++;
        
        TreeNode *root = new TreeNode(rt * sign);
        root->left = helper(s,i);
        root->right = helper(s,i);
        return root;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int i = 0;
        return helper(data,i);
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        buildString(root, sb);
        return sb.toString();
    }
    
    private void buildString(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append("n").append(",");
            return;
        }
        
        sb.append(root.val).append(",");
        buildString(root.left, sb);
        buildString(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        List<String> s = Arrays.asList(data.split(","));
        return toNode(s);
    }
    
    private int index = 0;
    private TreeNode toNode(List<String> s) {
        if (s.get(index).equals("n")) {
            index++;
            return null;
        }
        
        TreeNode node = new TreeNode(Integer.parseInt(s.get(index)));
        index++;
        node.left = toNode(s);
        node.right = toNode(s);
        
        return node;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

Bulls and Cows

You are playing the following Bulls and Cows game with your friend: You write a 4-digit secret number and ask your friend to guess it. Each time your friend guesses a number, you give a hint. The hint tells your friend how many digits are in the correct positions (called "bulls") and how many digits are in the wrong positions (called "cows"). Your friend will use those hints to find out the secret number.

For example:

Secret number:  "1807"
Friend's guess: "7810"

Hint: 1 bull and 3 cows. (The bull is 8, the cows are 0, 1 and 7.)

Write a function to return a hint according to the secret number and friend's guess, use A to indicate the bulls and B to indicate the cows. In the above example, your function should return "1A3B".

Please note that both secret number and friend's guess may contain duplicate digits, for example:

Secret number:  "1123"
Friend's guess: "0111"

In this case, the 1st 1 in friend's guess is a bull, the 2nd or 3rd 1 is a cow, and your function should return "1A1B".

You may assume that the secret number and your friend's guess only contain digits, and their lengths are always equal.

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

class Solution {
public:
    string getHint(string secret, string guess) {
        vector<int> upper(256,0);
        vector<int> lower(256,0);
        int bull = 0, cow = 0;
        
        for (int i = 0; i < guess.length(); i++) {
            if (secret[i] == guess[i]) {
                bull++;
            }else {
                if (upper[guess[i]] > 0) {
                    cow++;
                    upper[guess[i]]--;
                }else {
                    lower[guess[i]]++;
                }
                
                if (lower[secret[i]] > 0) {
                    cow++;
                    lower[secret[i]]--;
                }else {
                    upper[secret[i]]++;
                }
            }
        }
        
        return to_string(bull) + "A" + to_string(cow) + "B";
    }
};

Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

--------------------------------------------------------------
Solution #1, dp[i] 里存的是以i为后一位的，[0, i]之间的最长递增subsequence

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n,1);
        int len = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            len = max(len, dp[i]);
        }
        
        return len;
    }
};

Solution #2, N(lg N)
ref: http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/
原理：
假设我们有[100, 101, 102, 1, ......], 当处理到[3]的时候，我们不能把前3位的信息抛弃，只有当以1开头的subsequence长度>= 3时，才能将之前的3位丢掉。这时一个方法是把所有的subsequence信息都记录下来，然后每次对比长度。另一个方法就是下面这个，进行元素替换。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        vector<int> arr(1,nums[0]);
        
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] < arr[0]) {
                arr[0] = nums[i];
            }else if (nums[i] > arr.back()) {
                arr.push_back(nums[i]);
            }else {
                int low = 0, high = arr.size() - 1;
                while (low <= high) {
                    int mid= (low + high) / 2;
                    if (mid > 0 && arr[mid - 1] <= nums[i] && arr[mid] > nums[i]) {
                        arr[mid] = nums[i];
                        break;
                    }
                    if (arr[mid] < nums[i]) {
                        low = mid + 1;
                    }else {
                        high = mid - 1;
                    }
                }
            }
        }
        
        return arr.size();
    }
};

Remove Invalid Parentheses

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples:

"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]

--------------------------------------------------
都是brute force，以下为bfs

class Solution {
public:
    bool isValid(string s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(') count++;
            if (s[i] == ')') count--;
            if (count < 0) return false;
        }
        
        return count == 0;
    }

    vector<string> removeInvalidParentheses(string s) {
        queue<string> que;
        unordered_set<string> dic;
        que.push(s);
        dic.insert(s);
        vector<string> rt;
        bool found = false;
        
        while (!que.empty()) {
            string str = que.front();
            que.pop();
            if (isValid(str)) {
                rt.push_back(str);
                found = true;
            }
            
            if (found) continue;
            
            for (int i = 0; i < str.length(); i++) {
                if (str[i] != '(' && str[i] != ')') continue;
                
                string newStr = str.substr(0,i) + str.substr(i + 1);
                if (dic.find(newStr) == dic.end()) {
                    que.push(newStr);
                    dic.insert(newStr);
                }
            }
        }
        
        return rt;
    }
};

dfs, ref: http://blog.csdn.net/foreverling/article/details/49740665
remove the minimum number等于是建立一个最长的有效括号字符串

class Solution {
public:
    void dfs(vector<string> &rt, string s, string curS, int left, int totalLeft, int &maxLen, unordered_set<string> &dic) {
        if (s.length() == 0) {
            if (left == 0 && totalLeft > maxLen) {
                maxLen = totalLeft;
            }
            if (left == 0 && maxLen == totalLeft && dic.find(curS) == dic.end()) {
                rt.push_back(curS);
                dic.insert(curS);
            }
            return;
        }
        
        if (s[0] == '(') {
            dfs(rt,s.substr(1), curS + '(', left + 1, totalLeft + 1, maxLen,dic);
            dfs(rt,s.substr(1), curS, left, totalLeft, maxLen,dic);
        }else if (s[0] == ')') {
            if (left > 0) {
                dfs(rt,s.substr(1), curS + ')', left - 1, totalLeft, maxLen,dic);
            }
            dfs(rt, s.substr(1), curS, left, totalLeft, maxLen,dic);
        }else {
            dfs(rt, s.substr(1), curS + s[0], left, totalLeft, maxLen,dic);
        }
    }

    vector<string> removeInvalidParentheses(string s) {
        vector<string> rt;
        unordered_set<string> dic;
        int maxLen = 0;
        dfs(rt,s,"",0,0,maxLen,dic);
        
        return rt;
    }
};

Solution #3, in Java

1. 先预处理，计算出为了得到合法的String，最少需要移除多少个左、右括号 
2. 依次移除右、左括号，并递减计数。 
3. 先移除右括号是为了剪枝，如')(()',虽然不影响最后结果 
4. 加isValid是为了解决'()()()(' -> '()())(' 
5. ref: http://zxi.mytechroad.com/blog/searching/leetcode-301-remove-invalid-parentheses/

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        int left = 0, right = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {                
                left++;
            }else  if (s.charAt(i) == ')') {
                if (left == 0) {
                    right++;
                } else {
                    left--;
                }
            }
        }
        
        List<String> rt = new ArrayList<>();
        dfs(new StringBuilder(s),0,left,right,rt);
        return rt;
    }
    
    public void dfs(StringBuilder s, int index, int left, int right, List<String> rt) {
        if (right == 0 && left == 0 && isValid(s)) {
            rt.add(s.toString());
            return;
        }
        
        for (int i = index; i < s.length(); i++) {
            
            if (i != index && s.charAt(i) == s.charAt(i - 1)) continue;
            
            if (right > 0 && s.charAt(i) == ')') {                
                StringBuilder s1 = new StringBuilder(s);
                s1.deleteCharAt(i);
                dfs(s1, i, left, right - 1, rt);
            } else if (right == 0 && left > 0  && s.charAt(i) == '(') {                
                StringBuilder s1 = new StringBuilder(s);
                s1.deleteCharAt(i);
                dfs(s1, i, left - 1, right, rt);
            } 
        }
    }
    
    public boolean isValid(StringBuilder s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                count++;
            } 
            if (c == ')') {
                count--;
            }
            if (count < 0) {
                return false;
            }
        }
        
        return count == 0;
    }
}