目錄

278. 第一個錯誤的版本 First Bad Version????

279. 完全平方數(shù) Perfect Squares??????

?? 每日一練刷題專欄???

Rust每日一練 專欄

Golang每日一練 專欄

Python每日一練 專欄

C/C++每日一練 專欄

Java每日一練 專欄

278. 第一個錯誤的版本 First Bad Version

你是產(chǎn)品經(jīng)理，目前正在帶領(lǐng)一個團(tuán)隊開發(fā)新的產(chǎn)品。不幸的是，你的產(chǎn)品的最新版本沒有通過質(zhì)量檢測。由于每個版本都是基于之前的版本開發(fā)的，所以錯誤的版本之后的所有版本都是錯的。

假設(shè)你有?n?個版本?[1, 2, ..., n]，你想找出導(dǎo)致之后所有版本出錯的第一個錯誤的版本。

你可以通過調(diào)用?bool isBadVersion(version)?接口來判斷版本號?version?是否在單元測試中出錯。實(shí)現(xiàn)一個函數(shù)來查找第一個錯誤的版本。你應(yīng)該盡量減少對調(diào)用 API 的次數(shù)。

示例 1：

輸入：n = 5, bad = 4
輸出：4
解釋：
調(diào)用 isBadVersion(3) -> false 
調(diào)用 isBadVersion(5)?-> true 
調(diào)用 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. 完全平方數(shù) Perfect Squares

給你一個整數(shù)?n?，返回?和為?n?的完全平方數(shù)的最少數(shù)量?。

完全平方數(shù)?是一個整數(shù)，其值等于另一個整數(shù)的平方；換句話說，其值等于一個整數(shù)自乘的積。例如，1、4、9?和?16?都是完全平方數(shù)，而?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

?? 每日一練刷題專欄???

? 持續(xù)，努力奮斗做強(qiáng)刷題搬運(yùn)工！

?? 點(diǎn)贊，你的認(rèn)可是我堅持的動力！?

???收藏，你的青睞是我努力的方向！?

? 評論，你的意見是我進(jìn)步的財富！??

??主頁：https://hannyang.blog.csdn.net/?

6.13生日快樂文章來源地址http://www.zghlxwxcb.cn/news/detail-486281.html

到了這里，關(guān)于Golang每日一練(leetDay0095) 第一個錯誤的版本、完全平方數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！