8000 feat: 18 · chenshiwei-io/leetcode@bed8590 · GitHub
[go: up one dir, main page]
Skip to content

Commit bed8590

Browse files
author
陈世伟
committed
feat: 18
1 parent 675dc56 commit bed8590

File tree

14 files changed

+365
-58
lines changed

14 files changed

+365
-58
lines changed

‎leetcode/0015/three-sum.go

Lines changed: 0 additions & 47 deletions
This file was deleted.

‎leetcode/0202/is_happy.go

Lines changed: 16 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,19 +1,26 @@
11
package _202
22

33
func isHappy(n int) bool {
4-
var slow, first = n, squareSum(n)
5-
for slow != first {
6-
slow = squareSum(slow)
7-
first = squareSum(squareSum(first))
4+
var dict = make(map[int]struct{})
5+
for n != 1 {
6+
sum := getSum(n)
7+
if _, ok := dict[sum]; ok {
8+
return false
9+
} else {
10+
dict[sum] = struct{}{}
11+
}
12+
13+
n = sum
14+
815
}
9-
return slow == 1
16+
return true
17+
1018
}
1119

12-
func squareSum(n int) int {
13-
var sum = 0
20+
func getSum(n int) int {
21+
var sum int
1422
for n > 0 {
15-
digit := n % 10
16-
sum += digit * digit
23+
sum += (n % 10) * (n % 10)
1724
n /= 10
1825
}
1926
return sum

‎leetcode/0202/is_happy_test.go

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -28,3 +28,25 @@ func Test_isHappy(t *testing.T) {
2828
})
2929
}
3030
}
31+
32+
func Test_getSum(t *testing.T) {
33+
type args struct {
34+
n int
35+
}
36+
tests := []struct {
37+
name string
38+
args args
39+
want int
40+
}{
41+
{name: `19`, args: args{n: 19}, want: 82},
42+
{name: `0`, args: args{n: 0}, want: 0},
43+
{name: `1`, args: args{n: 1}, want: 1},
44+
}
45+
for _, tt := range tests {
46+
t.Run(tt.name, func(t *testing.T) {
47+
if got := getSum(tt.args.n); got != tt.want {
48+
t.Errorf("getSum() = %v, want %v", got, tt.want)
49+
}
50+
})
51+
}
52+
}

‎leetcode/15.三数之和/three-sum.go

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
package _5_三数之和
2+
3+
import (
4+
"sort"
5+
)
6+
7+
func ThreeSum(nums []int) [][]int {
8+
l := len(nums)
9+
if l < 3 {
10+
return nil
11+
}
12+
var result [][]int
13+
sort.Ints(nums)
14+
for i := 0; i < l; i++ {
15+
// 因为已排序 如果 nums[i] > 0 那么nums[left] nums[j] 不会为0
16+
if nums[i] > 0 {
17+
return result
18+
}
19+
// 错误去重方法，将会漏掉-1,-1,2 这种情况
20+
/*
21+
if nums[i] == nums[i + 1] {
22+
continue
23+
}
24+
*/
25+
if i > 0 && nums[i] == nums[i-1] {
26+
continue
27+
}
28+
left, right := i+1, l-1
29+
for left < right {
30+
sum := nums[i] + nums[left] + nums[right]
31+
if sum == 0 {
32+
result = append(result, []int{nums[i], nums[left], nums[right]})
33+
// 跳过值 一样的数
34+
for left < right && nums[left] == nums[left+1] {
35+
left++
36+
}
37+
// 跳过值 一样的数
38+
for left < right && nums[right] == nums[right-1] {
39+
right--
40+
}
41+
left++
42+
right--
43+
} else if sum < 0 {
44+
left++
45+
} else if sum > 0 {
46 10000 +
right--
47+
}
48+
}
49+
50+
}
51+
52+
return result
53+
}

‎leetcode/0015/three-sum_test.go renamed to ‎leetcode/15.三数之和/three-sum_test.go

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package _015
1+
package _5_三数之和
22

