关于散列表和字符串的 4 个必知必会的代码实现
散列表
实现一个基于链表法解决冲突问题的散列表
实现一个 LRU 缓存淘汰算法
字符串
字符串题目
思路
看到题目后首先想到的是双指针法，创建两个指针 head 和 tail 分别指向字符串头部和尾部，交换两个指针所指元素，然后 head 往后 tail 往前，直到两指针相遇。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public void reverseString(char[] s) {
if (s.length == 0 || s.length == 1) {
return;
}
int head = 0;
int tail = s.length - 1;
while (head < tail) {
char temp = s[head];
s[head] = s[tail];
s[tail] = temp;
head++;
tail--;
}
}
|
思路
从后往前遍历，遇到空格跳过，否则就记录下不是空格的位置，然后截取字串，放到临时字符串中
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public String reverseWords(String s) {
if (s.length() == 0) {
return s;
}
StringBuilder result = new StringBuilder();
for (int i = s.length() - 1; i >= 0;) {
int end = 0;
if (s.charAt(i) == ' ') {
i --;
continue;
}
end = i + 1;
while ((i >= 0) && s.charAt(i) != ' ') {
i --;
}
result.append(s, i + 1, end);
if (i > 0) {
result.append(" ");
}
}
return result.toString().trim();
}
|
思路
题目说明上已经给出限制条件，但是还有很多条件没有给出，最后一步步提交踩着坑终于踩出来了。。。
代码
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
| public int myAtoi(String str) {
if (str == null || "".equals(str)) {
return 0;
}
StringBuilder resultS = new StringBuilder();
boolean isNegative = false;
boolean isPositive = false;
String newStr = str.trim();
if ("".equals(newStr)) {
return 0;
}
if ((newStr.charAt(0) < '0') || (newStr.charAt(0) > '9')) {
if (newStr.charAt(0) != '+' && newStr.charAt(0) != '-') {
return 0;
} else {
if (newStr.charAt(0) == '-') {
isNegative = true;
}
if (newStr.charAt(0) == '+') {
isPositive = true;
}
}
}
char[] chars = newStr.toCharArray();
int i = isNegative | isPositive ? 1 : 0;
for (; i < chars.length; i++) {
char c = chars[i];
if (c == '0') {
chars[i] = '`';
} else {
break;
}
}
i = isNegative | isPositive ? 1 : 0;
for (; i < chars.length; i++) {
char c = chars[i];
if (c == '`') {
continue;
}
if (resultS.length() > 10) {
return isNegative ? Integer.MIN_VALUE : Integer.MAX_VALUE;
}
if (c >= '0' && c <= '9') {
resultS.append(c);
} else {
break;
}
}
if (resultS.length() == 0) {
return 0;
}
long aLong = Long.parseLong(resultS.toString());
if (isNegative) {
aLong = - aLong;
}
if (aLong > Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}
if (aLong < Integer.MIN_VALUE) {
return Integer.MIN_VALUE;
}
return (int) aLong;
}
|
精简版代码
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
| public int myAtoi2(String str) {
str = str.trim();
if (str.length() == 0) {
return 0;
}
long sum = 0;
int first = 0, n = str.length();
int flag = 1;
if (str.charAt(0) == '+') {
first++;
} else if (str.charAt(0) == '-') {
first++;
flag = -1;
}
for (int i = first; i < n; i++) {
if (!Character.isDigit(str.charAt(i))) {
return (int) sum * flag;
}
sum = 10 * sum + str.charAt(i) - '0';
if (flag == 1 && sum > Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}
if (flag == -1 && (-1) * sum < Integer.MIN_VALUE) {
return Integer.MIN_VALUE;
}
}
return (int) sum * flag;
}
|