leetcode每日一练-第278题-第一个错误的版本

这篇具有很好参考价值的文章主要介绍了leetcode每日一练-第278题-第一个错误的版本。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

leetcode每日一练-第278题-第一个错误的版本,算法,数据结构

 

一、思路

二分查找——因为它可以快速地将版本范围缩小一半,从而更快地找到第一个坏版本。

二、解题方法

维护一个左边界 left 和一个右边界 right,在每一步循环中,我们计算中间版本 mid,然后检查它是否是坏版本。如果是坏版本,说明第一个坏版本在 mid 或者它之前,我们将 right 更新为 mid。如果不是坏版本,说明第一个坏版本在 mid 之后,我们将 left 更新为 mid + 1。最终,当 leftright 相等时,就找到了第一个坏版本。

三、code

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int left=1;//设定一个左边界 left 和一个右边界 right
        int right=n;
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(isBadVersion(mid))
            {
                right=mid;
            }
            else
            {
                left=mid+1;
            }
        }
        return left;//也可以是right。当 left 和 right 相等时,就找到了第一个坏版本。
        
    }
};

===================================================================== 

 ①

二分查找(Binary Search)是一种高效的搜索算法,适用于已排序的数据集。它的核心思想是将待查找的数据与数据集的中间元素进行比较,从而排除一半的数据,然后继续在剩余的一半中继续查找,以此类推,直到找到目标元素或者确定目标元素不存在。

二分查找的步骤如下:

  1. 确定查找范围的起始点和终点,通常是整个数据集的起始和终止位置。

  2. 计算中间元素的位置。这可以通过 (start + end) / 2 来获得,也可以使用 (start + end) >> 1 来获得,这两种方法在整数运算中可以避免溢出问题。

  3. 比较中间元素与目标元素的大小关系,如果相等,则找到了目标元素,算法结束。

  4. 如果中间元素比目标元素大,那么目标元素应该在左半部分,将终点位置更新为中间位置减一。

  5. 如果中间元素比目标元素小,那么目标元素应该在右半部分,将起始位置更新为中间位置加一。

  6. 重复步骤2到步骤5,直到起始位置大于终点位置,表示查找范围为空,目标元素不存在。

二分查找是一种时间复杂度为 O(log n) 的算法,因此在处理大规模数据时非常高效。然而,它要求数据集是已排序的,否则无法正确进行查找。

错误:使用线性搜索来解决这个问题,但是可能因为版本数量很多而导致超时。

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        for (int i = 1; i <= n; ++i) {
            if (isBadVersion(i) == true) {
                return i;
            }
        }
        return -1; // 如果没有找到坏版本,可以根据题目要求返回一个特定值
    }
};
 文章来源地址https://www.toymoban.com/news/detail-631937.html

到了这里,关于leetcode每日一练-第278题-第一个错误的版本的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构:力扣OJ题(每日一练)

    目录 题一:环形链表 思路一: 题二:复制带随机指针的链表  思路一: 本人实力有限可能对一些地方解释的不够清晰,可以自己尝试读代码,望海涵! 给定一个链表的头节点   head  ,返回链表开始入环的第一个节点。  如果链表无环,则返回  null 。 如果链表中有某个节

    2024年02月12日
    浏览(42)
  • 数据结构:力扣OJ题(每日一练)

    示例:         初始化: 初始化队列Q1,Q2; 入栈: 先将要入栈的数据放入为空的队列中,都为空时,放入Q1; 出栈: 当要出栈时,将Q1的数据出列n-1个,此时的Q1就是栈要出栈的数据(每次出栈都进行一次第三步将为不为空的队列数据放n-1个到为空队列中)); 获取栈顶元

    2024年02月12日
    浏览(41)
  • 数据结构:选择题+编程题(每日一练)

    目录 选择题: 题一: 题二: 题三: 题四: 题五: 编程题: 题一:单值二叉树 思路一: 题二:二叉树的最大深度 思路一: 本人实力有限可能对一些地方解释和理解的不够清晰,可以自己尝试读代码,或者评论区指出错误,望海涵! 感谢大佬们的一键三连! 感谢大佬们

    2024年02月06日
    浏览(41)
  • leetcode每日一练-第53题-最大子数组和

    一、思路 动态规划 二、解题方法 使用了两个变量 maxSum 和 currentSum 来分别记录全局的最大和和当前连续子数组的和。遍历数组时,我们不断更新 currentSum ,并比较是否需要更新 maxSum 。最后, maxSum 就是最大的连续子数组和。 三、code ===================================================

    2024年02月10日
    浏览(36)
  • leetcode每日一练-第98题- 验证二叉搜索树

        一、思路 因为要验证多个节点是否是二叉搜索树,因此使用 递归 二、解题方法 设计一个递归函数 helper(root, lower, upper) 来递归判断,函数表示考虑以 root 为根的子树,判断子树中所有节点的值是否都在 (l,r)的范围内(注意是开区间)。如果 root 节点的值 val 不在 (l,r)的范

    2024年02月15日
    浏览(47)
  • 【LeetCode-SQL每日一练】—— 196. 删除重复的电子邮箱

    🙋‍♂️大家好呀,我是 超梦 。大家可以叫我 小梦 ~ 小伙伴们都知道,不管是在学习中还是日常工作中,几乎天天是要跟 数据库 打交道的,为了更好的操作数据库,我们的 SQL知识储备 是必不可少的。想要掌握好SQL,那少不了每天的练习与学习。接下来小梦会带领小伙伴

    2023年04月08日
    浏览(51)
  • 二叉树(下)+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”

    各位CSDN的uu们你们好呀,今天小雅兰的内容仍然是二叉树和Leetcode每日一题,下面,就让我们进入二叉树的世界吧!!! 这个题目需要重新定义一个函数,函数参数需要有左子树和右子树,题目所给定的函数无法解决问题。 每个不为空的结点,都可以认为是一棵子树的根 

    2024年02月16日
    浏览(43)
  • 二叉树(中)+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”

    各位CSDN的uu们你们好呀,今天继续数据结构与算法专栏中的二叉树,下面,让我们进入二叉树的世界吧!!! 二叉树(上)——“数据结构与算法”_认真学习的小雅兰.的博客-CSDN博客 二叉树链式结构的实现 二叉树链式结构的实现 求二叉树的高度 但是这种写法有很大的问题

    2024年02月17日
    浏览(38)
  • 【算法每日一练】——买卖股票的最好时机

    💻个人简介 ⌨️作者简介: 大家好,我是〖雪月清〗 ❄️ 🎉个人主页:〖雪月清〗🌸 📣算法每日一练:带你感受算法百态⭐ 原题传送门 假设你有一个数组prices,长度为n,其中prices[i]是股票在第i天的价格,请根据这个价格数组,返回买卖股票能获得的最大收益 1.你可以

    2024年01月18日
    浏览(40)
  • 每日一练:前端js实现算法之两数之和

    方法一:暴力法 方法二:哈希表 方法一 :使用暴力法,通过两层循环遍历数组来查找符合条件的两个数。 方法二 :使用哈希表,通过一次遍历数组,将每个数的值和索引存储在哈希表中,同时查找是否存在符合条件的数。 暴力法的时间复杂度为 O(n^2) ,空间复杂度为 O(1

    2024年02月21日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包