8000 feat: array[54,59,209] · chenshiwei-io/leetcode@c911d04 · GitHub
[go: up one dir, main page]
Skip to content

Commit c911d04

Browse files
author
chen-shiwei
committed
feat: array[54,59,209]
1 parent 02dd95d commit c911d04

File tree

12 files changed

+343
-18
lines changed

12 files changed

+343
-18
lines changed

‎leetcode/151.翻转字符串里的单词/reverseWords.go

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
package _151_翻转字符串里的单词
2+
3+
func reverseWords(s string) string {
4+
l := len(s)
5+
b := []byte(s)
6+
reverse(b, 0, l-1)
7+
left := 0
8+
for i := 0; i < l; i++ {
9+
if b[i] == ' ' {
10+
reverse(b, left, i-1)
11+
left = i + 1
12+
}
13+
}
14+
reverse(b, left, l-1)
15+
16+
c := removeSpaces(b)
17+
return string(c)
18+
}
19+
20+
func removeSpaces(b []byte) []byte {
21+
var slow, quick int
22+
23+
l := len(b)
24+
for l > 0 && quick < l && b[quick] == ' ' {
25+
quick++
26+
}
27+
28+
for ; quick < l; quick++ {
29+
if quick-1 > 0 && b[quick] == ' ' && b[quick-1] == ' ' {
30+
continue
31+
} else {
32+
b[slow] = b[quick]
33+
slow++
34+
}
35+
}
36+
if slow-1 > 0 && b[slow-1] == ' ' {
37+
return b[:slow-1]
38+
} else {
39+
return b[:slow]
40+
}
41+
}
42+
43+
func reverse(b []byte, left, right int) {
44+
l := len(b)
45+
if l < 2 {
46+
return
47+
}
48+
49+
for left < right {
50+
b[left], b[right] = b[right], b[left]
51+
left++
52+
right--
53+
}
54+
55+
return
56+
}

‎leetcode/151.翻转字符串里的单词/reverseWords_test.go

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
package _151_翻转字符串里的单词
2+
3+
import (
4+
"fmt"
5+
"reflect"
6+
"testing"
7+
)
8+
9+
func Test_reverseWords(t *testing.T) {
10+
type arg F438 s struct {
11+
s string
12+
}
13+
tests := []struct {
14+
name string
15+
args args
16+
want string
17+
}{
18+
{name: `输入："the sky is blue"
19+
输出："blue is sky the"`, args: args{s: "the sky is blue"}, want: "blue is sky the"},
20+
{name: `输入：" hello world! "
21+
输出："world! hello"`, args: args{s: " hello world! "}, want: "world! hello"},
22+
}
23+
for _, tt := range tests {
24+
t.Run(tt.name, func(t *testing.T) {
25+
if got := reverseWords(tt.args.s); got != tt.want {
26+
t.Errorf("reverseWords() = '%v', want '%v'", got, tt.want)
27+
}
28+
})
29+
}
30+
}
31+
32+
func Test(t *testing.T) {
33+
34+
a := []byte("abcd")
35+
36+
fmt.Println(a[0])
37+
fmt.Println(string(a[:2]))
38+
fmt.Println(string(a[1:3]))
39+
}
40+
41+
func Test_removeSpaces1(t *testing.T) {
42+
type args struct {
43+
b []byte
44+
}
45+
tests := []struct {
46+
name string
47+
args args
48+
want []byte
49+
}{
50+
{name: "", args: args{b: []byte(" a b c ")}, want: []byte("a b c")},
51+
{name: "", args: args{b: []byte(" a b c")}, want: []byte("a b c")},
52+
}
53+
for _, tt := range tests {
54+
t.Run(tt.name, func(t *testing.T) {
55+
got := removeSpaces(tt.args.b)
56+
57+
fmt.Println(tt.args.b)
58+
fmt.Println(got)
59+
fmt.Println(tt.want)
60+
if !reflect.DeepEqual(got, tt.want) {
61+
t.Errorf("removeSpaces() = %v, want %v", got, tt.want)
62+
}
63+
})
64+
}
65+
}

