Surrounded Regions

from codeganker
这个题目用到的方法是图形学中的一个常用方法：Flood fill算法，其实就是从一个点出发对周围区域进行目标颜色的填充。背后的思想就是把一个矩阵看成一个图的结构，每个点看成结点，而边则是他上下左右的相邻点，然后进行一次广度或者深度优先搜索。
接下来我们看看这个题如何用Flood fill算法来解决。首先根据题目要求，边缘上的'O'是不需要填充的，所以我们的办法是对上下左右边缘做Flood fill算法， 把所有边缘上的'O'都替换成另一个字符，比如'#'。接下来我们知道除去被我们换成'#'的那些顶点，剩下的所有'O'都应该被替换成'X'，而'#' 那些最终应该是还原成'O'，如此我们可以做最后一次遍历，然后做相应的字符替换就可以了。复杂度分析上，我们先对边缘做Flood fill算法， 因为只有是'O'才会进行，而且会被替换成'#'，所以每个结点改变次数不会超过一次，因而是O(m*n)的复杂度，最后一次遍历同样是O(m*n)，所 以总的时间复杂度是O(m*n)。空间上就是递归栈（深度优先搜索）或者是队列（广度优先搜索）的空间，同时存在的空间占用不会超过O(m+n)（以广度 优先搜索为例，每次队列中的结点虽然会往四个方向拓展，但是事实上这些结点会有很多重复，假设从中点出发，可以想象最大的扩展不会超过一个菱形，也就是 n/2*2+m/2*2=m+n，所以算法的空间复杂度是O(m+n)）。

class Solution {
public:
    void solve(vector<vector<char>> & board) {
    if(board.size()<=1 || board[0].size()<=1)
        return;
    for(int i=0;i<board[0].size();i++)
    {
        fill(board,0,i);
        fill(board,board.size()-1,i);
    }
    for(int i=0;i<board.size();i++)
    {
        fill(board,i,0);
        fill(board,i,board[0].size()-1);
    }
    for(int i=0;i<board.size();i++)
    {
        for(int j=0;j<board[0].size();j++)
        {
            if(board[i][j]=='O')
                board[i][j]='X';
            else if(board[i][j]=='#')
                board[i][j]='O';               
        }
    }
}
void fill(vector<vector<char>> & board, int i, int j)
{
    if(board[i][j]!='O')
        return;
    board[i][j] = '#';
    queue<int> queue;
    int code = i*board[0].size()+j;
    const int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    queue.push(code);
    while(!queue.empty())
    {
        code = queue.front();queue.pop();
        int row = code/board[0].size();
        int col = code%board[0].size();
        for(int i=0;i<4;i++){
            int currow=row+dir[i][0];
            int curcol=col+dir[i][1];
            if(currow>=0&&currow<board.size()&&curcol>=0&&curcol<board[0].size()){
                if(board[currow][curcol]=='O'){
                    board[currow][curcol]='#';
                    queue.push(currow*board[0].size()+curcol);
                }
            }
        }
       
    }
}
};

//another flavor, from anniekim
class Solution {
public:
    typedef vector<vector<char> > BOARDTYPE;
   
    void solve(BOARDTYPE &board) {
        if (board.empty() || board[0].empty()) return;
        int N = board.size(), M = board[0].size();
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < M; ++j)
                if (i == 0 || j == 0 || i == N-1 || j == M-1)
                    bfs(board, i, j); // you may call dfs or bfs here!
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < M; ++j)
                board[i][j] = (board[i][j] == 'V') ? 'O' : 'X';
    }
   
    void dfs(BOARDTYPE &board, int row, int col) {
        int N = board.size(), M = board[0].size();
        if (row < 0 || row >= N || col < 0 || col >= M) return;
        if (board[row][col] != 'O') return;
        board[row][col] = 'V';
        dfs(board, row+1, col);
        dfs(board, row-1, col);
        dfs(board, row, col+1);
        dfs(board, row, col-1);
    }

    void bfs(BOARDTYPE &board, int row, int col) {
        if (board[row][col] != 'O') return;
        int N = board.size(), M = board[0].size();
        queue<pair<int, int>> q;
        q.push(make_pair(row, col));
        while (!q.empty())
        {
            int i = q.front().first, j = q.front().second;
            q.pop();
            if (i < 0 || i >= N || j < 0 || j >= M) continue;
            if (board[i][j] != 'O') continue;// important to recheck!
            board[i][j] = 'V';
            q.push(make_pair(i-1, j));
            q.push(make_pair(i+1, j));
            q.push(make_pair(i, j-1));
            q.push(make_pair(i, j+1));
        }
    }
};

Word Search

 dfs
class Solution {
public:
    bool exist(vector<vector<char> > &board, string word) {
        if(board.size()==0) return false;
        if(word.length()==0) return true;
       
        int row=board.size(),col=board[0].size();
         vector<vector<bool>>used(row,vector<bool>(col,false));
        
         for(int i=0;i<row;i++)
            for(int j=0;j<col;j++)
               if(search(board,word,0,i,j,used))
                return true;
        return false;       
       
       
    }
    bool search(vector<vector<char> > &board, string word, int index,int i,int j, vector<vector<bool>>&used){
        if(index==word.length()) return true;
        if(i<0||j<0||i>=board.size()||j>=board[0].size()||used[i][j]||word[index]!=board[i][j])
            return false;
        used[i][j]=true;   
        bool res=search(board,word,index+1,i-1,j,used)
               ||search(board,word,index+1,i+1,j,used)
               ||search(board,word,index+1,i,j-1,used)
               ||search(board,word,index+1,i,j+1,used);
       
        used[i][j]=false;
        return res;
        //the above two line can be replaced by:
        //if(res) return true;
        //used[i][j]=false;
        //return false;
    }
};


