Skip to content

Commit b2a4f39

Browse files
halfrosthalfrost
committed
Add solution 0278
1 parent 259eba0 commit b2a4f39

26 files changed

+1672
-1460
lines changed

‎README.md

Lines changed: 971 additions & 956 deletions
Large diffs are not rendered by default.

‎leetcode/0278.First-Bad-Version/278. First Bad Version.go

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
package leetcode
2+
3+
import "sort"
4+
5+
/**
6+
* Forward declaration of isBadVersion API.
7+
* @param version your guess about first bad version
8+
* @return true if current version is bad
9+
* false if current version is good
10+
* func isBadVersion(version int) bool;
11+
*/
12+
13+
func firstBadVersion(n int) int {
14+
return sort.Search(n, func(version int) bool { return isBadVersion(version) })
15+
}
16+
17+
func isBadVersion(version int) bool {
18+
return true
19+
}

‎leetcode/0278.First-Bad-Version/278. First Bad Version_test.go

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
package leetcode
2+
3+
import (
4+
"fmt"
5+
"testing"
6+
)
7+
8+
type question278 struct {
9+
para278
10+
ans278
11+
}
12+
13+
// para 是参数
14+
// one 代表第一个参数
15+
type para278 struct {
16+
n int
17+
}
18+
19+
// ans 是答案
20+
// one 代表第一个答案
21+
type ans278 struct {
22+
one int
23+
}
24+
25+
func Test_Problem278(t *testing.T) {
26+
27+
qs := []question278{
28+
29+
{
30+
para278{5},
31+
ans278{4},
32+
},
33+
{
34+
para278{1},
35+
ans278{1},
36+
},
37+
}
38+
39+
fmt.Printf("------------------------Leetcode Problem 278------------------------\n")
40+
41+
for _, q := range qs {
42+
_, p := q.ans278, q.para278
43+
fmt.Printf("【input】:%v 【output】:%v\n", p, firstBadVersion(p.n))
44+
}
45+
fmt.Printf("\n\n\n")
46+
}

‎leetcode/0278.First-Bad-Version/README.md

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
# [278. First Bad Version](https://leetcode.com/problems/first-bad-version/)
2+
3+
## 题目
4+
5+
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
6+
7+
Suppose you have `n` versions `[1, 2, ..., n]` and you want to find out the first bad one, which causes all the following ones to be bad.
8+
9+
You are given an API `bool isBadVersion(version)` which returns whether `version` is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
10+
11+
**Example 1:**
12+
13+
```
14+
Input: n = 5, bad = 4
15+
Output: 4
16+
Explanation:
17+
call isBadVersion(3) -> false
18+
call isBadVersion(5) -> true
19+
call isBadVersion(4) -> true
20+
Then 4 is the first bad version.
21+
22+
```
23+
24+
**Example 2:**
25+
26+
```
27+
Input: n = 1, bad = 1
28+
Output: 1
29+
30+
```
31+
32+
**Constraints:**
33+
34+
- `1 <= bad <= n <= 231 - 1`
35+
36+
## 题目大意
37+
38+
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
39+
40+
## 解题思路
41+
42+
- 我们知道开发产品迭代的版本，如果当一个版本为正确版本，则该版本之前的所有版本均为正确版本；当一个版本为错误版本，则该版本之后的所有版本均为错误版本。利用这个性质就可以进行二分查找。利用二分搜索，也可以满足减少对调用 API 的次数的要求。时间复杂度：O(logn)，其中 n 是给定版本的数量。空间复杂度：O(1)。
43+
44+
## 代码
45+
46+
```go
47+
package leetcode
48+
49+
import "sort"
50+
51+
/**
52+
* Forward declaration of isBadVersion API.
53+
* @param version your guess about first bad version
54+
* @return true if current version is bad
55+
* false if current version is good
56+
* func isBadVersion(version int) bool;
57+
*/
58+
59+
func firstBadVersion(n int) int {
60+
return sort.Search(n, func(version int) bool { return isBadVersion(version) })
61+
}
62+
```

‎website/content/ChapterFour/0200~0299/0275.H-Index-II.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -74,5 +74,5 @@ func hIndex275(citations []int) int {
7474
----------------------------------------------
7575
<div style="display: flex;justify-content: space-between;align-items: center;">
7676
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0200~0299/0274.H-Index/">⬅️上一页</a></p>
77-
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0200~0299/0283.Move-Zeroes/">下一页➡️</a></p>
77+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0200~0299/0278.First-Bad-Version/">下一页➡️</a></p>
7878
</div>

‎website/content/ChapterFour/0200~0299/0278.First-Bad-Version.md

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
# [278. First Bad Version](https://leetcode.com/problems/first-bad-version/)
2+
3+
## 题目
4+
5+
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
6+
7+
Suppose you have `n` versions `[1, 2, ..., n]` and you want to find out the first bad one, which causes all the following ones to be bad.
8+
9+
You are given an API `bool isBadVersion(version)` which returns whether `version` is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
10+
11+
**Example 1:**
12+
13+
```
14+
Input: n = 5, bad = 4
15+
Output: 4
16+
Explanation:
17+
call isBadVersion(3) -> false
18+
call isBadVersion(5) -> true
19+
call isBadVersion(4) -> true
20+
Then 4 is the first bad version.
21+
22+
```
23+
24+
**Example 2:**
25+
26+
```
27+
Input: n = 1, bad = 1
28+
Output: 1
29+
30+
```
31+
32+
**Constraints:**
33+
34+
- `1 <= bad <= n <= 231 - 1`
35+
36+
## 题目大意
37+
38+
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
39+
40+
## 解题思路
41+
42+
- 我们知道开发产品迭代的版本，如果当一个版本为正确版本，则该版本之前的所有版本均为正确版本；当一个版本为错误版本，则该版本之后的所有版本均为错误版本。利用这个性质就可以进行二分查找。利用二分搜索，也可以满足减少对调用 API 的次数的要求。时间复杂度：O(logn)，其中 n 是给定版本的数量。空间复杂度：O(1)。
43+
44+
## 代码
45+
46+
```go
47+
package leetcode
48+
49+
import "sort"
50+
51+
/**
52+
* Forward declaration of isBadVersion API.
53+
* @param version your guess about first bad version
54+
* @return true if current version is bad
55+
* false if current version is good
56+
* func isBadVersion(version int) bool;
57+
*/
58+
59+
func firstBadVersion(n int) int {
60+
return sort.Search(n, func(version int) bool { return isBadVersion(version) })
61+
}
62+
```
63+
64+
65+
----------------------------------------------
66+
<div style="display: flex;justify-content: space-between;align-items: center;">
67+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0200~0299/0275.H-Index-II/">⬅️上一页</a></p>
68+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0200~0299/0283.Move-Zeroes/">下一页➡️</a></p>
69+
</div>

‎website/content/ChapterFour/0200~0299/0283.Move-Zeroes.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -57,6 +57,6 @@ func moveZeroes(nums []int) {
5757

5858
----------------------------------------------
5959
<div style="display: flex;justify-content: space-between;align-items: center;">
60-
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0200~0299/0275.H-Index-II/">⬅️上一页</a></p>
60+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0200~0299/0278.First-Bad-Version/">⬅️上一页</a></p>
6161
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0200~0299/0284.Peeking-Iterator/">下一页➡️</a></p>
6262
</div>

0 commit comments

Comments
 (0)