众所周知第一题是水题,模拟一下就行了(我还是wa了两次)

class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        vector<vector<int>>ans=grid;
        while(k--){
            for(int i=0;i<grid.size();i++){
                for(int j=0;j<grid[i].size();j++){
                    if(i==grid.size()-1&&j==grid[i].size()-1){
                        ans[0][0]=grid[i][j];
                    }else if(j==grid[i].size()-1){
                        ans[i+1][0]=grid[i][j];
                    }else{
                        ans[i][j+1]=grid[i][j];
                    }
                }
            }
            grid=ans;
        }
        return ans;
    }
};




写的可能有点复杂了,但也不是难题,左右递归分别建树左2i+1,右2i+2,然后一个dfs查询就好了

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
class FindElements {
public:
    TreeNode* rt;
    bool flag;
    void dfs(TreeNode *root){
        if(root!=NULL){
            if(root->left!=NULL){
                root->left->val=root->val*2+1;
                dfs(root->left);
            }
            if(root->right!=NULL){
                root->right->val=root->val*2+2;
                dfs(root->right);
            }
        }
    }
    FindElements(TreeNode* root) {
        root->val=0;
        rt=root;
        dfs(root);
    }
    void dfs1(TreeNode *rt,int ans){
        if(rt!=NULL){
            if(rt->val==ans){
                flag=true;
            }
            dfs1(rt->left,ans);
            dfs1(rt->right,ans);
        }
    }
    bool find(int target) {
        flag=false;
        dfs1(rt,target);
        if(flag)return true;
        else return false;
    }
};

/** * Your FindElements object will be instantiated and called as such: * FindElements* obj = new FindElements(root); * bool param_1 = obj->find(target); */

比赛的时候看到这道题的规模就知道是一道dp题,对于没学过dp的我来说直接放弃了,赛后学了一下,大概思路就是定义dp[i]表示模为i的和的最大值,因为模为1的最大和加上模为2的最大和可以组成模为0的最大和,模为2的最大和可以和模为0的组成和模为0的最大和,模为0的不用组合,所以一共有三种状态,然后一次O(n)就可以求出答案了

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        int dp[3]={0,0,0};
        for(int i=0;i<nums.size();i++){
            int mod=nums[i]%3;
            int a=dp[(3+0-mod)%3];
            int b=dp[(3+1-mod)%3];
            int c=dp[(3+2-mod)%3];
            if(a||mod==0)dp[0]=max(dp[0],a+nums[i]);
            if(b||mod==1)dp[1]=max(dp[1],b+nums[i]);
            if(c||mod==2)dp[2]=max(dp[2],c+nums[i]);
        }
        return dp[0];
    }
};



这道题看到直接上bfs,结果写了一个小时写完了交上去直接wa搞半天题意都搞错了(心都凉了),一开始就是我直接把人给丢了,直接找箱子到终点的最短路,最后发现人还要推着箱子走,也就是说箱子要往上,人就要在箱子下面的位置,然后移动完后人就在箱子的位置。赛后参考了hdu1254写完了(一次a了两个题,虽然花了我两天)
主要思路就是还是找箱子到终点的最短路,不过每次箱子移动都要再bfs一下,看人能不能到箱子即将移动的反方向,另外因为路有很多条,我们让一个点只访问一次,最后有些答案没办法求出来,所以用了vis[i][j][k]表示数组[i][j]的第k个方向有没有被访问,也就说每个格子有四个方向可以扩展。
代码

struct Node {
    int px,py,bx,by;
    int step;
};
struct node{
	int x,y;
	node(){}
	node(int a,int b):x(a),y(b){}
};
class Solution {
public:
    int n,m;
    int maze[100][100];
    int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
    bool vis[100][100][5]={false};
    bool bfs(int a,int b,int x1, int y1, int x2, int y2) {
    queue<node>ans;
    ans.push(node(x1, y1));
    bool vis[100][100]; 
    memset(vis, false, sizeof(vis));
    vis[x1][y1]=true;
    while (!ans.empty()) {
        node now = ans.front();
        ans.pop();
        if (now.x == x2 && now.y == y2)return true;
        for (int i = 0; i < 4; i++) {
            int fx = now.x + dir[i][0];
            int fy = now.y + dir[i][1];
            if (fx < 0 || fy < 0 || fx >= m || fy >= n)continue;
            if( fx == a && fy == b )continue;
            if (vis[fx][fy])continue;
            if (maze[fx][fy] == 1)continue;
            
            vis[fx][fy] = true;
            ans.push(node(fx, fy));
        }
    }
    return false;
}
    int minPushBox(vector<vector<char>>& grid) {
        m=grid.size();n=grid[0].size();
        Node s;s.step=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]=='#'){
                    maze[i][j]=1;
                }
                if(grid[i][j]=='T'){
                    maze[i][j]=3;
                }
                if(grid[i][j]=='.'){
                    maze[i][j]=0;
                }
                if(grid[i][j]=='B'){
                    maze[i][j]=2;
                    s.bx = i; s.by = j ;
                }
                if(grid[i][j]=='S'){
                    maze[i][j]=4;
                    s.px = i; s.py = j ;
                }
            }
        }
        queue<Node>st;
        st.push(s);
        int ans=0x3f3f3f3f;int x,y;
        while (!st.empty()) {
            Node now = st.front();
            st.pop();
            if (maze[now.bx][now.by]==3) {
                ans=min(ans,now.step);
            }
            for (int i = 0; i < 4; i++) {
                int fx = now.bx + dir[i][0];
                int fy = now.by + dir[i][1];
                x = now.bx - dir[i][0];
                y = now.by - dir[i][1];
                if (x < 0 || y < 0 || x >= m || y >= n)continue;
                if (fx < 0 || fy < 0 || fx >= m || fy >= n)continue;
                if (maze[fx][fy] == 1||maze[x][y]==1)continue;
                if (vis[fx][fy][i])continue; 
                
                Node cur=now,pre=now;
				pre.px=x;
				pre.py=y; 
                if (bfs(now.bx,now.by,now.px,now.py,x,y)) {
                	cur.bx=fx;cur.by=fy;
                	cur.px=now.bx;cur.py=now.by;//原来箱子的位置现在放人 
                    cur.step=now.step+1;
                    vis[fx][fy][i] = true;
                    st.push(cur);
                    //printf("%d %d\n",cur.bx,cur.by);
                }
            }
        }
        if(ans==0x3f3f3f3f)return -1;
		else return ans;
    }
};

要上晚自习了匆匆结束把