Skip to content

Commit aec0298

Browse files
yanglbmeyanglbme
committed
feat: update solutions to lc/lcof2 problem: Number of Segments in a
String
1 parent 3a9a779 commit aec0298

File tree

12 files changed

+305
-110
lines changed

12 files changed

+305
-110
lines changed

‎lcof2/剑指 Offer II 045. 二叉树最底层最左边的值/README.md

Lines changed: 28 additions & 35 deletions
Original file line numberDiff line numberDiff line change
@@ -63,18 +63,18 @@
6363
# self.right = right
6464
class Solution:
6565
def findBottomLeftValue(self, root: TreeNode) -> int:
66-
d = deque([root])
66+
q = deque([root])
6767
ans = -1
68-
while d:
69-
n = len(d)
68+
while q:
69+
n = len(q)
7070
for i in range(n):
71-
node = d.popleft()
71+
node = q.popleft()
7272
if i == 0:
7373
ans = node.val
7474
if node.left:
75-
d.append(node.left)
75+
q.append(node.left)
7676
if node.right:
77-
d.append(node.right)
77+
q.append(node.right)
7878
return ans
7979
```
8080

@@ -126,42 +126,35 @@ class Solution {
126126
### **C++**
127127

128128
```cpp
129+
/**
130+
* Definition for a binary tree node.
131+
* struct TreeNode {
132+
* int val;
133+
* TreeNode *left;
134+
* TreeNode *right;
135+
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
136+
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
137+
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
138+
* };
139+
*/
129140
class Solution {
130141
public:
131142
int findBottomLeftValue(TreeNode* root) {
132-
if (!root)
133-
{
134-
return 0;
135-
}
136-
137-
int res = root->val;
138-
queue<TreeNode*> que;
139-
que.push(root);
140-
while (!que.empty())
143+
queue<TreeNode*> q;
144+
q.push(root);
145+
int ans = -1;
146+
while (!q.empty())
141147
{
142-
int size = que.size();
143-
for (int i = 0; i < size; i++)
148+
for (int i = 0, n = q.size(); i < n; ++i)
144149
{
145-
TreeNode* ptr = que.front();
146-
que.pop();
147-
if (i == 0)
148-
{
149-
res = ptr->val;
150-
}
151-
152-
if (ptr->left)
153-
{
154-
que.push(ptr->left);
155-
}
156-
157-
if (ptr->right)
158-
{
159-
que.push(ptr->right);
160-
}
150+
TreeNode* node = q.front();
151+
if (i == 0) ans = node->val;
152+
q.pop();
153+
if (node->left) q.push(node->left);
154+
if (node->right) q.push(node->right);
161155
}
162156
}
163-
164-
return res;
157+
return ans;
165158
}
166159
};
167160
```

‎lcof2/剑指 Offer II 045. 二叉树最底层最左边的值/Solution.cpp

Lines changed: 23 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -1,38 +1,31 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* struct TreeNode {
4+
* int val;
5+
* TreeNode *left;
6+
* TreeNode *right;
7+
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
8+
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9+
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10+
* };
11+
*/
112
class Solution {
213
public:
314
int findBottomLeftValue(TreeNode* root) {
4-
if (!root)
15+
queue<TreeNode*> q;
16+
q.push(root);
17+
int ans = -1;
18+
while (!q.empty())
519
{
6-
return 0;
7-
}
8-
9-
int res = root->val;
10-
queue<TreeNode*> que;
11-
que.push(root);
12-
while (!que.empty())
13-
{
14-
int size = que.size();
15-
for (int i = 0; i < size; i++)
20+
for (int i = 0, n = q.size(); i < n; ++i)
1621
{
17-
TreeNode* ptr = que.front();
18-
que.pop();
19-
if (i == 0)
20-
{
21-
res = ptr->val;
22-
}
23-
24-
if (ptr->left)
25-
{
26-
que.push(ptr->left);
27-
}
28-
29-
if (ptr->right)
30-
{
31-
que.push(ptr->right);
32-
}
22+
TreeNode* node = q.front();
23+
if (i == 0) ans = node->val;
24+
q.pop();
25+
if (node->left) q.push(node->left);
26+
if (node->right) q.push(node->right);
3327
}
3428
}
35-
36-
return res;
29+
return ans;
3730
}
38-
};
31+
};

‎lcof2/剑指 Offer II 045. 二叉树最底层最左边的值/Solution.py

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -6,16 +6,16 @@
66
# self.right = right
77
class Solution:
88
def findBottomLeftValue(self, root: TreeNode) -> int:
9-
d = deque([root])
9+
q = deque([root])
1010
ans = -1
11-
while d:
12-
n = len(d)
11+
while q:
12+
n = len(q)
1313
for i in range(n):
14-
node = d.popleft()
14+
node = q.popleft()
1515
if i == 0:
1616
ans = node.val
1717
if node.left:
18-
d.append(node.left)
18+
q.append(node.left)
1919
if node.right:
20-
d.append(node.right)
20+
q.append(node.right)
2121
return ans

‎solution/0400-0499/0434.Number of Segments in a String/README.md

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -32,14 +32,14 @@ split 切分字符串，或者直接遍历计数。
3232
```python
3333
class Solution:
3434
def countSegments(self, s: str) -> int:
35-
return sum(1 for t in s.split(' ') if t)
35+
return len(s.split())
3636
```
3737

3838
```python
3939
class Solution:
4040
def countSegments(self, s: str) -> int:
41-
res, n = 0, len(s)
42-
for i in range(n):
41+
res = 0
42+
for i in range(len(s)):
4343
if s[i] != ' ' and (i == 0 or s[i - 1] == ' '):
4444
res += 1
4545
return res

