Repository navigation
Expand file tree
/
Copy path1、常见典例.md
More file actions
238 lines (176 loc) · 5.69 KB
/
Copy path1、常见典例.md
File metadata and controls
238 lines (176 loc) · 5.69 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
#### [17. 电话号码的字母组合](https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/)
难度中等1125收藏分享切换为英文接收动态反馈
给定一个仅包含数字 `2-9` 的字符串，返回所有它能表示的字母组合。答案可以按 **任意顺序** 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
**示例 1：**
```
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
```
**示例 2：**
```
输入：digits = ""
输出：[]
```
**示例 3：**
```
输入：digits = "2"
输出：["a","b","c"]
```
**题解**
```java
class Solution {
public List<String> letterCombinations(String digits) {
List<List<Character>> charsList = getDigitsList(digits);
List<String> res = new ArrayList<>();
if(charsList.size() == 0){
return res;
}
func(charsList , 0 , "" , res);
return res;
}
List<List<Character>> getDigitsList(String digits){
List<List<Character>> res = new ArrayList<>();
for(int i = 0 ; i < digits.length() ; i ++) {
List<Character> chars = new ArrayList<>();
if(digits.charAt(i) < '7'){
for(int j = 0 ; j < 3; j ++){
chars.add((char)((digits.charAt(i) - '2') * 3 + j + 'a'));
}
}else if(digits.charAt(i) == '7'){
for(int j = 0 ; j < 4 ; j ++){
chars.add((char)('p' + j));
}
}else if(digits.charAt(i) == '8'){
for(int j = 0 ; j < 3 ; j ++){
chars.add((char)('t' + j));
}
}else {
for(int j = 0 ; j < 4 ; j ++){
chars.add((char)('w' + j));
}
}
res.add(chars);
}
return res;
}
void func(List<List<Character>> charsList , int idx , String now , List<String> res){
if(idx == charsList.size()){
res.add(now);
return;
}
for(int i = 0 ; i < charsList.get(idx).size() ; i ++){
func(charsList, idx + 1 , now + charsList.get(idx).get(i) ,res);
}
}
}
```
#### [93. 复原IP地址](https://leetcode-cn.com/problems/restore-ip-addresses/)
难度中等497收藏分享切换为英文接收动态反馈
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
**有效的 IP 地址** 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 `0`），整数之间用 `'.' `分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是 **有效的** IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 **无效的** IP 地址。
**示例 1：**
```
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
```
**示例 2：**
```
输入：s = "0000"
输出：["0.0.0.0"]
```
**示例 3：**
```
输入：s = "1111"
输出：["1.1.1.1"]
```
**示例 4：**
```
输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]
```
**示例 5：**
```
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
```
**题解**
```java
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<>();
func(s , "" , 0 , 0 ,res);
return res;
}
void func(String s, String now , int idx , int n , List<String> res){
if(s.length() - idx < 4 - n || n > 4){
return;
}
if(idx == s.length() && n == 4){
res.add(now.substring(0 , now.length() - 1));
return ;
}
for(int i = 0; i < 3 ; i ++){
if(idx + i >= s.length()){
break;
}
String d = s.substring(idx , idx + i + 1);
if(Integer.parseInt(d) > 255 || (d.length() != 1 && Integer.parseInt(d) / ((d.length() - 1) * 10) == 0 )){
break;
}
func(s , now + d + "." , idx + i + 1,n + 1 ,res);
}
}
}
```
#### [131. 分割回文串](https://leetcode-cn.com/problems/palindrome-partitioning/)
难度中等478收藏分享切换为英文接收动态反馈
给定一个字符串 *s*，将 *s* 分割成一些子串，使每个子串都是回文串。
返回 *s* 所有可能的分割方案。
**示例:**
```
输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]
```
**题解**
```java
class Solution {
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
LinkedList<String> now = new LinkedList<>();
func(s , 0 , now , res);
return res;
}
void func(String s , int idx , LinkedList<String> now , List<List<String>> res){
if(idx == s.length()){
List list = new ArrayList();
for(String str : now){
list. add(str);
}
res.add(list);
return;
}
for(int i = 0 ; i < s.length() - idx; i ++){
int l = idx , r = idx + i;
boolean isTrue = true;
while(l < r){
if(s.charAt(l ++) != s.charAt(r --)){
isTrue = false;
break;
}
}
if(isTrue){
now.addLast(s.substring(idx , idx + i + 1));
func(s ,idx + i + 1 ,now ,res);
now.removeLast();
}
}
}
}
```