Skip to content

Commit 5cf1b80

Browse files
halfrosthalfrost
committed
Add solution 0279、0518
1 parent 48cb642 commit 5cf1b80

23 files changed

+507
-44
lines changed

‎README.md

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

‎leetcode/0279.Perfect-Squares/279. Perfect Squares.go

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
package leetcode
2+
3+
import "math"
4+
5+
func numSquares(n int) int {
6+
if isPerfectSquare(n) {
7+
return 1
8+
}
9+
if checkAnswer4(n) {
10+
return 4
11+
}
12+
for i := 1; i*i <= n; i++ {
13+
j := n - i*i
14+
if isPerfectSquare(j) {
15+
return 2
16+
}
17+
}
18+
return 3
19+
}
20+
21+
// 判断是否为完全平方数
22+
func isPerfectSquare(n int) bool {
23+
sq := int(math.Floor(math.Sqrt(float64(n))))
24+
return sq*sq == n
25+
}
26+
27+
// 判断是否能表示为 4^k*(8m+7)
28+
func checkAnswer4(x int) bool {
29+
for x%4 == 0 {
30+
x /= 4
31+
}
32+
return x%8 == 7
33+
}

‎leetcode/0279.Perfect-Squares/279. Perfect Squares_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 question279 struct {
9+
para279
10+
ans279
11+
}
12+
13+
// para 是参数
14+
// one 代表第一个参数
15+
type para279 struct {
16+
n int
17+
}
18+
19+
// ans 是答案
20+
// one 代表第一个答案
21+
type ans279 struct {
22+
one int
23+
}
24+
25+
func Test_Problem279(t *testing.T) {
26+
27+
qs := []question279{
28+
29+
{
30+
para279{13},
31+
ans279{2},
32+
},
33+
{
34+
para279{12},
35+
ans279{3},
36+
},
37+
}
38+
39+
fmt.Printf("------------------------Leetcode Problem 279------------------------\n")
40+
41+
for _, q := range qs {
42+
_, p := q.ans279, q.para279
43+
fmt.Printf("【input】:%v 【output】:%v\n", p, numSquares(p.n))
44+
}
45+
fmt.Printf("\n\n\n")
46+
}

‎leetcode/0279.Perfect-Squares/README.md

Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
# [279. Perfect Squares](https://leetcode.com/problems/perfect-squares/)
2+
3+
4+
## 题目
5+
6+
Given an integer `n`, return *the least number of perfect square numbers that sum to* `n`.
7+
8+
A **perfect square** is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, `1`, `4`, `9`, and `16` are perfect squares while `3` and `11` are not.
9+
10+
**Example 1:**
11+
12+
```
13+
Input: n = 12
14+
Output: 3
15+
Explanation: 12 = 4 + 4 + 4.
16+
```
17+
18+
**Example 2:**
19+
20+
```
21+
Input: n = 13
22+
Output: 2
23+
Explanation: 13 = 4 + 9.
24+
```
25+
26+
**Constraints:**
27+
28+
- `1 <= n <= 104`
29+
30+
## 题目大意
31+
32+
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
33+
34+
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
35+
36+
## 解题思路
37+
38+
- 由拉格朗日的四平方定理可得，每个自然数都可以表示为四个整数平方之和。 其中四个数字是整数。四平方和定理证明了任意一个正整数都可以被表示为至多四个正整数的平方和。这给出了本题的答案的上界。
39+
- 四平方和定理可以推出三平方和推论：当且仅当 {{< katex >}} n \neq 4^{k} \times (8*m + 7){{< /katex >}} 时，n 可以被表示为至多三个正整数的平方和。所以当 {{< katex >}} n = 4^{k} * (8*m + 7){{< /katex >}} 时，n 只能被表示为四个正整数的平方和。此时我们可以直接返回 4。
40+
- 当 {{< katex >}} n \neq 4^{k} \times (8*m + 7){{< /katex >}} 时，需要判断 n 到底可以分解成几个完全平方数之和。答案肯定是 1，2，3 中的一个。题目要求我们求最小的，所以从 1 开始一个个判断是否满足。如果答案为 1，代表 n 为完全平方数，这很好判断。如果答案为 2，代表 {{< katex >}} n = a^{2} + b^{2} {{< /katex >}}，枚举 {{< katex >}} 1 \leqslant a \leqslant \sqrt{n} {{< /katex >}}，判断 {{< katex >}} n - a^{2} {{< /katex >}} 是否为完全平方数。当 1 和 2 都排除了，剩下的答案只能为 3 了。
41+
42+
## 代码
43+
44+
```go
45+
package leetcode
46+
47+
import "math"
48+
49+
func numSquares(n int) int {
50+
if isPerfectSquare(n) {
51+
return 1
52+
}
53+
if checkAnswer4(n) {
54+
return 4
55+
}
56+
for i := 1; i*i <= n; i++ {
57+
j := n - i*i
58+
if isPerfectSquare(j) {
59+
return 2
60+
}
61+
}
62+
return 3
63+
}
64+
65+
// 判断是否为完全平方数
66+
func isPerfectSquare(n int) bool {
67+
sq := int(math.Floor(math.Sqrt(float64(n))))
68+
return sq*sq == n
69+
}
70+
71+
// 判断是否能表示为 4^k*(8m+7)
72+
func checkAnswer4(x int) bool {
73+
for x%4 == 0 {
74+
x /= 4
75+
}
76+
return x%8 == 7
77+
}
78+
```

