[LeetCode] Path Sum, Solution

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

» Solve this problem

[Thoughts]
二叉树遍历。遍历过程中累加节点值，当到达任意叶节点的时候，进行判断。


[Code]

1:       bool hasPathSum(TreeNode *root, int sum) {  
2:            return hasPathSum(root, 0, sum);      
3:       }  
4:       bool hasPathSum(TreeNode *root, int sum, int target) {  
5:            if(root == NULL) return false;  
6:            sum += root->val;  
7:            if(root->left == NULL && root->right == NULL) //leaf  
8:            {  
9:                 if(sum == target)  
10:                      return true;  
11:                 else  
12:                      return false;  
13:            }  
14:            return hasPathSum(root->left, sum, target)   
15:                   || hasPathSum(root->right, sum, target);      
16:       }  

[Interview] Serialize and De-serialize a tree

A very frequent interview question. Suppose you have a tree, how could you serialize it to file and revert it back?


for example,

                                               1
                                         /               \
                                        2                 3
                                             \          /    
                                             4        5    
                                          /       \
                                         6        7

[Thoughts]
一个比较简单直接的做法是，通过前序遍历来做，把所有空节点当做“#”来标示。那么这棵树可以表示为

                                               1
                                         /               \
                                        2                 3
                                     /       \          /      \
                                  #         4        5       #
                                          /       \
                                         6        7
                                     /      \     /    \
                                    #      #    #     #

那么前序遍历的结果就是： {'1','2','#','4','6','#','#','7','#','#','3','5','#','#','#'}; 代码如下：

void Serialize(TreeNode * node, vector<char> &output)

{

       if(node == NULL)

       {

             output.push_back('#');

             return;

       }

       output.push_back(node->val + '0');

       Serialize(node->left, output);

       Serialize(node->right, output);

}

而反序列化的代码也就是：

TreeNode *Deserialize(vector<char> output, int &index)

{

       if(index > output.size() || output[index] == '#') return NULL;

       TreeNode *node = new TreeNode(output[index] -'0');

       index ++;

       node->left = Deserialize(output, index);

       index++;

       node->right = Deserialize(output, index);

       return node;

}

这里只能通过前序遍历来做，中序及后序是行不通的。原因很简单，除了前序以外，其他遍历方式没办法找出头结点。

除了常规的三种遍历方式意外， 另一种可行的方法就是按层来遍历，同样可行。

[LeetCode] Convert Sorted Array to Binary Search Tree, Solution

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

» Solve this problem

[Thoughts]
If we build BST from array, we can build it from top to bottom, like
1. choose the middle one as root,
2. build left sub BST via left part array
3. build right sub BST via right part array
4. do this recursively.


[Code]

1:       TreeNode *sortedArrayToBST(vector<int> &num) {  
2:            return BuildTree(num, 0, num.size()-1);  
3:       }  
4:       TreeNode *BuildTree(vector<int> &num, int start, int end)  
5:       {  
6:            if(start>end) return NULL;  
7:            if(start == end) return new TreeNode(num[start]);  
8:            int mid = (start+end)/2;  
9:            TreeNode *node = new TreeNode(num[mid]);  
10:           node->left = BuildTree(num, start, mid-1);  
11:           node->right = BuildTree(num, mid+1, end);  
12:           return node;  
13:       }  

[LeetCode] Same Tree, Solution

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

» Solve this problem


[Thoughts]
递归判断左右子树是否相等。


[Code]

1:    bool isSameTree(TreeNode *p, TreeNode *q) {  
2:      if(!p && !q) return true;  
3:      if(!p || !q) return false;  
4:      return (p->val == q->val) &&  
5:           isSameTree(p->left, q->left) &&   
6:           isSameTree(p->right, q->right);      
7:    }  

[LeetCode] Unique Binary Search Trees II, Solution

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

» Solve this problem


[Thoughts]
分析请参看http://fisherlei.blogspot.com/2013/03/leetcode-unique-binary-search-trees.html
思路是一致的。划分左右子树，然后递归构造。

[Code]

