目录
278. 第一个错误的版本 First Bad Version 🌟
278. 第一个错误的版本 First Bad Version
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 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：
func firstBadVersion(n int) int {
for i := 1; i <= n; i++ {
if isBadVersion(i) {
return i
}
}
return n
}
代码2：
func firstBadVersion(n int) int {
left, right := 1, n
for left < right {
mid := left + (right-left)/2
if isBadVersion(mid) {
right = mid
} else {
left = mid + 1
}
}
return left
}
279. 完全平方数 Perfect Squares
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12 输出：3 解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13 输出：2 解释：13 = 4 + 9
提示：
1 <= n <= 10^4
代码1：
package main
import "fmt"
func numSquares(n int) int {
dp := make([]int, n+1)
for i := 1; i <= n; i++ {
dp[i] = i
for j := 1; j*j <= i; j++ {
dp[i] = min(dp[i], dp[i-j*j]+1)
}
}
return dp[n]
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
func main() {
n := 12
fmt.Println(numSquares(n)) // 输出：3
n = 13
fmt.Println(numSquares(n)) // 输出：2
}
代码2：贪心+DFS
package main
import "fmt"
func numSquares(n int) int {
squares := []int{}
for i := 1; i*i <= n; i++ {
squares = append(squares, i*i)
}
cnt := 1 << 31
var dfs func(int, int)
dfs = func(num, depth int) {
if depth >= cnt {
return
}
if num == 0 {
cnt = depth
return
}
for i := len(squares) - 1; i >= 0; i-- {
if squares[i] <= num {
dfs(num-squares[i], depth+1)
}
}
}
dfs(n, 0)
return cnt
}
func main() {
n := 12
fmt.Println(numSquares(n)) // 输出：3
n = 13
fmt.Println(numSquares(n)) // 输出：2
}
输出：
3
2
🌟 每日一练刷题专栏 🌟
✨ 持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
6.13生日快乐