Skip to content

Commit 555737b

Browse files
halfrosthalfrost
committed
Add solution 0473
1 parent 5cf1b80 commit 555737b

File tree

12 files changed

+311
-19
lines changed

12 files changed

+311
-19
lines changed

‎README.md

Lines changed: 13 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -126,16 +126,16 @@
126126

127127
| | Easy | Medium | Hard | Total |
128128
|:--------:|:--------:|:--------:|:--------:|:--------:|
129-
|Optimizing|33|33|23|89|
129+
|Optimizing|33|32|23|88|
130130
|Accepted|**285**|**386**|**114**|**785**|
131131
|Total|499|1003|399|1901|
132-
|Perfection Rate|88.4%|91.5%|79.8%|88.7%|
132+
|Perfection Rate|88.4%|91.7%|79.8%|88.8%|
133133
|Completion Rate|57.1%|38.5%|28.6%|41.3%|
134134
|------------|----------------------------|----------------------------|----------------------------|----------------------------|
135135

136136
## 二. 目录
137137

138-
以下已经收录了 696 道题的题解，还有 11 道题在尝试优化到 beats 100%
138+
以下已经收录了 697 道题的题解，还有 11 道题在尝试优化到 beats 100%
139139

140140
| No. | Title | Solution | Acceptance | Difficulty | Frequency |
141141
|:--------:|:--------------------------------------------------------------|:--------:|:--------:|:--------:|:--------:|
@@ -611,7 +611,7 @@
611611
|0470|Implement Rand10() Using Rand7()|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0470.Implement-Rand10()-Using-Rand7())|46.1%|Medium||
612612
|0471|Encode String with Shortest Length||50.0%|Hard||
613613
|0472|Concatenated Words||44.0%|Hard||
614-
|0473|Matchsticks to Square||40.0%|Medium||
614+
|0473|Matchsticks to Square|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0473.Matchsticks-to-Square)|40.0%|Medium||
615615
|0474|Ones and Zeroes|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0474.Ones-and-Zeroes)|43.5%|Medium||
616616
|0475|Heaters|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0475.Heaters)|33.9%|Medium||
617617
|0476|Number Complement|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0476.Number-Complement)|65.2%|Easy||
@@ -664,7 +664,7 @@
664664
|0523|Continuous Subarray Sum|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0523.Continuous-Subarray-Sum)|25.2%|Medium||
665665
|0524|Longest Word in Dictionary through Deleting|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0524.Longest-Word-in-Dictionary-through-Deleting)|50.3%|Medium||
666666
|0525|Contiguous Array|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0525.Contiguous-Array)|43.9%|Medium||
667-
|0526|Beautiful Arrangement|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0526.Beautiful-Arrangement)|62.4%|Medium||
667+
|0526|Beautiful Arrangement|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0526.Beautiful-Arrangement)|62.3%|Medium||
668668
|0527|Word Abbreviation||56.8%|Hard||
669669
|0528|Random Pick with Weight|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0528.Random-Pick-with-Weight)|45.0%|Medium||
670670
|0529|Minesweeper|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0529.Minesweeper)|62.1%|Medium||
@@ -1745,7 +1745,7 @@
17451745
|1604|Alert Using Same Key-Card Three or More Times in a One Hour Period||43.5%|Medium||
17461746
|1605|Find Valid Matrix Given Row and Column Sums||77.6%|Medium||
17471747
|1606|Find Servers That Handled Most Number of Requests||38.1%|Hard||
1748-
|1607|Sellers With No Sales||55.1%|Easy||
1748+
|1607|Sellers With No Sales||55.2%|Easy||
17491749
|1608|Special Array With X Elements Greater Than or Equal X|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/1608.Special-Array-With-X-Elements-Greater-Than-or-Equal-X)|61.4%|Easy||
17501750
|1609|Even Odd Tree||52.3%|Medium||
17511751
|1610|Maximum Number of Visible Points||32.5%|Hard||
@@ -1778,9 +1778,9 @@
17781778
|1637|Widest Vertical Area Between Two Points Containing No Points||83.8%|Medium||
17791779
|1638|Count Substrings That Differ by One Character||71.2%|Medium||
17801780
|1639|Number of Ways to Form a Target String Given a Dictionary||40.3%|Hard||
1781-
|1640|Check Array Formation Through Concatenation|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/1640.Check-Array-Formation-Through-Concatenation)|55.6%|Easy||
1781+
|1640|Check Array Formation Through Concatenation|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/1640.Check-Array-Formation-Through-Concatenation)|55.5%|Easy||
17821782
|1641|Count Sorted Vowel Strings|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/1641.Count-Sorted-Vowel-Strings)|75.0%|Medium||
1783-
|1642|Furthest Building You Can Reach|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/1642.Furthest-Building-You-Can-Reach)|43.3%|Medium||
1783+
|1642|Furthest Building You Can Reach|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/1642.Furthest-Building-You-Can-Reach)|43.4%|Medium||
17841784
|1643|Kth Smallest Instructions||45.4%|Hard||
17851785
|1644|Lowest Common Ancestor of a Binary Tree II||56.9%|Medium||
17861786
|1645|Hopper Company Queries II||38.9%|Hard||
@@ -1857,7 +1857,7 @@
18571857
|1716|Calculate Money in Leetcode Bank|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/1716.Calculate-Money-in-Leetcode-Bank)|64.1%|Easy||
18581858
|1717|Maximum Score From Removing Substrings||41.6%|Medium||
18591859
|1718|Construct the Lexicographically Largest Valid Sequence||48.4%|Medium||
1860-
|1719|Number Of Ways To Reconstruct A Tree||39.7%|Hard||
1860+
|1719|Number Of Ways To Reconstruct A Tree||39.8%|Hard||
18611861
|1720|Decode XORed Array|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/1720.Decode-XORed-Array)|85.4%|Easy||
18621862
|1721|Swapping Nodes in a Linked List|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/1721.Swapping-Nodes-in-a-Linked-List)|66.6%|Medium||
18631863
|1722|Minimize Hamming Distance After Swap Operations||46.0%|Medium||
@@ -1917,7 +1917,7 @@
19171917
|1776|Car Fleet II||49.7%|Hard||
19181918
|1777|Product's Price for Each Store||86.4%|Easy||
19191919
|1778|Shortest Path in a Hidden Grid||45.0%|Medium||
1920-
|1779|Find Nearest Point That Has the Same X or Y Coordinate||66.7%|Easy||
1920+
|1779|Find Nearest Point That Has the Same X or Y Coordinate||66.6%|Easy||
19211921
|1780|Check if Number is a Sum of Powers of Three||63.2%|Medium||
19221922
|1781|Sum of Beauty of All Substrings||58.3%|Medium||
19231923
|1782|Count Pairs Of Nodes||34.4%|Hard||
@@ -1981,7 +1981,7 @@
19811981
|1840|Maximum Building Height||34.3%|Hard||
19821982
|1841|League Statistics||61.7%|Medium||
19831983
|1842|Next Palindrome Using Same Digits||63.8%|Hard||
1984-
|1843|Suspicious Bank Accounts||52.2%|Medium||
1984+
|1843|Suspicious Bank Accounts||52.1%|Medium||
19851985
|1844|Replace All Digits with Characters||80.1%|Easy||
19861986
|1845|Seat Reservation Manager||55.1%|Medium||
19871987
|1846|Maximum Element After Decreasing and Rearranging||54.6%|Medium||
@@ -2023,7 +2023,7 @@
20232023
|1882|Process Tasks Using Servers||30.4%|Medium||
20242024
|1883|Minimum Skips to Arrive at Meeting On Time||38.0%|Hard||
20252025
|1884|Egg Drop With 2 Eggs and N Floors||70.6%|Medium||
2026-
|1885|Count Pairs in Two Arrays||56.2%|Medium||
2026+
|1885|Count Pairs in Two Arrays||56.3%|Medium||
20272027
|1886|Determine Whether Matrix Can Be Obtained By Rotation||53.6%|Easy||
20282028
|1887|Reduction Operations to Make the Array Elements Equal||59.5%|Medium||
20292029
|1888|Minimum Number of Flips to Make the Binary String Alternating||33.6%|Medium||
@@ -2032,7 +2032,7 @@
20322032
|1891|Cutting Ribbons||55.8%|Medium||
20332033
|1892|Page Recommendations II||40.6%|Hard||
20342034
|1893|Check if All the Integers in a Range Are Covered||48.8%|Easy||
2035-
|1894|Find the Student that Will Replace the Chalk||37.9%|Medium||
2035+
|1894|Find the Student that Will Replace the Chalk||37.8%|Medium||
20362036
|1895|Largest Magic Square||48.4%|Medium||
20372037
|1896|Minimum Cost to Change the Final Value of Expression||49.4%|Hard||
20382038
|1897|Redistribute Characters to Make All Strings Equal||58.1%|Easy||

