Skip to content

Commit 3f1eeb9

Browse files
maolonglongmaolonglong
committed
feat: update golang solutions to lcci problems: No. 01.02~01.07
1 parent 00a59df commit 3f1eeb9

File tree

18 files changed

+457
-9
lines changed

18 files changed

+457
-9
lines changed

‎lcci/01.02.Check Permutation/README.md

Lines changed: 24 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -10,7 +10,7 @@
1010
<p><strong>示例 1：</strong></p>
1111

1212
<pre><strong>输入:</strong> <code>s1</code> = &quot;abc&quot;, <code>s2</code> = &quot;bca&quot;
13-
<strong>输出:</strong> true
13+
<strong>输出:</strong> true
1414
</pre>
1515

1616
<p><strong>示例 2：</strong></p>
@@ -97,6 +97,29 @@ var CheckPermutation = function(s1, s2) {
9797
};
9898
```
9999

100+
### **Go**
101+
102+
```go
103+
func CheckPermutation(s1 string, s2 string) bool {
104+
freq := make(map[rune]int)
105+
for _, r := range s1 {
106+
freq[r]++
107+
}
108+
for _, r := range s2 {
109+
if freq[r] == 0 {
110+
return false
111+
}
112+
freq[r]--
113+
}
114+
for _, v := range freq {
115+
if v != 0 {
116+
return false
117+
}
118+
}
119+
return true
120+
}
121+
```
122+
100123
### **...**
101124

102125
```

‎lcci/01.02.Check Permutation/README_EN.md

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -95,6 +95,29 @@ var CheckPermutation = function(s1, s2) {
9595
};
9696
```
9797

98+
### **Go**
99+
100+
```go
101+
func CheckPermutation(s1 string, s2 string) bool {
102+
freq := make(map[rune]int)
103+
for _, r := range s1 {
104+
freq[r]++
105+
}
106+
for _, r := range s2 {
107+
if freq[r] == 0 {
108+
return false
109+
}
110+
freq[r]--
111+
}
112+
for _, v := range freq {
113+
if v != 0 {
114+
return false
115+
}
116+
}
117+
return true
118+
}
119+
```
120+
98121
### **...**
99122

100123
```

‎lcci/01.02.Check Permutation/Solution.go

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
func CheckPermutation(s1 string, s2 string) bool {
2+
freq := make(map[rune]int)
3+
for _, r := range s1 {
4+
freq[r]++
5+
}
6+
for _, r := range s2 {
7+
if freq[r] == 0 {
8+
return false
9+
}
10+
freq[r]--
11+
}
12+
for _, v := range freq {
13+
if v != 0 {
14+
return false
15+
}
16+
}
17+
return true
18+
}

‎lcci/01.03.String to URL/README.md

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -88,6 +88,28 @@ var replaceSpaces = function(S, length) {
8888
};
8989
```
9090

91+
### **Go**
92+
93+
```go
94+
func replaceSpaces(S string, length int) string {
95+
// return url.PathEscape(S[:length])
96+
j := len(S)
97+
b := []byte(S)
98+
for i := length - 1; i >= 0; i-- {
99+
if b[i] == ' ' {
100+
b[j-1] = '0'
101+
b[j-2] = '2'
102+
b[j-3] = '%'
103+
j -= 3
104+
} else {
105+
b[j-1] = b[i]
106+
j--
107+
}
108+
}
109+
return string(b[j:])
110+
}
111+
```
112+
91113
### **...**
92114

93115
```

‎lcci/01.03.String to URL/README_EN.md

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -97,6 +97,28 @@ var replaceSpaces = function(S, length) {
9797
};
9898
```
9999

100+
### **Go**
101+
102+
```go
103+
func replaceSpaces(S string, length int) string {
104+
// return url.PathEscape(S[:length])
105+
j := len(S)
106+
b := []byte(S)
107+
for i := length - 1; i >= 0; i-- {
108+
if b[i] == ' ' {
109+
b[j-1] = '0'
110+
b[j-2] = '2'
111+
b[j-3] = '%'
112+
j -= 3
113+
} else {
114+
b[j-1] = b[i]
115+
j--
116+
}
117+
}
118+
return string(b[j:])
119+
}
120+
```
121+
100122
### **...**
101123

102124
```

‎lcci/01.03.String to URL/Solution.go

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
func replaceSpaces(S string, length int) string {
2+
// return url.PathEscape(S[:length])
3+
j := len(S)
4+
b := []byte(S)
5+
for i := length - 1; i >= 0; i-- {
6+
if b[i] == ' ' {
7+
b[j-1] = '0'
8+
b[j-2] = '2'
9+
b[j-3] = '%'
10+
j -= 3
11+
} else {
12+
b[j-1] = b[i]
13+
j--
14+
}
15+
}
16+
return string(b[j:])
17+
}

‎lcci/01.04.Palindrome Permutation/README.md

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -72,6 +72,25 @@ class Solution {
7272
}
7373
```
7474

75+
### **Go**
76+
77+
```go
78+
func canPermutePalindrome(s string) bool {
79+
m := make(map[rune]bool)
80+
count := 0
81+
for _, r := range s {
82+
if m[r] {
83+
m[r] = false
84+
count--
85+
} else {
86+
m[r] = true
87+
count++
88+
}
89+
}
90+
return count <= 1
91+
}
92+
```
93+
7594
### **...**
7695

7796
```

