Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit9deafb5

Browse files
authored
Merge pull request6boris#210 from 0xff-dev/master
Add solution and test-cases for problem 729
2 parentsebe37ac +fbf6f0f commit9deafb5

File tree

8 files changed

+281
-54
lines changed

8 files changed

+281
-54
lines changed
Lines changed: 78 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,81 @@
11
package Solution
22

3-
funcSolution(xbool)bool {
4-
returnx
3+
const (
4+
push="push"
5+
pop="pop"
6+
top="top"
7+
getMin="getMIn"
8+
)
9+
10+
typeMinStackstruct {
11+
data,min []int
12+
}
13+
14+
funcConstructor4()MinStack {
15+
returnMinStack{
16+
data:make([]int,0),
17+
min:make([]int,0),
18+
}
19+
}
20+
21+
func (this*MinStack)Push(valint) {
22+
iflen(this.data)==0 {
23+
this.data=append(this.data,val)
24+
this.min=append(this.min,val)
25+
return
26+
}
27+
28+
top:=this.min[len(this.min)-1]
29+
this.data=append(this.data,val)
30+
iftop>val {
31+
top=val
32+
}
33+
34+
this.min=append(this.min,top)
35+
}
36+
37+
func (this*MinStack)Pop() {
38+
iflen(this.data)>0 {
39+
l:=len(this.data)
40+
this.data=this.data[:l-1]
41+
this.min=this.min[:l-1]
42+
}
43+
}
44+
45+
func (this*MinStack)Top()int {
46+
iflen(this.data)>0 {
47+
returnthis.data[len(this.data)-1]
48+
}
49+
50+
return-1
51+
}
52+
53+
func (this*MinStack)GetMin()int {
54+
returnthis.min[len(this.min)-1]
55+
}
56+
57+
// action, push, pop, top, getMin
58+
funcSolution(actions []string,vals []int) []int {
59+
o:=Constructor4()
60+
expect:=make([]int,0)
61+
foridx,act:=rangeactions {
62+
ifact==push {
63+
o.Push(vals[idx])
64+
continue
65+
}
66+
ifact==pop {
67+
o.Pop()
68+
continue
69+
}
70+
71+
ifact==top {
72+
top:=o.Top()
73+
expect=append(expect,top)
74+
continue
75+
}
76+
77+
m:=o.GetMin()
78+
expect=append(expect,m)
79+
}
80+
returnexpect
581
}

‎leetcode/101-200/0155.Min-Stack/Solution_test.go‎

Lines changed: 9 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -9,22 +9,22 @@ import (
99
funcTestSolution(t*testing.T) {
1010
//测试用例
1111
cases:= []struct {
12-
namestring
13-
inputsbool
14-
expectbool
12+
namestring
13+
actions []string
14+
inputs []int
15+
expect []int
1516
}{
16-
{"TestCase",true,true},
17-
{"TestCase",true,true},
18-
{"TestCase",false,false},
17+
{"TestCase1", []string{push,push,push,getMin,pop,top,getMin}, []int{-2,0,-3,0,0,0,0}, []int{-3,0,-2}},
18+
{"TestCase2", []string{push,push,getMin,top,pop,push,getMin,top}, []int{1,2,0,0,0,-2,0,0}, []int{1,2,-2,-2}},
1919
}
2020

2121
//开始测试
2222
fori,c:=rangecases {
2323
t.Run(c.name+" "+strconv.Itoa(i),func(t*testing.T) {
24-
got:=Solution(c.inputs)
24+
got:=Solution(c.actions,c.inputs)
2525
if!reflect.DeepEqual(got,c.expect) {
26-
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
27-
c.expect,got,c.inputs)
26+
t.Fatalf("expected: %v, but got: %v, withinput-actions: %v, input-inputs: %v",
27+
c.expect,got,c.actions,c.inputs)
2828
}
2929
})
3030
}

‎leetcode/301-400/0341.Flatten-Nested-List-Iterator/README.md‎

Lines changed: 23 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -1,26 +1,36 @@
11
#[341.Flatten Nested List Iterator][title]
22

3-
>[!WARNING|style:flat]
4-
>This question is temporarily unanswered if you have good ideas. Welcome to[Create Pull Request PR](https://github.com/kylesliu/awesome-golang-algorithm)
5-
63
##Description
4+
You are given a nested list of integers`nestedList`. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.
75

8-
**Example 1:**
6+
Implement the`NestedIterator` class:
97

8+
-`NestedIterator(List<NestedInteger> nestedList)` Initializes the iterator with the nested list`nestedList`.
9+
-`int next()` Returns the next integer in the nested list.
10+
-`boolean hasNext()` Returns`true` if there are still some integers in the nested list and`false` otherwise.
11+
Your code will be tested with the following pseudocode:
1012
```
11-
Input: a = "11", b = "1"
12-
Output: "100"
13+
initialize iterator with nestedList
14+
res = []
15+
while iterator.hasNext()
16+
append iterator.next() to the end of res
17+
return res
1318
```
19+
If`res` matches the expected flattened list, then your code will be judged as correct.
1420

15-
##题意
16-
>...
21+
**Example 1:**
1722

18-
##题解
23+
```
24+
Input: nestedList = [[1,1],2,[1,1]]
25+
Output: [1,1,2,1,1]
26+
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].
27+
```
1928

20-
###思路1
21-
>...
22-
Flatten Nested List Iterator
23-
```go
29+
__Example 2:__
30+
```
31+
Input: nestedList = [1,[4,[6]]]
32+
Output: [1,4,6]
33+
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].
2434
```
2535

2636

Lines changed: 66 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,69 @@
11
package Solution
22

3-
funcSolution(xbool)bool {
4-
returnx
3+
typeNestedIntegerstruct {
4+
Valint
5+
isIntbool
6+
list []*NestedInteger
7+
}
8+
9+
func (thisNestedInteger)IsInteger()bool {
10+
returnthis.isInt
11+
}
12+
13+
func (thisNestedInteger)GetInteger()int {
14+
returnthis.Val
15+
}
16+
17+
func (thisNestedInteger)SetInteger(valueint) {
18+
19+
}
20+
func (thisNestedInteger)Add(eleNestedInteger) {
21+
22+
}
23+
24+
func (thisNestedInteger)GetList() []*NestedInteger {
25+
returnthis.list
26+
}
27+
28+
typeNestedIteratorstruct {
29+
Raw []*NestedInteger
30+
idxint
31+
}
32+
33+
funcConstructor3(nestedList []*NestedInteger)*NestedIterator {
34+
raw:=make([]*NestedInteger,0)
35+
deepTraverse(nestedList,&raw)
36+
return&NestedIterator{
37+
Raw:raw,
38+
idx:0,
39+
}
40+
}
41+
42+
funcdeepTraverse(nestedList []*NestedInteger,raw*[]*NestedInteger) {
43+
foridx,ele:=rangenestedList {
44+
ifele.IsInteger() {
45+
*raw=append(*raw,nestedList[idx])
46+
continue
47+
}
48+
deepTraverse(ele.GetList(),raw)
49+
}
50+
}
51+
52+
func (this*NestedIterator)Next()int {
53+
r:=this.Raw[this.idx].GetInteger()
54+
this.idx++
55+
returnr
56+
}
57+
58+
func (this*NestedIterator)HasNext()bool {
59+
returnthis.idx<len(this.Raw)
60+
}
61+
62+
funcSolution(nestedList []*NestedInteger) []int {
63+
o:=Constructor3(nestedList)
64+
expect:=make([]int,0)
65+
foro.HasNext() {
66+
expect=append(expect,o.Next())
67+
}
68+
returnexpect
569
}

‎leetcode/301-400/0341.Flatten-Nested-List-Iterator/Solution_test.go‎

Lines changed: 15 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -10,12 +10,22 @@ func TestSolution(t *testing.T) {
1010
//测试用例
1111
cases:= []struct {
1212
namestring
13-
inputsbool
14-
expectbool
13+
inputs[]*NestedInteger
14+
expect[]int
1515
}{
16-
{"TestCase",true,true},
17-
{"TestCase",true,true},
18-
{"TestCase",false,false},
16+
{"TestCase1", []*NestedInteger{{Val:1,isInt:true}, {isInt:false,list: []*NestedInteger{{Val:2,isInt:true}, {Val:3,isInt:true}}}, {Val:1,isInt:true,list:nil}}, []int{1,2,3,1}},
17+
{"TestCase2", []*NestedInteger{{Val:1,isInt:true}, {Val:2,isInt:true}, {Val:3,isInt:true}}, []int{1,2,3}},
18+
{"TestCase3", []*NestedInteger{
19+
{Val:1,isInt:true},
20+
{isInt:false,list: []*NestedInteger{
21+
{isInt:false,list: []*NestedInteger{{Val:2,isInt:true}}},
22+
{isInt:false,list: []*NestedInteger{
23+
{Val:3,isInt:true},
24+
{Val:4,isInt:true},
25+
}},
26+
}},
27+
{Val:5,isInt:true}},
28+
[]int{1,2,3,4,5}},
1929
}
2030

2131
//开始测试

‎leetcode/701-800/0729.My-Calendar-I/README.md‎

Lines changed: 20 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1,26 +1,32 @@
11
#[729.My Calendar I][title]
22

3-
>[!WARNING|style:flat]
4-
>This question is temporarily unanswered if you have good ideas. Welcome to[Create Pull Request PR](https://github.com/kylesliu/awesome-golang-algorithm)
53

64
##Description
5+
You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a__double booking__.
76

8-
**Example 1:**
7+
A__double booking__ happens when two events have some non-empty intersection (i.e., some moment is common to both events.).
98

10-
```
11-
Input: a = "11", b = "1"
12-
Output: "100"
13-
```
9+
The event can be represented as a pair of integers`start` and`end` that represents a booking on the half-open interval`[start, end)`, the range of real numbers`x` such that`start <= x < end`.
1410

15-
##题意
16-
>...
11+
Implement the`MyCalendar` class:
1712

18-
##题解
13+
-`MyCalendar()` Initializes the calendar object.
14+
-`boolean book(int start, int end)` Returns`true` if the event can be added to the calendar successfully without causing a__double booking__. Otherwise, return`false` and do not add the event to the calendar.
1915

20-
###思路1
21-
>...
22-
My Calendar I
23-
```go
16+
**Example 1:**
17+
18+
```
19+
Input
20+
["MyCalendar", "book", "book", "book"]
21+
[[], [10, 20], [15, 25], [20, 30]]
22+
Output
23+
[null, true, false, true]
24+
25+
Explanation
26+
MyCalendar myCalendar = new MyCalendar();
27+
myCalendar.book(10, 20); // return True
28+
myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event.
29+
myCalendar.book(20, 30); // return True, The event can be booked, as the first event takes every time less than 20, but not including 20.
2430
```
2531

2632

Lines changed: 62 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,65 @@
11
package Solution
22

3-
funcSolution(xbool)bool {
4-
returnx
3+
typesegstruct {
4+
start,endint
5+
}
6+
7+
typeMyCalendarstruct {
8+
books []seg
9+
}
10+
11+
funcConstructor()MyCalendar {
12+
returnMyCalendar{
13+
books:make([]seg,0),
14+
}
15+
}
16+
17+
func (this*MyCalendar)Book(start,endint)bool {
18+
s:=seg{start,end}
19+
iflen(this.books)==0 {
20+
this.books=append(this.books,s)
21+
returntrue
22+
}
23+
24+
idx:=len(this.books)-1
25+
breakPoint:=false
26+
for ;idx>=0;idx-- {
27+
ifs.end>=this.books[idx].end&&s.start>=this.books[idx].end {
28+
breakPoint=true
29+
break
30+
}
31+
if (s.start>=this.books[idx].start&&s.start<this.books[idx].end)|| (s.end>this.books[idx].start&&s.end<this.books[idx].end)|| (s.end>=this.books[idx].end&&s.start<=this.books[idx].start) {
32+
returnfalse
33+
}
34+
ifidx==0 {
35+
breakPoint=true
36+
}
37+
}
38+
ifbreakPoint {
39+
ifidx<0 {
40+
this.books=append([]seg{s},this.books...)
41+
}else {
42+
tmp:=make([]seg,0)
43+
tmp=append(tmp,this.books[:idx+1]...)
44+
tmp=append(tmp,s)
45+
tmp=append(tmp,this.books[idx+1:]...)
46+
this.books=tmp
47+
}
48+
}
49+
50+
returnbreakPoint
51+
}
52+
53+
funcSolution(segs []seg,res []bool)bool {
54+
iflen(segs)!=len(res) {
55+
returnfalse
56+
}
57+
c:=Constructor()
58+
59+
foridx:=0;idx<len(segs);idx++ {
60+
ifres[idx]!=c.Book(segs[idx].start,segs[idx].end) {
61+
returnfalse
62+
}
63+
}
64+
returntrue
565
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp