一、每日一题 DFS递归回溯
之前总结过的网格类DFS问题，这段时间一直在练，很简单。
class Solution {
public:
int sum =0,maxval =0;
int n,m;
bool st[16][16];
void dfs(vector<vector<int>>& grid,int i,int j,int sum)
{
if(i<0||j<0||i>=n||j>=m||grid[i][j] == 0||st[i][j])
{
if(sum>maxval) maxval = sum;
return;
}
int res = grid[i][j];
st[i][j]=true; //标记走到了这个点
dfs(grid,i-1,j,sum+res);
dfs(grid,i+1,j,sum+res);
dfs(grid,i,j-1,sum+res);
dfs(grid,i,j+1,sum+res);
st[i][j] = false; // 恢复现场
}
int getMaximumGold(vector<vector<int>>& grid) {
n = grid.size(),m = grid[0].size();
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(grid[i][j]!=0) {
memset(st,false,sizeof st); // 每一次开始深搜前要把所有点置为未走到状态
dfs(grid,i,j,sum);
}
}
}
return maxval;
}
};?二、今日刷题总结
?这题很好理解，就是递归构建左右子树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode *root;
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
if(!nums.size())
{
return nullptr;
}
auto it = max_element(nums.begin(),nums.end());
vector<int> l(nums.begin(),it);
vector<int> r(it+1,nums.end());
TreeNode *root = new TreeNode(*it);
root->left = constructMaximumBinaryTree(l);
root->right = constructMaximumBinaryTree(r);
return root;
}
};
明明都是最大二叉树这个2.0版本是怎么回事。一开始以为把右子树摘下来重新构造就行了，后来发现这个题更偏向于插入一个节点，并且插入方式非常奇怪，看了题解才知道是啥意思。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
if(val>=root->val)
root = new TreeNode(val,root,NULL);//当前根变成左子树
else/
if(root->right==NULL)
root->right = new TreeNode(val);
else
root->right=insertIntoMaxTree(root->right,val);
return root;
}
};?
网格型深搜问题，不多说。
class Solution {
public:
int sum =0,maxval =0;
int n,m;
bool st[16][16];
void dfs(vector<vector<int>>& grid,int i,int j,int sum)
{
if(i<0||j<0||i>=n||j>=m||grid[i][j] == 0||st[i][j])
{
if(sum>maxval) maxval = sum;
return;
}
int res = grid[i][j];
st[i][j]=true;
dfs(grid,i-1,j,sum+res);
dfs(grid,i+1,j,sum+res);
dfs(grid,i,j-1,sum+res);
dfs(grid,i,j+1,sum+res);
st[i][j] = false;
}
int getMaximumGold(vector<vector<int>>& grid) {
n = grid.size(),m = grid[0].size();
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(grid[i][j]!=0) {
memset(st,false,sizeof st);
dfs(grid,i,j,sum);
}
}
}
return maxval;
}
};?
也是网格型深搜问题，这个题有几个需要注意的地方。首先需要扩展的只有没有相邻地雷且没有被挖出的空方块，挖出地雷并且游戏结束只可能发生在递归开始之前。
?
class Solution {
public:
int n,m;
int dir_x[8] = {0, 1, 0, -1, 1, 1, -1, -1};
int dir_y[8] = {1, 0, -1, 0, 1, -1, 1, -1};
void dfs(vector<vector<char>>& board,int x,int y)
{
int cnt = 0;
for (int i = 0; i < 8; ++i) {
int tx = x + dir_x[i];
int ty = y + dir_y[i];
if (tx < 0 || tx >= board.size() || ty < 0 || ty >= board[0].size()) {
continue;
}
cnt += board[tx][ty] == 'M';
}
if(cnt > 0)
{
board[x][y] = cnt+'0';
}
else
{
board[x][y] = 'B';
for(int i=0;i<8;i++)
{
int tx = x+dir_x[i];
int ty = y + dir_y[i];
if (tx < 0 || tx >= board.size() || ty < 0 || ty >= board[0].size() || board[tx][ty] != 'E') {
continue;
}
dfs(board,tx,ty);
}
}
}
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
n = board.size(),m = board[0].size();
int x = click[0],y = click[1];
if(board[x][y]=='M')
{
board[x][y] = 'X';
}
else dfs(board,x,y);
return board;
}
};