Skip to content

Commit 6414ff6

Browse files
zwfangzwfang
committed
init leetcode
1 parent 4304c44 commit 6414ff6

File tree

84 files changed

+3714
-0
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

84 files changed

+3714
-0
lines changed

‎leetcode/0001_two_sum/twosum.go

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
/*
2+
1. Two Sum
3+
4+
Source: https://leetcode.com/problems/two-sum/
5+
6+
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
7+
8+
You may assume that each input would have exactly one solution, and you may not use the same element twice.
9+
10+
Example:
11+
12+
Given nums = [2, 7, 11, 15], target = 9,
13+
14+
Because nums[0] + nums[1] = 2 + 7 = 9,
15+
return [0, 1].
16+
17+
*/
18+
19+
package twosum
20+
21+
// Time complexity: O(n)
22+
// Space complexity: O(n)
23+
func twoSum(nums []int, target int) []int {
24+
record := make(map[int]int)
25+
26+
for i, j := range nums {
27+
complement := target - j
28+
if res, ok := record[complement]; ok {
29+
return []int{res, i}
30+
}
31+
record[j] = i
32+
}
33+
return []int{}
34+
}

‎leetcode/0001_two_sum/twosum_test.go

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
package twosum
2+
3+
import (
4+
"reflect"
5+
"testing"
6+
)
7+
8+
func TestTwoSum(t *testing.T) {
9+
nums := []int{2, 7, 11, 15}
10+
11+
if res := twoSum(nums, 9); !reflect.DeepEqual(res, []int{0, 1}) {
12+
t.Error("Failed, two sum")
13+
}
14+
15+
if res := twoSum(nums, 6); !reflect.DeepEqual(res, []int{}) {
16+
t.Error("Failed, two sum")
17+
}
18+
}

‎leetcode/0002_add_two_numbers/add_two_numbers.go

Lines changed: 96 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,96 @@
1+
/*
2+
2. Add Two Numbers
3+
4+
Source: https://leetcode.com/problems/add-two-numbers/
5+
6+
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
7+
8+
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
9+
10+
Example:
11+
12+
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
13+
Output: 7 -> 0 -> 8
14+
Explanation: 342 + 465 = 807.
15+
*/
16+
17+
package addtwonumbers
18+
19+
// ListNode is node of linked list
20+
type ListNode struct {
21+
Val int
22+
Next *ListNode
23+
}
24+
25+
// 解法一，暴力解法
26+
func addTwoNumbers1(l1 *ListNode, l2 *ListNode) *ListNode {
27+
head := ListNode{Val: -1}
28+
cur := &head
29+
carry := 0
30+
for l1 != nil && l2 != nil {
31+
sum := l1.Val + l2.Val + carry
32+
val := sum % 10
33+
carry = sum / 10
34+
node := ListNode{Val: val}
35+
cur.Next = &node
36+
cur = cur.Next
37+
l1 = l1.Next
38+
l2 = l2.Next
39+
}
40+
if carry == 0 {
41+
if l1 != nil {
42+
cur.Next = l1
43+
}
44+
if l2 != nil {
45+
cur.Next = l2
46+
}
47+
return head.Next
48+
}
49+
for l1 != nil {
50+
sum := l1.Val + carry
51+
val := sum % 10
52+
carry = sum / 10
53+
node := ListNode{Val: val}
54+
cur.Next = &node
55+
cur = cur.Next
56+
l1 = l1.Next
57+
}
58+
for l2 != nil {
59+
sum := l2.Val + carry
60+
val := sum % 10
61+
carry = sum / 10
62+
node := ListNode{Val: val}
63+
cur.Next = &node
64+
cur = cur.Next
65+
l2 = l2.Next
66+
}
67+
for carry != 0 {
68+
val := carry % 10
69+
carry = carry / 10
70+
node := ListNode{Val: val}
71+
cur.Next = &node
72+
cur = cur.Next
73+
}
74+
return head.Next
75+
}
76+
77+
// 解法二，递归
78+
func addTwoNumbers2(l1 *ListNode, l2 *ListNode) *ListNode {
79+
if l1 == nil && l2 == nil {
80+
return nil
81+
} else if l1 == nil && l2 != nil {
82+
return l2
83+
} else if l1 != nil && l2 == nil {
84+
return l1
85+
}
86+
87+
sum := l1.Val + l2.Val
88+
next := addTwoNumbers2(l1.Next, l2.Next)
89+
90+
if sum >= 10 {
91+
carry := sum / 10
92+
sum %= 10
93+
next = addTwoNumbers2(next, &ListNode{Val: carry})
94+
}
95+
return &ListNode{Val: sum, Next: next}
96+
}

