Skip to content

Commit ced5740

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lcof problem: No.09
1 parent 723452d commit ced5740

File tree

13 files changed

+146
-136
lines changed

13 files changed

+146
-136
lines changed

‎lcci/16.02.Words Frequency/README_EN.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -71,7 +71,7 @@ class WordsFrequency {
7171
cnt.merge(x, 1, Integer::sum);
7272
}
7373
}
74-
74+
7575
public int get(String word) {
7676
return cnt.getOrDefault(word, 0);
7777
}
@@ -94,7 +94,7 @@ public:
9494
++cnt[x];
9595
}
9696
}
97-
97+
9898
int get(string word) {
9999
return cnt[word];
100100
}

‎lcof/面试题07. 重建二叉树/Solution.cs

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -18,4 +18,4 @@ public TreeNode BuildTree(int[] preorder, int[] inorder) {
1818
root.right = BuildTree(preorder[(index+1)..], inorder[(idx+1)..]);
1919
return root;
2020
}
21-
}
21+
}

‎lcof/面试题07. 重建二叉树/Solution.ts

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -30,4 +30,4 @@ function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
3030
return root;
3131
};
3232
return dfs(0, 0, n);
33-
};
33+
}

‎lcof/面试题09. 用两个栈实现队列/README.md

Lines changed: 88 additions & 81 deletions
Original file line numberDiff line numberDiff line change
@@ -31,11 +31,15 @@
3131

3232
## 解法
3333

34-
- 两个栈，一个负责**输入**，一个负责**输出**；
35-
- 执行输入时，只放入输入栈中；
36-
- 执行输出时，将输入栈的所有元素依次出栈，放入输出栈中；
37-
- 根据栈的特点，处于输入栈**栈底**的元素，在输出栈中便是**栈顶**；
38-
- 只有输出栈中没有元素时才进行倒放，而非每一次。
34+
**方法一：双栈**
35+
36+
我们可以使用两个栈来实现队列，其中一个栈 `stk1` 用来存储输入的元素，另一个栈 `stk2` 用来输出元素。
37+
38+
当调用 `appendTail()` 方法时，我们将元素压入 `stk1` 中。
39+
40+
当调用 `deleteHead()` 方法时，如果此时栈 `stk2` 为空，我们将栈 `stk1` 中的元素逐个弹出并压入栈 `stk2` 中，然后弹出栈 `stk2` 的栈顶元素即可。如果此时栈 `stk2` 不为空，我们直接弹出栈 `stk2` 的栈顶元素即可。如果两个栈都为空，说明队列中没有元素，返回 `-1`。
41+
42+
时间复杂度上，对于 `appendTail()` 方法，时间复杂度为 $O(1)$；对于 `deleteHead()` 方法，时间复杂度为 $O(n)$；空间复杂度为 $O(n)$。其中 $n$ 为队列中的元素个数。
3943

4044
<!-- tabs:start -->
4145

