字符串
344.反转字符串
344. 反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须**原地修改输入数组**、使用 O(1) 的额外空间解决这一问题。
思路: 双指针
代码:
class Solution {public void reverseString(char[] s) {// 双指针int l = 0,r = s.length - 1;while(l < r) {char t = s[l];s[l] = s[r];s[r] = t;l++;r--;}}
}
- 时间复杂度: O(n)
- 空间复杂度: O(1)
541.反转字符串 II
541. 反转字符串 II
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
- 如果剩余字符少于
k个，则将剩余字符全部反转。 - 如果剩余字符小于
2k但大于或等于k个，则反转前k个字符，其余字符保持原样。
思路: 步长为2k进行循环, 每次循环内对: 2k的前k个 或 不足2k的剩余所有, 进行反转
代码:
class Solution {public String reverseStr(String s, int k) {char[] str = s.toCharArray();// 1. 2k 2k 循环遍历for(int i = 0;i < str.length;i += 2*k) {// 2. 找2k的前k个 或 不足2k的剩余所有 进行反转int start = i;int end = Math.min(str.length - 1,start + k - 1);while(start < end) {char t = str[start];str[start] = str[end];str[end] = t;start++;end--;}}// 3. 反转return new String(str);}
}
54.替换数字
54.替换数字（第八期模拟笔试）
思路: 双指针, 先计算新数组的大小, 将原数组复制到新数组后, 从后往前开始替换
代码:
import java.util.*;
public class Main{public static void main (String[] args) {// 1. 输入Scanner sc = new Scanner(System.in);String s = sc.next();char[] oStr = s.toCharArray();// 2. 计算新数组的长度int olen = oStr.length;int nlen = olen;for(int i = 0;i < olen;i++) {if(oStr[i] >= '0' && oStr[i] <= '9') {nlen += 5;// number共6位, 覆盖原来字母一位, 每次还需再加5位}}// 3. 将原数组的内容copy到新数组char[] nStr = new char[nlen];for(int i = 0;i < olen;i++) {nStr[i] = oStr[i];}// 4. 对新数组进行处理for(int i = olen - 1,j = nlen - 1;i >= 0;i--) {if(nStr[i] >= '0' && nStr[i] <= '9') {nStr[j--] = 'r';nStr[j--] = 'e';nStr[j--] = 'b';nStr[j--] = 'm';nStr[j--] = 'u';nStr[j--] = 'n';}else {nStr[j--] = nStr[i]; }}// 5. 打印结果System.out.print(nStr); }
}
法二: 不将原数组的内容copy到新数组
import java.util.*;
public class Main {public static void main (String[] args) {Scanner sc = new Scanner(System.in);String str = sc.next();char[] s = str.toCharArray();// 1. 计算新数组长度int len = s.length;int newLen = len;for(int i = 0;i < len;i++) {if(s[i] >= '0' && s[i] <= '9') {newLen+=5;}}// 2. 替换char[] c = new char[newLen];for(int i = len - 1,j = newLen - 1;i >= 0;i--) {if(s[i] >= '0' && s[i] <= '9') {c[j--] = 'r';c[j--] = 'e';c[j--] = 'b';c[j--] = 'm';c[j--] = 'u';c[j--] = 'n';}else {c[j--] = s[i];}}// 3. 输出System.out.print(c);}
}
151.反转字符串中的单词
反转字符串中的单词
思路: 双指针, 先去掉多余空格, 再反转整个字符串, 最后反转每个单词
代码:
class Solution {public String reverseWords(String s) {char[] str = s.toCharArray();// 1. 去除 首尾 以及 中间 多余空格str = removeSpace(str);// 2. 将整个字符串反转reverse(str,0,str.length - 1);// 3. 将每个单词反转reverseEachWords(str);return new String(str);}// 1. 去除 首尾 以及 中间 多余空格public static char[] removeSpace(char[] str) {int slow = 0;// 1. 去空格for(int fast = 0;fast < str.length;fast++) {// 该if 每次操作一个单词if(str[fast] != ' ') {// fast所指的是字母时开始移动if(slow != 0) {// 处理是否加空格str[slow++] = ' ';}// 加单词, slow每次增加一个单词的长度while(fast < str.length && str[fast] != ' ') {// 顺序不能换, 否则下标越界str[slow++] = str[fast++];}}}// 2. 返回有效数组return Arrays.copyOfRange(str,0,slow);// 0 ~ (slow - 1}// 2. 将整个字符串反转public static void reverse(char[] str,int left,int right) {while(left < right) {str[left] ^= str[right];str[right] ^= str[left];str[left] ^= str[right];// 注意两个指针的变换不同left++;right--;}}// 3. 将每个单词反转public static void reverseEachWords(char[] str) {for(int start = 0,end = 0;end <= str.length;end++) { // end = str.length 便于与 str[end] = ' ' 统一操作if(end == str.length || str[end] == ' ') {// 走到一个单词尽头reverse(str,start,end - 1);// 反转该单词start = end + 1;// 更新start位置}}}}
55.右旋字符串（第八期模拟笔试）
右旋字符串（第八期模拟笔试）
题目描述
字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。
例如，对于输入字符串 “abcdefg” 和整数 2，函数应该将其转换为 “fgabcde”。
输入描述
输入共包含两行，第一行为一个正整数 k，代表右旋转的位数。第二行为字符串 s，代表需要旋转的字符串。
输出描述
输出共一行，为进行了右旋转操作后的字符串。
思路: 反转字符串, 先反转整体, 再依次翻转子串
代码:
import java.util.Scanner;
public class Main{public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = Integer.parseInt(sc.next());String s = sc.next();char[] str = s.toCharArray();int len = str.length;// 1. 整体翻转reverse(str,0,len - 1);// 2. 前半部分翻转reverse(str,0,n - 1);// 3. 后半部分翻转reverse(str,n,len - 1);System.out.print(str);}public static void reverse(char[] str,int left,int right) {while(left < right) {str[left] ^= str[right];str[right] ^= str[left];str[left] ^= str[right];left++;right--;}}
}
28.找出字符串中第一个匹配项的下标
28. 找出字符串中第一个匹配项的下标
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
提示：
1 <= haystack.length, needle.length <= 104haystack和needle仅由小写英文字符组成
思路: kmp
代码:
class Solution {public int strStr(String haystack, String needle) {char[] s1 = haystack.toCharArray();char[] s2 = needle.toCharArray();int m = s1.length,n = s2.length;// 1. 计算next数组int[] next = nextArray(s2,n);// 2. 匹配子串int x = 0,y = 0;// x,y分别指向s1,s2当前操作的位置while(x < m && y < n) {if(s1[x] == s2[y]) {// 两字符串当前位置相等x++;// 继续往后匹配y++;}else if(y > 0) {// 两字符串当前位置不相等, s2要匹配的不是第一个字母y = next[y];// y前退}else {// 两字符串当前位置不相等, s2要匹配的是第一个字母x++;// s1往后走}}return y == n ? x - y : -1;// s2是否完全匹配}// 1. 计算next数组public static int[] nextArray(char[] s2,int len) {// 1.1 对0 1位置的特殊判断if(len == 1) return new int[] {-1};int[] next = new int[len];next[0] = -1;next[1] = 0;// 1.2 完善next数组int cnt = 0,i = 2;while(i < len) {if(s2[i - 1] == s2[cnt]) {// 当前位置和要比对的位置相同next[i++] = ++cnt;// 前缀和累加}else if(cnt > 0) {cnt = next[cnt];// 当前位置和要比对的位置不相同, 能往前退就往前退}else {// 当前位置和要比对的位置不相同, 不能往前退, 则next[i] = 0next[i++] = 0;}}// 1.3 返回return next;}
}
注: 不能用for, 因为每次判断i不一定要往后走
459.重复的子字符串
459. 重复的子字符串
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s = “abab”
输出: true
解释: 可由子串 “ab” 重复两次构成。
提示：
1 <= s.length <= 104s由小写英文字母组成
思路: kmp求next数组, 求到len + 1的位置, 求出整个串的最长公共前后缀, 原串减去公共前后缀剩下的就是最小重复子字符串
代码随想录讲解
代码:
class Solution {public boolean repeatedSubstringPattern(String s) {// 1. 计算next数组(要将整个串的最长公共前后缀计算出来)char[] cs = s.toCharArray();int len = cs.length;int[] next = getNext(cs,len);// 2. 判断原字符串的长度是否是 公共前后缀剩余串(最小子串)的整数倍if(next[len] > 0 && len % (len - next[len]) == 0) {// 要判断next[len] > 0// 3. 返回return true;}return false;}// 1. 计算next数组(要将整个串的最长公共前后缀计算出来)public int[] getNext(char[] cs,int len) {// 1. 对0 1位置的特殊判断if(len == 1) {return new int[] {-1,0};}// 2. 补充next数组int i = 2,cnt = 0;// i代表当前处理的位置(后缀),cnt前缀的位置int[] next = new int[len + 1];// 要计算整个数组的最长公共前后缀next[0] = -1;next[1] = 0;while(i <= len) {if(cs[i - 1] == cs[cnt]) {next[i++] = ++cnt;}else if (cnt > 0) {cnt = next[cnt];}else {next[i++] = cnt;}}// 3. 返回return next;}
}