‎leetcode/0002_add_two_numbers/add_two_numbers_test.go

Lines changed: 130 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,130 @@
1+
package addtwonumbers
2+
3+
import (
4+
"os"
5+
"reflect"
6+
"testing"
7+
)
8+
9+
func createSingleLinkedList(arr []int) *ListNode {
10+
head := &ListNode{}
11+
cur := head
12+
13+
for _, j := range arr {
14+
cur.Next = &ListNode{Val: j}
15+
cur = cur.Next
16+
}
17+
return head.Next
18+
}
19+
20+
func TestAddTwoNumbers1(t *testing.T) {
21+
testDatas := []struct {
22+
name string
23+
arg1 *ListNode
24+
arg2 *ListNode
25+
expected *ListNode
26+
}{
27+
{
28+
name: "one",
29+
arg1: createSingleLinkedList([]int{2, 4, 3}),
30+
arg2: createSingleLinkedList([]int{5, 6, 4}),
31+
expected: createSingleLinkedList([]int{7, 0, 8}),
32+
},
33+
{
34+
name: "two",
35+
arg1: createSingleLinkedList([]int{5}),
36+
arg2: createSingleLinkedList([]int{5}),
37+
expected: createSingleLinkedList([]int{0, 1}),
38+
},
39+
{
40+
name: "three",
41+
arg1: createSingleLinkedList([]int{1}),
42+
arg2: createSingleLinkedList([]int{9, 9, 9}),
43+
expected: createSingleLinkedList([]int{0, 0, 0, 1}),
44+
},
45+
{
46+
name: "four",
47+
arg1: createSingleLinkedList([]int{9, 9, 9}),
48+
arg2: createSingleLinkedList([]int{1}),
49+
expected: createSingleLinkedList([]int{0, 0, 0, 1}),
50+
},
51+
{
52+
name: "five",
53+
arg1: createSingleLinkedList([]int{4, 3, 1}),
54+
arg2: createSingleLinkedList([]int{1}),
55+
expected: createSingleLinkedList([]int{5, 3, 1}),
56+
},
57+
{
58+
name: "six",
59+
arg1: createSingleLinkedList([]int{1}),
60+
arg2: createSingleLinkedList([]int{4, 3, 1}),
61+
expected: createSingleLinkedList([]int{5, 3, 1}),
62+
},
63+
}
64+
65+
for _, testData := range testDatas {
66+
t.Run(testData.name, func(t *testing.T) {
67+
if result := addTwoNumbers1(testData.arg1, testData.arg2); !reflect.DeepEqual(result, testData.expected) {
68+
t.Errorf("expected %v, got %v", testData.expected, result)
69+
}
70+
})
71+
}
72+
}
73+
74+
func TestAddTwoNumbers2(t *testing.T) {
75+
testDatas := []struct {
76+
name string
77+
arg1 *ListNode
78+
arg2 *ListNode
79+
expected *ListNode
80+
}{
81+
{
82+
name: "one",
83+
arg1: createSingleLinkedList([]int{2, 4, 3}),
84+
arg2: createSingleLinkedList([]int{5, 6, 4}),
85+
expected: createSingleLinkedList([]int{7, 0, 8}),
86+
},
87+
{
88+
name: "two",
89+
arg1: createSingleLinkedList([]int{5}),
90+
arg2: createSingleLinkedList([]int{5}),
91+
expected: createSingleLinkedList([]int{0, 1}),
92+
},
93+
{
94+
name: "three",
95+
arg1: createSingleLinkedList([]int{1}),
96+
arg2: createSingleLinkedList([]int{9, 9, 9}),
97+
expected: createSingleLinkedList([]int{0, 0, 0, 1}),
98+
},
99+
{
100+
name: "four",
101+
arg1: createSingleLinkedList([]int{9, 9, 9}),
102+
arg2: createSingleLinkedList([]int{1}),
103+
expected: createSingleLinkedList([]int{0, 0, 0, 1}),
104+
},
105+
{
106+
name: "five",
107+
arg1: createSingleLinkedList([]int{4, 3, 1}),
108+
arg2: createSingleLinkedList([]int{1}),
109+
expected: createSingleLinkedList([]int{5, 3, 1}),
110+
},
111+
{
112+
name: "six",
113+
arg1: createSingleLinkedList([]int{1}),
114+
arg2: createSingleLinkedList([]int{4, 3, 1}),
115+
expected: createSingleLinkedList([]int{5, 3, 1}),
116+
},
117+
}
118+
119+
for _, testData := range testDatas {
120+
t.Run(testData.name, func(t *testing.T) {
121+
if result := addTwoNumbers2(testData.arg1, testData.arg2); !reflect.DeepEqual(result, testData.expected) {
122+
t.Errorf("expected %v, got %v", testData.expected, result)
123+
}
124+
})
125+
}
126+
}
127+
128+
func TestMain(m *testing.M) {
129+
os.Exit(m.Run())
130+
}

