本文最后更新于 2025-03-30T12:48:37+08:00
题目
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
| 你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。
由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n],你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。
实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例 1:
输入:n = 5, bad = 4 输出:4 解释: 调用 isBadVersion(3) -> false 调用 isBadVersion(5) -> true 调用 isBadVersion(4) -> true 所以,4 是第一个错误的版本。 示例 2:
输入:n = 1, bad = 1 输出:1
提示:
1 <= bad <= n <= 2^31 - 1
|
题目思路
- 1、这里要注意,当API接口返回true时,不一定是找到了目标位置,还需要继续向前查找,直到找到第一个有问题的目标。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
|
class Solution { public: int firstBadVersion(int n) { int l = 1, r = n; while(l < r) { int mid = l + (r - l) / 2; if(isBadVersion(mid)) r = mid; else l = mid + 1; } return l; } };
|
复杂度
Day 38 278. 第一个错误的版本
https://chaggle.github.io/2021/10/17/Leetcode/91-day/day-38/