leetcode每日一题44

130. 被围绕的区域

图论
dfs/bfs
dfs代码框架

void dfs(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本节点所连接的其他节点) {
        处理节点;
        dfs(图，选择的节点); // 递归
        回溯，撤销处理结果
    }
}

思路：本题要求找到被x围绕的陆地，所以边界的陆地O肯定不符合条件。那么我们只要从周边找到陆地O然后 通过 dfs或者bfs 将周边靠陆地且相邻的陆地O都变成A，然后再去重新遍历地图的时候，把剩下的O变成X，再把所有的A变成O。

1. 确认递归函数，参数
   一般情况，深搜需要 二维数组数组结构保存所有路径，需要一维数组保存单一路径，这种保存结果的数组，我们可以定义一个全局变量，避免让我们的函数参数过多。
   因为需要上下左右遍历，所以构建一个方向坐标
   int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};
   递归函数参数为地图，还有当前坐标x,y
   void dfs(vector<vector<char>>& board, int x, int y)
2. 确认终止条件
   终止添加不仅是结束本层递归，同时也是我们收获结果的时候。
   另外，其实很多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;
	}

3. 处理目前搜索节点出发的路径
   把当前节点改为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刀
递归表示在第一刀的基础上，下面的几刀在哪切

1. 递归函数的返回值以及参数
   定义两个全局变量，一个用来存放符合条件单一结果，一个用来存放符合条件结果的集合。
   vector<vector<string>> result;
   vector<string> path;
   函数里有两个参数，字符串s，还有记录本层递归的中从哪里开始切的startIndex
   void backtracking (const string& s, int startIndex)
2. 递归函数终止条件
   字符串切完了就终止，把当前路径存到结果里

if(startIndex>=s.length()){
	result.push_back(path);
	return;
}

3. 单层搜索的逻辑
   从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;
    }
};