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/
|
Rust每日一练 专栏 （2023.5.16~）更新中... |
|
Golang每日一练 专栏 （2023.3.11~）更新中... |
|
Python每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
C/C++每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
Java每日一练 专栏 （2023.3.11~2023.5.18）暂停更 |
6.13生日快乐
