Day8 圆圈中最后剩下的数字+机器人的运动范围+从上到下打印二叉树

⭐TODO:

1. 能推出约瑟夫环问题的状态转移方程
   2.重做机器人的运动范围

一、剑指 Offer 62. 圆圈中最后剩下的数字(简单)

😥似会非会的。这个题解讲的很不错https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/jian-zhi-offer-62-yuan-quan-zhong-zui-ho-dcow/

image.png

class Solution {
public:
    int lastRemaining(int n, int m) {
        int x = 0;
        for (int i = 2; i <= n; i++) {
            x = (x + m) % i;
        }
        return x;
    }
};

二、剑指 Offer 13. 机器人的运动范围(中等)

应该是一个很典型的递归问题吧。但是一看题目就怕了，于是看题解后写出来的。
题解妙就妙在对坐标每位相加做的巧妙处理，从1->2增加了1，从9->10减少了8。
Krahets简直是题解之光！写的题解都对我这种小白太友好了！https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/solution/mian-shi-ti-13-ji-qi-ren-de-yun-dong-fan-wei-dfs-b/

class Solution {
public:
    int dfs(int i, int j, int si,int sj,vector<vector<bool>>&vis, int m, int n, int k){
        if(i >= m || j>=n || si+sj>k||vis[i][j]) return 0;
        vis[i][j] = 1;
        return 1 + dfs(i+1,j, (i+1)%10 !=0?si+1:si-8,sj,vis,m,n,k) + dfs(i,j+1,si,(j+1)%10 !=0?sj+1:sj-8,vis,m,n,k);//⭐
    }
    int movingCount(int m, int n, int k) {
        vector<vector<bool>> vis(m,vector<bool>(n));
        return dfs(0,0, 0,0,vis,m,n,k);
    }
};

题解里还有个BFS的方法也很棒！

三、 剑指 Offer 32 - I. 从上到下打印二叉树(中等)

这道题，一看就觉得是一道简单的BFS题。于是很轻松的写了出来！🙂

class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        if(root == nullptr) return {};
        TreeNode* head = root;
        queue<TreeNode*> que;
        vector<int> ans;
        que.push(head);
        while(!que.empty()){
            int ts = que.size();
            while(ts--){
                TreeNode* temp = que.front();
                que.pop();
                if(temp == nullptr) continue;
                ans.push_back(temp->val);
                if(temp->left) que.push(temp->left);
                if(temp->right)que.push(temp->right);
            }
        }
        return ans;
    }
};