1:       vector<TreeNode *> generateTrees(int n) {   
2:            if(n ==0) return generate(1,0);  
3:            return generate(1, n);  
4:       }       
5:       vector<TreeNode *> generate(int start, int end)  
6:       {  
7:            vector<TreeNode *> subTree;  
8:            if(start>end)  
9:            {  
10:                 subTree.push_back(NULL);  
11:                 return subTree;  
12:            }  
13:            for(int i =start; i<=end; i++)  
14:            {  
15:                 vector<TreeNode*> leftSubs = generate(start, i-1);  
16:                 vector<TreeNode*> rightSubs = generate(i+1, end);  
17:                 for(int j = 0; j< leftSubs.size(); j++)  
18:                 {  
19:                      for(int k=0; k<rightSubs.size(); k++)  
20:                      {  
21:                           TreeNode *node = new TreeNode(i);  
22:                           node->left = leftSubs[j];  
23:                           node->right = rightSubs[k];  
24:                           subTree.push_back(node);  
25:                      }  
26:                 }  
27:            }  
28:            return subTree;  
29:       }      

[Note]
写完第一个版本之后，立即发现一个严重的问题。上面的function存在大量的对象拷贝，因为所有变量都是在栈上开辟，所以返回值的时候都需要通过拷贝构造函数来重构vector，面试中这个疏忽是不应该的。

修改版，这里应该用指针及堆来存储变量。

1:       vector<TreeNode *> generateTrees(int n) {   
2:            if(n ==0) return *generate(1,0);  
3:            return *generate(1, n);  
4:       }  
5:       vector<TreeNode *>* generate(int start, int end)  
6:       {  
7:            vector<TreeNode *> *subTree = new vector<TreeNode*>();  
8:            if(start>end)  
9:            {  
10:                 subTree->push_back(NULL);  
11:                 return subTree;  
12:            }  
13:            for(int i =start; i<=end; i++)  
14:            {  
15:                 vector<TreeNode*> *leftSubs = generate(start, i-1);  
16:                 vector<TreeNode*> *rightSubs = generate(i+1, end);  
17:                 for(int j = 0; j< leftSubs->size(); j++)  
18:                 {  
19:                      for(int k=0; k<rightSubs->size(); k++)  
20:                      {  
21:                           TreeNode *node = new TreeNode(i);  
22:                           node->left = (*leftSubs)[j];  
23:                           node->right = (*rightSubs)[k];  
24:                           subTree->push_back(node);  
25:                      }  
26:                 }  
27:            }  
28:            return subTree;  
29:       }      

[LeetCode] Unique Binary Search Trees, Solution

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

» Solve this problem

[Thoughts]
这题想了好久才想清楚。其实如果把上例的顺序改一下，就可以看出规律了。
 1                1                      2                       3             3
    \                 \                 /      \                  /              /
      3               2              1       3               2             1
    /                   \                                       /                  \
 2                       3                                   1                    2

比如，以1为根的树有几个，完全取决于有二个元素的子树有几种。同理，2为根的子树取决于一个元素的子树有几个。以3为根的情况，则与1相同。

定义Count[i] 为以[0,i]能产生的Unique Binary Tree的数目，

如果数组为空，毫无疑问，只有一种BST，即空树，
Count[0] =1

如果数组仅有一个元素{1}，只有一种BST，单个节点
Count[1] = 1

如果数组有两个元素{1,2}， 那么有如下两种可能
1                       2
  \                    /
    2                1
