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;
}
};
