0

我想出了一个算法来解决leetcode上发布的包围区域问题。

但可悲的是我的解决方案可以通过第一个判断输入集，但不能通过第二个更大的输入集，并且报告运行时错误。但是，我可以在我的笔记本电脑上成功运行！我在这个问题上花了几个小时，但我仍然不知道！

下面是问题。

给定一个包含“X”和“O”的二维板，捕获所有被“X”包围的区域。

通过将包围区域中的所有“O”翻转为“X”来捕获一个区域。

例如，

XXXX

XOOX

XXOX

XOXX

运行你的函数后，板应该是：

XXXX

XXXX

XXXX

XOXX

以下是我的解决方案：

class Solution {
public:
    void solve(vector<vector<char> > &board) {
      if(board.size() == 0) return;

      int row = board.size();
      set<pair<int, int> > map;

      for(int i=0; i<= row/2; i++){
         int bottom = row-i-1;
         for(int j=i; j<= bottom; j++){
            checkPoint(board, i, j, map);
            checkPoint(board, bottom, j, map);
            checkPoint(board, j, i, map);
            checkPoint(board, j, bottom, map);
         }
      }        
   }

  void mark(vector<vector<char> >& board, int row, int col, set<pair<int, int> >& map){
      if(row < 0 || row > board.size()-1 || col < 0 || col > board[0].size()-1 )
          return;

    int temp = col;
    while(temp-1 >= 0 && board[row][temp-1] == 'O' &&\
        map.find(pair<int,int>(row, temp-1)) ==   map.end()){
        map.insert(pair<int, int>(row, temp-1));
        temp -=1;
        mark(board, row, temp, map);
    }
    temp = col;
    while(temp+1 <= board[0].size()-1 && board[row][temp+1] == 'O' && \
        map.find(pair<int,int>(row, temp+1)) == map.end()){
        map.insert(pair<int, int>(row, temp+1));
        temp +=1;
        mark(board, row, temp, map);
    }
    temp = row;
    while(temp -1 >= 0 && board[temp-1][col] == 'O'&& \
         map.find(pair<int,int>(temp-1, col)) == map.end()){
        map.insert(pair<int, int>(temp-1, col));
        temp -=1;
        mark(board, temp, col, map);
    }
    temp = row;
    while(temp+1 <= board.size()-1 && board[temp+1][col] == 'O'&& \
         map.find(pair<int,int>(temp+1, col)) == map.end()){
        map.insert(pair<int, int>(temp+1, col));
        temp +=1;
        mark(board, temp, col, map);
    }          
 }

  void checkPoint(vector<vector<char> >& board, int row, int col, set<pair<int, int> >& map){
     if(board[row][col] == 'O'){
       if(row ==0 || col== 0 || row == board.size()-1 || col == board[0].size()-1 ){
           if(map.find(pair<int, int>(row, col)) == map.end()){
               map.insert(pair<int,int>(row, col));
               mark(board, row, col, map);
           }
       }else if(map.find(pair<int, int>(row, col)) == map.end()){
              board[row][col] = 'X';
      }
    }
    return;
  }

};
4

2 回答 2

1

我同意其他答案之一，要么您使用了过多的运行时间或堆栈空间。试试这个想法。请注意，对于“O”的连接区域，该区域要么接触板的边缘，要么该区域完全被“X”包围。因此，您可以使用以下策略。首先沿着棋盘的边缘走，直到找到一个“O”。然后初始化一个集合 CurrentBoundaryO 等于刚刚这个 'O' 的集合，并将一个集合 NextBoundaryO 初始化为空。然后迭代地执行以下操作。将 CurrentBoundaryO 中的每个位置标记为“未更改的 O”。然后遍历 CurrentBoundaryO 的元素并检查所有邻居。每个未标记为“未更改 O”的“O”邻居都应添加到集合 NextBoundaryO。然后设置 CurrentBoundaryO = NextBoundaryO 并重复，直到 CurrentBoundryO 没有元素。然后继续围绕板的边缘搜索，直到找到未标记为“未更改的 O”的“O”，并重复该过程。不断重复，直到您沿着电路板的整个边缘移动。那么每个'X'仍然是'X'，每一个标有'unchanged O'的'O'仍然是'O'，并且板上所有其他'O'都应该切换到'X'。该策略在输入大小方面以线性时间运行，并且避免了递归，因此也不存在堆栈空间问题。这应该通过判断软件评估。O'不变，重复上述过程。不断重复，直到您沿着电路板的整个边缘移动。那么每个'X'仍然是'X'，每一个标有'unchanged O'的'O'仍然是'O'，并且板上所有其他'O'都应该切换到'X'。该策略在输入大小方面以线性时间运行，并且避免了递归，因此也不存在堆栈空间问题。这应该通过判断软件评估。O'不变，重复上述过程。不断重复，直到您沿着电路板的整个边缘移动。那么每个'X'仍然是'X'，每一个标有'unchanged O'的'O'仍然是'O'，并且板上所有其他'O'都应该切换到'X'。该策略在输入大小方面以线性时间运行，并且避免了递归，因此也不存在堆栈空间问题。这应该通过判断软件评估。并且它避免了递归，因此也不存在堆栈空间问题。这应该通过判断软件评估。并且它避免了递归，因此也不存在堆栈空间问题。这应该通过判断软件评估。

于 2013-07-14T01:35:23.503 回答
0

一般来说，在线评委的运行环境与您桌面上的环境完全不同。服务器使用商用硬件，这意味着 cpu 可能很慢且内存很小。没有什么可以阻止您的代码在线程中运行。此外，您无法控制使用的优化级别和编译器。

该错误可能是由于mark函数的递归性质造成的。运行时错误恕我直言，要么是堆栈溢出，要么是程序被杀死，因为它花费了太多时间才能完成。

功能标记非常不直观且成本高昂。首先它是递归的，最大深度与板的尺寸成线性关系。如果板子有 100 万行，我们将有

mark(1000000,...)   
  mark(1000000-1,...)
    ...
      mark(1,...) 
        mark(0,...)

堆栈可能不够大。

其次，每次调用时，将同一行或列中的每个单元格标记为“已访问”（map.find(pair<int,int>(x, y)) == map.end()）比需要的次数多几次。假设网格是 nxn。如果您调用 mark(x,y)，则上述测试将对 x 行和 y 行上的每个位置进行 n 次。这意味着标记的复杂度是 O(n^2)。一般来说，它是 O(#row^2 + #columns^2)

然后你有：

 for(int i=0; i<= row/2; i++){
     int bottom = row-i-1;
     for(int j=i; j<= bottom; j++){
        checkPoint(board, i, j, map);         <--O(n^2)
        checkPoint(board, bottom, j, map);    <--O(n^2)
        checkPoint(board, j, i, map);         <--O(n^2)
        checkPoint(board, j, bottom, map);    <--O(n^2)
     }
  }

您的代码运行时间最差O(n^4)，n = max(row, cols)。

ps：我如何想出标记的复杂性？

标记（x，y）与board[row][y-1] = 'O'导致

  mark(x,y-1)
  mark(x,y-2)
  ...
  mark(x,0)

在每个标记中，再次测试完整的行。对函数进行 n 次调用map.find(pair<int,int>(A, B))。因此 n^2 复杂度。

于 2013-07-14T00:55:12.040 回答