反转字符串
常规的双指针方法即可解决，比较简单
class Solution {
public void reverseString(char[] s) {
int front = 0;
int behind = s.length - 1;
while(front < behind) {
char temp = s[front];
s[front] = s[behind];
s[behind] = temp;
front++;
behind--;
}
}
}反转字符串 II
class Solution {
public String reverseStr(String s, int k) {
char[] c = s.toCharArray();
int sLen = c.length;
// 关键在于每次以2k为区间进行递进
for(int i = 0; i < sLen; i += 2 * k) {
int left = i;
// 确定2k区间内的右边界，与数组长度比较取最小值即可（即判断尾数够不够k个来取决right指针的位置）
int right = Math.min(sLen - 1, i + k - 1);
while(left < right) {
char temp = c[left];
c[left] = c[right];
c[right] = temp;
left++;
right--;
// 方法二：利用异或实现反转(异或运算：一个数异或另一个数两次得到的是其原来的值)
c[left] ^= c[right];
c[right] ^= c[left]; // c[right] = c[left] ^ c[right] ^ c[right] = c[left]
c[left] ^= c[right]; // c[left] = c[left] ^ c[left] ^ c[]
left++;
right--;
}
}
return String.valueOf(c);
}
}替换空格
Java可以利用StringBuilder：
class Solution {
public String replaceSpace(String s) {
StringBuilder sb = new StringBuilder();
for(int i = 0; i < s.length(); i++) {
if(s.charAt(i) == ' ') {
sb.append("%20");
} else{
sb.append(s.charAt(i));
}
}
return sb.toString();
}
}C语言可以利用双指针方法：
char* replaceSpace(char* s){
int len = strlen(s);
// 计算空格的数量
int trimCount = 0;
for(int i = 0; i < len; i++) {
if(s[i] == ' '){
trimCount++;
}
}
// 新数组长度
int newLen = len + trimCount * 2;
// 数组扩容，+1的原因是在C语言中，把一个字符串存入一个数组时，也把结束符 '\0'存入数组，并以此作为该字符串是否结束的标志。
char *newStr = malloc(sizeof(char) * newLen + 1);
// 双指针。指针i指向原长度最后一个位置，指针j指向扩容后数组的最后一个位置
for(int i = len - 1, j = newLen - 1; i >= 0; i--, j--) {
// 不是空格直接将原数组元素移动
if(s[i] != ' ') {
newStr[j] = s[i];
} else {
// 空格即将内容替换（因为是从后往前，故替换内容逆着来）
newStr[j--] = '0';
newStr[j--] = '2';
newStr[j] = '%';
}
}
// 最后一个位置放置结束符
newStr[newLen] = '\0';
return newStr;
}反转字符串中的单词
Java版本：
public class ReverseWordsInStr {
public static void main(String[] args) {
String s = "a good example";
StringBuilder sb = removeSpace(s);
reverseString(sb, 0, sb.length() - 1);
reverseEachWords(sb);
System.out.println(sb.toString());
}
public static StringBuilder removeSpace(String str) {
StringBuilder sb = new StringBuilder();
int start = 0;
int end = str.length() - 1;
// 去除头尾的空格
while (str.charAt(start) == ' ') start++;
while (str.charAt(end) == ' ') end--;
// 去除中间多余的空格
while (start <= end) {
char c = str.charAt(start);
if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
sb.append(c);
}
start++;
}
return sb;
}
public static void reverseString(StringBuilder sb, int start, int end) {
while (start < end) {
char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, temp);
start++;
end--;
}
}
public static void reverseEachWords(StringBuilder sb) {
int start = 0;
int end = 1;
int sbLen = sb.length();
while (start < sbLen) {
// 不为空格表明还不是一个完整的单词
while (end < sbLen && sb.charAt(end) != ' ') {
end++;
}
// 完整的单词，开始单词反转
reverseString(sb, start, end - 1);
// 寻找下一个单词
start = end + 1;
end = start + 1;
}
}
}C版本：
// 待写左旋转字符串
Java版本（利用了额外的空间）：
class Solution {
public String reverseLeftWords(String s, int n) {
int len = s.length();
char[] sChar = s.toCharArray();
char[] temp = new char[n];
for (int i = 0; i < n; i++) {
temp[i] = sChar[i];
}
int j;
for (j = n; j < len; j++) {
sChar[j - n] = sChar[j];
}
for(int k = 0; k < temp.length; k++) {
sChar[j - n] = temp[k];
j++;
}
return String.valueOf(sChar);
}
}不利用额外空间，原地操作，具体操作步骤：
- 反转区间为前n的子串
- 反转区间为n到末尾的子串
- 反转整个字符串
public static String reverseLeftWords(String s, int n) {
char[] chars = s.toCharArray();
StringBuilder sb = new StringBuilder();
sb.append(chars);
// 反转前n位子串
reverseString(sb, 0, n - 1);
// 反转从n到末尾的子串
reverseString(sb, n, chars.length - 1);
// 整个字符串反转
reverseString(sb, 0, chars.length - 1);
return sb.toString();
}
public static void reverseString(StringBuilder sb, int start, int end) {
while (start < end) {
char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, temp);
start++;
end--;
}
}找出字符串中第一个匹配项的下标
典型的KMP算法
KMP算法学习与回顾：
几个概念：
前缀：包含首位字符但不包含末位字符的子串
后缀：包含末位字符但不包含首位字符的子串
next数组定义：当主串与模式串的某一位字符不匹配时，模式串要回退的位置
next 数组存放的是当前长度下的 最长相同前后缀 的长度（不同的定义代码实现方法略有不同的，但基本原理是一致的）
kmp求next数组代码：
public static void getNext(String needle, int[] next) {
int left = 0; // 上图的j
int right = 2; // 上图的i
// 只与模式串有关
while (right < needle.length()) {
// 模式串前后字符对比
while (left > 0 && needle.charAt(right) != needle.charAt(left + 1)) {
left = next[left];
}
// 有相同的前后缀，更新
if(needle.charAt(right) == needle.charAt(left + 1)) {
left++;
next[right] = left;
}
right++;
}
}最终完整代码：
class Solution {
public int strStr(String haystack, String needle) {
String newHaystack = " " + haystack;
String newNeedle = " " + needle;
int len1 = newHaystack.length();
int len2 = newNeedle.length();
// 分配next数组空间(给多一个空间，令下标从1开始)
int[] next = new int[len2];
// 更新next数组内容
getNext(newNeedle, next);
// 遍历模式串指针
int j = 0;
// 遍历主串指针
int i = 1;
while (i < len1) {
// 主串与模式串比较，不匹配的模式串指针回退
while (j > 0 && newHaystack.charAt(i) != newNeedle.charAt(j + 1)) {
j = next[j];
}
// 匹配就往后移
if (newHaystack.charAt(i) == newNeedle.charAt(j + 1)) {
j++;
}
// 若模式串遍历完毕，则证明寻找结束
if(j == len2 - 1) {
// 最终返回第一个匹配的字符下标
return i - len2 + 1;
}
i++;
}
// 没有符合的返回-1
return -1;
}
public static void getNext(String needle, int[] next) {
int left = 0;
int right = 2;
while (right < needle.length()) {
while (left > 0 && needle.charAt(right) != needle.charAt(left + 1)) {
left = next[left];
}
if(needle.charAt(right) == needle.charAt(left + 1)) {
left++;
next[right] = left;
}
right++;
}
}
}重复的子字符串
移动匹配法
原字符串S，两个S拼接在一起组成SS，去掉首尾字符后仍包含原S，则表明是由重复的字符串组成的
public static boolean repeatedSubstringPattern(String s) {
String ss = s + s;
// substring(beginIndex, endIndex)是左闭右开的
String subString = ss.substring(1, ss.length() - 1);
if (subString.contains(s)) {
return true;
}
return false;
}- KMP法(难以理解…)
class Solution {
public boolean repeatedSubstringPattern(String s) {
// 添加多一个空格(哨兵)，令下标从1开始
String ss = " " + s;
int len = ss.length();
int[] next = new int[len];
getNext(ss, next);
// next[len - 1] 代表next数组中最后的值，判断是否是重复的字符串 ？？？
if (next[len - 1] > 0 && s.length() % (s.length() - next[len - 1]) == 0) return true;
return false;
}
public static void getNext(String neddle, int[] next){
int left = 0;
int right = 2;
while (right < neddle.length()) {
while (left > 0 && neddle.charAt(left + 1) != neddle.charAt(right)) {
left = next[left];
}
if(neddle.charAt(left + 1) == neddle.charAt(right)) {
left++;
next[right]= left;
}
right++;
}
}
}
