昨天寫了BFS模板&一題模板題,今天放幾題比較複雜的~~
909. 蛇梯棋
這題最難的地方在看懂題目吧==
解釋一下題目
1.一次可以走1~6格
2.遇到梯子或蛇一定要走
3.一次移動只能用一次梯子或蛇
((就代表如果有一個梯子或蛇接到下一個,不能繼續接下去,就會停在那一格))
再來就BFS爆搜
class Solution {
public:
int snakesAndLadders(vector<vector<int>>& board) {
int N = board.size();
vector<int> ladder(N*N+1, -1);
queue<int> q;
vector<bool> vis(N*N+1, false);
int res = 0;
bool r = true;
bool good = false;
for(int i = N-1; i>=0; --i){
for(int j = 0; j<N; ++j){
if(board[i][j]!=-1){
//用i, j算出這個梯子在哪
//第N列一定往右,(N-i)-2k列一定也是往右
int pos = -1;
if(r)
pos = (N-i)*N-(N-j-1);
else
pos = (N-i)*N-j;
ladder[pos] = board[i][j]; //這有梯子
}
}
r = !r;
}
q.push(1);
while(!q.empty()){
int size = q.size();
for(int i = 0; i<size; ++i){
int curr = q.front();
q.pop();
if(curr==N*N){
return res;
}
for(int j = 1; j<=6; ++j){
if(curr+j<=N*N&&vis[curr+j]==0){
int newPos = curr+j;
vis[newPos] = 1;
if(ladder[newPos]!=-1){
newPos=ladder[newPos];
}
q.push(newPos);
}
}
}
++res;
}
return -1;
}
};
863. 二叉树中所有距离为 K 的结点
經典的樹轉成圖,然後還是BFS模板~~
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
#define vt vector
#define pb push_back
#define iipair pair<int, int>
#define cipair pair<char, int>
#define icpair pair<int, char>
#define ispair pair<int, string>
#define sipair pair<string, int>
#define MOD 1e9+7
#define iMat vector<vector<int>>
#define cMat vector<vector<char>>
#define ll long long
class Solution {
unordered_map<TreeNode*, TreeNode*> link;
unordered_map<TreeNode*, bool> vis;
public:
vector<int> distanceK(TreeNode* root, TreeNode* target, int k){
/*
遍歷到target節點前都往後鏈接
*/
vector<int> res;
make_link(nullptr, root);
queue<TreeNode*> q;
q.push(target);
vis[target] = 1;
if(k==0){
res.pb(target->val);
return res;
}
while(!q.empty()&&k--){
int s = q.size();
for(int i = 0; i < s; ++i){
TreeNode* curr = q.front();
q.pop();
TreeNode* pre = link[curr];
if(!vis[curr->right]){
vis[curr->right] = true;
if(curr->right)
q.push(curr->right);
}
if(curr->left&&!vis[curr->left]){
vis[curr->left] = true;
if(curr->left)
q.push(curr->left);
}
if(!vis[pre]){
vis[pre] = true;
if(pre)
q.push(pre);
}
}
// print_queue(q);
if(k==0){
while(!q.empty()){
if(q.front())
res.pb(q.front()->val);
q.pop();
}
return res;
}
}
return res;
}
void make_link(TreeNode* pre,TreeNode* root){
if(root==nullptr){
return;
}
link[root] = pre;
make_link(root, root->left);
make_link(root, root->right);
return;
}
};
剑指 Offer 13. 机器人的运动范围
這種題目有一個小技巧可以用
const int dir_x[]{1,0,-1,0};
const int dir_y[]{0,1,0,-1};
用這兩個數組來代替四個方向的if(寫成一個迴圈)
沒什麼特別的,但是程式會簡潔很多!!!
#define vt vector
#define mp make_pair
class Solution {
public:
int movingCount(int m, int n, int k) {
vt<vt<bool>> vis(m, vt<bool>(n, false));
for(int i = 0; i<m; ++i){
for(int j = 0; j<n; ++j){
//不符合規定的grid視為visited
if(sumOfdigit(i)+sumOfdigit(j)>k){
vis[i][j] = true;
}
}
}
const int dir_x[]{1,0,-1,0};
const int dir_y[]{0,1,0,-1};
queue<pair<int, int> > q;
q.push(mp(0,0));
int g_cnt = 0;
while(!q.empty()){
g_cnt++;
int x = q.front().first;
int y = q.front().second;
q.pop();
vis[x][y] = true;
for(int i = 0; i<4; ++i){
int next_x = x+dir_x[i];
int next_y = y+dir_y[i];
if(next_x>=m||next_y>=n||next_x<0||next_y<0||vis[next_x][next_y]){
continue;
}
q.push(mp(next_x, next_y));
vis[next_x][next_y] = 1;
}
}
return g_cnt;
}
int sumOfdigit(int n){
int res = 0;
while(n){
res+=n%10;
n/=10;
}
return res;
}
};