Skip to content

Commit ae31047

Browse files
DreamCatsDreamCats
committed
📝 update alg lc
1 parent 94a18e7 commit ae31047

File tree

5 files changed

+386
-0
lines changed

5 files changed

+386
-0
lines changed

‎Java/alg/README.md‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -104,6 +104,10 @@
104104
- [6.Z字形变换](lc/6.Z字形变换.md)
105105
- [11.盛最多水的容器](lc/11.盛最多水的容器.md)
106106
- [15.三数之和](lc/15.三数之和.md)
107+
- [17.电话号码的字母组合](lc/17.电话号码的字母组合.md)
108+
- [19.删除链表的倒数第N个结点](lc/19.删除链表的倒数第N个结点.md)
109+
- [22.括号生成](lc/22.括号生成.md)
110+
- [24.两两交换链表中的节点](lc/24.两两交换链表中的节点.md)
107111

108112
## 笔试
109113

‎Java/alg/lc/17.电话号码的字母组合.md‎

Lines changed: 110 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,110 @@
1+
# 17. 电话号码的字母组合
2+
3+
4+
[url](https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/)
5+
6+
## 题目
7+
8+
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
9+
10+
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
11+
12+
![](https://assets.leetcode-cn.com/aliyun-lc-upload/original_images/17_telephone_keypad.png)
13+
14+
15+
```
16+
输入：digits = "23"
17+
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
18+
输入：digits = ""
19+
输出：[]
20+
输入：digits = "2"
21+
输出：["a","b","c"]
22+
```
23+
24+
## 方法
25+
26+
27+
## code
28+
29+
### js
30+
31+
```js
32+
let letterCombinations = digits => {
33+
let dfs = (digits, sb) => {
34+
if (sb.length === digits.length) {
35+
ret.push(sb);
36+
return;
37+
}
38+
let c = digits[sb.length] - '0';
39+
let cur = KEYS[c];
40+
for (const a of cur) {
41+
sb += a;
42+
dfs(digits, sb);
43+
sb = sb.substring(0, sb.length - 1);
44+
}
45+
};
46+
let KEYS = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
47+
let ret = [];
48+
if (digits === null || digits.length === 0)
49+
return ret;
50+
dfs(digits, "");
51+
return ret;
52+
};
53+
```
54+
55+
### go
56+
57+
```go
58+
var KEYS = []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
59+
var res1 []string
60+
func letterCombinations(digits string) []string {
61+
if len(digits) == 0 {
62+
return res1
63+
}
64+
dfs(digits, "")
65+
return res1
66+
}
67+
func dfs(digits string, sb string) {
68+
if len(sb) == len(digits) {
69+
res1 = append(res1, sb)
70+
return
71+
}
72+
c := digits[len(sb)] - byte('0')
73+
cur := KEYS[c]
74+
for _, v := range cur {
75+
sb += string(v)
76+
dfs(digits, sb)
77+
sb = sb[0:len(sb) - 1]
78+
}
79+
}
80+
```
81+
82+
### java
83+
84+
```java
85+
class Solution {
86+
private static final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
87+
List<String> ret = new ArrayList<>();
88+
public List<String> letterCombinations(String digits) {
89+
if(digits == null || digits.length() == 0) return ret;
90+
dfs(digits, new StringBuilder());
91+
return ret;
92+
}
93+
94+
private void dfs(String digits, StringBuilder sb) {
95+
if (sb.length() == digits.length()){
96+
ret.add(sb.toString());
97+
return;
98+
}
99+
int c = digits.charAt(sb.length()) - '0';
100+
String cur = KEYS[c];
101+
for (char a : cur.toCharArray()){
102+
sb.append(a);
103+
dfs(digits, sb);
104+
sb.deleteCharAt(sb.length() - 1);
105+
}
106+
107+
}
108+
}
109+
```
110+

‎Java/alg/lc/19.删除链表的倒数第N个结点.md‎

Lines changed: 90 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,90 @@
1+
# 19. 删除链表的倒数第 N 个结点
2+
3+
4+
[url](https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/)
5+
6+
## 题目
7+
8+
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
9+
10+
进阶：你能尝试使用一趟扫描实现吗？
11+
12+
![](https://assets.leetcode.com/uploads/2020/10/03/remove_ex1.jpg)
13+
14+
```
15+
输入：head = [1,2,3,4,5], n = 2
16+
输出：[1,2,3,5]
17+
输入：head = [1], n = 1
18+
输出：[]
19+
输入：head = [1,2], n = 1
20+
输出：[1]
21+
```
22+
23+
## 方法
24+
25+
26+
## code
27+
28+
### js
29+
30+
```js
31+
let removeNthFromEnd = (head, n) => {
32+
let fast = head;
33+
while (n-- > 0) {
34+
fast = fast.next;
35+
}
36+
if (fast === null)
37+
return head.next;
38+
let slow = head;
39+
while (fast.next !== null) {
40+
fast = fast.next;
41+
slow = slow.next;
42+
}
43+
slow.next = slow.next.next;
44+
return head;
45+
};
46+
```
47+
48+
### go
49+
50+
```go
51+
func removeNthFromEnd(head *ListNode, n int) *ListNode {
52+
fast := head
53+
for n > 0 {
54+
n--
55+
fast = fast.Next
56+
}
57+
if fast == nil {
58+
return head.Next
59+
}
60+
slow := head
61+
for fast.Next != nil {
62+
fast = fast.Next
63+
slow = slow.Next
64+
}
65+
slow.Next = slow.Next.Next
66+
return head
67+
}
68+
```
69+
70+
### java
71+
72+
```java
73+
class Solution {
74+
public ListNode removeNthFromEnd(ListNode head, int n) {
75+
ListNode fast = head;
76+
while (n-- > 0) {
77+
fast = fast.next;
78+
}
79+
if (fast == null) return head.next;
80+
ListNode slow = head;
81+
while (fast.next != null) {
82+
fast = fast.next;
83+
slow = slow.next;
84+
}
85+
slow.next = slow.next.next;
86+
return head;
87+
}
88+
}
89+
```
90+

‎Java/alg/lc/22.括号生成.md‎

Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
# 22. 括号生成
2+
3+
4+
[url](https://leetcode-cn.com/problems/generate-parentheses/)
5+
6+
## 题目
7+
8+
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
9+
10+
11+
```
12+
输入：n = 3
13+
输出：["((()))","(()())","(())()","()(())","()()()"]
14+
输入：n = 1
15+
输出：["()"]
16+
```
17+
18+
## 方法
19+
20+
21+
## code
22+
23+
### js
24+
25+
```js
26+
let generateParenthesis = n => {
27+
let dfs = (ans, cnt1, cnt2, n) => {
28+
if (cnt1 > n || cnt2 > n)
29+
return;
30+
if (cnt1 === n && cnt2 === n)
31+
ret.push(ans);
32+
if (cnt1 >= cnt2){
33+
dfs(ans + "(", cnt1 + 1, cnt2, n);
34+
dfs(ans + ")", cnt1, cnt2 + 1, n);
35+
}
36+
};
37+
let ret = []
38+
dfs("", 0, 0, n);
39+
return ret;
40+
};
41+
```
42+
43+
### go
44+
45+
```go
46+
var res2 []string
47+
func generateParenthesis(n int) []string {
48+
dfs1("", 0, 0, n)
49+
return res2
50+
}
51+
func dfs1(ans string, cnt1 int, cnt2 int, n int) {
52+
if cnt1 > n || cnt2 > n {
53+
return
54+
}
55+
if cnt1 == n && cnt2 == n {
56+
res2 = append(res2, ans)
57+
}
58+
if cnt1 >= cnt2 {
59+
//ans1 := ans
60+
dfs1(ans + "(", cnt1 + 1, cnt2, n)
61+
dfs1(ans + ")", cnt1, cnt2 + 1, n)
62+
}
63+
}
64+
```
65+
66+
### java
67+
68+
```java
69+
class Solution {
70+
List<String> ret = new ArrayList<>();
71+
public List<String> generateParenthesis(int n) {
72+
dfs("", 0, 0, n);
73+
return ret;
74+
}
75+
76+
public void dfs(String ans, int cnt1, int cnt2, int n){
77+
if (cnt1 > n || cnt2 > n)
78+
return;
79+
if (cnt1 == n && cnt2 == n)
80+
ret.add(ans);
81+
if (cnt1 >= cnt2){
82+
String ans1 = new String(ans);
83+
dfs(ans + "(", cnt1 + 1, cnt2, n);
84+
dfs(ans + ")", cnt1, cnt2 + 1, n);
85+
}
86+
}
87+
}
88+
```
89+

‎Java/alg/lc/24.两两交换链表中的节点.md‎

Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
# 24. 两两交换链表中的节点
2+
3+
4+
5+
[url](https://leetcode-cn.com/problems/swap-nodes-in-pairs/)
6+
7+
## 题目
8+
9+
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
10+
11+
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
12+
13+
![](https://assets.leetcode.com/uploads/2020/10/03/swap_ex1.jpg)
14+
```
15+
输入：head = [1,2,3,4]
16+
输出：[2,1,4,3]
17+
输入：head = []
18+
输出：[]
19+
输入：head = [1]
20+
输出：[1]
21+
```
22+
23+
## 方法
24+
25+
26+
## code
27+
28+
### js
29+
30+
```js
31+
let swapPairs = head => {
32+
if (head === null)
33+
return head;
34+
let node = new ListNode();
35+
node.next = head;
36+
let pre = node;
37+
while (pre.next !== null && pre.next.next !== null) {
38+
let l1 = pre.next, l2 = pre.next.next;
39+
let next = l2.next;
40+
l1.next = next;
41+
l2.next = l1;
42+
pre.next = l2;
43+
pre = l1;
44+
}
45+
return node.next;
46+
};
47+
```
48+
49+
### go
50+
51+
```go
52+
func swapPairs(head *ListNode) *ListNode {
53+
if head == nil {
54+
return head
55+
}
56+
node := &ListNode{Val: 0}
57+
node.Next = head
58+
pre := node
59+
for pre.Next != nil && pre.Next.Next != nil {
60+
l1, l2 := pre.Next, pre.Next.Next
61+
next := l2.Next
62+
l1.Next = next
63+
l2.Next = l1
64+
pre.Next = l2
65+
pre = l1
66+
}
67+
return node.Next
68+
}
69+
```
70+
71+
### java
72+
73+
```java
74+
class Solution {
75+
public ListNode swapPairs(ListNode head) {
76+
if (head == null)
77+
return head;
78+
ListNode node = new ListNode(0);
79+
node.next = head;
80+
ListNode pre = node;
81+
while (pre.next != null && pre.next.next != null) {
82+
ListNode l1 = pre.next, l2 = pre.next.next;
83+
ListNode next = l2.next;
84+
l1.next = next;
85+
l2.next = l1;
86+
pre.next = l2;
87+
pre = l1;
88+
}
89+
return node.next;
90+
}
91+
}
92+
```
93+

0 commit comments

Comments
 (0)