Count[2] = Count[0] * Count[1]   (1为根的情况)
                  + Count[1] * Count[0]  (2为根的情况。

再看一遍三个元素的数组，可以发现BST的取值方式如下：
Count[3] = Count[0]*Count[2]  (1为根的情况)
               + Count[1]*Count[1]  (2为根的情况)
               + Count[2]*Count[0]  (3为根的情况)

所以，由此观察，可以得出Count的递推公式为
Count[i] = ∑ Count[0...k] * [ k+1....i]     0<=k<i-1
问题至此划归为一维动态规划。

[Code]

1:       int numTrees(int n) {  
2:            vector<int> count(n+1, 0);  
3:            count[0] =1;  
4:            count[1] =1;  
5:            for(int i =2; i<=n; i++)  
6:            {  
7:                 for(int j =0; j<i; j++)  
8:                 {  
9:                      count[i] += count[j]*count[i-j-1];   
10:                 }  
11:            }  
12:            return count[n];  
13:       }  

[Note]
这是很有意思的一个题。刚拿到这题的时候，完全不知道从那下手，因为对于BST是否Unique，很难判断。最后引入了一个条件以后，立即就清晰了，即
当数组为 1，2，3，4，.. i，.. n时，基于以下原则的BST建树具有唯一性：
以i为根节点的树，其左子树由[0, i-1]构成， 其右子树由[i+1, n]构成。

[LeetCode] Remove Duplicates from Sorted List II, Solution

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

» Solve this problem

[Thoughts]
实现题。前面加一个Safeguard，这样可以避免处理头结点的复杂。

[Code]

1:       ListNode *deleteDuplicates(ListNode *head) {  
2:            if(head == NULL) return head;  
3:            ListNode *G = new ListNode(INT_MIN);  
4:            G->next = head;  
5:            ListNode *cur = G, *pre = head;  
6:            while(pre!=NULL)  
7:            {  
8:                 bool isDup = false;  
9:                 while(pre->next!=NULL && pre->val == pre->next->val)  
10:                 {  
11:                      isDup = true;  
12:                      ListNode *temp = pre;  
13:                      pre = pre->next;  
14:                      delete temp;  
15:                 }  
16:                 if(isDup)  
17:                 {  
18:                      ListNode *temp = pre;  
19:                      pre = pre->next;  
20:                      delete temp;  
21:                      continue;  
22:                 }  
23:                 cur->next = pre;  
24:                 cur = cur->next;  
25:                 pre= pre->next;  
26:            }  
27:            cur->next = pre;  
28:            ListNode *temp = G->next;  
29:            delete G;  
30:            return temp;      
31:       }  

[LeetCode] Search a 2D Matrix, Solution

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

» Solve this problem

[Thoughts]
做两次二分就好了，首先二分第一列，找出target所在的行，然后二分该行。

[Code]

1:       bool searchMatrix(vector<vector<int> > &matrix, int target) {  
2:            int row = matrix.size();  
3:            if(row ==0) return false;  
4:            int col = matrix[0].size();  
5:            if(col ==0) return false;      
6:            if(target< matrix[0][0]) return false;  
7:            int start = 0, end = row-1;  
8:            while(start<= end)  
9:            {  
10:                 int mid = (start+end)/2;  
11:                 if(matrix[mid][0] == target)  
12:                      return true;  
13:                 else if(matrix[mid][0] < target)  
14:                      start = mid+1;  
15:                 else  
16:                      end = mid-1;  
17:            }  
18:            int targetRow = end;  
19:            start =0;  
20:            end = col-1;  
21:            while(start <=end)  
22:            {  
23:                 int mid = (start+end)/2;  
24:                 if(matrix[targetRow][mid] == target)  
25:                      return true;  
26:                 else if(matrix[targetRow][mid] < target)  
27:                      start = mid+1;  
28:                 else  
29:                      end = mid-1;  
30:            }  
31:            return false;  
32:       }  

注意，
二分的条件应该是（start<=end）， 而不是（start<end）。

[LeetCode] Merge Two Sorted Lists, Solution

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
» Solve this problem

[Thoughts]
简单的实现，也没什么可说的。

[Code]

1:    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {  
2:      if(l1 == NULL) return l2;  
3:      if(l2 == NULL) return l1;  
4:      ListNode *head = new ListNode(-1);  
5:      ListNode *p = head;  
6:      while(l1 != NULL && l2!=NULL)  
7:      {  
8:          if(l1->val < l2->val)  
9:          {  
10:             p->next = l1;  
11:             l1= l1->next;  
12:          }  
13:          else  
14:          {  
15:             p->next = l2;  
16:             l2 = l2->next;  
17:          }  
18:          p = p->next;  
19:      }  
20:      if(l1 != NULL)  
21:          p->next = l1;  
22:      if(l2 != NULL)  
23:          p->next = l2;  
24:      p = head->next;  
25:      delete head;  
26:      return p;      
27:    }  

Update 04/13/13 refactor code for succinct

1:       ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {  
2:            ListNode* head = new ListNode(-1);  
3:            ListNode* p = head;  
4:            while(l1!=NULL || l2!= NULL)  
5:            {  
6:                 int val1 = l1==NULL?INT_MAX:l1->val;  
7:                 int val2 = l2==NULL? INT_MAX:l2->val;  
8:                 if(val1<=val2)  
9:                 {  
10:                      p->next = l1;          
11:                      l1=l1->next;  
12:                 }  
13:                 else  
14:                 {  
15:                      p->next = l2;  
16:                      l2 = l2->next;  
17:                 }  
18:                 p= p->next;  
19:            }  
20:            p = head->next;  
21:            delete head;  
22:            return p;  
23:       }  

[LeetCode] Longest Valid Parentheses, Solution

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

» Solve this problem

[Thoughts]
维护一个栈，每次维护上一个可能的左边际。


[Code]

1:       int longestValidParentheses(string s) {  
2:            const char* str = s.c_str();  
3:            int nMax=0;  
4:            const char *p = str;  
5:            vector<const char*> sta;  
6:            while(*p !='\0')  
7:            {  
8:                 if(*p == '(')  
9:                 {  
10:                      sta.push_back(p);                      
11:                 }  
12:                 else  
13:                 {  
14:                      if(!sta.empty() && *sta.back()=='(')  
15:                      {  
16:                           sta.pop_back();  
17:                           nMax = max(nMax, p-(sta.empty()?str-1:sta.back()));  
18:                      }  
19:                      else  
20:                      {  
21:                           sta.push_back(p);  
22:                      }  
23:                 }  
24:                 p++;  
25:            }  
26:            return nMax;  
27:       }  

[LeetCode] Two Sum, Solution

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

» Solve this problem

[Thoughts]
两种解法。
解法一， hash
从左往右扫描一遍，然后将数及坐标，存到map中。然后再扫描一遍即可。时间复杂度O(n)

解法二，双指针扫描
将数组排序，然后双指针从前后往中间扫描。时间复杂度O(n*lgn)。因为是要求返回原数组的下标，所以在排序的时候还得有额外的数组来存储下标信息， 也挺麻烦。

解法三，暴力搜索
这个倒是最省事的。时间复杂度O(n*n)

解法一实现如下：

1:    vector<int> twoSum(vector<int> &numbers, int target) {  
2:      map<int, int> mapping;  
3:      vector<int> result;  
4:      for(int i =0; i< numbers.size(); i++)  
5:      {  
6:        mapping[numbers[i]]=i;  
7:      }  
8:      for(int i =0; i< numbers.size(); i++)  
9:      {  
10:        int searched = target - numbers[i];  
11:        if(mapping.find(searched) != mapping.end())  
12:        {  
13:          result.push_back(i+1);  
14:          result.push_back(mapping[searched]+1);  
15:          break;  
16:        }  
17:      }  
18:      return result;  
19:    }  

解法二

1:       struct Node  
2:       {  
3:            int val;  
4:            int index;      
5:            Node(int pVal, int pIndex):val(pVal), index(pIndex){}  
6:       };  
7:       static bool compare(const Node &left, const Node &right)  
8:       {  
9:            return left.val < right.val;  
10:       }  
11:       vector<int> twoSum(vector<int> &numbers, int target) {  
12:            vector<Node> elements;  
13:            for(int i =0; i< numbers.size(); i++)  
14:            {  
15:                 elements.push_back(Node(numbers[i], i));  
16:            }  
17:            std::sort(elements.begin(), elements.end(), compare);  
18:            int start = 0, end = numbers.size()-1;  
19:            vector<int> result;  
20:            while(start < end)  
21:            {  
22:                 int sum = elements[start].val + elements[end].val;  
23:                 if(sum == target)  
24:                 {  
25:                      result.push_back(elements[start].index+1);  
26:                      if(elements[start].index < elements[end].index)  
27:                           result.push_back(elements[end].index+1);  
28:                      else  
29:                           result.insert(result.begin(),elements[end].index+1);  
30:                      break;  
31:                 }  
32:                 else if(sum > target)  
33:                      end--;  
34:                 else  
35:                      start++;                 
36:            }  
37:            return result;  
38:       }  

解法三，两个循环嵌套搜索，不写了。

[LeetCode] Palindrome Partitioning II, Solution

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

» Solve this problem

[Thoughts]
凡是求最优解的，一般都是走DP的路线。这一题也不例外。首先求dp函数，

定义函数
D[i,n] = 区间[i,n]之间最小的cut数，n为字符串长度

 a   b   a   b   b   b   a   b   b   a   b   a
                     i                                  n
如果现在求[i,n]之间的最优解？应该是多少？简单看一看，至少有下面一个解


 a   b   a   b   b   b   a   b   b   a   b   a
                     i                   j   j+1     n

此时  D[i,n] = min(D[i, j] + D[j+1,n])  i<=j <n。这是个二维的函数，实际写代码时维护比较麻烦。所以要转换成一维DP。如果每次，从i往右扫描，每找到一个回文就算一次DP的话，就可以转换为
D[i] = 区间[i,n]之间最小的cut数，n为字符串长度， 则,

D[i] = min(1+D[j+1] )    i<=j <n

有个转移函数之后，一个问题出现了，就是如何判断[i,j]是否是回文？每次都从i到j比较一遍？太浪费了，这里也是一个DP问题。
定义函数
P[i][j] = true if [i,j]为回文

那么
P[i][j] = str[i] == str[j] && P[i+1][j-1];

基于以上分析，实现如下：

1:       int minCut(string s) {  
2:            int len = s.size();  
3:            int D[len+1];  
4:            bool P[len][len];  
5:            //the worst case is cutting by each char  
6:            for(int i = 0; i <= len; i++)   
7:            D[i] = len-i;  
8:            for(int i = 0; i < len; i++)  
9:            for(int j = 0; j < len; j++)  
10:            P[i][j] = false;  
11:            for(int i = len-1; i >= 0; i--){  
12:                 for(int j = i; j < len; j++){  
13:                      if(s[i] == s[j] && (j-i<2 || P[i+1][j-1])){  
14:                           P[i][j] = true;  
15:                           D[i] = min(D[i],D[j+1]+1);  
16:                      }  
17:                 }  
18:            }  
19:            return D[0]-1;  
20:       }  

或者可以考虑使用回溯+剪枝，比如：

1:    int minCut(string s) {  
2:      int min = INT_MAX;  
3:      DFS(s, 0, 0, min);  
4:      return min;  
5:    }  
6:    void DFS(string &s, int start, int depth, int& min)  
7:    {     
8:      if(start == s.size())  
9:      {  
10:        if(min> depth-1)  
11:          min = depth-1;  
12:        return;  
13:      }  
14:      for(int i = s.size()-1; i>=start; i--)  //find the biggest palindrome first
15:      {  
16:        if(isPalindrome(s, start, i))  
17:        {        
18:          DFS(s, i+1, depth+1, min);  
19:        }  
20:        if(min!=INT_MAX)  //if get result, then stop search.
21:          break;  
22:      }  
23:    }  
24:    bool isPalindrome(string &s, int start, int end)  
25:    {  
26:      while(start< end)  
27:      {  
28:        if(s[start] != s[end])  
29:          return false;  
30:        start++; end--;  
31:      }  
32:      return true;  
33:    }  

[LeetCode] Palindrome Partitioning, Solution

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

» Solve this problem

[Thoughts]
这种需要输出所有结果的基本上都是DFS的解法。实现如下。

[Code]

1:       vector<vector<string>> partition(string s) {  
2:            vector<vector<string>> result;  
3:            vector<string> output;  
4:            DFS(s, 0, output, result);  
5:            return result;  
6:       }  
7:       void DFS(string &s, int start, vector<string>& output, vector<vector<string>> &result)  
8:       {      
9:            if(start == s.size())  
10:            {  
11:                 result.push_back(output);  
12:                 return;  
13:            }  
14:            for(int i = start; i< s.size(); i++)  
15:            {    
16:                 if(isPalindrome(s, start, i))  
17:                 {  
18:                      output.push_back(s.substr(start, i-start+1));  
19:                      DFS(s, i+1, output, result);  
20:                      output.pop_back();  
21:                 }  
22:            }  
23:       }  
24:       bool isPalindrome(string &s, int start, int end)  
25:       {  
26:            while(start< end)  
27:            {  
28:                 if(s[start] != s[end])  
29:                 return false;  
30:                 start++; end--;  
31:            }  
32:            return true;  
33:       }  

[LeetCode] Surrounded Regions, Solution

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

» Solve this problem

[解题思路]
刚拿到这个题，首先得想法就是BFS。对于每一个O，扫描其相邻节点，然后标示之，如果一个联通区域中有任何一个O在边界上，则保留之，否则清除该联通域。实现代码如下：

1:    vector<int> xIndex;  
2:    vector<int> yIndex;  
3:    map<int, int> visited;  
4:    void solve(vector<vector<char>> &board) {  
5:      int row = board.size();  
6:      if(row == 0) return;  
7:      int col = board[0].size();  
8:      for(int i =0; i < row; i++)  
9:      {  
10:        for(int j =0; j< col; j++)  
11:        {  
12:          if(board[i][j] == 'X' || IsVisited(i*row+j)) continue;  
13:          visited.clear();  
14:          bool surranded = true;  
15:          xIndex.clear();  
16:          xIndex.push_back(i);  
17:          yIndex.clear();  
18:          yIndex.push_back(j);  
19:          int k =0;  
20:          while(k<xIndex.size())  
21:          {  
22:            int x = xIndex[k];  
23:            int y = yIndex[k];     
24:            visited[x*row +y] =1;  
25:            if(IsInBoundary(x, y, row, col)) surranded = false;  
26:            if(x<row-1 && board[x+1][y] == 'O' && !IsVisited((x+1)*row+y)) {xIndex.push_back(x+1); yIndex.push_back(y);}  
27:            if(y<col-1 && board[x][y+1] == 'O' && !IsVisited(x*row+y+1)) {xIndex.push_back(x); yIndex.push_back(y+1);}  
28:            k++;  
29:          }  
30:          if(surranded) //clean the surranded mask  
31:          {  
32:            for(int m = 0; m<xIndex.size(); m++)  
33:            {  
34:              board[xIndex[m]][yIndex[m]] = 'X';    
35:            }  
36:          }  
37:        }  
38:      }  
39:    }  
40:    bool IsInBoundary(int x, int y, int row, int col)  
41:    {  
42:      if(x ==0 || x == row-1) return true;  
43:      if(y ==0 || y == col-1) return true;  
44:      return false;  
45:    }  
46:    bool IsVisited(int index)  
47:    {  
48:      if(visited.find(index) == visited.end()) return false;  
49:      return true;  
50:    }  

小数据可以过，但是大数据提示Memory Limit Exceeded，代码中唯一用到的就是visited这个map，所以，系统期望的方法应该是不需要辅助空间的。

转换一下思路，真的需要开辟一个map在存储访问信息吗？其实这个可以省掉的，既然已经知道连通区域必须至少一个元素是在四边，那么一开始直接从四边开始扫描就好了，所以无法connect到得元素都是应该被清除的。所以，算法如下：
1. 从四条边上的O元素开始BFS，所有相连的O都赋个新值，比如‘Y’
2. 扫描整个数组，所有现存的O元素全部置为X，所有Y元素置为O
打完收工。代码实现如下：

1:       vector<int> xIndex;  
2:       vector<int> yIndex;  
3:       void solve(vector<vector<char>> &board) {  
4:            int row = board.size();  
5:            if(row == 0) return;  
6:            int col = board[0].size();  
7:            xIndex.clear();  
8:            yIndex.clear();            
9:            for(int i =0; i< row; i++)  
10:            {  
11:                 if(board[i][0] == 'O')  
12:                 {  
13:                      xIndex.push_back(i);  
14:                      yIndex.push_back(0);  
15:                 }  
16:                 if(board[i][col-1] == 'O')  
17:                 {  
18:                      xIndex.push_back(i);  
19:                      yIndex.push_back(col-1);  
20:                 }  
21:            }  
22:            for(int i =0; i< col; i++)  
23:            {  
24:                 if(board[0][i] == 'O')  
25:                 {  
26:                      xIndex.push_back(0);  
27:                      yIndex.push_back(i);  
28:                 }  
29:                 if(board[row-1][i] == 'O')  
30:                 {  
31:                      xIndex.push_back(row-1);  
32:                      yIndex.push_back(i);  
33:                 }  
34:            }            
35:            int k =0;  
36:            while(k<xIndex.size())  
37:            {  
38:                 int x = xIndex[k];  
39:                 int y = yIndex[k];     
40:                 board[x][y] = 'Y';  
41:                 if(x>0 && board[x-1][y] == 'O' ) {xIndex.push_back(x-1); yIndex.push_back(y);}  
42:                 if(x<row-1 && board[x+1][y] == 'O' ) {xIndex.push_back(x+1); yIndex.push_back(y);}                 
43:                 if(y>0 && board[x][y-1] == 'O' ) {xIndex.push_back(x); yIndex.push_back(y-1);}  
44:                 if(y<col-1 && board[x][y+1] == 'O' ) {xIndex.push_back(x); yIndex.push_back(y+1);}  
45:                 k++;  
46:            }  
47:            for(int i =0; i< row; i++)  
48:            {  
49:                 for(int j =0; j< col; j++)  
50:                 {  
51:                      if(board[i][j] =='O') board[i][j] = 'X';  
52:                      if(board[i][j] == 'Y') board[i][j] = 'O';  
53:                 }  
54:            }            
55:       }