‎solution/0400-0499/0434.Number of Segments in a String/README_EN.md

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -56,14 +56,14 @@
5656
```python
5757
class Solution:
5858
def countSegments(self, s: str) -> int:
59-
return sum(1 for t in s.split(' ') if t)
59+
return len(s.split())
6060
```
6161

6262
```python
6363
class Solution:
6464
def countSegments(self, s: str) -> int:
65-
res, n = 0, len(s)
66-
for i in range(n):
65+
res = 0
66+
for i in range(len(s)):
6767
if s[i] != ' ' and (i == 0 or s[i - 1] == ' '):
6868
res += 1
6969
return res

‎solution/0400-0499/0434.Number of Segments in a String/Solution.py

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
class Solution:
22
def countSegments(self, s: str) -> int:
3-
res, n = 0, len(s)
4-
for i in range(n):
3+
res = 0
4+
for i in range(len(s)):
55
if s[i] != ' ' and (i == 0 or s[i - 1] == ' '):
66
res += 1
77
return res

‎solution/0500-0599/0513.Find Bottom Left Tree Value/README.md

Lines changed: 83 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -65,18 +65,19 @@
6565
# self.right = right
6666
class Solution:
6767
def findBottomLeftValue(self, root: TreeNode) -> int:
68-
res = 0
69-
q = collections.deque([root])
68+
q = deque([root])
69+
ans = -1
7070
while q:
71-
res = q[0].val
7271
n = len(q)
73-
for _ in range(n):
72+
for i in range(n):
7473
node = q.popleft()
74+
if i == 0:
75+
ans = node.val
7576
if node.left:
7677
q.append(node.left)
7778
if node.right:
7879
q.append(node.right)
79-
return res
80+
return ans
8081
```
8182

8283
### **Java**
@@ -101,13 +102,16 @@ class Solution:
101102
*/
102103
class Solution {
103104
public int findBottomLeftValue(TreeNode root) {
104-
Deque<TreeNode> q = new ArrayDeque<>();
105+
Queue<TreeNode> q = new ArrayDeque<>();
105106
q.offer(root);
106-
int res = 0;
107+
int ans = -1;
107108
while (!q.isEmpty()) {
108-
res = q.peek().val;
109-
for (int i = 0, n = q.size(); i < n; ++i) {
109+
int n = q.size();
110+
for (int i = 0; i < n; i++) {
110111
TreeNode node = q.poll();
112+
if (i == 0) {
113+
ans = node.val;
114+
}
111115
if (node.left != null) {
112116
q.offer(node.left);
113117
}
@@ -116,8 +120,77 @@ class Solution {
116120
}
117121
}
118122
}
119-
return res;
123+
return ans;
124+
}
125+
}
126+
```
127+
128+
### **C++**
129+
130+
```cpp
131+
/**
132+
* Definition for a binary tree node.
133+
* struct TreeNode {
134+
* int val;
135+
* TreeNode *left;
136+
* TreeNode *right;
137+
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
138+
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
139+
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
140+
* };
141+
*/
142+
class Solution {
143+
public:
144+
int findBottomLeftValue(TreeNode* root) {
145+
queue<TreeNode*> q;
146+
q.push(root);
147+
int ans = -1;
148+
while (!q.empty())
149+
{
150+
for (int i = 0, n = q.size(); i < n; ++i)
151+
{
152+
TreeNode* node = q.front();
153+
if (i == 0) ans = node->val;
154+
q.pop();
155+
if (node->left) q.push(node->left);
156+
if (node->right) q.push(node->right);
157+
}
158+
}
159+
return ans;
120160
}
161+
};
162+
```
163+
164+
### **Go**
165+
166+
```go
167+
/**
168+
* Definition for a binary tree node.
169+
* type TreeNode struct {
170+
* Val int
171+
* Left *TreeNode
172+
* Right *TreeNode
173+
* }
174+
*/
175+
func findBottomLeftValue(root *TreeNode) int {
176+
q := []*TreeNode{root}
177+
ans := -1
178+
for n := len(q); n > 0; n = len(q) {
179+
for i := 0; i < n; i++ {
180+
node := q[0]
181+
q = q[1:]
182+
if i == 0 {
183+
ans = node.Val
184+
}
185+
if node.Left != nil {
186+
q = append(q, node.Left)
187+
}
188+
if node.Right != nil {
189+
q = append(q, node.Right)
190+
}
191+
}
192+
}
193+
return ans
121194
}
122195
```
123196

0 commit comments

Comments
 (0)