‎leetcode/18.四数之和/fourSum.go

Lines changed: 12 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,19 +1,27 @@
11
package _8_四数之和
22

3+
import "sort"
4+
35
func fourSum(nums []int, target int) [][]int {
46
l := len(nums)
7+
8+
sort.Ints(nums)
59
result := [][]int{}
610
for i := 0; i < l; i++ {
711
if i > 0 && nums[i] == nums[i-1] {
812
continue
913
}
1014
for j := i + 1; j < l; j++ {
15+
if j > i+1 && nums[j-1] == nums[j] {
16+
continue
17+
}
18+
1119
left, right := j+1, l-1
1220
for left < right {
1321
sum := nums[i] + nums[j] + nums[left] + nums[right]
14-
if sum > 0 {
22+
if sum > target {
1523
right--
16-
} else if sum < 0 {
24+
} else if sum < target {
1725
left++
1826
} else {
1927
result = append(result, []int{nums[i], nums[j], nums[left], nums[right]})
@@ -26,9 +34,10 @@ func fourSum(nums []int, target int) [][]int {
2634
left++
2735
right--
2836
}
29-
3037
}
3138
}
3239
}
3340

41+
return result
42+
3443
}

‎leetcode/18.四数之和/fourSum_test.go

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package _8_四数之和
2+
3+
import (
4+
"reflect"
5+
"testing"
6+
)
7+
8+
func Test_fourSum(t *testing.T) {
9+
type args struct {
10+
nums []int
11+
target int
12+
}
13+
tests := []struct {
14+
name string
15+
args args
16+
want [][]int
17+
}{
18+
{name: `输入：nums = [1,0,-1,0,-2,2], target = 0
19+
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]`, args: args{
20+
nums: []int{1, 0, -1, 0, -2, 2},
21+
target: 0,
22+
}, want: [][]int{
23+
{-2, -1, 1, 2},
24+
{-2, 0, 0, 2},
25+
{-1, 0, 0, 1},
26+
}},
27+
}
28+
for _, tt := range tests {
29+
t.Run(tt.name, func(t *testing.T) {
30+
if got := fourSum(tt.args.nums, tt.args.target); !reflect.DeepEqual(got, tt.want) {
31+
t.Errorf("fourSum() = %v, want %v", got, tt.want)
32+
}
33+
})
34+
}
35+
}

‎leetcode/3.无重复字符的最长子串/lengthOfLongestSubstring.go

Lines changed: 11 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -2,30 +2,26 @@ package __无重复字符的最长子串
22

33
func lengthOfLongestSubstring(s string) int {
44
var (
5-
l = len(s)
6-
dict = make(map[uint8]int)
7-
start int
8-
maxLen int
5+
l = len(s)
6+
dict = make(map[uint8]int)
7+
left int
8+
max int
99
)
1010
if l == 0 {
1111
return 0
1212
}
1313

1414
for i := 0; i < l; i++ {
1515
if idx, ok := dict[s[i]]; ok {
16-
start = max(idx+1, start)
16+
if idx+1 > left {
17+
left = idx + 1
18+
}
1719
}
1820
dict[s[i]] = i
19-
maxLen = max(i-start+1, maxLen)
20-
}
21-
22-
return maxLen
23-
}
24-
25-
func max(a, b int) int {
26-
if a >= b {
27-
return a
21+
if i-left+1 > max {
22+
max = i - left + 1
23+
}
2824
}
2925

30-
return b
26+
return max
3127
}

‎leetcode/3.无重复字符的最长子串/lengthOfLongestSubstring_test.go

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -13,6 +13,8 @@ func Test_lengthOfLongestSubstring(t *testing.T) {
1313
}{
1414
{name: `输入: s = "abcabcbb"输出: 3解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。`, args: args{s: "abcabcbb"}, want: 3},
1515
{name: `输入: s = "dvdf"输出: 3`, args: args{s: "dvdf"}, want: 3},
16+
{name: `输入: s = "au"输出: 2`, args: args{s: "au"}, want: 2},
17+
{name: `输入: s = ""abcabcbb""输出: 4`, args: args{s: "abcabcbb"}, want: 3},
1618
}
1719
for _, tt := range tests {
1820
t.Run(tt.name, func(t *testing.T) {

‎leetcode/344.反转字符串/reverseString.go

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
package _44_反转字符串
2+
3+
func reverseString(s []byte) {
4+
l := len(s)
5+
if l < 2 {
6+
return
7+
}
8+
9+
left, right := 0, l-1
10+
for left < right {
11+
s[left], s[right] = s[right], s[left]
12+
left++
13+
right--
14+
}
15+
}

‎leetcode/344.反转字符串/reverseString_test.go

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package _44_反转字符串
2+
3+
import (
4+
"reflect"
5+
"testing"
6+
)
7+
8+
func Test_reverseString(t *testing.T) {
9+
type args struct {
10+
s []byte
11+
}
12+
tests := []struct {
13+
name string
14+
args args
15+
want []byte
16+
}{
17+
{name: `输入：["h","e","l","l","o"]
18+
输出：["o","l","l","e","h"]`, args: args{s: []byte{'h', 'e', 'l', 'l', 'o'}}, want: []byte{'o', 'l', 'l', 'e', 'h'}},
19+
}
20+
for _, tt := range tests {
21+
t.Run(tt.name, func(t *testing.T) {
22+
reverseString(tt.args.s)
23+
if !reflect.DeepEqual(tt.args.s, tt.want) {
24+
t.Error(tt.name)
25+
}
26+
27+
})
28+
}
29+
}

‎leetcode/541.反转字符串II/reverseStr.go

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
package _41_反转字符串II
2+
3+
func reverseStr(s string, k int) string {
4+
5+
b := []byte(s)
6+
7+
l := len(s)
8+
9+
for i := 0; i < l; {
10+
var right int
11+
if i+k >= l {
12+
right = i + (l -< C848 /span> i)
13+
} else {
14+
right = i + k
15+
}
16+
reverse(b, i, right-1)
17+
i = right + k
18+
}
19+
20+
return string(b)
21+
}
22+
23+
func reverse(s []byte, left, right int) {
24+
l := len(s)
25+
if l < 2 {
26+
return
27+
}
28+
29+
for left < right {
30+
s[left], s[right] = s[right], s[left]
31+
left++
32+
right--
33+
}
34+
35+
return
36+
}

‎leetcode/541.反转字符串II/reverseStr_test.go

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package _41_反转字符串II
2+
3+
import "testing"
4+
5+
func Test_reverseStr(t *testing.T) {
6+
type args struct {
7+
s string
8+
k int
9+
}
10+
tests := []struct {
11+
name string
12+
args args
13+
want string
14+
}{
15+
{name: `输入: s = "abcdefg", k = 2
16+
输出: "bacdfeg"`, args: args{
17+
s: "abcdefg",
18+
k: 2,
19+
}, want: "bacdfeg"},
20+
}
21+
for _, tt := range tests {
22+
t.Run(tt.name, func(t *testing.T) {
23+
if got := reverseStr(tt.args.s, tt.args.k); got != tt.want {
24+
t.Errorf("reverseStr() = %v, want %v", got, tt.want)
25+
}
26+
})
27+
}
28+
}

‎剑指Offer/剑指Offer05.替换空格.go

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
package 剑指Offer
2+
3+
func replaceSpace(s string) string {
4+
l := len(s)
5+
c := 0
6+
for i := 0; i < l; i++ {
7+
if s[i] == ' ' {
8+
c++
9+
}
10+
}
11+
12+
l2 := l + c*2
13+
newS := make([]byte, l2)
14+
i, j := l-1, l2-1
15+
16+
for i >= 0 {
17+
if s[i] == ' ' {
18+
newS[j] = '0'
19+
newS[j-1] = '2'
20+
newS[j-2] = '%'
21+
j = j - 3
22+
i--
23+
} else {
24+
newS[j] = s[i]
25+
j--
26+
i--
27+
}
28+
}
29+
return string(newS)
30+
}

0 commit comments

Comments
 (0)
0