Leetcode算法Java全解答--278. 第一个错误的版本 偏执的太偏执、 2022-04-02 08:39 138阅读 0赞 # Leetcode算法Java全解答–278. 第一个错误的版本 # ### 文章目录 ### * Leetcode算法Java全解答--278. 第一个错误的版本 * * 题目 * 想法 * 结果 * 总结 * 代码 * * 我的答案 * 大佬们的答案 * 测试用例 * 其他 ## 题目 ## 你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。 假设你有 n 个版本 \[1, 2, …, n\],你想找出导致之后所有版本出错的第一个错误的版本。 你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。 示例: 给定 n = 5,并且 version = 4 是第一个错误的版本。 调用 isBadVersion(3) -> false 调用 isBadVersion(5) -> true 调用 isBadVersion(4) -> true 所以,4 是第一个错误的版本。 ## 想法 ## 1. 线性循环,在输入值为这个的时候失败了。 1420736637 1150769282 2. 二分法,记得控制好边界条件 ## 结果 ## 超过76%的测试案例 时间复杂度/空间复杂度:log(n)/1 ## 总结 ## ## 代码 ## ### 我的答案 ### public class Solution extends VersionControl { public int firstBadVersion(int n) { int left = 1; int right = n; while(left< right){ int center = left + (right - left) / 2; // int center = (left+right)/2; if(isBadVersion(center)){ right = center; }else{ left = center+1; } } return left; } } /** * 线性 */ public class Solution extends VersionControl { public int firstBadVersion(int n) { for(int i=n;i>0;i--){ if(!isBadVersion(i)){ return i+1; } } return 1; } } ### 大佬们的答案 ### public class Solution extends VersionControl { public int firstBadVersion(int n) { if( n == 2126753390){ return 1702766719; } if(n == 1420736637){ return 1150769282; } if(n == 1792997410) { return 1240808008; } if(n == 1926205968) return 1167880583; if(n == 1705930310) return 1508243771; if(n == 2147483647) return 2147483647; int start = 1; int end = n; int medium = ((n+1)-(n+1)%2)/2; while(start < end){ if(isBadVersion(medium)){ end = medium - 1; }else{ start = medium + 1; } medium = (start + end - (start + end) % 2) /2; } if(isBadVersion(start) == true){ return start; } return start + 1; } } ### 测试用例 ### ## 其他 ## 代码托管码云地址:[https://gitee.com/lizhaoandroid/LeetCodeAll.git][https_gitee.com_lizhaoandroid_LeetCodeAll.git] 查看其他内容可以点击专栏或者我的博客哈:[https://blog.csdn.net/cmqwan][https_blog.csdn.net_cmqwan] “大佬们的答案” 标签来自leetcode,侵权请联系我进行删改 如有疑问请联系,联系方式:QQ3060507060 [https_gitee.com_lizhaoandroid_LeetCodeAll.git]: https://gitee.com/lizhaoandroid/LeetCodeAll.git [https_blog.csdn.net_cmqwan]: https://blog.csdn.net/cmqwan
还没有评论,来说两句吧...