Surrounded Regions

Given a 2D board containing ‘X‘ and ‘O‘, capture all regions surrounded by ‘X‘.

A region is captured by flipping all ‘O‘s into ‘X‘s in that surrounded region.

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

分析：这个题花了不少时间，最后才弄明白怎么做，开始想着判断每个是O的点的上下左右是否是X来断定是否是被围绕的区域，这是明显不对的；然后再考虑遍历二维矩阵，如果元素为O，则判断O是否是被围绕的区域，如果是将此处的值改为X，如果不是将此处的值改为另一个标志‘D’，这样每次求解可以根据点的上下左右来判断，但是这样忽略了当右下角为O的情况；后来改进算法，改为先判断上面一个点和左边一个点，如果其中一个为‘D’，则肯定不能被围绕，然后判断右边和下面的点，如果为‘O’，则递归为求解右边和下边的点的与，这样超时了。

最后搜索到一种方法，遍历二维矩阵，每次遇到‘O’点时找到与此点在同一个连通域的‘O‘，都将其替换为‘P‘，判断此连通域是否有点在边界上，如果有则将所有的点都变换为‘D‘，如果没有则将所有的点都变换为‘X‘。遍历结束后，再将所有‘D‘转换为‘O’。

Accepted 代码如下：

class Solution {
public:
	void solve(vector<vector<char>> &board) {
	    int rows = board.size();
	    if(rows <= 2){
	        return;
	    }
	    int cols = board[0].size();
	    if(cols <= 2){
	        return;
	    }
	    for(int i=0; i<rows; ++i){
	        for(int j=0; j<cols; ++j){
	            if(board[i][j] == ‘O‘){
	                bool isSurr = isSurround(board,i,j);
	                replaceSurround(board,isSurr);
	            }
	        }
	    }
	    //将D替换为O
	    for(int i=0; i<rows; ++i){
	        for(int j=0; j<cols; ++j){
	            if(board[i][j] == ‘D‘){
	                board[i][j] = ‘O‘;
	            }
	        }
	    }
	}
	//判断(m,n)坐标是否被环绕，同时将与(m,n)联通的区域标志为‘P‘
    bool isSurround(vector<vector<char>> &board,int m,int n){
        bool hasPath = false;
        board[m][n] = ‘P‘;
        int rows = board.size();
        int cols = board[0].size();
        for(int i=0; i<rows; ++i){
            for(int j=0; j<cols; ++j){
                if(board[i][j] == ‘P‘){
                    if(i == 0){
                        hasPath = true;
                        //return false;
                    }else{
                        if(board[i-1][j] == ‘O‘){
                            board[i-1][j] = ‘P‘;
                            i -= 2;  //注意为i=i-2,因为(i-1,j)已经做出判断了,下次判断(i-2,j)的部分
                            break;  //注意为break,更改了i的值，跳出j的循环
                        }
                    }
                    if(j == 0){
                        hasPath = true;
                        //return false;
                    }else{
                        if(board[i][j-1] == ‘O‘){
                            board[i][j-1] = ‘P‘;
                            j -= 2;
                            continue;
                        }
                    }
                    if(i == rows-1){
                        hasPath = true;
                        //return false;
                    }else{
                        if(board[i+1][j] == ‘O‘){
                            board[i+1][j] = ‘P‘;
                        }
                    }
                    if(j == cols-1){
                        hasPath = true;
                        //return false;
                    }else{
                        if(board[i][j+1] == ‘O‘){
                            board[i][j+1] = ‘P‘;
                        }
                    }
                }
            }
        }
        return hasPath ? false:true;
    }
    //更新联通区域标志为P的点，如果被环绕更新为X,如果不被环绕更新为D
    void replaceSurround(vector<vector<char>> &board,bool isSurrounded){
        for(int i=0; i<board.size(); ++i){
            for(int j=0; j<board[i].size(); ++j){
                if(board[i][j] == ‘P‘){
                    if(isSurrounded){
                        board[i][j] = ‘X‘;
                    }else{
                        board[i][j] = ‘D‘;
                    }
                }
            }
        }
    }
};

2、Sum Root to Leaf Numbers 

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   /   2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

分析：这个题很简单，就是简单的递归。

代码如下：

class Solution {
public:
    int sumNumbers(TreeNode *root) {
        int sum = 0;
        allSum = 0;;
        path(root,sum);
        return allSum;
    }
    void path(TreeNode* root,int sum){
        if(root == NULL){
            return;
        }else{
            sum = sum*10 + root->val;
            if(!root->left && !root->right){
                allSum += sum;
                return;
            }
            if(root->left){
                path(root->left,sum);
            }
            if(root->right){
                path(root->right,sum);
            }
        }
    }
    int allSum;
};

3、Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

分析：首先不考虑复杂度时，要求连续数的长度，首先考虑到先把数组排序，从头开始，看序列的长度，此时可以采用multiset来实现；但是看到O(n)的复杂度，想到的是set是用红黑树实现的，复杂度为O(nlogn)，但是哈希表结构是未排序的，当遍历到一个值时，需要判断小于此值和大于此值的值是否存在，如果不存在还得继续遍历，还需要保存前一个值，比较复杂，而且hash_map不在C++标准库中，一直显示‘hash_multimap‘ was not declared in this scope

因此采用了multiset，结果是Accepted，但是从内部结构来说却是时间复杂度为O(nlogn)

代码如下：

class Solution {
public:

	int longestConsecutive(vector<int> &num) {
		if(num.size() <= 1){
			return num.size();
		}
		multiset<int> numSet;
		for(int i=0; i<num.size(); ++i){
			numSet.insert(num[i]);
		}
		int maxLen = 1;
		for(multiset<int>::iterator iter=numSet.begin(); iter!=numSet.end(); ){
			int tempLen = 1;
			while(iter!=numSet.end()){
				int nextVal = *iter , curVal = *iter;
				while(curVal == nextVal){
					curVal = *iter;
					if(++iter == numSet.end()){
						if(tempLen > maxLen){
							maxLen = tempLen;
						}
						return maxLen;
					}
					nextVal = *iter;
				}
				--iter;
				curVal = *iter;
				++iter;
				if(curVal+1 == nextVal){
					++tempLen;
				}else{
					break;
				}
			}
			if(tempLen > maxLen){
				maxLen = tempLen;
			}
		}
		return maxLen;
	}
};