33
import (
44
"reflect"
@@ -14,7 +14,7 @@ func TestThreeSum(t *testing.T) {
1414
args args
1515
want [][]int
1616
}{
17-
{name: "[-1, 0, 1, 2, -1, -4]", args: args{nums: []int{-1, 0, 1, 2, -1, -4}}, want: [][]int{{-1, 0, 1}, {-1, -1, 2}}},
17+
{name: "[-1, 0, 1, 2, -1, -4]", args: args{nums: []int{-1, 0, 1, 2, -1, -4}}, want: [][]int{{-1, -1, 2}, {-1, 0, 1}}},
1818
{name: "[0,0,0]", args: args{nums: []int{0, 0, 0}}, want: [][]int{{0, 0, 0}}},
1919
}
2020
for _, tt := range tests {

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

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package _8_四数之和
2+
3+
func fourSum(nums []int, target int) [][]int {
4+
l := len(nums)
5+
result := [][]int{}
6+
for i := 0; i < l; i++ {
7+
if i > 0 && nums[i] == nums[i-1] {
8+
continue
9+
}
10+
for j := i + 1; j < l; j++ {
11+
left, right := j+1, l-1
12+
for left < right {
13+
sum := nums[i] + nums[j] + nums[left] + nums[right]
14+
if sum > 0 {
15+
right--
16+
} else if sum < 0 {
17+
left++
18+
} else {
19+
result = append(result, []int{nums[i], nums[j], nums[left], nums[right]})
20+
for left < right && nums[left] == nums[left+1] {
21+
left++
22+
}
23+
for left < right && nums[right] == nums[right-1] {
24+
right--
25+
}
26+
left++
27+
right--
28+
}
29+
30+
}
31+
}
32+
}
33+
34+
}

‎leetcode/242.有效的字母异位词/isAnagram.go

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
package _42_有效的字母异位词
2+
3+
func isAnagram(s string, t string) bool {
4+
var dict [26]int
5+
6+
for i := range s {
7+
dict[s[i]-'a']++
8+
}
9+
10+
for i := range t {
11+
dict[t[i]-'a']--
12+
}
13+
14+
for i := range dict {
15+
if dict[i] != 0 {
16+
return false
17+
}
18+
}
19+
20+
return true
21+
}

‎leetcode/242.有效的字母异位词/isAnagram_test.go

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package _42_有效的字母异位词
2+
3+
import "testing"
4+
5+
func Test_isAnagram(t *testing.T) {
6+
type args struct {
7+
s string
8+
t string
9+
}
10+
tests := []struct {
11+
name string
12+
args args
13+
want bool
14+
}{
15+
{name: `输入: s = "anagram", t = "nagaram"
16+
输出: true`, args: args{
17+
s: "anagram",
18+
t: "nagaram",
19+
}, want: true},
20+
}
21+
for _, tt := range tests {
22+
t.Run(tt.name, func(t *testing.T) {
23+
if got := isAnagram(tt.args.s, tt.args.t); got != tt.want {
24+
t.Errorf("isAnagram() = %v, want %v", got, tt.want)
25+
}
26+
})
27+
}
28+
}

‎leetcode/349.两个数组的交集/intersection.go

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
package _49_两个数组的交集
2+
3+
func intersection(nums1 []int, nums2 []int) []int {
4+
var dict = make(map[int]int)
5+
6+
for _, v := range nums1 {
7+
dict[v] = 1
8+
}
9+
10+
var result []int
11+
for _, v := range nums2 {
12+
if _, ok := dict[v]; ok {
13+
dict[v] = 2
14+
}
15+
}
16+
17+
for i, v := range dict {
18+
if v == 2 {
19+
result = append(result, i)
20+
}
21+
}
22+
23+
return result
24+
}

‎leetcode/349.两个数组的交集/intersection_test.go

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

‎leetcode/383.赎金信/canConstruct.go

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
package _83_赎金信
2+
3+
func canConstruct(ransomNote string, magazine string) bool {
4+
var dict = [26]int{}
5+
6+
for i := 0; i < len(magazine); i++ {
7+
dict[magazine[i]-'a']++
8+
}
9+
10+
// ransomNote有字符在 magazine没有
11+
for j := 0; j < len(ransomNote); j++ {
12+
dict[ransomNote[j]-'a']--
13+
if dict[ransomNote[j]-'a'] < 0 {
14+
return false
15+
}
16+
}
17+
18+
return true
19+
}

‎leetcode/383.赎金信/canConstruct_test.go

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
package _83_赎金信
2+
3+
import "testing"
4+
5+
func Test_canConstruct(t *testing.T) {
6+
type args struct {
7+
ransomNote string
8+
magazine string
9+
}
10+
tests := []struct {
11+
name string
12+
args args
13+
want bool
14+
}{
15+
{name: `输入：ransomNote = "a", magazine = "b"
16+
输出：false`, args: args{
17+
ransomNote: "a",
18+
magazine: "b",
19+
}},
20+
{name: `输入：ransomNote = "aa", magazine = "aab"
21+
输出：true`, args: args{
22+
ransomNote: "aa",
23+
magazine: "aab",
24+
}, want: true},
25+
}
26+
for _, tt := range tests {
27+
t.Run(tt.name, func(t *testing.T) {
28+
if got := canConstruct(tt.args.ransomNote, tt.args.magazine); got != tt.want {
29+
t.Errorf("canConstruct() = %v, want %v", got, tt.want)
30+
}
31+
})
32+
}
33+
}

0 commit comments

Comments
 (0)
0