剑指 Offer 05. 替换空格
请实现一个函数，把字符串 s 中的每个空格替换成 "%20"。
方法：双指针
首先统计空格数量 count，然后为原字符串数组扩展出 2 * count 的空间，用来存放每个空格对应的的 %20 三个字符中的两个。扩展之后，用 left 指向原数组的最后一个字符，用 right 指向扩展数组的最后一个字符，开始向前遍历：
- 如果遇到空格，在
right及其之前的两个位置分别写入%, 2, 0三个字符； - 否则，直接将遇到的字符填充到
right处。
public String replaceSpace(String s) {
if (s == null) return null;
// 统计空格数量
int space_num = 0;
for (char c : s.toCharArray()) {
if (c == ' ') space_num++;
}
if (space_num == 0) return s;
// 扩展原字符串数组
StringBuilder builder = new StringBuilder(s);
for (int i = 0; i < 2 * space_num; i++)
builder.append(" ");
char[] charArray = builder.toString().toCharArray();
// 用双指针搜索并填充
int left = s.length() - 1;
int right = builder.length() - 1;
while (left >= 0) { // 编码空格
if (charArray[left] == ' ') {
charArray[right--] = '0';
charArray[right--] = '2';
charArray[right] = '%';
} else {
charArray[right] = charArray[left];
}
left--;
right--;
}
return new String(charArray);
}
151. 颠倒字符串中的单词
输入：s = "the sky is blue"
输出："blue is sky the"
注意：输入字符串 s 中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
解题思路：
- 移除多余空格
- 翻转整个字符串
- 翻转每个单词
方法一：使用库函数
public String reverseWords(String s) {
s = s.trim();
List<String> wordList = Arrays.asList(s.split("\\s+"));
Collections.reverse(wordList);
return String.join(" ", wordList);
}
方法二：自己实现
去除多余空格：
public StringBuilder trimSpaces(String s) {
int left = 0, right = s.length() - 1;
// 去除开头结尾的空格
while (left <= right && s.charAt(left) == ' ') left++;
while (left <= right && s.charAt(right) == ' ') right--;
// 去除中间多余空格
StringBuilder builder = new StringBuilder();
while (left <= right) {
char c = s.charAt(left);
if (c != ' ') // 插入普通字符
builder.append(c);
else if (builder.charAt(builder.length()-1) != ' ')
builder.append(c); // 插入单个空格
left++;
}
return builder;
}
翻转整个字符串：
public void reverse(StringBuilder builder, int left, int right) {
while (left < right) {
char temp = builder.charAt(left);
builder.setCharAt(left, builder.charAt(right));
builder.setCharAt(right, temp);
left++;
right--;
}
}
翻转每个单词：
public void reverseEachWord(StringBuilder builder) {
int n = builder.length();
// 双指针：start 指向单词的第一个字母，end 指向单词最后一个字母
int start = 0, end = 0;
while (start < n) {
// 找到单词末尾
while (end < n && builder.charAt(end) != ' ')
end++;
// 翻转这个单词：[start, end-1]
reverse(builder, start, end-1);
// 更新 start
end++;
start = end;
}
}
将这三步结合起来：
public String reverseWords(String s) {
StringBuilder builder = trimSpace(s);
reverse(builder, 0, builder.length()-1);
reverseEachWord(builder);
return builder.toString();
}
方法三：使用栈
public void reverseEachWord(StringBuilder builder) {
int left = 0, right = s.length() - 1;
while (left <= right && s.charAt(left) == ' ') left++;
while (left <= right && s.charAt(right) == ' ') right--;
Deque<String> stack = new LinkedList<>();
StringBuilder builder = new StringBuilder();
// 不断找出一个个单词，放入栈中
while (left <= right) {
char c = s.charAt(left);
// 走到单词末尾
if (c == ' ' && builder.length() > 0) {
stack.push(builder.toString());
builder.setLength(0);
} else if (c != ' '){
builder.append(c);
}
left++;
}
stack.push(builder.toString());
return String.join(" ", stack);
}
20. 有效的括号
方法：栈
boolean isValid(String s) {
int n = s.length();
if(n % 2 == 1) return false;
Map<Character, Character> map = new HashMap<>();
map.put(')', '(');
map.put(']', '[');
map.put('}', '{');
Deque<Character> stack = new LinkedList<>();
for(int i = 0; i < n; i++) {
char c = s.charAt(i);
if(map.containsKey(c)) {
if(stack.isEmpty() || stack.peek() != map.get(c))
return false;
stack.pop();
} else {
stack.push(c);
}
}
return stack.isEmpty();
}
28. 实现 strStr()
判断一个字符串是否是另一个字符串的子串。
方法：KMP算法
KMP 算法的核心，是一个被称为 部分匹配表 （Partial Match Table）的数组，它分别记录着从第一个字符到每个字符为止的子串中，最大相同前缀和后缀的长度。以字符串 "abab" 为例，它的前缀集合为 {"a", "ab", "aba"}，后缀集合为 {"b", "ab", "bab"}，那么它的最长前缀和后缀就是 "ab"。
以字符串 "abababca" 为例，它的 PMT 表为：
| a | b | a | b | a | b | c | a | |
|---|---|---|---|---|---|---|---|---|
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| value | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |
匹配到主串的 i 处时出现失配，这说明主串中 [i-j, i-1] 这一段是和模式串中 [0, j-1] 这一段相匹配的。而模式串中这一段的最长相同前后缀长度（PMT[j-1]）为 4，即 "abab"，也就是说，主串中 i 之前的最后 4 位（后缀）一定与模式串中开头的 4 位（前缀）是相同的，那么就可以跳过这一段的比较，直接比较后面的子串。—— 具体做法是，保持 i 指针不动，j 指向模式串的 PMT[j-1] 位置即可。
将主串子串
s[i-j: i-1]的后缀和模式串子串p[0:j-1]的前缀对齐，直接从模式串的next[j-1]位置开始匹配。
可以看到，在模式串的 j 处失配时，会将 j 指针移动到 PMT[j-1] 处。为了编程方便，将 PMT 数组向后偏移一位，并将得到的新数组称为 next 数组：
| a | b | a | b | a | b | c | a | |
|---|---|---|---|---|---|---|---|---|
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| pmt | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |
| next | -1 | 0 | 0 | 1 | 2 | 3 | 4 | 0 |
next[i]表示p[0:i]这个子串中，最长相同前后缀的长度。将next[0]设为-1没有特别的意义，因为不会用到这个值。
利用 next 数组进行匹配：(这里的 next 数组没有向右移动移动)
int search(String s, String p) {
int i = 0, j = 0; // i, j 分别指示 s, p 的位置
while (i < s.length()) {
if (s.charAt(i) == p.charAt(j)) {
i++;
j++;
} else if (j == 0) { // 在模式串的第一个字符就失配
i++; // 主串移动，模式串不动
} else { // 在其他位置发生失配
j = next[j-1]; // 根据最长相同前后缀长度来移动
}
if (j == p.length()) {
return i - j;
}
}
return -1;
}
核心问题来了：如何求解 next 数组。
考虑用递推的方式求 next[i] —— 已知 next[i-1] （即 p[0:i-1] 子串中最长的相同前后缀的长度），如何求 next[i]？
- 如果
p[i]==p[next[i-1]]，说明p[0:i]的最长相同前后缀长度为next[i-1]+1（即在前一个位置又多出一位），所以next[i] = next[i-1] + 1。（下图中的now就是next[i-1]，x就是i）
图片来源：https://www.zhihu.com/question/21923021/answer/281346746
- 否则，就要将
now变小后再比较p[i]和p[now]的值，从而找到那个使得p[i]==p[now]的最大的now，此时就又能够满足next[i] = now+1。这个now就是子串 A 的前缀集合和子串 B 的后缀集合交集中的最大者的长度，因为子串 A 和子串 B 是相同的，所以就是求子串 A 的最长相同前后缀的长度——也就是next[now-1]。
int[] getNextArray(String s) {
int n = s.length();
int[] next = new int[n];
// j 就是上面图中的 now，i 就是 x
for (int i = 1, j = 0; i < n; i++) {
while (j > 0 && s.charAt(i) != s.charAt(j)) {
j = next[j-1];
}
if (s.charAt(i) == s.charAt(j)) {
j++;
}
next[i] = j;
}
}
最后代码：
class Solution {
public int strStr(String haystack, String needle) {
int len_str = haystack.length(), len_pattern = needle.length();
if (len_pattern == 0) return 0;
int[] next = getNext(needle);
// i,j 分别指向主串和模式串
int i = 0, j = 0;
while (i < len_str) {
if(haystack.charAt(i) == needle.charAt(j)) {
i++;
j++;
} else if (j == 0) {
i++;
} else {
j = next[j-1];
}
if (j == len_pattern) return i - j;
}
return -1;
}
int[] getNext(String s) {
int n = s.length();
int[] next = new int[n];
for (int i = 1, j = 0; i < n; i++) {
while (j > 0 && s.charAt(i) != s.charAt(j)) {
j = next[j-1];
}
if (s.charAt(i) == s.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}
}
459. 重复的子字符串
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
方法一：枚举
如果这个重复子串的长度为 \(i\)，那么对于每个字符 \(s[j]\)，它与 \(s[i+j]\) 相同。
因此可以从小到大枚举 \(i\)，遍历字符串，判断上面的条件是否成立。注意两点：
- 如果 \(i\) 不能被字符串长度整除，直接跳过。
- 因为子串至少需要重复一次，所以最大子串长度为 \(n/2\)，只需要在 \([1,n/2]\) 范围内枚举 \(i\) 即可。
public boolean repeatedSubstring(String s) {
int n = s.length();
// 枚举子串长度
for (int i = 1; i * 2 <= n; i++) {
if (n % i != 0) continue;
boolean match = true;
for (int j = 0; j < n - i; j++) {
if (s.charAt(j) != s.charAt(j + i)) {
match = false;
break;
}
}
if (match) return true;
}
return false;
}
43. 字符串相乘
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
方法一：做加法
通过模拟「竖式乘法」的方法计算乘积。从右往左遍历乘数，将乘数的每一位与被乘数相乘得到对应的结果，再将每次得到的结果累加。
String multiply(String num1, String num2) {
if(num1.equals("0") || num2.equals("0"))
return "0";
String result = "0";
int len1 = num1.length(), len2 = num2.length();
// 遍历乘数（竖式中位于下面的数）
for(int i = len2-1; i >= 0; i--) {
// 每次计算一位乘数与被乘数的乘积，最后加起来
StringBuffer buffer = new StringBuffer();
int add = 0; // 进位
for(int j = len2-1; j > i; j--)
buffer.append(0); // 补零——十位补一个，百位两个
// 当前位上的数字
int x2 = num2.charAt(i) - '0';
// 遍历被乘数
for(int j = len1-1; j >= 0; j--) {
int x1 = num1.charAt(j);
int product = x1 * x2 + add;
add = product / 10;
buffer.append(product % 10);
}
if(add > 0) buffer.append(add);
result = addString(result, buffer.reverse().toString());
}
return result;
}
String addString(String num1, String num2) {
StringBuffer buffer = new StringBuffer();
int add = 0;
for(int i = num1.length() - 1, j = num2.length() - 1;
i >= 0 || j >= 0; i--, j--) {
int x1 = (i >= 0) ? num1.charAt(i) - '0' : 0;
int x2 = (j >= 0) ? num2.charAt(j) - '0' : 0;
int sum = x1 + x2 + add;
add = sum / 10;
buffer.append(sum % 10);
}
if(add > 0) buffer.append(add);
buffer.reverse();
return buffer.toString();
}
方法二：做乘法
用 \(m,n\) 分别表示两数的长度，则两数乘积的长度为 \(m+n-1\) 或者 \(m+n\)。
- 如果两数都取最小值，则分别为 \(10^{m-1}, \; 10^{n-1}\)，乘积为 \(10^{m+n-2}\)，其长度为 \(m+n-1\)。
- 如果两数都取最大值，则分别为 \(10^m-1, \; 10^n-1\)，乘积小于\(10^{m+n}\)且大于\(10^{m+n-1}\)，长度为 \(m+n\)。
因为最大长度为 \(m+n\)，所以创建该长度的数组用于存储乘积。对任意两位数 \(num1[i], \; num2[j]\)，其乘积存放到结果数组的 \(i+j+1\) 索引处，如果乘积大于 10，则将进位加到 \(i+j\) 索引处。
最后将结果数组转成字符串，如果最高位是 0 则舍弃。
String multiply(String num1, String num2) {
if(num1.equals("0") || num2.equals("0"))
return "0";
int m = num1.length(), n = num2.length();
int[] result = new int[m+n];
for(int i = m-1; i >= 0; i--) {
int x1 = num1.charAt(i) - '0';
for(int j = n-1; j >= 0; j--) {
int x2 = num2.charAt(j) - '0';
result[i+j+1] += x1 * x2;
}
}
// 进位
for(int i = m+n-1; i > 0; i--) {
result[i-1] += result[i]/10;
result[i] %= 10; // 进位后，只保存余数
}
int index = result[0] == 0 ? 1 : 0;
StringBuffer buffer = new StringBuffer();
while(index < m + n) {
buffer.append(result[index]);
index++;
}
return buffer.toString();
}
93. 复原 IP 地址
有效 IP 地址 正好有四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
方法：回溯
要素的确定：
- 状态变量：
segId：正在搜索 IP 地址的第几段；segStart：正在从字符串中哪个位置开始搜索。 - 结束条件：
segId==4 && segStart==s.length()，表示找出了一种有效的 IP 地址；- 如果提前遍历完了字符串，需要结束搜索，回溯到上一步；
- 因为不能有前导 0，所以碰到
s.charAt(segStart)=='0'，就需要将这个 0 作为当前段。
- 路径：已经找到的段。
- 选择列表：在 0~255 之间，以
segStart位置开头的所有子串。
用递归函数 dfs(segId, segStart) 表示正在从 segStart 位置开始，搜索 IP 地址中的第 segId 段。因为每一段必须是 [0,255] 中的数，所以从小到大枚举当前这一段 IP 的结束位置 segEnd 。如果满足要求，就递归进行下一段搜索： dfs(segId+1, segEnd+1) 。
特别地。由于 IP 地址每一段不能有前导 0，所以如果 segStart 位置为 0，那么当前段只能为 0.
如果已经得到了 4 段 IP，并且遍历完了整个字符串，那么就复原出了一种有效的 IP 地址，此时将其加入答案。其他时刻，如果提前遍历完了字符串，就需要结束搜索，回溯到上一步。
List<String> result = new ArrayList<>();
int[] segments = new int[4]; // 用整数记录每一段的数字
List<String> ipAddress(String s) {
dfs(s, 0, 0);
return result;
}
void dfs(String s, int segId, int segStart) {
// 如果已经找到了 4 段，并且遍历完了字符串，那么就记下这个答案
if(segId == 4) {
if(segStart == s.length()) {
StringBuffer ipAddr = new StringBuffer();
for(int i = 0; i < 4; i++) {
ipAddr.append(segments[i]);
if(i != 3)
ipAddr.append('.');
}
result.add(ipAddr.toString());
}
return;
}
// 没有找到4段就已经遍历完成字符串，提前回溯
if(segStart == s.length()) return;
// 不能有前导 0
if(s.charAt(segStart) == '0') {
segments[segId] = 0;
dfs(s, segId + 1, segStart + 1);
}
// 一般情况，枚举每一种可能性
int addr = 0;
for(int i = segStart; i < s.length(); i++) {
addr = addr * 10 + (s.charAt(i) - '0');
if(addr > 0 && addr <= 255) {
segments[segId] = addr;
dfs(s, segId+1, i+1);
} else {
break;
}
}
}
844. 比较含退格的字符串
给定两字符串，其中特殊符号 # 表示退格键，会从原字符串中删除最后输入的一个字符，比较这两个输入字符串是否相同。
方法一：借助栈来还原输入结果字符串。
方法二：双指针。
一个字符是否会被删除只取决于其后面的退格键有多少，所以逆序遍历字符串就可以知道当前遍历到的每个字符是否会被删除，如果不会被删除则比较当前两个字符，直到遇到两字符不相等或者两字符串遍历结束。
用变量 skip 记录当前的待生效退格数，对于每个字符，
- 如果是普通字符且
skip > 0， 则删除（跳过）当前字符； - 如果是普通字符且
skip <= 0，则表示遇到一个有效输入字符，拿它进行比较； - 如果是
#，则skip++。
boolean compareInput(String s, String t) {
int i = s.length() - 1, j = t.length() - 1;
int skipS = 0, skipT = 0;
while(i >= 0 || j >= 0) {
// 找出 s 中的有效输入字符
while(i >= 0) {
if(s.charAt(i) == '#') {
skipS++;
i--;
} else if(skipS > 0) {
skipS--;
i--;
} else
break;
}
// 找出 t 中的有效输入字符
while(j >= 0) {
if(t.charAt(j) == '#') {
skipT++;
j--;
} else if(skipT > 0) {
skipT--;
j--;
} else
break;
}
// 比较这两个有效字符
// >= 0 说明当前还存在有效字符
if(i >= 0 && j >= 0) {
if(s.charAt(i) != t.charAt(j))
return false;
} else if(i >= 0 || j >= 0) {
return false;
}
i--;
j--;
}
return true;
}
784. 字母大小写全排列
示例
输入：S = "a1b2"
输出：["a1b2", "a1B2", "A1b2", "A1B2"]
遍历字符串：
- 如果下一个字符 c 是字母，将当前已遍历过的字符串全排列复制两份，在第一份的每个字符串末尾添加
lowercase(c)，在第二份的每个字符串末尾添加uppercase(c)。 - 如果下一个字符 c 是数字，将 c 直接添加到每个字符串的末尾。
例如，当 S = "abc" 时，考虑字母 "a", "b", "c"，初始令 ans = [""]，依次更新 ans = ["a", "A"]， ans = ["ab", "Ab", "aB", "AB"]， ans = ["abc", "Abc", "aBc", "ABc", "abC", "AbC", "aBC", "ABC"]。
List<String> letterCasePermutation(String s) {
List<StringBuilder> resultBuilder = new ArrayList<>();
resultBuilder.add(new StringBuilder()); // 先添加一个空串
for(char cur : s.toCharArray()) {
int size = resultBuilder.size();
if(Character.isLetter(cur)) {
for(int i = 0; i < size; i++) {
// 在末尾复制一份
resultBuilder.add(new StringBuilder(resultBuilder.get(i)));
// 在这两份后面分别追加当前字母的大小写
resultBuilder.get(i).append(Character.toLowerCase(cur));
resultBuilder.get(size + i).append(Character.toUpperCase(cur));
}
} else {
for(int i = 0; i < size; i++)
resultBuilder.get(i).append(cur);
}
}
List<String> result= new ArrayList<>();
for(StringBuilder builder : resultBuilder)
result.add(builder.toString());
return result;
}
31. 下一个排列
用数组表示一个排列，求出下一个紧接着的所表示数字更大的排列。
通过观察下图示例，可以发现生成下一个紧接排列的方法：
- 首先从后往前找到
nums[i] < nums[i+1]的一对元素，这个nums[i]称为 较小值。[i+1, len-1]这个序列必定是降序排列的（如果不是降序，较小值就会在该范围内部。） - 然后从后往前找到第一个大于较小值的元素
nums[j]，称为 较大值。 - 将较小值和较大值互换位置；交换后，
[i+1, len-1]这个序列必定还是降序的，因为和较小值交换的那个较大值是这个序列中的最小值。 - 然后将原来较小值所在位置后面的子数组升序排序（由于序列降序，所以使用双指针逐一交换前后元素的位置即可）。
void nextPermutation(int[] nums) {
// 找到「较小值」
int small = nums.length - 2;
while(small >= 0 && nums[small] >= nums[small+1])
small--;
// 找到「较大值」
if(small >= 0) { // 如果是最大那个排列，则 small < 0
int big = nums.length - 1;
while(big > small && nums[big] < nums[small])
big--;
// 交换「较小值」和「较大值」
swap(nums, small, big);
}
// 较小值位置后面序列升序排序
reverse(nums, small+1);
}
void reverse(int[] nums, int start) {
int left = start, int right = nums.length - 1;
while(left < right) {
swap(nums, left, right);
left++;
right--;
}
}
void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
394. 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。
示例：
输入：s = "3[a2[c]]"
输出："accaccacc"
方法一：栈
使用两个辅助栈来遍历整个字符串：
stack_multi存储重复次数。当遇到[时将当前重复次数multi放入stack_multi，stack_result存储每一段子串，即两个括号之间的子串以及前面的重复次数解码出来的子串。这个子串用builder表示。当遇到[时，将当前builder放入stack_result。- 进入到新的
[后，builder和multi重新记录。
String decodeString(String s) {
StringBuilder builder = new StringBuilder();
int multi = 0;
Deque<Integer> stack_multi = new LinkedList<>();
Deque<String> stack_result = new LinkedList<>();
for(char c : s.toCharArray()) {
if(Character.isDigit(c)) {
multi = multi * 10 + (c - '0');
} else if(c == '[') {
stack_multi.push(multi);
stack_result.push(builder.toString());
// 重新初始化 multi 和 builder
multi = 0;
builder = new StringBuilder();
} else if(c == ']') {
// 记录当前这一段子串重复的结果
StringBuilder temp = new StringBuilder();
int cur_multi = stack_multi.pop();
for(int i = 0; i < cur_multi; i++)
temp.append(builder);
// 处理完一层 ] 后更新 builder
builder = new StringBuilder(stack_result.pop() + temp);
} else {
builder.append(c);
}
}
return builder.toString();
}