Showing posts with label COME_BACK. Show all posts
Showing posts with label COME_BACK. Show all posts

Saturday, November 14, 2015

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

Tuesday, October 27, 2015

Day 131, #288 #289 #293 #294 #295 #298 Unique Word Abbreviation, Game of Life, Flip Game, Flip Game II, Find Median from Data Stream, Binary Tree Longest Consecutive Sequence

Unique Word Abbreviation
An abbreviation of a word follows the form <first letter><number><last letter>. Below are some examples of word abbreviations:
a) it                      --> it    (no abbreviation)

     1
b) d|o|g                   --> d1g

              1    1  1
     1---5----0----5--8
c) i|nternationalizatio|n  --> i18n

              1
     1---5----0
d) l|ocalizatio|n          --> l10n
Assume you have a dictionary and given a word, find whether its abbreviation is unique in the dictionary. A word's abbreviation is unique if no other word from the dictionary has the same abbreviation.
Example: 
Given dictionary = [ "deer", "door", "cake", "card" ]

isUnique("dear") -> false
isUnique("cart") -> true
isUnique("cane") -> false
isUnique("make") -> true
-----------------------------------------------------------------
COME_BACK
看清题意
class ValidWordAbbr {
public:
    string getAbre(string s) {
        int len = s.length();
        if (len > 1) {
            s = s[0] + to_string(len - 2) + s[len - 1];
        }
        return s;
    }
    
    ValidWordAbbr(vector<string> &dictionary) {
        for (int i = 0; i < dictionary.size(); i++) {
            string abre = getAbre(dictionary[i]);
            if (dic.find(abre) == dic.end()) {
                vector<string> second;
                second.push_back(dictionary[i]);
                dic[abre] = second;
            }else {
                dic[abre].push_back(dictionary[i]);
            }
        }
    }

    bool isUnique(string word) {
        string abre = getAbre(word);
        if (dic.find(abre) == dic.end()) return true;
        return dic[abre][0] == word && dic[abre].size() == 1;
    }
    
private:
    unordered_map<string,vector<string>> dic;
};


// Your ValidWordAbbr object will be instantiated and called as such:
// ValidWordAbbr vwa(dictionary);
// vwa.isUnique("hello");
// vwa.isUnique("anotherWord");

Game of Life
According to the Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."
Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):
  1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
  2. Any live cell with two or three live neighbors lives on to the next generation.
  3. Any live cell with more than three live neighbors dies, as if by over-population..
  4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
Write a function to compute the next state (after one update) of the board given its current state.
Follow up: 
  1. Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
  2. In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?
---------------------------------------------------------------------
额外空间
class Solution {
public:
    vector<int> row;
    vector<int> col; 
    bool isLive(int i, int j, int m, int n, vector<vector<int>>& board) {
        if (i < 0 || j < 0 || i == m || j == n) return false;
        return board[i][j];
    }

    void gameOfLife(vector<vector<int>>& board) {
        int m = board.size();
        int n = board[0].size();
        vector<vector<int>> rt(m, vector<int>(n));
        row = {-1,-1,-1,0,0,1,1,1};
        col = {-1,0,1,-1,1,-1,0,1};
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int numOfLives = 0;
                for (int k = 0; k < 8; k++) {
                    if (isLive(row[k] + i,col[k] + j, m, n, board)) {
                        numOfLives++;
                    }
                }
                
                if (numOfLives < 2 || numOfLives > 3) rt[i][j] = 0;
                else if (board[i][j] && numOfLives <= 3) rt[i][j] = 1;
                else if (numOfLives == 3) rt[i][j] = 1;
            }
        }
        board = rt;
    }
};

constant space
用-1来表示之前为0,现在为1. -2来表示之前为1,现在为0
0 -> -1 -> 1
1 -> -2 -> 0
class Solution {
public:
    vector<int> row;
    vector<int> col; 
    bool isLive(int i, int j, int m, int n, vector<vector<int>>& board) {
        if (i < 0 || j < 0 || i == m || j == n) return false;
        if (board[i][j] == 0 || board[i][j] == -1) return false; 
        return true;
    }