‎lcci/01.04.Palindrome Permutation/README_EN.md

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -61,6 +61,25 @@ class Solution {
6161
}
6262
```
6363

64+
### **Go**
65+
66+
```go
67+
func canPermutePalindrome(s string) bool {
68+
m := make(map[rune]bool)
69+
count := 0
70+
for _, r := range s {
71+
if m[r] {
72+
m[r] = false
73+
count--
74+
} else {
75+
m[r] = true
76+
count++
77+
}
78+
}
79+
return count <= 1
80+
}
81+
```
82+
6483
### **...**
6584

6685
```

‎lcci/01.04.Palindrome Permutation/Solution.go

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
func canPermutePalindrome(s string) bool {
2+
m := make(map[rune]bool)
3+
count := 0
4+
for _, r := range s {
5+
if m[r] {
6+
m[r] = false
7+
count--
8+
} else {
9+
m[r] = true
10+
count++
11+
}
12+
}
13+
return count <= 1
14+
}

‎lcci/01.05.One Away/README.md

Lines changed: 51 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,7 @@
1111

1212
<p><strong>示例&nbsp;1:</strong></p>
1313

14-
<pre><strong>输入:</strong>
14+
<pre><strong>输入:</strong>
1515
first = &quot;pale&quot;
1616
second = &quot;ple&quot;
1717
<strong>输出:</strong> True</pre>
@@ -20,7 +20,7 @@ second = &quot;ple&quot;
2020

2121
<p><strong>示例&nbsp;2:</strong></p>
2222

23-
<pre><strong>输入:</strong>
23+
<pre><strong>输入:</strong>
2424
first = &quot;pales&quot;
2525
second = &quot;pal&quot;
2626
<strong>输出:</strong> False
@@ -146,6 +146,55 @@ public:
146146
};
147147
```
148148
149+
### **Go**
150+
151+
可以直接扩展成[编辑距离](https://leetcode-cn.com/problems/edit-distance/)问题的解法
152+
153+
```go
154+
func oneEditAway(first string, second string) bool {
155+
if first == second {
156+
return true
157+
}
158+
m, n := len(first), len(second)
159+
dp := make([][]int, m+1)
160+
for i := 0; i <= m; i++ {
161+
dp[i] = make([]int, n+1)
162+
}
163+
for i := 0; i <= m; i++ {
164+
dp[i][0] = i
165+
}
166+
for j := 0; j <= n; j++ {
167+
dp[0][j] = j
168+
}
169+
for i := 1; i <= m; i++ {
170+
for j := 1; j <= n; j++ {
171+
if first[i-1] == second[j-1] {
172+
dp[i][j] = dp[i-1][j-1]
173+
} else {
174+
insert := dp[i][j-1] + 1
175+
delete := dp[i-1][j] + 1
176+
update := dp[i-1][j-1] + 1
177+
dp[i][j] = min(insert, delete, update)
178+
}
179+
}
180+
}
181+
return dp[m][n] == 1
182+
}
183+
184+
func min(x, y, z int) int {
185+
if x < y {
186+
if x < z {
187+
return x
188+
}
189+
return z
190+
}
191+
if y < z {
192+
return y
193+
}
194+
return z
195+
}
196+
```
197+
149198
### **...**
150199

151200
```

‎lcci/01.05.One Away/README_EN.md

Lines changed: 51 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -10,7 +10,7 @@
1010

1111
<pre>
1212

13-
<strong>Input:</strong>
13+
<strong>Input:</strong>
1414

1515
first = &quot;pale&quot;
1616

@@ -24,7 +24,7 @@ second = &quot;ple&quot;
2424

2525
<pre>
2626

27-
<strong>Input:</strong>
27+
<strong>Input:</strong>
2828

2929
first = &quot;pales&quot;
3030

@@ -130,6 +130,55 @@ public:
130130
};
131131
```
132132
133+
### **Go**
134+
135+
Similar to [Edit Distance](https://leetcode-cn.com/problems/edit-distance/) solution
136+
137+
```go
138+
func oneEditAway(first string, second string) bool {
139+
if first == second {
140+
return true
141+
}
142+
m, n := len(first), len(second)
143+
dp := make([][]int, m+1)
144+
for i := 0; i <= m; i++ {
145+
dp[i] = make([]int, n+1)
146+
}
147+
for i := 0; i <= m; i++ {
148+
dp[i][0] = i
149+
}
150+
for j := 0; j <= n; j++ {
151+
dp[0][j] = j
152+
}
153+
for i := 1; i <= m; i++ {
154+
for j := 1; j <= n; j++ {
155+
if first[i-1] == second[j-1] {
156+
dp[i][j] = dp[i-1][j-1]
157+
} else {
158+
insert := dp[i][j-1] + 1
159+
delete := dp[i-1][j] + 1
160+
update := dp[i-1][j-1] + 1
161+
dp[i][j] = min(insert, delete, update)
162+
}
163+
}
164+
}
165+
return dp[m][n] == 1
166+
}
167+
168+
func min(x, y, z int) int {
169+
if x < y {
170+
if x < z {
171+
return x
172+
}
173+
return z
174+
}
175+
if y < z {
176+
return y
177+
}
178+
return z
179+
}
180+
```
181+
133182
### **...**
134183

135184
```

0 commit comments

Comments
 (0)