Skip to content

Commit 35530a4

Browse files
halfrosthalfrost
committed
Update solution 0116
1 parent d1e24bf commit 35530a4

15 files changed

+200
-60
lines changed

‎README.md

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

127127
| | Easy | Medium | Hard | Total |
128128
|:--------:|:--------:|:--------:|:--------:|:--------:|
129-
|Optimizing|33|37|27|97|
129+
|Optimizing|33|36|27|96|
130130
|Accepted|**284**|**407**|**120**|**811**|
131131
|Total|506|1035|415|1956|
132-
|Perfection Rate|88.4%|90.9%|77.5%|88.0%|
132+
|Perfection Rate|88.4%|91.2%|77.5%|88.2%|
133133
|Completion Rate|56.1%|39.3%|28.9%|41.5%|
134134
|------------|----------------------------|----------------------------|----------------------------|----------------------------|
135135

136136
## 二. 目录
137137

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

140140
| No. | Title | Solution | Acceptance | Difficulty | Frequency |
141141
|:--------:|:--------------------------------------------------------------|:--------:|:--------:|:--------:|:--------:|
@@ -254,7 +254,7 @@
254254
|0113|Path Sum II|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0113.Path-Sum-II)|51.4%|Medium||
255255
|0114|Flatten Binary Tree to Linked List|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0114.Flatten-Binary-Tree-to-Linked-List)|54.5%|Medium||
256256
|0115|Distinct Subsequences|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0115.Distinct-Subsequences)|40.6%|Hard||
257-
|0116|Populating Next Right Pointers in Each Node||51.4%|Medium||
257+
|0116|Populating Next Right Pointers in Each Node|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0116.Populating-Next-Right-Pointers-in-Each-Node)|51.4%|Medium||
258258
|0117|Populating Next Right Pointers in Each Node II||43.5%|Medium||
259259
|0118|Pascal's Triangle|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0118.Pascals-Triangle)|58.2%|Easy||
260260
|0119|Pascal's Triangle II|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0119.Pascals-Triangle-II)|53.8%|Easy||
@@ -514,7 +514,7 @@
514514
|0373|Find K Pairs with Smallest Sums|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0373.Find-K-Pairs-with-Smallest-Sums)|39.0%|Medium||
515515
|0374|Guess Number Higher or Lower|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0374.Guess-Number-Higher-or-Lower)|46.0%|Easy||
516516
|0375|Guess Number Higher or Lower II||43.5%|Medium||
517-
|0376|Wiggle Subsequence|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0376.Wiggle-Subsequence)|42.8%|Medium||
517+
|0376|Wiggle Subsequence|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0376.Wiggle-Subsequence)|42.9%|Medium||
518518
|0377|Combination Sum IV|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0377.Combination-Sum-IV)|47.5%|Medium||
519519
|0378|Kth Smallest Element in a Sorted Matrix|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0378.Kth-Smallest-Element-in-a-Sorted-Matrix)|58.0%|Medium||
520520
|0379|Design Phone Directory||49.3%|Medium||
@@ -633,7 +633,7 @@
633633
|0492|Construct the Rectangle||51.3%|Easy||
634634
|0493|Reverse Pairs|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0493.Reverse-Pairs)|28.2%|Hard||
635635
|0494|Target Sum|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0494.Target-Sum)|45.4%|Medium||
636-
|0495|Teemo Attacking||56.3%|Easy||
636+
|0495|Teemo Attacking||56.2%|Easy||
637637
|0496|Next Greater Element I|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0496.Next-Greater-Element-I)|66.9%|Easy||
638638
|0497|Random Point in Non-overlapping Rectangles|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0497.Random-Point-in-Non-overlapping-Rectangles)|39.1%|Medium||
639639
|0498|Diagonal Traverse|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0498.Diagonal-Traverse)|52.0%|Medium||
@@ -859,7 +859,7 @@
859859
|0718|Maximum Length of Repeated Subarray|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0718.Maximum-Length-of-Repeated-Subarray)|51.1%|Medium||
860860
|0719|Find K-th Smallest Pair Distance|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0719.Find-K-th-Smallest-Pair-Distance)|33.2%|Hard||
861861
|0720|Longest Word in Dictionary|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0720.Longest-Word-in-Dictionary)|49.9%|Medium||
862-
|0721|Accounts Merge|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0721.Accounts-Merge)|53.3%|Medium||
862+
|0721|Accounts Merge|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0721.Accounts-Merge)|53.4%|Medium||
863863
|0722|Remove Comments||36.9%|Medium||
864864
|0723|Candy Crush||73.5%|Medium||
865865
|0724|Find Pivot Index|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0724.Find-Pivot-Index)|48.0%|Easy||
@@ -982,7 +982,7 @@
982982
|0841|Keys and Rooms|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0841.Keys-and-Rooms)|67.2%|Medium||
983983
|0842|Split Array into Fibonacci Sequence|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0842.Split-Array-into-Fibonacci-Sequence)|37.2%|Medium||
984984
|0843|Guess the Word||45.2%|Hard||
985-
|0844|Backspace String Compare|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0844.Backspace-String-Compare)|47.2%|Easy||
985+
|0844|Backspace String Compare|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0844.Backspace-String-Compare)|47.3%|Easy||
986986
|0845|Longest Mountain in Array|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0845.Longest-Mountain-in-Array)|39.0%|Medium||
987987
|0846|Hand of Straights||55.8%|Medium||
988988
|0847|Shortest Path Visiting All Nodes||54.9%|Hard||
@@ -1406,7 +1406,7 @@
14061406
|1265|Print Immutable Linked List in Reverse||94.1%|Medium||
14071407
|1266|Minimum Time Visiting All Points|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/1266.Minimum-Time-Visiting-All-Points)|79.2%|Easy||
14081408
|1267|Count Servers that Communicate||57.9%|Medium||
1409-
|1268|Search Suggestions System|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/1268.Search-Suggestions-System)|65.5%|Medium||
1409+
|1268|Search Suggestions System|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/1268.Search-Suggestions-System)|65.6%|Medium||
14101410
|1269|Number of Ways to Stay in the Same Place After Some Steps||43.3%|Hard||
14111411
|1270|All People Report to the Given Manager||88.3%|Medium||
14121412
|1271|Hexspeak||56.0%|Easy||
@@ -1688,7 +1688,7 @@
16881688
|1547|Minimum Cost to Cut a Stick||53.9%|Hard||
16891689
|1548|The Most Similar Path in a Graph||55.4%|Hard||
16901690
|1549|The Most Recent Orders for Each Product||67.5%|Medium||
1691-
|1550|Three Consecutive Odds||64.0%|Easy||
1691+
|1550|Three Consecutive Odds||64.1%|Easy||
16921692
|1551|Minimum Operations to Make Array Equal|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/1551.Minimum-Operations-to-Make-Array-Equal)|80.6%|Medium||
16931693
|1552|Magnetic Force Between Two Balls||51.2%|Medium||
16941694
|1553|Minimum Number of Days to Eat N Oranges||31.3%|Hard||
@@ -1744,7 +1744,7 @@
17441744
|1603|Design Parking System|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/1603.Design-Parking-System)|86.6%|Easy||
17451745
|1604|Alert Using Same Key-Card Three or More Times in a One Hour Period||44.0%|Medium||
17461746
|1605|Find Valid Matrix Given Row and Column Sums||78.3%|Medium||
1747-
|1606|Find Servers That Handled Most Number of Requests||38.7%|Hard||
1747+
|1606|Find Servers That Handled Most Number of Requests||38.6%|Hard||
17481748
|1607|Sellers With No Sales||55.0%|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.2%|Easy||
17501750
|1609|Even Odd Tree||52.2%|Medium||
@@ -1900,7 +1900,7 @@
19001900
|1759|Count Number of Homogenous Substrings||44.0%|Medium||
19011901
|1760|Minimum Limit of Balls in a Bag||54.5%|Medium||
19021902
|1761|Minimum Degree of a Connected Trio in a Graph||39.5%|Hard||
1903-
|1762|Buildings With an Ocean View||81.3%|Medium||
1903+
|1762|Buildings With an Ocean View||81.4%|Medium||
19041904
|1763|Longest Nice Substring||61.5%|Easy||
19051905
|1764|Form Array by Concatenating Subarrays of Another Array||53.1%|Medium||
19061906
|1765|Map of Highest Peak||57.6%|Medium||
@@ -1925,7 +1925,7 @@
19251925
|1784|Check if Binary String Has at Most One Segment of Ones||41.2%|Easy||
19261926
|1785|Minimum Elements to Add to Form a Given Sum||40.2%|Medium||
19271927
|1786|Number of Restricted Paths From First to Last Node||36.7%|Medium||
1928-
|1787|Make the XOR of All Segments Equal to Zero||37.7%|Hard||
1928+
|1787|Make the XOR of All Segments Equal to Zero||37.6%|Hard||
19291929
|1788|Maximize the Beauty of the Garden||67.0%|Hard||
19301930
|1789|Primary Department for Each Employee||79.8%|Easy||
19311931
|1790|Check if One String Swap Can Make Strings Equal||44.6%|Easy||
@@ -1942,14 +1942,14 @@
19421942
|1801|Number of Orders in the Backlog||44.6%|Medium||
19431943
|1802|Maximum Value at a Given Index in a Bounded Array||28.6%|Medium||
19441944
|1803|Count Pairs With XOR in a Range||45.4%|Hard||
1945-
|1804|Implement Trie II (Prefix Tree)||58.4%|Medium||
1945+
|1804|Implement Trie II (Prefix Tree)||58.3%|Medium||
19461946
|1805|Number of Different Integers in a String||34.9%|Easy||
19471947
|1806|Minimum Number of Operations to Reinitialize a Permutation||70.3%|Medium||
19481948
|1807|Evaluate the Bracket Pairs of a String||66.5%|Medium||
19491949
|1808|Maximize Number of Nice Divisors||28.5%|Hard||
19501950
|1809|Ad-Free Sessions||62.1%|Easy||
19511951
|1810|Minimum Path Cost in a Hidden Grid||54.1%|Medium||
1952-
|1811|Find Interview Candidates||66.5%|Medium||
1952+
|1811|Find Interview Candidates||66.4%|Medium||
19531953
|1812|Determine Color of a Chessboard Square||77.0%|Easy||
19541954
|1813|Sentence Similarity III||31.6%|Medium||
19551955
|1814|Count Nice Pairs in an Array||39.3%|Medium||
@@ -1981,7 +1981,7 @@
19811981
|1840|Maximum Building Height||34.5%|Hard||
19821982
|1841|League Statistics||61.8%|Medium||
19831983
|1842|Next Palindrome Using Same Digits||62.8%|Hard||
1984-
|1843|Suspicious Bank Accounts||51.5%|Medium||
1984+
|1843|Suspicious Bank Accounts||51.4%|Medium||
19851985
|1844|Replace All Digits with Characters||80.1%|Easy||
19861986
|1845|Seat Reservation Manager||56.4%|Medium||
19871987
|1846|Maximum Element After Decreasing and Rearranging|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/1846.Maximum-Element-After-Decreasing-and-Rearranging)|55.4%|Medium||
@@ -2009,7 +2009,7 @@
20092009
|1868|Product of Two Run-Length Encoded Arrays||59.7%|Medium||
20102010
|1869|Longer Contiguous Segments of Ones than Zeros||59.5%|Easy||
20112011
|1870|Minimum Speed to Arrive on Time||32.9%|Medium||
2012-
|1871|Jump Game VII||24.3%|Medium||
2012+
|1871|Jump Game VII||24.2%|Medium||
20132013
|1872|Stone Game VIII||51.3%|Hard||
20142014
|1873|Calculate Special Bonus||90.9%|Easy||
20152015
|1874|Minimize Product Sum of Two Arrays||90.6%|Medium||
@@ -2026,7 +2026,7 @@
20262026
|1885|Count Pairs in Two Arrays||55.5%|Medium||
20272027
|1886|Determine Whether Matrix Can Be Obtained By Rotation||54.1%|Easy||
20282028
|1887|Reduction Operations to Make the Array Elements Equal||60.0%|Medium||
2029-
|1888|Minimum Number of Flips to Make the Binary String Alternating||34.4%|Medium||
2029+
|1888|Minimum Number of Flips to Make the Binary String Alternating||34.5%|Medium||
20302030
|1889|Minimum Space Wasted From Packaging||29.1%|Hard||
20312031
|1890|The Latest Login in 2020||85.9%|Easy||
20322032
|1891|Cutting Ribbons||51.3%|Medium||
@@ -2056,8 +2056,8 @@
20562056
|1915|Number of Wonderful Substrings||38.5%|Medium||
20572057
|1916|Count Ways to Build Rooms in an Ant Colony||50.1%|Hard||
20582058
|1917|Leetcodify Friends Recommendations||32.2%|Hard||
2059-
|1918|Kth Smallest Subarray Sum||56.0%|Medium||
2060-
|1919|Leetcodify Similar Friends||44.2%|Hard||
2059+
|1918|Kth Smallest Subarray Sum||56.1%|Medium||
2060+
|1919|Leetcodify Similar Friends||44.1%|Hard||
20612061
|1920|Build Array from Permutation||93.8%|Easy||
20622062
|1921|Eliminate Maximum Number of Monsters||37.4%|Medium||
20632063
|1922|Count Good Numbers||38.9%|Medium||
@@ -2087,9 +2087,9 @@
20872087
|1946|Largest Number After Mutating Substring||32.6%|Medium||
20882088
|1947|Maximum Compatibility Score Sum||56.9%|Medium||
20892089
|1948|Delete Duplicate Folders in System||61.9%|Hard||
2090-
|1949|Strong Friendship||62.7%|Medium||
2090+
|1949|Strong Friendship||62.6%|Medium||
20912091
|1950|Maximum of Minimum Values in All Subarrays||52.8%|Medium||
2092-
|1951|All the Pairs With the Maximum Number of Common Followers||78.8%|Medium||
2092+
|1951|All the Pairs With the Maximum Number of Common Followers||78.9%|Medium||
20932093
|1952|Three Divisors||55.8%|Easy||
20942094
|1953|Maximum Number of Weeks for Which You Can Work||33.5%|Medium||
20952095
|1954|Minimum Garden Perimeter to Collect Enough Apples||52.0%|Medium||