@@ -95,52 +99,55 @@ class CQueue {
9599
*/
96100
```
97101

98-
### **JavaScript**
102+
### **C++**
99103

100-
```js
101-
var CQueue = function () {
102-
this.stk1 = [];
103-
this.stk2 = [];
104-
};
104+
```cpp
105+
class CQueue {
106+
public:
107+
CQueue() {
105108

106-
/**
107-
* @param {number} value
108-
* @return {void}
109-
*/
110-
CQueue.prototype.appendTail = function (value) {
111-
this.stk1.push(value);
112-
};
109+
}
113110

114-
/**
115-
* @return {number}
116-
*/
117-
CQueue.prototype.deleteHead = function () {
118-
if (!this.stk2.length) {
119-
while (this.stk1.length) {
120-
this.stk2.push(this.stk1.pop());
111+
void appendTail(int value) {
112+
stk1.push(value);
113+
}
114+
115+
int deleteHead() {
116+
if (stk2.empty()) {
117+
while (!stk1.empty()) {
118+
stk2.push(stk1.top());
119+
stk1.pop();
120+
}
121+
}
122+
if (stk2.empty()) {
123+
return -1;
121124
}
125+
int ans = stk2.top();
126+
stk2.pop();
127+
return ans;
122128
}
123-
return this.stk2.length ? this.stk2.pop() : -1;
129+
130+
private:
131+
stack<int> stk1, stk2;
124132
};
125133

126134
/**
127135
* Your CQueue object will be instantiated and called as such:
128-
* var obj = new CQueue()
129-
* obj.appendTail(value)
130-
* var param_2 = obj.deleteHead()
136+
* CQueue* obj = new CQueue();
137+
* obj->appendTail(value);
138+
* int param_2 = obj->deleteHead();
131139
*/
132140
```
133141
134142
### **Go**
135143
136144
```go
137145
type CQueue struct {
138-
stk1 []int
139-
stk2 []int
146+
stk1, stk2 []int
140147
}
141148
142149
func Constructor() CQueue {
143-
return CQueue{stk1: []int{}, stk2: []int{}}
150+
return CQueue{[]int{}, []int{}}
144151
}
145152
146153
func (this *CQueue) AppendTail(value int) {
@@ -151,14 +158,14 @@ func (this *CQueue) DeleteHead() int {
151158
if len(this.stk2) == 0 {
152159
for len(this.stk1) > 0 {
153160
this.stk2 = append(this.stk2, this.stk1[len(this.stk1)-1])
154-
this.stk1 = this.stk1[0 : len(this.stk1)-1]
161+
this.stk1 = this.stk1[:len(this.stk1)-1]
155162
}
156163
}
157164
if len(this.stk2) == 0 {
158165
return -1
159166
}
160167
ans := this.stk2[len(this.stk2)-1]
161-
this.stk2 = this.stk2[0 : len(this.stk2)-1]
168+
this.stk2 = this.stk2[:len(this.stk2)-1]
162169
return ans
163170
}
164171
@@ -170,64 +177,65 @@ func (this *CQueue) DeleteHead() int {
170177
*/
171178
```
172179

173-
### **C++**
174-
175-
```cpp
176-
class CQueue {
177-
private:
178-
stack<int> s1, s2;
180+
### **JavaScript**
179181

180-
public:
181-
CQueue() {
182-
}
182+
```js
183+
var CQueue = function () {
184+
this.stk1 = [];
185+
this.stk2 = [];
186+
};
183187

184-
void appendTail(int value) {
185-
s1.push(value);
186-
}
188+
/**
189+
* @param {number} value
190+
* @return {void}
191+
*/
192+
CQueue.prototype.appendTail = function (value) {
193+
this.stk1.push(value);
194+
};
187195

188-
int deleteHead() {
189-
if (s2.empty()) {
190-
while (!s1.empty()) {
191-
s2.push(s1.top());
192-
s1.pop();
193-
}
194-
}
195-
if (s2.empty()) {
196-
return -1;
196+
/**
197+
* @return {number}
198+
*/
199+
CQueue.prototype.deleteHead = function () {
200+
if (!this.stk2.length) {
201+
while (this.stk1.length) {
202+
this.stk2.push(this.stk1.pop());
197203
}
198-
int head = s2.top();
199-
s2.pop();
200-
return head;
201204
}
205+
return this.stk2.length ? this.stk2.pop() : -1;
202206
};
207+
208+
/**
209+
* Your CQueue object will be instantiated and called as such:
210+
* var obj = new CQueue()
211+
* obj.appendTail(value)
212+
* var param_2 = obj.deleteHead()
213+
*/
203214
```
204215

205216
### **TypeScript**
206217

207218
```ts
208219
class CQueue {
209-
private stack1: number[];
210-
private stack2: number[];
220+
private stk1: number[];
221+
private stk2: number[];
222+
211223
constructor() {
212-
this.stack1 = [];
213-
this.stack2 = [];
224+
this.stk1 = [];
225+
this.stk2 = [];
214226
}
215227

216228
appendTail(value: number): void {
217-
this.stack1.push(value);
218-
}
219-
220-
move(): void {
221-
while (this.stack1.length != 0) {
222-
this.stack2.push(this.stack1.pop());
223-
}
229+
this.stk1.push(value);
224230
}
225231

226232
deleteHead(): number {
227-
if (this.stack2.length == 0) {
228-
this.move();
233+
if (this.stk2.length == 0) {
234+
while (this.stk1.length) {
235+
this.stk2.push(this.stk1.pop());
236+
}
229237
}
230-
return this.stack2.length == 0 ? -1 : this.stack2.pop();
238+
return this.stk2.length == 0 ? -1 : this.stk2.pop();
231239
}
232240
}
233241

@@ -290,25 +298,24 @@ impl CQueue {
290298

291299
```cs
292300
public class CQueue {
293-
private Stack<int> stack1;
294-
private Stack<int> stack2;
301+
private Stack<int> stk1 = new Stack<int>();
302+
private Stack<int> stk2 = new Stack<int>();
295303

296304
public CQueue() {
297-
stack1 = new Stack<int>();
298-
stack2 = new Stack<int>();
305+
299306
}
300307

301308
public void AppendTail(int value) {
302-
stack1.Push(value);
309+
stk1.Push(value);
303310
}
304311

305312
public int DeleteHead() {
306-
if (stack2.Count == 0) {
307-
while (stack1.Count != 0) {
308-
stack2.Push(stack1.Pop());
313+
if (stk2.Count == 0) {
314+
while (stk1.Count != 0) {
315+
stk2.Push(stk1.Pop());
309316
}
310317
}
311-
return stack2.Count == 0 ? -1 : stack2.Pop();
318+
return stk2.Count == 0 ? -1 : stk2.Pop();
312319
}
313320
}
314321

‎lcof/面试题09. 用两个栈实现队列/Solution.cpp

Lines changed: 22 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1,27 +1,35 @@
11
class CQueue {
2-
private:
3-
stack<int> s1, s2;
4-
52
public:
63
CQueue() {
7-
}
84

5+
}
6+
97
void appendTail(int value) {
10-
s1.push(value);
8+
stk1.push(value);
119
}
12-
10+
1311
int deleteHead() {
14-
if (s2.empty()) {
15-
while (!s1.empty()) {
16-
s2.push(s1.top());
17-
s1.pop();
12+
if (stk2.empty()) {
13+
while (!stk1.empty()) {
14+
stk2.push(stk1.top());
15+
stk1.pop();
1816
}
1917
}
20-
if (s2.empty()) {
18+
if (stk2.empty()) {
2119
return -1;
2220
}
23-
int head = s2.top();
24-
s2.pop();
25-
return head;
21+
int ans = stk2.top();
22+
stk2.pop();
23+
return ans;
2624
}
25+
26+
private:
27+
stack<int> stk1, stk2;
2728
};
29+
30+
/**
31+
* Your CQueue object will be instantiated and called as such:
32+
* CQueue* obj = new CQueue();
33+
* obj->appendTail(value);
34+
* int param_2 = obj->deleteHead();
35+
*/

‎lcof/面试题09. 用两个栈实现队列/Solution.cs

Lines changed: 8 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,23 +1,22 @@
11
public class CQueue {
2-
private Stack<int> stack1;
3-
private Stack<int> stack2;
2+
private Stack<int> stk1 = new Stack<int>();
3+
private Stack<int> stk2 = new Stack<int>();
44

55
public CQueue() {
6-
stack1 = new Stack<int>();
7-
stack2 = new Stack<int>();
6+
87
}
98

109
public void AppendTail(int value) {
11-
stack1.Push(value);
10+
stk1.Push(value);
1211
}
1312

1413
public int DeleteHead() {
15-
if (stack2.Count == 0) {
16-
while (stack1.Count != 0) {
17-
stack2.Push(stack1.Pop());
14+
if (stk2.Count == 0) {
15+
while (stk1.Count != 0) {
16+
stk2.Push(stk1.Pop());
1817
}
1918
}
20-
return stack2.Count == 0 ? -1 : stack2.Pop();
19+
return stk2.Count == 0 ? -1 : stk2.Pop();
2120
}
2221
}
2322

0 commit comments

Comments
 (0)