    void gameOfLife(vector<vector<int>>& board) {
        int m = board.size();
        int n = board[0].size();
        row = {-1,-1,-1,0,0,1,1,1};
        col = {-1,0,1,-1,1,-1,0,1};
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int numOfLives = 0;
                for (int k = 0; k < 8; k++) {
                    if (isLive(row[k] + i,col[k] + j, m, n, board)) {
                        numOfLives++;
                    }
                }
                
                if (board[i][j] && numOfLives < 2) board[i][j] = -2;
                else if (board[i][j] && (numOfLives == 3 || numOfLives == 2)) continue;
                else if (board[i][j] && numOfLives > 3) board[i][j] = -2;
                else if (numOfLives == 3) board[i][j] = -1;
            }
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == -1) board[i][j] = 1;
                if (board[i][j] == -2) board[i][j] = 0;
            }
        }
    }
};

Flip Game
You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip twoconsecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.
Write a function to compute all possible states of the string after one valid move.
For example, given s = "++++", after one move, it may become one of the following states:
[
  "--++",
  "+--+",
  "++--"
]
If there is no valid move, return an empty list [].
---------------------------------------------
class Solution {
public:
    vector<string> generatePossibleNextMoves(string s) {
        vector<string> rt;
        for (int i = 1; i < s.length(); i++) {
            if (s[i] == '+' && s[i - 1] == '+') {
                s[i] = '-';
                s[i - 1] = '-';
                rt.push_back(s);
                s[i] = '+';
                s[i - 1] = '+';
            }
        }
        
        return rt;
    }
};

Flip Game II
You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip twoconsecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.
Write a function to determine if the starting player can guarantee a win.
For example, given s = "++++", return true. The starting player can guarantee a win by flipping the middle "++" to become "+--+".
Follow up:
Derive your algorithm's runtime complexity.
--------------------------------------------------------------
递归
T(n) = n * T(n - 1)
        = n * (n - 1) * T(n - 2)
        = n * (n - 1) * (n - 2) * T(n - 3)
        ...
        = n!
class Solution {
public:
    bool canWin(string s) {
        for (int i = 1; i < s.length(); i++) {
            if (s[i] == '+' && s[i - 1] == '+') {
                s[i] = '-';
                s[i - 1] = '-';
                if (!canWin(s)) return true;
                s[i] = '+';
                s[i - 1] = '+';
            }
        }
        
        return false;
    }
};
COME_BACK
game theory的方法可以达到O(n^2)

Find Median from Data Stream
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
Examples: 
[2,3,4] , the median is 3
[2,3], the median is (2 + 3) / 2 = 2.5
Design a data structure that supports the following two operations:
  • void addNum(int num) - Add a integer number from the data stream to the data structure.
  • double findMedian() - Return the median of all elements so far.
For example:
add(1)
add(2)
findMedian() -> 1.5
add(3) 
findMedian() -> 2
---------------------------------------------------------------------------
2个queue,还有其他方法吗
一个TreeSet加2个指针,跟2个heap原理是一样的
class MedianFinder {
public:
    struct cmp {
        bool operator() (int i1, int i2) {
            return i1 > i2;
        }
    };
    
    // Adds a number into the data structure.
    void addNum(int num) {
        small.push(num);
        int temp = small.top();
        small.pop();
        large.push(temp);
        temp = large.top();
        large.pop();
        if (small.size() > large.size()) {
            large.push(temp);
        }else {
            small.push(temp);
        }
    }

    // Returns the median of current data stream
    double findMedian() {
        if ((small.size() + large.size()) % 2 == 0) {
            return (small.top() + large.top()) / 2.0;
        }else {
            return small.top();
        }
    }

private:
    priority_queue<int> small;
    priority_queue<int,vector<int>,cmp> large;
};

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf;
// mf.addNum(1);
// mf.findMedian();

Binary Tree Longest Consecutive Sequence
Given a binary tree, find the length of the longest consecutive sequence path.
The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).
For example,
   1
    \
     3
    / \
   2   4
        \
         5
Longest consecutive sequence path is 3-4-5, so return 3.
   2
    \
     3
    / 
   2    
  / 
 1