‎leetcode/0473.Matchsticks-to-Square/473. Matchsticks to Square.go

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
package leetcode
2+
3+
import "sort"
4+
5+
func makesquare(matchsticks []int) bool {
6+
if len(matchsticks) < 4 {
7+
return false
8+
}
9+
total := 0
10+
for _, v := range matchsticks {
11+
total += v
12+
}
13+
if total%4 != 0 {
14+
return false
15+
}
16+
sort.Slice(matchsticks, func(i, j int) bool {
17+
return matchsticks[i] > matchsticks[j]
18+
})
19+
visited := make([]bool, 16)
20+
return dfs(matchsticks, 0, 0, 0, total, &visited)
21+
}
22+
23+
func dfs(matchsticks []int, cur, group, sum, total int, visited *[]bool) bool {
24+
if group == 4 {
25+
return true
26+
}
27+
if sum > total/4 {
28+
return false
29+
}
30+
if sum == total/4 {
31+
return dfs(matchsticks, 0, group+1, 0, total, visited)
32+
}
33+
last := -1
34+
for i := cur; i < len(matchsticks); i++ {
35+
if (*visited)[i] {
36+
continue
37+
}
38+
if last == matchsticks[i] {
39+
continue
40+
}
41+
(*visited)[i] = true
42+
last = matchsticks[i]
43+
if dfs(matchsticks, i+1, group, sum+matchsticks[i], total, visited) {
44+
return true
45+
}
46+
(*visited)[i] = false
47+
}
48+
return false
49+
}

