• wy的leetcode刷题记录_Day33


    wy的leetcode刷题记录_Day33

    时间:2022-11-4

    754. 到达终点数字

    今天的每日一题是:754. 到达终点数字

    题目介绍

    1. 在一根无限长的数轴上,你站在0的位置。终点在target的位置。
    2. 你可以做一些数量的移动 numMoves :
    3. 每次你可以选择向左或向右移动。
    4. 第 i 次移动(从 i == 1 开始,到 i == numMoves ),在选择的方向上走 i 步。
    5. 给定整数 target ,返回 到达目标所需的 最小 移动次数(即最小 numMoves ) 。

    示例 1:
    输入: target = 2
    输出: 3
    解释: 第一次移动,从 0 到 1 。 第二次移动,从 1 到 -1 。第三次移动,从 -1 到 2。

    示例 2:
    输入: target = 3
    输出: 2
    解释: 第一次移动,从 0 到 1 。 第二次移动,从 1 到 3 。

    思路

    通过观察发现,不管是任意的向左还是向右移动,最终得到的target<0的话,其实将向左和向右的相应步数反过来就可以实现target>0的情况,综上我们只考虑target>0的情况。
    假设我们不回头寻找了k次才找到现在的pos位置>=target,如果恰好pos==start,这样的话就正好寻找到那么k就是最小寻找次数,如果pos>target,就是无法恰好走到终点的情况就需要讨论了:

    1. 越过终点的差距dealt为偶数,这样的话我们只需要在前k-1步中寻找一步将其改成反向即可,要满足这个数等于dealt/2
    2. 越过重点的差距dealt为奇数,我们只需要在k步的基础之上再走一步,如果走之后差距dealt为偶数就通过步骤一即可完成,如果仍不行还需重复步骤二。
      下面证明为什么多走两步一定是偶数:
      首先我们分析一下多走一步为什么还是奇数,因为有可能我这个下一步走的是偶数步,也就是我们这次迭代只能走偶数个距离,众所周知偶数加奇数还是奇数,所以不行,于是再走一步而这一步已知上面是偶数步那这一步肯定是奇数步,奇数加奇数就是偶数。如果一开始的下一步就是奇数,那么奇数加奇数就是偶数。证毕!

    代码

    class Solution {
    public:
        int reachNumber(int target) {
            target = abs(target);
            int step = 0;
            int pos=0;
            int dealt=-1;
            while (dealt < 0) {
                step ++;
                pos+=step;
                dealt=pos-target;//现在距离目标的偏差
            }
            return dealt% 2 == 0 ? step : step + 1 + step % 2;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    收获

    仔细分析题目,这道题有一点贪心的想法在里面,先直接一条路走到底,再反思自己这个过程,如果够的话就改正,如果觉得不够就继续走,不够就继续走,直到够且能改正为止。

    199. 二叉树的右视图

    199. 二叉树的右视图

    题目介绍

    • 给定一个二叉树的 根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。

    示例 1:
    在这里插入图片描述

    输入: [1,2,3,null,5,null,4]
    输出: [1,3,4]

    示例 2:
    输入: [1,null,3]
    输出: [1,3]

    思路

    方法一:BFS:根据题目意思,画出右视图,其实就是将树的每一层的最右边的节点打印出来就可以,用层序遍历即可;
    方法二:DFS:每次先遍历根节点再遍历右节点再遍历左节点,每当第一次遍历相应的深度时,最先遍历的就是最右边的节点。

    代码

    bfs

    /**
     * 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:
        vector<int> rightSideView(TreeNode* root) {
            queue<TreeNode*> qu;
            vector<int> ans;
            if(root==nullptr)
                return ans;
            TreeNode* node=root;
            qu.push(root);
    
            while(!qu.empty())
            {
                int n=qu.size();
                for(int i=0;i<n;i++)
                {
                    node=qu.front();
                    qu.pop();
                    if(node->left)
                        qu.push(node->left);
                    if(node->right)
                        qu.push(node->right);
                    if(i==n-1)
                        ans.push_back(node->val);
                }
            }
            return ans;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    dfs

    /**
     * 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:
        vector<int> ans;
        vector<int> rightSideView(TreeNode* root) {
            dfs(root,0);
            return ans;
        }
        void dfs(TreeNode *node,int depth)
        {
            if(!node)
                return;
            if(ans.size()==depth)
                ans.push_back(node->val);
            depth++;
            dfs(node->right,depth); 
            dfs(node->left,depth); 
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    收获

    复习层序遍历

  • 相关阅读:
    css预编语言sass使用语法详解
    操作系统学习笔记13 | 目录与文件系统
    科技云报道:云计算走向工业互联网“深水区”
    Dapr学习积累(一)
    【Qt炫酷动画】1.easing官方demo详细剖析
    OpenJDK17-JVM源码阅读-ZGC-并发标记
    C/C++布尔运算的短路
    在Python中使用sqlite3进行数据持久化操作
    SAP S/4 HANA 与R3(ECC) 的区别
    蓝桥杯——分巧克力
  • 原文地址:https://blog.csdn.net/m0_54015435/article/details/127694828