Longest consecutive sequence path is 2-3,not3-2-1, so return 2.
-------------------------------------------------------
/**
 * 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:
    void dfs(TreeNode* root, int cur, int &maxL, int target) {
        if (root == NULL) return;
        if (root->val == target) {
            cur++;
        }else {
            cur = 1;
        }
        maxL = max(maxL,cur);
        dfs(root->left, cur, maxL, root->val + 1);
        dfs(root->right, cur, maxL, root->val + 1);
    }

    int longestConsecutive(TreeNode* root) {
        int maxL = 0;
        if (root == NULL) return 0;
        dfs(root,0,maxL,root->val);
        return maxL;
    }
};

Friday, September 25, 2015

Day 130, #282 #286 Expression Add Operators, Walls and Gates

Expression Add Operators
Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.
Examples: 
"123", 6 -> ["1+2+3", "1*2*3"] 
"232", 8 -> ["2*3+2", "2+3*2"]
"105", 5 -> ["1*0+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []
---------------------------------------------------------------------------
COME_BACK
#1 这种for循环内的写法可以简化没有符合时的情况
如1234
1 _ 234
12_34
123_4
1234
-----------
from 1_234:
1_2_34
1_23_4
1_234
........

如果遇到“*”,则返回之前的操作(因为之前的运算符和值都已经存好)
1 + 2 * 3,之前 1 + 2已经算出为3,之前的运算符为+,值为2。然后此时 总值- 2 + 2 * 3
cur为当前的总值,op为之前运算符,val为上一步计算的值

class Solution {
public:
    int target;
    void dfs(vector<string> &rt,string num,int index,string sofar,long cur,string op,long val) {
        if (index == num.length() && target == cur) {
            rt.push_back(sofar);
        }
        
        for (int i = index; i < num.length(); i++) {
            string s = num.substr(index,i + 1 - index);
            if (s != to_string(stol(s))) continue;
            int now = stol(s);
            dfs(rt,num,i + 1,sofar + "+" + s,cur + now,"+",now);
            dfs(rt,num,i + 1,sofar + "-" + s,cur - now,"-",now);
            if (op == "-") {
                dfs(rt,num,i + 1,sofar + "*" + s,cur + val - val * now,op,val * now);
            }else if (op == "+") {
                dfs(rt,num,i + 1,sofar + "*" + s,cur - val + val * now,op,val * now);
            }else {
                dfs(rt,num,i + 1,sofar + "*" + s,val * now,op,val * now);
            }
        }
    }

    vector<string> addOperators(string num, int target) {
        vector<string> rt;
        this->target = target;
        
        for (int i = 1; i <= num.length(); i++) {
            string s = num.substr(0,i);
            if (s != to_string(stol(s))) continue;
            dfs(rt,num,i,s,stol(s),"",stol(s));
        }
        
        return rt;
    }
};

Walls and Gates
You are given a m x n 2D grid initialized with these three possible values.
  1. -1 - A wall or an obstacle.
  2. 0 - A gate.
  3. 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 than2147483647.
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.
For 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
------------------------------------------------------------------------
找出所有的gate,然后同时bfs

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        int m = rooms.size();
        if (m == 0) return;
        int n = rooms[0].size();
        queue<pair<int,int>> que;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rooms[i][j] == 0) {
                    que.push(make_pair(i,j));
                }
            }
        }
        
        int size = que.size();
        int dis = 1;
        while (!que.empty()) {
            int row = que.front().first;
            int col = que.front().second;
            size--;
            que.pop();
           
            if (row + 1 < m && rooms[row + 1][col] > dis) {
                rooms[row + 1][col] = dis;
                que.push(make_pair(row + 1,col));
            }
            if (row - 1 >= 0 && rooms[row - 1][col] > dis) {
                rooms[row - 1][col] = dis;
                que.push(make_pair(row - 1,col));
            }
            if (col + 1 < n && rooms[row][col + 1] > dis) {
                rooms[row][col + 1] = dis;
                que.push(make_pair(row,col + 1));
            }
            if (col - 1 >= 0 && rooms[row][col - 1] > dis) {
                rooms[row][col - 1] = dis;
                que.push(make_pair(row,col - 1));
            }
            
            if (size == 0) {
                size = que.size();
                dis++;
            }
        }
    }
};

Tuesday, September 22, 2015

Day 129, #277 #278 #281 #283 #284 #285 Find the Celebrity, First Bad Version, Zigzag Iterator, Move Zeroes, Peeking Iterator, Inorder Successor in BST

Find the Celebrity
Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1people know him/her but he/she does not know any of them.
Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: "Hi, A. Do you know B?" to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).
You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n), your function should minimize the number of calls to knows.
Note: There will be exactly one celebrity if he/she is in the party. Return the celebrity's label if there is a celebrity in the party. If there is no celebrity, return -1.
-------------------------------------------------------------------
COME_BACK
对a做检测,如果a认识b || b不认识a,a就不会是celebrity
// Forward declaration of the knows API.
bool knows(int a, int b);

class Solution {
public:
    int findCelebrity(int n) {
        for (int a = 0; a < n; a++) {
            int b = 0;
            for (; b < n; b++) {
                if (a == b) continue;
                if (knows(a,b) || !knows(b,a)) {
                    break;
                }
            }
            if (b == n) return a;
        }
        
        return -1;
    }
};
第一个循坏对can进行挑选,如果i不认识can,则说明can一定不是celebrity。如果i认识can,能说明i一定不是celebrity
// Forward declaration of the knows API.
bool knows(int a, int b);

class Solution {
public:
    int findCelebrity(int n) {
        int can = 0;
        for (int i = 1; i < n; i++) {
            if (!knows(i,can)) {
                can = i;
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (i == can) continue;
            if (!knows(i,can) || knows(can,i)) return -1;
        }
        
        return can;
    }
};

Java, 关键:
1. 所有人都认识celebrity(第二个for循环),如果谁不被人认识,那他就不是celebrity( 第一个for循环)
2. celebrity谁也不认识(第二个for循环)
/* The knows API is defined in the parent class Relation.
      boolean knows(int a, int b); */