//another flavor
public boolean exist(char[][] board, String word) {
    if(board == null) return false;
    if(word == null || word.length() == 0) return true;
    boolean [][] visited = new boolean[board.length][board[0].length];
    for(int i = 0; i < board.length; i++)
        for(int j = 0; j < board[0].length; j++)
            if(DFS(board, i, j, word, 0, visited)) return true;
    return false;
}
public boolean DFS(char[][] b, int i, int j, String word, int index, boolean[][] v){
    if(v[i][j] || b[i][j] != word.charAt(index)) return false;
    if(index == word.length() - 1) return true;
    v[i][j] = true;
    if(i != 0 && DFS(b, i - 1, j, word, index + 1, v)) return true;                  
    if(i != b.length - 1 && DFS(b, i + 1, j, word, index + 1, v)) return true;
    if(j != 0 && DFS(b, i, j - 1, word, index + 1, v)) return true;
    if(j != b[0].length - 1 && DFS(b, i, j + 1, word, index + 1, v)) return true;
    v[i][j] = false;
    return false;
}

Clone Graph

dfs or bfs

//dfs

class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        unordered_map<UndirectedGraphNode *,UndirectedGraphNode *> nodeMap;
        return cloneGraph(node,nodeMap);
    }

    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node,unordered_map<
        UndirectedGraphNode *,UndirectedGraphNode *>& nodeMap ){

            if(!node) return NULL;

            if(nodeMap.count(node) > 0)
                return nodeMap[node];

            UndirectedGraphNode *newNode = new UndirectedGraphNode(node->label);

            nodeMap[node] = newNode;

            for(auto it = (node->neighbors).begin(); it != (node->neighbors).end(); ++it){
                (newNode->neighbors).push_back( cloneGraph(*it,nodeMap) );
            }

            return newNode;

    }

};


//bfs
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if(!node) return NULL;
        UndirectedGraphNode *clnode=new UndirectedGraphNode(node->label);
        unordered_map<UndirectedGraphNode *,UndirectedGraphNode *> map;
        map[node]=clnode;
        queue<UndirectedGraphNode *> que;
        que.push(node);
        while(!que.empty()){
            UndirectedGraphNode *current=que.front();que.pop();
            for(auto it=current->neighbors.begin();it!=current->neighbors.end();it++){
                if(map.find(*it)==map.end()){
                    UndirectedGraphNode *neibor=new UndirectedGraphNode((*it)->label);
                    map[*it]=neibor;
                    map[current]->neighbors.push_back(neibor);
                    que.push(*it);
                }else{
                    map[current]->neighbors.push_back(map[*it]);
                }
               
            }
        }
        return clnode;
}

Path Sum II

 //dfs
class Solution {
public:
    vector<vector<int> > pathSum(TreeNode *root, int sum) {
        vector<vector<int> >ret;
        vector<int> path;
        pathSum(root,sum,ret,path);
        return ret;
    }
    void pathSum(TreeNode *root, int sum,vector<vector<int> >&ret,vector<int>&path) {
        if(!root)
            return ;
        path.push_back(root->val);   
        if(root->left==NULL&&root->right==NULL&&root->val==sum)
        {
            ret.push_back(path);
            path.pop_back();
            return;
        }

        pathSum(root->left,sum-root->val,ret,path);
        pathSum(root->right,sum-root->val,ret,path);
        path.pop_back();
    }

};

Minimum Depth of Binary Tree

two methods:1)recursion. 2) use queue, level order traverse
//from anniekim
    int minDepth(TreeNode *root) {
        if(!root) return 0;
        if(!root->left)
            return 1+minDepth(root->right);
        if(!root->right)
            return 1+minDepth(root->left);
        return 1+min(minDepth(root->left),minDepth(root->right));
    }

    int minDepth(TreeNode *root) {
        if (!root) return 0;
        queue<TreeNode *> q;
        q.push(root);
        q.push(NULL);
        int depth = 1;
        while (true)
        {
            TreeNode *node = q.front();
            q.pop();
            if (!node) {
                depth++;
                q.push(NULL);
            } else {
                if (!node->left && !node->right) return depth;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
    }



// another flavor of using queue

int minDepth(TreeNode *root) {
    if(!root)
        return 0;
    queue<TreeNode*> aQueue;
    aQueue.push(root);
    int curdep=1;
    int curlevel=1;
    int nexlevel=0;
    while(!aQueue.empty())
    {
        TreeNode*pointer=aQueue.front();
        aQueue.pop();
        curlevel--;
        if(pointer->left==NULL&&pointer->right==NULL)
            return curdep;
        if(pointer->left)
            {aQueue.push(pointer->left);nexlevel++;}
        if(pointer->right)
            {aQueue.push(pointer->right);nexlevel++;}
        if(curlevel==0) 
            {curdep++;swap(curlevel,nexlevel);    }
    }
}
int minDepth(TreeNode *root) {
    if (!root) return 0;
    queue<TreeNode *> q;
    q.push(root);
    TreeNode * rightmost = root;
    int depth = 1;
    while (!q.empty())
    {
        TreeNode *node = q.front();
        q.pop();
        if (!node->left && !node->right) return depth;
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
        if (node == rightmost) {
            ++depth;
            rightmost = node->right?node->right:node->left;
        }
    }
}