太原模板建站平台,国外黄冈网站推广,杭州优化网站,推广文案范文130. 被围绕的区域
图论 dfs/bfs dfs代码框架
void dfs(参数) {if (终止条件) {存放结果;return;}for (选择#xff1a;本节点所连接的其他节点) {处理节点;dfs(图#xff0c;选择的节点); // 递归回溯#xff0c;撤销处理结果}
}思路#xff1a;本题要求找到被x围绕的陆…130. 被围绕的区域
图论 dfs/bfs dfs代码框架
void dfs(参数) {if (终止条件) {存放结果;return;}for (选择本节点所连接的其他节点) {处理节点;dfs(图选择的节点); // 递归回溯撤销处理结果}
}思路本题要求找到被x围绕的陆地所以边界的陆地O肯定不符合条件。那么我们只要从周边找到陆地O然后 通过 dfs或者bfs 将周边靠陆地且相邻的陆地O都变成A然后再去重新遍历地图的时候把剩下的O变成X再把所有的A变成O。
确认递归函数参数 一般情况深搜需要 二维数组数组结构保存所有路径需要一维数组保存单一路径这种保存结果的数组我们可以定义一个全局变量避免让我们的函数参数过多。 因为需要上下左右遍历所以构建一个方向坐标 int dir[4][2] {-1, 0, 0, -1, 1, 0, 0, 1}; 递归函数参数为地图还有当前坐标x,y void dfs(vectorvectorchar board, int x, int y)确认终止条件 终止添加不仅是结束本层递归同时也是我们收获结果的时候。 另外其实很多dfs写法没有写终止条件其实终止条件写在了 下面dfs递归的逻辑里了也就是不符合条件直接不会向下递归。 这个代码的终止条件就是写在递归逻辑里的。 当前方向超出边界停止当前方向的遍历
for(int i0;i4;i){nextxxdir[i][0];nextyydir[i][1];if(nextx0||nextxboard.size()||nexty0||nextyboard[0].size())continue;}处理目前搜索节点出发的路径 把当前节点改为A 没必要回溯得到坐标且坐标没有过界则判断该节点是否是X或者A若是则停止当前方向的遍历 若不是就继续递归
class Solution {
public:int dir[4][2] {-1, 0, 0, -1, 1, 0, 0, 1}; void dfs(vectorvectorchar board, int x, int y){board[x][y]A;for(int i0;i4;i){int nextxxdir[i][0];int nextyydir[i][1];if(nextx0||nextxboard.size()||nexty0||nextyboard[0].size())continue;if(board[nextx][nexty]X||board[nextx][nexty]A)continue;dfs(board, nextx, nexty);}return;}void solve(vectorvectorchar board) {int nboard.size(), mboard[0].size();for(int i0;in;i){if(board[i][0]O)dfs(board,i,0);if(board[i][m-1]O)dfs(board,i,m-1);}for(int j0;jm;j){if(board[0][j]O)dfs(board,0,j);if(board[n-1][j]O)dfs(board,n-1,j);}for(int i0;in;i)for(int j0;jm;j){if (board[i][j] O) board[i][j] X;if (board[i][j] A) board[i][j] O;}return;}
};
131. 分割回文串
回溯 切割问题类似组合问题 for循环表示在哪里切下第1刀 递归表示在第一刀的基础上下面的几刀在哪切
递归函数的返回值以及参数 定义两个全局变量一个用来存放符合条件单一结果一个用来存放符合条件结果的集合。 vectorvectorstring result; vectorstring path; 函数里有两个参数字符串s还有记录本层递归的中从哪里开始切的startIndex void backtracking (const string s, int startIndex)递归函数终止条件 字符串切完了就终止把当前路径存到结果里
if(startIndexs.length()){result.push_back(path);return;
}单层搜索的逻辑 从startIndex开始遍历startIndex后面所有的位置。如果startIndex到当前位置的字符串是回文子串则加入当前路径。否则跳过 然后递归当前位置的下一个位置为下一个递归的startIndex 递归结束回溯弹出当前字符串
for(int istartIndex; is.length();i)
{if(isPalindrome(s, startIndex, i)){string str s.substr(startIndex, i - startIndex 1);path.push_back(str);}else continue;backtracking(s, i1);path.pop_back();
}然后要写是否是回文子串 双指针一前一后对比
bool isPalindrome(const string s, int startIndex, int end)
{for(int istartIndex, int jend;ij; i,j--){if(s[i]!s[j])return false;}return true;
}整体代码
class Solution {
public:bool isPalindrome(const string s, int startIndex, int end){for(int istartIndex,jend;ij; i,j--){if(s[i]!s[j])return false;}return true;}vectorvectorstring result;vectorstring path;void backtracking (const string s, int startIndex) {if(startIndexs.length()){result.push_back(path);return;}for(int istartIndex; is.length();i){if(isPalindrome(s, startIndex, i)){string str s.substr(startIndex, i - startIndex 1);path.push_back(str);}else continue;backtracking(s, i1);path.pop_back();}return;}vectorvectorstring partition(string s) {result.clear();path.clear();backtracking(s, 0);return result;}
};