public class Solution extends Relation {
    public int findCelebrity(int n) {
        int cand = 0;
        
        for (int i = 1; i < n; i++) {
            if (knows(cand, i)) {
                cand = i;
            }
        }
        
        for (int i = 0; i < n; i++) {
            if ((cand != i && knows(cand, i)) || !knows(i, cand)) return -1;
        }
        
        return cand;
    }
}

First Bad Version
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
------------------------------------------------------
Binary search
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            bool bad = isBadVersion(mid);
            if (bad && (mid == 1 || !isBadVersion(mid - 1))) return mid;
            if (bad) {
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        
        return -1;
    }
};

Java, recursion
/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        return rec(1, n);
    }
    
    private int rec(int left, int right) {
        if (left > right) return left;
        int mid = left + (right - left) / 2;
        boolean isBad = isBadVersion(mid);
        if (!isBad && isBadVersion(mid + 1)) {
            return mid + 1;
        }
        
        if (isBad) {
            return rec(left, mid - 1);
        }
        
        return rec(mid + 1, right);
    }
}

Zigzag Iterator
Given two 1d vectors, implement an iterator to return their elements alternately.
For example, given two 1d vectors:
v1 = [1, 2]
v2 = [3, 4, 5, 6]
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1, 3, 2, 4, 5, 6].
Follow up: What if you are given k 1d vectors? How well can your code be extended to such cases?
Clarification for the follow up question - Update (2015-09-18):
The "Zigzag" order is not clearly defined and is ambiguous for k > 2 cases. If "Zigzag" does not look right to you, replace "Zigzag" with "Cyclic". For example, given the following input:
[1,2,3]
[4,5,6,7]
[8,9]
It should return [1,4,8,2,5,9,3,6,7].
-------------------------------------------------------------
适用于k个
http://shibaili.blogspot.com/2015/08/notes-from-others.html
class ZigzagIterator {
public:
    ZigzagIterator(vector<int>& v1, vector<int>& v2) {
        v.push_back(v1);
        v.push_back(v2);
        zig = 0;
        itrs = vector<int>(v.size(),0);
    }