‎leetcode/0003_longest_substring_without_repeating_characters/longest_substring_without_repeating_characters.go

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
/*
2+
3. Longest Substring Without Repeating Characters
3+
4+
Source: https://leetcode.com/problems/longest-substring-without-repeating-characters/
5+
6+
Given a string, find the length of the longest substring without repeating characters.
7+
8+
Example 1:
9+
10+
Input: "abcabcbb"
11+
Output: 3
12+
Explanation: The answer is "abc", with the length of 3.
13+
Example 2:
14+
15+
Input: "bbbbb"
16+
Output: 1
17+
Explanation: The answer is "b", with the length of 1.
18+
Example 3:
19+
20+
Input: "pwwkew"
21+
Output: 3
22+
Explanation: The answer is "wke", with the length of 3.
23+
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
24+
*/
25+
26+
package longestsubstringwithoutrepeatingcharacters
27+
28+
// Time complexity: O(n)
29+
// Space complexity: O(n)
30+
func lengthOfLongestSubstring(s string) int {
31+
32+
var (
33+
start = 0
34+
res = 0
35+
lastOccurredRecord = make(map[rune]int)
36+
)
37+
38+
for i, ch := range []rune(s) {
39+
if lastIndex, ok := lastOccurredRecord[ch]; ok && lastIndex >= start {
40+
start = lastIndex + 1
41+
}
42+
if i-start+1 > res {
43+
res = i - start + 1
44+
}
45+
lastOccurredRecord[ch] = i
46+
}
47+
return res
48+
}

‎leetcode/0003_longest_substring_without_repeating_characters/longest_substring_without_repeating_characters_test.go

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
package longestsubstringwithoutrepeatingcharacters
2+
3+
import "testing"
4+
5+
func TestLengthOfLongestSubstring(t *testing.T) {
6+
testData := []string{
7+
"abcabcbb",
8+
"bbbbb",
9+
"pwwkew",
10+
}
11+
expectedData := []int{3, 1, 3}
12+
13+
for index, data := range testData {
14+
if res := lengthOfLongestSubstring(data); res != expectedData[index] {
15+
t.Errorf("expected %d, got %d", expectedData[index], res)
16+
}
17+
}
18+
}

0 commit comments

Comments
 (0)