● 151.翻转字符串里的单词
● 卡码网：55.右旋转字符串
● 28. 实现 strStr()
● 459.重复的子字符串
● 字符串总结
● 双指针回顾
详细布置
151.翻转字符串里的单词
建议：这道题目基本把 刚刚做过的字符串操作 都覆盖了，不过就算知道解题思路，本题代码并不容易写，要多练一练。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0151.%E7%BF%BB%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%87%8C%E7%9A%84%E5%8D%95%E8%AF%8D.html
class Solution {
public String reverseWords(String s) {
// System.out.println("ReverseWords.reverseWords2() called with: s = [" + s + "]");
// 1.去除首尾以及中间多余空格
StringBuilder sb = removeSpace(s);
// 2.反转整个字符串
reverseString(sb, 0, sb.length() - 1);
// 3.反转各个单词
reverseEachWord(sb);
return sb.toString();
}
private StringBuilder removeSpace(String s) {
// System.out.println("ReverseWords.removeSpace() called with: s = [" + s + "]");
int start = 0;
int end = s.length() - 1;
while (s.charAt(start) == ' ') start++;
while (s.charAt(end) == ' ') end--;
StringBuilder sb = new StringBuilder();
while (start <= end) {
char c = s.charAt(start);
if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
sb.append(c);
}
start++;
}
// System.out.println("ReverseWords.removeSpace returned: sb = [" + sb + "]");
return sb;
}
/**
* 反转字符串指定区间[start, end]的字符
*/
public void reverseString(StringBuilder sb, int start, int end) {
// System.out.println("ReverseWords.reverseString() called with: sb = [" + sb + "], start = [" + start + "], end = [" + end + "]");
while (start < end) {
char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, temp);
start++;
end--;
}
// System.out.println("ReverseWords.reverseString returned: sb = [" + sb + "]");
}
private void reverseEachWord(StringBuilder sb) {
int start = 0;
int end = 1;
int n = sb.length();
while (start < n) {
while (end < n && sb.charAt(end) != ' ') {
end++;
}
reverseString(sb, start, end - 1);
start = end + 1;
end = start + 1;
}
}
}
卡码网：55.右旋转字符串
建议：题解中的解法如果没接触过的话，应该会想不到
题目链接/文章讲解：
https://programmercarl.com/kama55.%E5%8F%B3%E6%97%8B%E5%AD%97%E7%AC%A6%E4%B8%B2.html
import java.util.*;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int k = Integer.parseInt(sc.nextLine());
String s = sc.nextLine();
String r = s.substring(s.length()-k,s.length()) + s.substring(0, s.length()-k);
System.out.println(r);
}
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = Integer.parseInt(in.nextLine());
String s = in.nextLine();
int len = s.length(); //获取字符串长度
char[] chars = s.toCharArray();
reverseString(chars, 0, len - 1); //反转整个字符串
reverseString(chars, 0, n - 1); //反转前一段字符串，此时的字符串首尾尾是0,n - 1
reverseString(chars, n, len - 1); //反转后一段字符串，此时的字符串首尾尾是n,len - 1
System.out.println(chars);
}
public static void reverseString(char[] ch, int start, int end) {
//异或法反转字符串，参照题目 344.反转字符串的解释
while (start < end) {
ch[start] ^= ch[end];
ch[end] ^= ch[start];
ch[start] ^= ch[end];
start++;
end--;
}
}
}
28. 实现 strStr() （本题可以跳过）
因为KMP算法很难，大家别奢求 一次就把kmp全理解了，大家刚学KMP一定会有各种各样的疑问，先留着，别期望立刻啃明白，第一遍了解大概思路，二刷的时候，再看KMP会 好懂很多。
或者说大家可以放弃一刷可以不看KMP，今天来回顾一下之前的算法题目就可以。
因为大家 算法能力还没到，细扣 很难的算法，会把自己绕进去，就算别人给解释，只会激发出更多的问题和疑惑。所以大家先了解大体过程，知道这么回事， 等自己有 算法基础和思维了，在看多看几遍视频，慢慢就理解了。
class Solution {
public int strStr(String haystack, String needle) {
int[] next = new int[needle.length()];
getNext(next, needle);
int i = 0, j = 0;
int m = haystack.length();
int n = needle.length();
while(i < m && j < n){
if (haystack.charAt(i) == needle.charAt(j)){
i ++;
j ++;
}else if(j == 0){
i++;//第一个字母就不匹配
}else{
j = next[j-1];
}
}
if (j < n){
return -1;
}else{
return i - n;
}
}
private void getNext(int[] next, String s){
//初始化
next[0] = 0;
int j = 0;//前缀末尾
for(int i = 1; i < s.length(); 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;
}
}
}
题目链接/文章讲解/视频讲解：https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html
459.重复的子字符串 （本题可以跳过）
本题算是KMP算法的一个应用，不过 对KMP了解不够熟练的话，理解本题就难很多。
我的建议是 KMP和本题，一刷的时候 ，可以适当放过，了解怎么回事就行，二刷的时候再来硬啃
题目链接/文章讲解/视频讲解：https://programmercarl.com/0459.%E9%87%8D%E5%A4%8D%E7%9A%84%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2.html
class Solution {
public boolean repeatedSubstringPattern(String s) {
int[] next = new int[s.length()];
getNext(next, s);
int len = s.length();
if(len % (len - next[len - 1]) == 0 && next[len - 1] > 0){
return true;
}else{
return false;
}
}
private void getNext(int[] next, String s){
int j = 0;//前缀末尾
next[j] = 0;
for(int i = 1; i < s.length(); 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;
}
}
}
字符串总结
比较简单，大家读一遍就行
题目链接/文章讲解：https://programmercarl.com/%E5%AD%97%E7%AC%A6%E4%B8%B2%E6%80%BB%E7%BB%93.html
双指针回顾
此时我们已经做过10道双指针的题目了，来一起回顾一下，大家自己也总结一下双指针的心得
文章讲解：https://programmercarl.com/%E5%8F%8C%E6%8C%87%E9%92%88%E6%80%BB%E7%BB%93.html