    int next() {
        hasNext();
        int rt = v[zig][itrs[zig]];
        itrs[zig]++;
        zig = (zig + 1) % v.size();
        return rt;
    }

    bool hasNext() {
        for (int i = 0; i < v.size(); i++) {
            if (itrs[zig] >= v[zig].size()) {
                zig = (zig + 1) % v.size();
            }else {
                return true;
            }
        }
        return false;
    }
private:
    vector<vector<int>> v;
    vector<int> itrs;
    int zig = 0;
};

/**
 * Your ZigzagIterator object will be instantiated and called as such:
 * ZigzagIterator i(v1, v2);
 * while (i.hasNext()) cout << i.next();
 */

Move Zeroes
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.
For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
Note:
  1. You must do this in-place without making a copy of the array.
  2. Minimize the total number of operations.

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

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int zero = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != 0) {
                swap(nums[i],nums[zero]);
                zero++;
            }
        }
    }
};

Peeking Iterator
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().

Here is an 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.
Hint:
  1. Think of "looking ahead". You want to cache the next element.
  2. Is one variable sufficient? Why or why not?
  3. Test your design with call order of peek() before next() vs next() before peek().
  4. For a clean implementation, check out Google's guava library source code.
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 {
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.
 }

    // Returns the next element in the iteration without advancing the iterator.
 int peek() {
        if (st.empty()) {
         st.push(Iterator::next());
     }
     return st.top();
 }

 // hasNext() and next() should behave the same as in the Iterator interface.
 // Override them if needed.
 int next() {
     if (st.empty()) return Iterator::next();
     int rt = st.top();
     st.pop();
     return rt;
 }

 bool hasNext() const {
     return !st.empty() || Iterator::hasNext();
 }
private:
    stack<int> st;
};

In Java
// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html
class PeekingIterator implements Iterator<Integer> {

    private Iterator<Integer> itr;
    private Integer next;
	public PeekingIterator(Iterator<Integer> iterator) {
	    // initialize any member here.
	    itr = iterator;
        next = itr.hasNext() ? itr.next() : null;
	}

    // 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 rt = next;
        next = itr.hasNext() ? itr.next() : null;
        return rt;
	}

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