‎leetcode/0518.Coin-Change-2/518. Coin Change 2.go

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
package leetcode
2+
3+
func change(amount int, coins []int) int {
4+
dp := make([]int, amount+1)
5+
dp[0] = 1
6+
for _, coin := range coins {
7+
for i := coin; i <= amount; i++ {
8+
dp[i] += dp[i-coin]
9+
}
10+
}
11+
return dp[amount]
12+
}

‎leetcode/0518.Coin-Change-2/518. Coin Change 2_test.go

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

‎leetcode/0518.Coin-Change-2/README.md

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
# [518. Coin Change 2](https://leetcode.com/problems/coin-change-2/)
2+
3+
4+
## 题目
5+
6+
You are given an integer array `coins` representing coins of different denominations and an integer `amount` representing a total amount of money.
7+
8+
Return *the number of combinations that make up that amount*. If that amount of money cannot be made up by any combination of the coins, return `0`.
9+
10+
You may assume that you have an infinite number of each kind of coin.
11+
12+
The answer is **guaranteed** to fit into a signed **32-bit** integer.
13+
14+
**Example 1:**
15+
16+
```
17+
Input: amount = 5, coins = [1,2,5]
18+
Output: 4
19+
Explanation: there are four ways to make up the amount:
20+
5=5
21+
5=2+2+1
22+
5=2+1+1+1
23+
5=1+1+1+1+1
24+
```
25+
26+
**Example 2:**
27+
28+
```
29+
Input: amount = 3, coins = [2]
30+
Output: 0
31+
Explanation: the amount of 3 cannot be made up just with coins of 2.
32+
```
33+
34+
**Example 3:**
35+
36+
```
37+
Input: amount = 10, coins = [10]
38+
Output: 1
39+
```
40+
41+
**Constraints:**
42+
43+
- `1 <= coins.length <= 300`
44+
- `1 <= coins[i] <= 5000`
45+
- All the values of `coins` are **unique**.
46+
- `0 <= amount <= 5000`
47+
48+
## 题目大意
49+
50+
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。假设每一种面额的硬币有无限个。题目数据保证结果符合 32 位带符号整数。
51+
52+
## 解题思路
53+
54+
- 此题虽然名字叫 Coin Change，但是不是经典的背包九讲问题。题目中 coins 的每个元素可以选取多次，且不考虑选取元素的顺序，因此这道题实际需要计算的是选取硬币的组合数。定义 dp[i] 表示金额之和等于 i 的硬币组合数，目标求 dp[amount]。初始边界条件为 dp[0] = 1，即不取任何硬币，就这一种取法，金额为 0 。状态转移方程 dp[i] += dp[i-coin]，coin 为当前枚举的 coin。
55+
- 可能有读者会有疑惑，上述做法会不会出现重复计算。答案是不会。外层循环是遍历数组 coins 的值，内层循环是遍历不同的金额之和，在计算 dp[i] 的值时，可以确保金额之和等于 i 的硬币面额的顺序，由于顺序确定，因此不会重复计算不同的排列。
56+
- 和此题完全一致的解题思路的题有，第 377 题和第 494 题。
57+
58+
## 代码
59+
60+
```go
61+
package leetcode
62+
63+
func change(amount int, coins []int) int {
64+
dp := make([]int, amount+1)
65+
dp[0] = 1
66+
for _, coin := range coins {
67+
for i := coin; i <= amount; i++ {
68+
dp[i] += dp[i-coin]
69+
}
70+
}
71+
return dp[amount]
72+
}
73+
```

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

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -65,5 +65,5 @@ func firstBadVersion(n int) int {
6565
----------------------------------------------
6666
<div style="display: flex;justify-content: space-between;align-items: center;">
6767
<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>
68+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0200~0299/0279.Perfect-Squares/">下一页➡️</a></p>
6969
</div>

‎website/content/ChapterFour/0200~0299/0279.Perfect-Squares.md

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
# [279. Perfect Squares](https://leetcode.com/problems/perfect-squares/)
2+
3+
4+
## 题目
5+
6+
Given an integer `n`, return *the least number of perfect square numbers that sum to* `n`.
7+
8+
A **perfect square** is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, `1`, `4`, `9`, and `16` are perfect squares while `3` and `11` are not.
9+
10+
**Example 1:**
11+
12+
```
13+
Input: n = 12
14+
Output: 3
15+
Explanation: 12 = 4 + 4 + 4.
16+
```
17+
18+
**Example 2:**
19+
20+
```
21+
Input: n = 13
22+
Output: 2
23+
Explanation: 13 = 4 + 9.
24+
```
25+
26+
**Constraints:**
27+
28+
- `1 <= n <= 104`
29+
30+
## 题目大意
31+
32+
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
33+
34+
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
35+
36+
## 解题思路
37+
38+
- 由拉格朗日的四平方定理可得，每个自然数都可以表示为四个整数平方之和。 其中四个数字是整数。四平方和定理证明了任意一个正整数都可以被表示为至多四个正整数的平方和。这给出了本题的答案的上界。
39+
- 四平方和定理可以推出三平方和推论：当且仅当 {{< katex >}} n \neq 4^{k} \times (8*m + 7){{< /katex >}} 时，n 可以被表示为至多三个正整数的平方和。所以当 {{< katex >}} n = 4^{k} * (8*m + 7){{< /katex >}} 时，n 只能被表示为四个正整数的平方和。此时我们可以直接返回 4。
40+
- 当 {{< katex >}} n \neq 4^{k} \times (8*m + 7){{< /katex >}} 时，需要判断 n 到底可以分解成几个完全平方数之和。答案肯定是 1，2，3 中的一个。题目要求我们求最小的，所以从 1 开始一个个判断是否满足。如果答案为 1，代表 n 为完全平方数，这很好判断。如果答案为 2，代表 {{< katex >}} n = a^{2} + b^{2} {{< /katex >}}，枚举 {{< katex >}} 1 \leqslant a \leqslant \sqrt{n} {{< /katex >}}，判断 {{< katex >}} n - a^{2} {{< /katex >}} 是否为完全平方数。当 1 和 2 都排除了，剩下的答案只能为 3 了。
41+
42+
## 代码
43+
44+
```go
45+
package leetcode
46+
47+
import "math"
48+
49+
func numSquares(n int) int {
50+
if isPerfectSquare(n) {
51+
return 1
52+
}
53+
if checkAnswer4(n) {
54+
return 4
55+
}
56+
for i := 1; i*i <= n; i++ {
57+
j := n - i*i
58+
if isPerfectSquare(j) {
59+
return 2
60+
}
61+
}
62+
return 3
63+
}
64+
65+
// 判断是否为完全平方数
66+
func isPerfectSquare(n int) bool {
67+
sq := int(math.Floor(math.Sqrt(float64(n))))
68+
return sq*sq == n
69+
}
70+
71+
// 判断是否能表示为 4^k*(8m+7)
72+
func checkAnswer4(x int) bool {
73+
for x%4 == 0 {
74+
x /= 4
75+
}
76+
return x%8 == 7
77+
}
78+
```
79+
80+
81+
----------------------------------------------
82+
<div style="display: flex;justify-content: space-between;align-items: center;">
83+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0200~0299/0278.First-Bad-Version/">⬅️上一页</a></p>
84+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0200~0299/0283.Move-Zeroes/">下一页➡️</a></p>
85+
</div>

0 commit comments

Comments
 (0)