‎leetcode/0473.Matchsticks-to-Square/473. Matchsticks to Square_test.go

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

‎leetcode/0473.Matchsticks-to-Square/README.md

Lines changed: 94 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,94 @@
1+
# [473. Matchsticks to Square](https://leetcode.com/problems/matchsticks-to-square/)
2+
3+
4+
## 题目
5+
6+
You are given an integer array `matchsticks` where `matchsticks[i]` is the length of the `ith` matchstick. You want to use **all the matchsticks** to make one square. You **should not break** any stick, but you can link them up, and each matchstick must be used **exactly one time**.
7+
8+
Return `true` if you can make this square and `false` otherwise.
9+
10+
**Example 1:**
11+
12+
![https://assets.leetcode.com/uploads/2021/04/09/matchsticks1-grid.jpg](https://assets.leetcode.com/uploads/2021/04/09/matchsticks1-grid.jpg)
13+
14+
```
15+
Input: matchsticks = [1,1,2,2,2]
16+
Output: true
17+
Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.
18+
```
19+
20+
**Example 2:**
21+
22+
```
23+
Input: matchsticks = [3,3,3,3,4]
24+
Output: false
25+
Explanation: You cannot find a way to form a square with all the matchsticks.
26+
```
27+
28+
**Constraints:**
29+
30+
- `1 <= matchsticks.length <= 15`
31+
- `0 <= matchsticks[i] <= 109`
32+
33+
## 题目大意
34+
35+
现在已知小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。
36+
37+
## 解题思路
38+
39+
- 将火柴拼成一个正方形，可以将它们分成四组，每一根火柴恰好属于其中的一组；并且每一组火柴的长度之和都相同，等于所有火柴长度之和的四分之一。
40+
- 考虑暴力解法，使用深度优先搜索枚举出所有的分组情况，并对于每一种情况，判断是否满足上述的两个条件(每根火柴属于其中一组，每组火柴长度之和相同)。依次对每一根火柴进行搜索，当搜索到第 i 根火柴时，可以考虑把它放到四组中的任意一种。对于每一种放置方法，继续对第 i + 1 根火柴进行深搜。当我们搜索完全部的 N 根火柴后，再判断每一组火柴的长度之和是否都相同。
41+
42+
## 代码
43+
44+
```go
45+
package leetcode
46+
47+
import "sort"
48+
49+
func makesquare(matchsticks []int) bool {
50+
if len(matchsticks) < 4 {
51+
return false
52+
}
53+
total := 0
54+
for _, v := range matchsticks {
55+
total += v
56+
}
57+
if total%4 != 0 {
58+
return false
59+
}
60+
sort.Slice(matchsticks, func(i, j int) bool {
61+
return matchsticks[i] > matchsticks[j]
62+
})
63+
visited := make([]bool, 16)
64+
return dfs(matchsticks, 0, 0, 0, total, &visited)
65+
}
66+
67+
func dfs(matchsticks []int, cur, group, sum, total int, visited *[]bool) bool {
68+
if group == 4 {
69+
return true
70+
}
71+
if sum > total/4 {
72+
return false
73+
}
74+
if sum == total/4 {
75+
return dfs(matchsticks, 0, group+1, 0, total, visited)
76+
}
77+
last := -1
78+
for i := cur; i < len(matchsticks); i++ {
79+
if (*visited)[i] {
80+
continue
81+
}
82+
if last == matchsticks[i] {
83+
continue
84+
}
85+
(*visited)[i] = true
86+
last = matchsticks[i]
87+
if dfs(matchsticks, i+1, group, sum+matchsticks[i], total, visited) {
88+
return true
89+
}
90+
(*visited)[i] = false
91+
}
92+
return false
93+
}
94+
```

‎website/content/ChapterFour/0400~0499/0470.Implement-Rand10-Using-Rand7.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -103,5 +103,5 @@ func rand101() int {
103103
----------------------------------------------
104104
<div style="display: flex;justify-content: space-between;align-items: center;">
105105
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0400~0499/0463.Island-Perimeter/">⬅️上一页</a></p>
106-
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0400~0499/0474.Ones-and-Zeroes/">下一页➡️</a></p>
106+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0400~0499/0473.Matchsticks-to-Square/">下一页➡️</a></p>
107107
</div>

0 commit comments

Comments
 (0)