Inorder Successor in BST
Given a binary search tree and a node in it, find the in-order successor of that node in the BST.
Note: If the given node has no in-order successor in the tree, return null.
------------------------------------------------
遍历
/**
 * 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:
    TreeNode *mostLeft(TreeNode *root) {
        while (root->left != NULL) {
            root = root->left;
        }
        return root;
    }

    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if (p->right != NULL) {
            return mostLeft(p->right);
        }
        
        TreeNode *suc = NULL;
        while (root != NULL) {
            if (root->val > p->val) {
                suc = root;
                root = root->left;
            }else {
                root = root->right;
            }
        }
        return suc;
    }
};

递归
/**
 * 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:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if (root == NULL) {
            return root;
        }
        if (root->val <= p->val) {
            return inorderSuccessor(root->right,p);
        }
        TreeNode *next = inorderSuccessor(root->left,p);
        if (next == NULL) return root;
        return next;
    }
};

Saturday, September 19, 2015

Day 127, #248 #249 #250 #252 #253 #254 #255 Strobogrammatic Number III, Group Shifted Strings, Count Univalue Subtrees, Meeting Rooms, Meeting Rooms II, Factor Combinations, Verify Preorder Sequence in Binary Search Tree

Strobogrammatic Number III
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.
For example,
Given low = "50", high = "100", return 3. Because 69, 88, and 96 are three strobogrammatic numbers.
Note:
Because the range might be a large number, the low and high numbers are represented as string.
-----------------------------------
类似 II。 对最后生成的数字跟low和high做对比,如果在范围内,count就加1
面试时不要用global variable
class Solution {
public:
    string low;
    string high;
    bool compareStrings(string &s1,string &s2) {
        if (s1.length() != s2.length()) return s1.length() < s2.length();
        for (int i = 0; i < s1.length(); i++) {
            if (s1[i] != s2[i]) return s1[i] < s2[i]; 
        }
        
        return true;
    }
    
    void helper(vector &rt,string s,int left,int right,int &count) {
        if (left > right) {
            if (s[0] != '0' && compareStrings(low,s) && compareStrings(s,high)) {
                count++;
            }
            return;
        }
        if (left != 0) {
            s[left] = '0',s[right] = '0';
            helper(rt,s,left + 1,right - 1,count);
        }
        s[left] = '1',s[right] = '1';
        helper(rt,s,left + 1,right - 1,count);
        s[left] = '8',s[right] = '8';
        helper(rt,s,left + 1,right - 1,count);
        if (left != right) {
            s[left] = '6',s[right] = '9';
            helper(rt,s,left + 1,right - 1,count);
            s[left] = '9',s[right] = '6';
            helper(rt,s,left + 1,right - 1,count);
        }
    }

    int strobogrammaticInRange(string low, string high) {
        this->low = low;
        this->high = high;
        int count = 0;
        vector rt;
        for (int i = low.length(); i <= high.length(); i++) {
            string s(i,'\0');
            helper(rt,s,0,i - 1,count);
        }
        if (low == "0") return count + 1;
        return count;
    }
};

Group Shifted Strings
Given a string, we can "shift" each of its letter to its successive letter, for example: "abc" -> "bcd". We can keep "shifting" which forms the sequence:
"abc" -> "bcd" -> ... -> "xyz"
Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.
For example, given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"],
Return:
[
  ["abc","bcd","xyz"],
  ["az","ba"],
  ["acef"],
  ["a","z"]
]
Note: For the return value, each inner list's elements must follow the lexicographic order.
-----------------------------------
注意:是string里的每一个字母都往后挪一次

class Solution {
public:
    vector<vector<string>> groupStrings(vector<string>& strings) {
        unordered_map<string,vector<string>> dic;
        for (int i = 0; i < strings.size(); i++) {
            string key = "";
            
            for (int j = 1; j < strings[i].length(); j++) {
                int diff = strings[i][j] - strings[i][j - 1];
                if (diff >= 0) {
                    key += to_string(diff) + ",";
                }else {
                    key += to_string(diff + 26) + ",";
                }
            }
            dic[key].push_back(strings[i]);
        }
        
        vector<vector<string>> rt;
        for (auto kv : dic) {
            vector<string> t = kv.second;
            sort(t.begin(),t.end());
            rt.push_back(t);
        }
        
        return rt;
    }
};

Count Univalue Subtrees
Given a binary tree, count the number of uni-value subtrees.
A Uni-value subtree means all nodes of the subtree have the same value.
For example:
Given binary tree,

              5
             / \
            1   5
           / \   \
          5   5   5


return 4.
--------------------------------------
uni-value subtree的定义是tree里所有的node都含有相同的值

/**
 * 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:
    string helper(TreeNode *root, int &count) {
        if (root == NULL) {
            return "";
        }
        
        string left = helper(root->left,count);
        string right = helper(root->right,count);
        string val = to_string(root->val);
        if ((left == "" || val == left) && (val == right || right == "")) {
            count++;
            return val;
        }
        return "#";
    }

    int countUnivalSubtrees(TreeNode* root) {
        if (root == NULL) return 0;
        int count = 0;
        helper(root,count);
        return count;
    }
};

Meeting Rooms
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.
For example,
Given [[0, 30],[5, 10],[15, 20]],
return false.
------------------------------------------

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    class Cmp {
    public:
        bool operator() (Interval &i1, Interval &i2) {
            if (i1.start == i2.start) {
                return i1.end < i2.end;
            }
            return i1.start < i2.start;
        }  
    };

    bool canAttendMeetings(vector<Interval>& intervals) {
        sort(intervals.begin(),intervals.end(),Cmp());
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i].start < intervals[i - 1].end) {
                return false;
            }
        }
        return true;
    }
};

Meeting Rooms II
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.
For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.
-------------------------------------
sort所有时间点,从头开始扫,如果是开始时间,count + 1。结束时间,count - 1

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    static bool cmp(int i1, int i2) {
        if (abs(i1) == abs(i2)) return i1 < i2;
        return abs(i1) < abs(i2);
    }

    int minMeetingRooms(vector<Interval>& intervals) {
        vector<int> times;
        for (int i = 0; i < intervals.size(); i++) {
            times.push_back(intervals[i].start);
            times.push_back(-intervals[i].end);
        }
        
        sort(times.begin(),times.end(),cmp);
        int minNumber = 0;
        int cur = 0;
        for (int i = 0; i < times.size(); i++) {
            if (times[i] >= 0) {
                cur++;
                minNumber = max(minNumber,cur);
            }else {
                cur--;
            }
        }
        
        return minNumber;
    }
};

Java, with PriorityQueue
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        if (intervals.length <= 1) return intervals.length;
        
        Arrays.sort(intervals, (a, b) -> a.start - b.start);
        PriorityQueue<Integer> q = new PriorityQueue<>();
        q.add(intervals[0].end);
        int size = 1;
        
        for (int i = 1; i < intervals.length; i++) {
            if (q.peek() <= intervals[i].start) {
                q.poll();
            }
            q.add(intervals[i].end);
            size = Math.max(size, q.size());
        }
        
        return size;
    }
}

Factor Combinations
Numbers can be regarded as product of its factors. For example,
8 = 2 x 2 x 2;
  = 2 x 4.
Write a function that takes an integer n and return all possible combinations of its factors.
Note: 
  1. Each combination's factors must be sorted ascending, for example: The factors of 2 and 6 is [2, 6], not [6, 2].
  2. You may assume that n is always positive.
  3. Factors should be greater than 1 and less than n.
Examples: 
input: 1
output: 
[]
input: 37
output: 
[]
input: 12
output:
[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]
input: 32
output:
[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]
--------------------------------------------------------
典型的combination,注意边界条件
class Solution {
public:
    void combination(vector> &rt, int n,vector v,int start,int orig) {
        if (n == 0 || start == orig) return;
        if (n == 1) {
            vector t = v;
            rt.push_back(t);
            return;
        }
        
        for (int i = start; i <= n; i++) {
            if (n % i != 0) continue;
            v.push_back(i);
            combination(rt,n / i,v,i,orig);
            v.pop_back();
        }
    }

    vector> getFactors(int n) {
        vector> rt;
        if (n == 1) return rt;
        vector v;
        combination(rt,n,v,2,n);
        return rt;
    }
};

Verify Preorder Sequence in Binary Search Tree
Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.
You may assume each number in the sequence is unique.
Follow up:
Could you do it using only constant space complexity?
------------------------------------------------------
用stack,有额外空间
#1 因为是preorder,一开始队列成递减(如果root没有左子树,则为只有一个元素的递减数列),压入所有遇到的node
#2 遇到拐点时说明此node为之前某一个node的右子树,则开始pop stack,直到找到之前的那个node,然后将minVal设好,pop掉的部分都为已经验证过的,符合bst条件的
#3 如果在遍历的过程中发现一个node的值小于minVal,则返回false

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        if (preorder.size() == 0) return true;
        stack<int> st;
        int minVal = INT_MIN;
        st.push(preorder[0]);
        
        for (int i = 1; i < preorder.size(); i++) {
            if (preorder[i] < minVal) return false;
            if (preorder[i] > preorder[i - 1]) {
                while (!st.empty() && preorder[i] > st.top()) {
                    minVal = st.top();
                    st.pop();
                }
            }
            
            st.push(preorder[i]);
        }
        
        return true;
    }
};
COME_BACK
O(1) 空间,run time complexity未知,最坏可能为O(n^2)
bool verifyPreorder(vector<int>& preorder) {
        if (preorder.size() == 0) return true;
        int minIndex = -1;
        int top = 0, end = 0;
        
        for (int i = 1; i < preorder.size(); i++) {
            if (minIndex != -1 && preorder[i] < preorder[minIndex]) return false;
            if (preorder[i] > preorder[i - 1]) {
                while (top >= end && preorder[i] > preorder[top]) {
                    minIndex = top;
                    top--;
                }
            }
            if (top < end) end = i;
            top = i;
        }
        
        return true;
    }