字符串基础题
通关进度
| 题目 |
说明 |
| 转换成小写字母 |
通关 |
| 字符串转换整数 |
通关 |
参考资料
字符串与常见面试题
转换成小写字母
709. 转换成小写字母
问题
【LeetCode 709】：给你一个字符串 s ，将该字符串中的大写字母转换成相同的小写字母，返回新的字符串。
ASCII
- 大写字母
A - Z 的 ASCII 码范围为 $[65,90]$
- 小写字母
a - z 的 ASCII 码范围为 $[97,122]$
如果 ch 的 ASCII 码在 $[65,90]$ 的范围内，那么将它的 ASCII 码增加 $32$，即可得到对应的小写字母。
由于 $[65,90]$ 对应的二进制表示为 $[(01000001)_2,(01011010)_2]$， $32$ 对应的二进制表示为 $(00100000)_2$，而对于 $[(01000001)_2,(01011010)_2]$ 内的所有数，表示 $32$ 的那个二进制位都是 0，因此可以对 ch 的 ASCII 码与 $32$ 做按位或运算，替代与 $32$ 的加法运算。
1
2
3
4
5
6
7
8
9
10
11
12
| public String toLowerCase(String s) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch >= 65 && ch <= 90) {
ch |= 32;
}
sb.append(ch);
}
return sb.toString();
}
|
字符串转换整数
8. 字符串转换整数 (atoi)
问题
【LeetCode 8】：请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数
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
| public int myAtoi(String s) {
char[] chars = s.toCharArray();
int index = 0;
while (index < s.length() && chars[index] == ' ') {
index++;
}
if (index == s.length()) {
return 0;
}
int sign = 1;
char firstChar = chars[index];
if (firstChar == '+') {
index++;
} else if (firstChar == '-') {
index++;
sign = -1;
}
int ans = 0;
while (index < s.length()) {
char curChar = chars[index];
if (curChar > '9' || curChar < '0') {
break;
}
if (ans > Integer.MAX_VALUE / 10 ||
(ans == Integer.MAX_VALUE / 10 && (curChar - '0') > Integer.MAX_VALUE % 10)) {
return Integer.MAX_VALUE;
}
if (ans < Integer.MIN_VALUE / 10 ||
(ans == Integer.MIN_VALUE / 10 && (curChar - '0') > -(Integer.MIN_VALUE % 10))) {
return Integer.MIN_VALUE;
}
ans = ans * 10 + sign * (curChar - '0');
index++;
}
return ans;
}
|
字符串经典题
通关进度
| 题目 |
说明 |
| 字符串反转问题 |
通关 |
| 回文串问题 |
通关 |
| 搜索第一个唯一字符 |
通关 |
| 有效的字母异位词 |
通关 |
字符串反转专题
反转字符串
344. 反转字符串
问题
【LeetCode 344】：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
1
2
3
4
5
6
7
8
| public void reverseString(char[] s) {
for (int left = 0, right = s.length - 1; left < right; left++, right--) {
char temp = s[left];
s[left] = s[right];
s[right] = temp;
}
}
|
K 组反转字符串
541. 反转字符串 II
问题
【LeetCode 541】：给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
- 如果剩余字符少于
k 个，则将剩余字符全部反转
- 如果剩余字符小于
2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public String reverseStr(String s, int k) {
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i += 2 * k) {
reverse(chars, i, Math.min(i + k, chars.length) - 1);
}
return new String(chars);
}
public void reverse(char[] arr, int left, int right) {
while (left < right) {
char temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
|
仅反转字母
917. 仅仅反转字母
问题
【LeetCode 917】：给你一个字符串 s ，根据下述规则反转字符串：
- 所有非英文字母保留在原有位置。
- 所有英文字母（小写或大写）位置反转。
返回反转后的 s 。
双指针
使用 left 指针从左边开始扫描字符串 s，right 指针从右边开始扫描字符串 s。如果两个指针都扫描到字母，且 left<right，那么交换 s[left] 和 s[right]，然后继续进行扫描；否则表明反转过程结束，返回处理后的字符串。
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
| public String reverseOnlyLetters(String s) {
char[] arr = s.toCharArray();
int left = 0, right = s.length() - 1;
while (left < right) {
while (left < right && !Character.isLetter(s.charAt(left))) {
left++;
}
while (left < right && !Character.isLetter(s.charAt(right))) {
right--;
}
swap(arr, left, right);
left++;
right--;
}
return new String(arr);
}
public void swap(char[] arr, int left, int right) {
char temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
|
反转字符串里的单词
151. 反转字符串中的单词
问题
【LeetCode 151】：给你一个字符串 s ，请你反转字符串中 单词 的顺序
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
| public String reverseWords(String s) {
StringBuilder sb = trimSpace(s);
reverse(sb, 0, sb.length() - 1);
reverseEachWord(sb);
return sb.toString();
}
public StringBuilder trimSpace(String str) {
int left = 0, right = str.length() - 1;
while (left <= right && str.charAt(left) == ' ') {
++left;
}
while (left <= right && str.charAt(right) == ' ') {
--right;
}
StringBuilder sb = new StringBuilder();
while (left <= right) {
char ch = str.charAt(left);
if (ch != ' ') {
sb.append(ch);
} else if (sb.charAt(sb.length() - 1) != ' ') {
sb.append(ch);
}
++left;
}
return sb;
}
public void reverse(StringBuilder sb, int left, int right) {
while (left < right) {
char tmp = sb.charAt(left);
sb.setCharAt(left++, sb.charAt(right));
sb.setCharAt(right--, tmp);
}
}
public void reverseEachWord(StringBuilder sb) {
int n = sb.length();
int start = 0, end = 0;
while (start < n) {
while (end < n && sb.charAt(end) != ' ') {
++end;
}
reverse(sb, start, end - 1);
start = end + 1;
++end;
}
}
|
验证回文串
125. 验证回文串
问题
【LeetCode 125】：如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
直接在原字符上判断
- 直接在原字符串
s 上使用双指针
- 在移动任意一个指针时，需要不断地向另一指针的方向移动，直到遇到一个字母或数字字符，或者两指针重合为止
- 每次将指针移到下一个字母字符或数字字符，再判断这两个指针指向的字符是否相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
++left;
}
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
--right;
}
if (left < right) {
if (Character.toLowerCase(s.charAt(left)) !=
Character.toLowerCase(s.charAt(right))) {
return false;
}
++left;
--right;
}
}
return true;
}
|
字符串中的第一个唯一字符
387. 字符串中的第一个唯一字符
问题
【LeetCode 387】：给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1
使用哈希表存储频数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public int firstUniqChar(String s) {
Map<Character, Integer> frequency = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);
}
for (int i = 0; i < s.length(); i++) {
if (frequency.get(s.charAt(i)) == 1) {
return i;
}
}
return -1;
}
|
有效的字母异位词
242. 有效的字母异位词
问题
【LeetCode 242】：给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
排序
1
2
3
4
5
6
7
8
9
10
11
12
| public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
char[] chars1 = s.toCharArray();
char[] chars2 = t.toCharArray();
Arrays.sort(chars1);
Arrays.sort(chars2);
return Arrays.equals(chars1, chars2);
}
|
哈希表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] frequency = new int[26];
for (int i = 0; i < s.length(); i++) {
frequency[s.charAt(i) - 'a']++;
}
for (int i = 0; i < t.length(); i++) {
frequency[t.charAt(i) - 'a']--;
if (frequency[t.charAt(i) - 'a'] < 0) {
return false;
}
}
return true;
}
|
字符串冲刺题
通关进度
| 题目 |
说明 |
| 最长公共前缀问题 |
通关 |
| 字符串压缩问题 |
通关 |
| 表示数值的字符串 |
通关 |
最长公共前缀
14. 最长公共前缀
问题
【LeetCode 14】：编写一个函数来查找字符串数组中的最长公共前缀。
横向扫描
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 String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
String prefix = strs[0];
int count = strs.length;
for (int i = 1; i < count; i++) {
prefix = longestCommonPrefix(prefix, strs[i]);
if (prefix.length() == 0) {
break;
}
}
return prefix;
}
public String longestCommonPrefix(String str1, String str2) {
int len = Math.min(str1.length(), str2.length());
int index = 0;
while (index < len) {
if (str1.charAt(index) != str2.charAt(index)) {
break;
}
index++;
}
return str1.substring(0, index);
}
|
纵向扫描
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
int length = strs[0].length();
int count = strs.length;
for (int i = 0; i < length; i++) {
char ch = strs[0].charAt(i);
for (int j = 1; j < count; j++) {
if (i == strs[j].length() || strs[j].charAt(i) != ch) {
return strs[0].substring(0,i);
}
}
}
return strs[0];
}
|
分治
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
|
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
} else {
return longestCommonPrefix(strs, 0, strs.length - 1);
}
}
public String longestCommonPrefix(String[] strs, int start, int end) {
if (start == end) {
return strs[start];
}
int mid = start + ((end - start) >> 1);
String lcpLeft = longestCommonPrefix(strs, start, mid);
String lcpRight = longestCommonPrefix(strs, mid + 1, end);
return commonPrefix(lcpLeft, lcpRight);
}
public String commonPrefix(String lcpLeft, String lcpRight) {
int minLength = Math.min(lcpLeft.length(), lcpRight.length());
for (int i = 0; i < minLength; i++) {
if (lcpLeft.charAt(i) != lcpRight.charAt(i)) {
return lcpLeft.substring(0, i);
}
}
return lcpLeft.substring(0, minLength);
}
|
字符串压缩问题
443. 压缩字符串
问题
【LeetCode 443】：给你一个字符数组 chars ，请使用下述算法压缩：
从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 ：
- 如果这一组长度为
1 ，则将字符追加到 s 中
- 否则，需要向
s 追加字符，后跟这一组的长度
压缩后得到的字符串 s 不应该直接返回 ，需要转储到字符数组 chars 中。需要注意的是，如果组长度为 10 或 10 以上，则在 chars 数组中会被拆分为多个字符。
请在 修改完输入数组后 ，返回该数组的新长度。
双指针
- 可以使用双指针分别标志我们在字符串中读和写的位置
- 每次当读指针
read 移动到某一段连续相同子串的最右侧
- 就在写指针
write 处依次写入该子串对应的字符和子串长度即可
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
| public int compress(char[] chars) {
int write = 0, left = 0;
for (int read = 0; read < chars.length; read++) {
if (read == chars.length - 1
|| chars[read] != chars[read + 1]) {
chars[write++] = chars[read];
int num = read - left + 1;
if (num > 1) {
int anchor = write;
while (num > 0) {
chars[write++] = (char) (num % 10 + '0');
num /= 10;
}
reverse(chars, anchor, write - 1);
}
left = read + 1;
}
}
return write;
}
public void reverse(char[] chars, int left, int right) {
while (left < right) {
char temp = chars[left];
chars[left] = chars[right];
chars[right] = temp;
left++;
right--;
}
}
|
有效数字
LCR 138. 有效数字
问题
【LCR 138. 有效数字】：有效数字（按顺序）可以分成以下几个部分：
- 若干空格
- 一个 小数 或者 整数
- （可选）一个
'e' 或 'E' ，后面跟着一个 整数
- 若干空格
