leetcode每日一题44
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(vector<vector<char>>& board, int x, int y) - 确认终止条件
终止添加不仅是结束本层递归，同时也是我们收获结果的时候。
另外，其实很多dfs写法，没有写终止条件，其实终止条件写在了， 下面dfs递归的逻辑里了，也就是不符合条件，直接不会向下递归。
这个代码的终止条件就是写在递归逻辑里的。
当前方向超出边界，停止当前方向的遍历
for(int i=0;i<4;i++){nextx=x+dir[i][0];nexty=y+dir[i][1];if(nextx<0||nextx>=board.size()||nexty<0||nexty>=board[0].size())continue;}
- 处理目前搜索节点出发的路径
把当前节点改为A
没必要回溯，得到坐标且坐标没有过界，则判断该节点是否是X或者A，若是，则停止当前方向的遍历
若不是，就继续递归
class Solution {
public:int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1}; void dfs(vector<vector<char>>& board, int x, int y){board[x][y]='A';for(int i=0;i<4;i++){int nextx=x+dir[i][0];int nexty=y+dir[i][1];if(nextx<0||nextx>=board.size()||nexty<0||nexty>=board[0].size())continue;if(board[nextx][nexty]=='X'||board[nextx][nexty]=='A')continue;dfs(board, nextx, nexty);}return;}void solve(vector<vector<char>>& board) {int n=board.size(), m=board[0].size();for(int i=0;i<n;i++){if(board[i][0]=='O')dfs(board,i,0);if(board[i][m-1]=='O')dfs(board,i,m-1);}for(int j=0;j<m;j++){if(board[0][j]=='O')dfs(board,0,j);if(board[n-1][j]=='O')dfs(board,n-1,j);}for(int i=0;i<n;i++)for(int j=0;j<m;j++){if (board[i][j] == 'O') board[i][j] = 'X';if (board[i][j] == 'A') board[i][j] = 'O';}return;}
};131. 分割回文串
回溯
切割问题类似组合问题
for循环表示在哪里切下第1刀
递归表示在第一刀的基础上，下面的几刀在哪切
- 递归函数的返回值以及参数
定义两个全局变量，一个用来存放符合条件单一结果，一个用来存放符合条件结果的集合。
vector<vector<string>> result;
vector<string> path;
函数里有两个参数，字符串s，还有记录本层递归的中从哪里开始切的startIndex
void backtracking (const string& s, int startIndex) - 递归函数终止条件
字符串切完了就终止，把当前路径存到结果里
if(startIndex>=s.length()){result.push_back(path);return;
}
- 单层搜索的逻辑
从startIndex开始，遍历startIndex后面所有的位置。如果startIndex到当前位置的字符串是回文子串，则加入当前路径。否则跳过
然后递归当前位置的下一个位置为下一个递归的startIndex
递归结束，回溯，弹出当前字符串
for(int i=startIndex; i<s.length();i++)
{if(isPalindrome(s, startIndex, i)){string str = s.substr(startIndex, i - startIndex + 1);path.push_back(str);}else continue;backtracking(s, i+1);path.pop_back();
}
然后要写是否是回文子串
双指针，一前一后对比
bool isPalindrome(const string& s, int startIndex, int end)
{for(int i=startIndex, int j=end;i<j; 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 i=startIndex,j=end;i<j; i++,j--){if(s[i]!=s[j])return false;}return true;}vector<vector<string>> result;vector<string> path;void backtracking (const string& s, int startIndex) {if(startIndex>=s.length()){result.push_back(path);return;}for(int i=startIndex; i<s.length();i++){if(isPalindrome(s, startIndex, i)){string str = s.substr(startIndex, i - startIndex + 1);path.push_back(str);}else continue;backtracking(s, i+1);path.pop_back();}return;}vector<vector<string>> partition(string s) {result.clear();path.clear();backtracking(s, 0);return result;}
};