‎leetcode/0116.Populating-Next-Right-Pointers-in-Each-Node/116.Populating Next Right Pointers in Each Node.go

Lines changed: 0 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -12,12 +12,9 @@ func connect(root *Node) *Node {
1212
if root == nil {
1313
return root
1414
}
15-
1615
q := []*Node{root}
17-
1816
for len(q) > 0 {
1917
var p []*Node
20-
2118
// 遍历这一层的所有节点
2219
for i, node := range q {
2320
if i+1 < len(q) {
@@ -32,7 +29,6 @@ func connect(root *Node) *Node {
3229
}
3330
q = p
3431
}
35-
3632
return root
3733
}
3834

@@ -42,7 +38,6 @@ func connect2(root *Node) *Node {
4238
return nil
4339
}
4440
connectTwoNode(root.Left, root.Right)
45-
4641
return root
4742
}
4843

@@ -51,7 +46,6 @@ func connectTwoNode(node1, node2 *Node) {
5146
return
5247
}
5348
node1.Next = node2
54-
5549
connectTwoNode(node1.Left, node1.Right)
5650
connectTwoNode(node2.Left, node2.Right)
5751
connectTwoNode(node1.Right, node2.Left)

‎leetcode/0116.Populating-Next-Right-Pointers-in-Each-Node/README.md

Lines changed: 38 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -1,64 +1,86 @@
1-
# [116. Distinct Subsequences](https://leetcode.com/problems/populating-next-right-pointers-in-each-node/)
1+
# [116. Populating Next Right Pointers in Each Node](https://leetcode.com/problems/populating-next-right-pointers-in-each-node/)
22

33

44
## 题目
55

6-
You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:
7-
```go
6+
You are given a **perfect binary tree** where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:
7+
8+
```
89
struct Node {
910
int val;
1011
Node *left;
1112
Node *right;
1213
Node *next;
1314
}
15+
1416
```
15-
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
1617

17-
Initially, all next pointers are set to NULL.
18+
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to `NULL`.
19+
20+
Initially, all next pointers are set to `NULL`.
1821

1922
**Follow up:**
23+
2024
- You may only use constant extra space.
2125
- Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.
2226

23-
2427
**Example 1:**
2528

29+
![https://assets.leetcode.com/uploads/2019/02/14/116_sample.png](https://assets.leetcode.com/uploads/2019/02/14/116_sample.png)
30+
2631
```
2732
Input: root = [1,2,3,4,5,6,7]
2833
Output: [1,#,2,3,#,4,5,6,7,#]
29-
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.
34+
Explanation:Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.
35+
3036
```
3137

3238
**Constraints:**
33-
- The number of nodes in the given tree is less than 4096.
34-
- -1000 <= node.val <= 1000
39+
40+
- The number of nodes in the given tree is less than `4096`.
41+
- `1000 <= node.val <= 1000`
3542

3643
## 题目大意
3744

38-
将二叉树的每一层节点都连接起来形成一个链表，每层的最后一个节点指向NULL.
45+
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
3946

47+
```jsx
48+
struct Node {
49+
int val;
50+
Node *left;
51+
Node *right;
52+
Node *next;
53+
}
4054

41-
## 解题思路
55+
```
4256

43-
本质上是二叉树的层序遍历，基于广度优先搜索，将每层的节点放入队列，并遍历队列进行连接。
57+
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。
4458

59+
## 解题思路
60+
61+
- 本质上是二叉树的层序遍历，基于广度优先搜索，将每层的节点放入队列，并遍历队列进行连接。
4562

4663
## 代码
4764

4865
```go
4966
package leetcode
5067

51-
// 解法一：迭代
68+
type Node struct {
69+
Val int
70+
Left *Node
71+
Right *Node
72+
Next *Node
73+
}
74+
75+
//解法一：迭代
5276
func connect(root *Node) *Node {
5377
if root == nil {
5478
return root
5579
}
56-
5780
q := []*Node{root}
58-
5981
for len(q) > 0 {
6082
var p []*Node
61-
83+
// 遍历这一层的所有节点
6284
for i, node := range q {
6385
if i+1 < len(q) {
6486
node.Next = q[i+1]
@@ -72,18 +94,15 @@ func connect(root *Node) *Node {
7294
}
7395
q = p
7496
}
75-
7697
return root
7798
}
7899

79-
80100
// 解法二 递归
81101
func connect2(root *Node) *Node {
82102
if root == nil {
83103
return nil
84104
}
85105
connectTwoNode(root.Left, root.Right)
86-
87106
return root
88107
}
89108

@@ -92,7 +111,6 @@ func connectTwoNode(node1, node2 *Node) {
92111
return
93112
}
94113
node1.Next = node2
95-
96114
connectTwoNode(node1.Left, node1.Right)
97115
connectTwoNode(node2.Left, node2.Right)
98116
connectTwoNode(node1.Right, node2.Left)

‎website/content/ChapterFour/0100~0199/0115.Distinct-Subsequences.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -104,5 +104,5 @@ func numDistinct1(s, t string) int {
104104
----------------------------------------------
105105
<div style="display: flex;justify-content: space-between;align-items: center;">
106106
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0100~0199/0114.Flatten-Binary-Tree-to-Linked-List/">⬅️上一页</a></p>
107-
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0100~0199/0118.Pascals-Triangle/">下一页➡️</a></p>
107+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0100~0199/0116.Populating-Next-Right-Pointers-in-Each-Node/">下一页➡️</a></p>
108108
</div>

0 commit comments

Comments
 (0)