Summary
- 反转字符串 344. Reverse String 💚
- 反转字符串II 541. Reverse String II 💚
- 替换空格 剑指 Offer 05 💚
- 翻转字符串中的单词 151. Reverse Words in a String 🧡
- 左旋转字符串 剑指 Offer 58 - II 💚
- KMP实现 strStr() 28. Find the Index of the First Occurrence in a String 🧡
- KMP重复的子字符串 459. Repeated Substring Pattern 💚
1. 反转字符串 344. Reverse String 💚
思路： 双指针
对于字符串，我们定义两个指针（也可以说是索引下标），一个从字符串前面，一个从字符串后面，两个指针同时向中间移动，并交换元素。
以字符串hello为例，过程如下：
双指针交换过程
- 常见的交换数值：
int tmp = s[I];
s[i] = s[j];
s[j] = tmp;
- 位运算交换
s[i] ^= s[j];
s[j] ^= s[I];
s[i] ^= s[j];
class Solution {
public void reverseString(char[] s) {
int left = 0;
int right = s.length - 1;
while(left < right){
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
}
2. 反转字符串II 541. Reverse String II 💚
当需要固定规律一段一段去处理字符串的时候，要想想在在for循环的表达式上做做文章。
这道题目其实也是模拟，实现题目中规定的反转规则就可以了。
一些同学可能为了处理逻辑：每隔2k个字符的前k的字符，写了一堆逻辑代码或者再搞一个计数器，来统计2k，再统计前k个字符。
其实在遍历字符串的过程中，只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。
因为要找的也就是每2 * k 区间的起点，这样写，程序会高效很多。
//题目的意思其实概括为 每隔2k个反转前k个，尾数不够k个时候全部反转
class Solution {
public String reverseStr(String s, int k) {
char[] ch = s.toCharArray();
for(int i = 0; i < ch.length; i += 2 * k){
int start = I;
int end = Math.min(ch.length - 1, start + k -1);
while(start < end){
char temp = ch[start];
ch[start] = ch[end];
ch[end] = temp;
start++;
end--;
}
}
return new String(ch);
}
}
3. 替换空格 剑指 Offer 05 💚
双指针
如果想把这道题目做到极致，就不要只用额外的辅助空间了！
首先扩充数组到每个空格替换成"%20"之后的大小。
然后从后向前替换空格，也就是双指针法，过程如下：
i指向新长度的末尾，j指向旧长度的末尾。
操作演示
有同学问了，为什么要从后向前填充，从前向后填充不行么？
从前向后填充就是O(n^2)的算法了，因为每次添加元素都要将添加元素之后的所有元素向后移动。
其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。
这么做有两个好处：
不用申请新数组。
从后向前填充元素，避免了从前先后填充元素要来的 每次添加元素都要将添加元素之后的所有元素向后移动。
Time: O(n)/Space: O(1)
class Solution {
public String replaceSpace(String s) {
if(s == null || s.length() == 0){
return s;
}
//扩充空间，空格数量2倍
StringBuilder str = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if(s.charAt(i) == ' '){
str.append(" ");
}
}
//若是没有空格直接返回
if(str.length() == 0){
return s;
}
//有空格情况 定义两个指针
int left = s.length() - 1;//左指针：指向原始字符串最后一个位置
s += str.toString();
int right = s.length()-1;//右指针：指向扩展字符串的最后一个位置
char[] chars = s.toCharArray();
while(left>=0){
if(chars[left] == ' '){
chars[right--] = '0';
chars[right--] = '2';
chars[right] = '%';
}else{
chars[right] = chars[left];
}
left--;
right--;
}
return new String(chars);
}
}
4. 翻转字符串中的单词 151. Reverse Words in a String 🧡
思路：
- 移除多余空格
- 将整个字符串反转
- 将每个单词反转
举个例子，源字符串为："the sky is blue "
- 移除多余空格 : "the sky is blue"
- 字符串反转："eulb si yks eht"
- 单词反转："blue is sky the"
class Solution {
//用 char[] 来实现 String 的 removeExtraSpaces，reverse 操作
public String reverseWords(String s) {
char[] chars = s.toCharArray();
//1.去除首尾以及中间多余空格
chars = removeExtraSpaces(chars);
//2.整个字符串反转
reverse(chars, 0, chars.length - 1);
//3.单词反转
reverseEachWord(chars);
return new String(chars);
}
//1.用 快慢指针 去除首尾以及中间多余空格，可参考数组元素移除的题解
public char[] removeExtraSpaces(char[] chars) {
int slow = 0;
for (int fast = 0; fast < chars.length; fast++) {
//先用 fast 移除所有空格
if (chars[fast] != ' ') {
//在用 slow 加空格。 除第一个单词外，单词末尾要加空格
if (slow != 0)
chars[slow++] = ' ';
//fast 遇到空格或遍历到字符串末尾，就证明遍历完一个单词了
while (fast < chars.length && chars[fast] != ' ')//先判长度，不然会报错
chars[slow++] = chars[fast++];
}
}
//相当于 c++ 里的 resize()
char[] newChars = new char[slow];
System.arraycopy(chars, 0, newChars, 0, slow);
return newChars;
}
//双指针实现指定范围内字符串反转，可参考字符串反转题解
public void reverse(char[] chars, int left, int right) {
while (left < right) {
chars[left] ^= chars[right];
chars[right] ^= chars[left];
chars[left] ^= chars[right];
left++;
right--;
}
}
//3.单词反转
public void reverseEachWord(char[] chars) {
int start = 0;
//end <= s.length() 这里的 = ，是为了让 end 永远指向单词末尾后一个位置，这样 reverse 的实参更好设置
for (int end = 0; end <= chars.length; end++) {
// end 每次到单词末尾后的空格或串尾,开始反转单词
if (end == chars.length || chars[end] == ' ') {
reverse(chars, start, end - 1);
start = end + 1;
}
}
}
}
5. 左旋转字符串 剑指 Offer 58 - II 💚
思路：
- 反转区间为前n的子串
- 反转区间为n到末尾的子串
- 反转整个字符串
例如 ：示例1中 输入：字符串abcdefg，n=2
例
//空间复杂度：O(1)。用原始数组来进行反转操作
class Solution {
public String reverseLeftWords(String s, int n) {
char[] chars = s.toCharArray();
reverse(chars, 0, n - 1);
reverse(chars, n, chars.length - 1);
reverse(chars, 0, chars.length - 1);
return new String(chars);
}
public void reverse(char[] ch, int start, int end){
while(start < end){
char temp = ch[end];
ch[end] = ch[start];
ch[start] = temp;
start++;
end--;
}
}
}
6. KMP实现 strStr()28. Find the Index of the First Occurrence in a String 🧡
在一个串中查找是否出现过另一个串，这是KMP的看家本领。
详见：KMP
class Solution {
public static int strStr(String str1, String str2) {
if (str1 == null || str2 == null || str1.length() < str2.length()) {
return -1;
}
return process(str1.toCharArray(), str2.toCharArray());
}
public static int process(char[] str1, char[] str2) {
// i1是str1的匹配指针，i2是str2的匹配指针
int i1 = 0;
int i2 = 0;
// 获取str2所有字符的最长前缀和后缀
int[] next = getMaximalPrefixAndSuffix(str2);
// 匹配过程只要i1越界或者i2越界匹配都会终止（i1和i2也可能同时越界）
while (i1 < str1.length && i2 < str2.length) {
// KMP加速过程中只有三种情况
if (str1[i1] == str2[i2]) {
// 对应位置一样，str1和str2并行向后继续匹配
i1 ++;
i2 ++; // 只有匹配字符相等时i2才会往后走
} else if (i2 == 0) { // next[i2] == -1
// 对应位置不一样，但是str2的匹配指针在0位置，说明i2跳到0位置了，意味着str1前面一整段没有位置能和str2匹配成功
// str1匹配指针向后移一位开始下一段与str2的匹配
i1 ++;
} else {
// 对应位置不一样，且str2的匹配指针不在0位置，此时i2需要跳到最长前缀的下一位，进行下一次比较
// i2跳的这个过程就是KMP常数加速的操作
i2 = next[i2];
}
}
// 如果i2越界，那么说明str1中匹配成功了str2，那么就返回str1中子串的首位
// 如果i1越界，那么说明str1中没有任何一位能够与str2匹配成功，返回-1
return i2 == str2.length ? i1 - i2 : -1;
}
// 统计最大前后缀的本质就是确定str2每一位的最大前缀，预估的最大前缀在没有匹配成功时每一轮都会缩小，直到收缩到0，则表示该位置没有最大前缀
public static int[] getMaximalPrefixAndSuffix(char[] str2) {
// 如果str2中只有一个字符，那么一定是next[0]
if (str2.length == 1) {
return new int[] {-1};
}
// 如果不止一个字符，那么手动给next[0]和next[1]赋值
int[] next = new int[str2.length];
next[0] = -1;
next[1] = 0;
// str2的游标，从str2[2]后开始给next填值
int i = 2;
// prefix是c[i]目前最有可能的最长前缀的后一位的下标
//prefix 跟i-1的位置比较
int prefix = 0;
// 当i越界时表示next已经全部填满
while (i < str2.length) {
if (str2[i - 1] == str2[prefix]) {
// str2[i]的前一位和str2[i]当前最有可能的最长前缀的后一位的下标相同，说明最长前缀还能延长，需要包含str2[prefix]
// 同时当前第i位匹配成功
next[i] = prefix + 1;
i++;
prefix++;
} else if (prefix > 0) {
// 如果str2[i]的前一位和str2[i]当前最有可能的最长前缀的后一位的下标不相同，说明最长前缀必须缩小，prefix需要向前跳
// prefix需要跳到c[prefix]最长前缀的后一位
// 当前第i位匹配失败，下一轮继续匹配第i位
prefix = next[prefix];
} else {
// 当prefix跳到第0位时，还和第i位匹配不上，说明str2[i]没有最长前缀，置为0
// 同时当前第i位匹配成功
next[i] = 0;
i++;
}
}
return next;
}
}
7. KMP重复的子字符串 459. Repeated Substring Pattern 💚
KMP标记next，然后
数组长度为：len。
如果len % (len - (next[len - 1] + 1)) == 0 ，则说明数组的长度正好可以被 (数组长度-最长相等前后缀的长度) 整除 ，说明该字符串有重复的子字符串。
例：
next[len - 1] = 7，next[len - 1] + 1 = 8，8就是此时字符串asdfasdfasdf的最长相同前后缀的长度。
(len - (next[len - 1] + 1)) 也就是： 12(字符串的长度) - 8(最长公共前后缀的长度) = 4， 4正好可以被 12(字符串的长度) 整除，所以说明有重复的子字符串（asdf）。
但是，按照左神的kmp，next数组中记录的是不含元素本身的最大匹配长度，所以，本题中，要在数组中多加一个元素，来判断整个字符串的最大匹配长度，然后用整个字符串的最大匹配长度来取模
class Solution {
public boolean repeatedSubstringPattern(String s) {
char[] ch = s.toCharArray();
int[] next = new int[ch.length + 1];
int len = s.length();
if(ch.length == 1){
next[0] = -1;
}
next[0] = -1;
next[1] = 0;
int i = 2;
int prefix = 0;
while(i <= ch.length){
if(ch[i - 1] == ch[prefix]){
next[i] = prefix + 1;
i++;
prefix++;
}else if(prefix > 0){
prefix = next[prefix];
}else{
next[i] = 0;
i++;
}
}
System.out.print(next[ch.length]);
if(next[len] > 0 && len % (len - next[len]) == 0){
return true;
}
return false;
}
}
