代码随想录刷题记录 - 字符串
代码随想录刷题记录 - 字符串
1. 反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
我的答案
使用双指针，一前一末，向中间逼近
class Solution {
public void reverseString(char[] s) {
for(int l = 0, r = s.length-1; l<r; l++, r--){
char temp = s[l];
s[l] = s[r];
s[r] = temp;
}
}
}
2. 反转字符串II
给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
示例:
输入: s = "abcdefg", k = 2
输出: "bacdfeg"
我的答案
结合题目1使用双指针，使用StringBuilder，分为三种情况处理：
一般情况：以2k为区间
末尾情况：1. < k；2. >= k&<2k
然后确定两个指针的位置，向中间逼近
// 我的答案
class Solution {
public String reverseStr(String s, int k) {
StringBuilder sb = new StringBuilder(s);
int total = sb.length();
int i = 1;
while(total > 0){
int gap = 0;
if(total < k){
reverse(sb, sb.length()-total, sb.length()-1);
break;
}else if(total >= k && total <2*k){
reverse(sb, sb.length()-total, sb.length()-total+k-1);
break;
}else{
int right = i*2*k - 1;
int left = right - 2*k + 1;
int mid = (left+right)/2;
reverse(sb, left, mid);
}
total -= 2*k;
i++;
}
String sNew = sb.toString();
return sNew;
}
// 题目1的字符串反转
public void reverse(StringBuilder sb, int left, int mid){
while(left < mid){
char temp = sb.charAt(mid);
sb.setCharAt(mid, sb.charAt(left));
sb.setCharAt(left, temp);
left++;
mid--;
}
}
}
官方解答
for循环以 2k 为单位移动start，在确定第二个 (第三个) 指针
class Solution {
public String reverseStr(String s, int k) {
StringBuffer res = new StringBuffer();
int length = s.length();
int start = 0;
while (start < length) {
// 找到k处和2k处
StringBuffer temp = new StringBuffer();
// 与length进行判断，如果大于length了，那就将其置为length
int firstK = (start + k > length) ? length : start + k;
int secondK = (start + (2 * k) > length) ? length : start + (2 * k);
//无论start所处位置，至少会反转一次
temp.append(s.substring(start, firstK));
res.append(temp.reverse());
// 如果firstK到secondK之间有元素，这些元素直接放入res里即可。
if (firstK < secondK) { //此时剩余长度一定大于k。
res.append(s.substring(firstK, secondK));
}
start += (2 * k);
}
return res.toString();
}
}
异或实现交换
异或运算性质
- 自反性: 对于任意数
a，有a ^ a = 0。- 结合性: 对于任意数
a, b, c，有(a ^ b) ^ c = a ^ (b ^ c)。- 交换性: 对于任意数
a与b，有a ^ b = b ^ a
ch[start] = a;
ch[end] = b;
ch[start] ^= ch[end]; // a = a ^ b
ch[end] ^= ch[start]; // b = b ^ (a ^ b) = a
ch[start] ^= ch[end]; // a = (a ^ b) ^ a = b
/* 不能用于String */
3. 替换数字
给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。
例如，对于输入字符串 "a1b2c3"，函数应该将其转换为 "anumberbnumbercnumber"。
我的答案
'a～z'=97~122
'A~Z'=65 ~ 90
'0~ 9'=48 ~ 57
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner ms = new Scanner(System.in);
while(ms.hasNext()){
String s = ms.nextLine();
char[] ch = s.toCharArray();
StringBuilder sb = new StringBuilder();
for(int i = 0; i<ch.length; i++){
if(ch[i] >= 48 && ch[i] <= 57){ // '0' <= ch[i] && ch[i] <= '9'
sb.append("number");
}else{
sb.append(ch[i]);
}
}
System.out.println(sb.toString());
}
}
}
官方题解
思路：从后向前填充
先预先给数组扩容待填充后的大小，然后在从后向前进行操作
从前向后填充就是O(n^2)的算法了，因为每次添加元素都要将添加元素之后的所有元素整体向后移动
import java.util.Scanner;
public class Main {
public static String replaceNumber(String s) {
int count = 0; // 统计数字的个数
int sOldSize = s.length();
for (int i = 0; i < s.length(); i++) {
if(Character.isDigit(s.charAt(i))){
count++;
}
}
// 扩充字符串s的大小，也就是每个空格替换成"number"之后的大小
char[] newS = new char[s.length() + count * 5];
int sNewSize = newS.length;
// 将旧字符串的内容填入新数组
System.arraycopy(s.toCharArray(), 0, newS, 0, sOldSize);
// 从后先前将空格替换为"number"
for (int i = sNewSize - 1, j = sOldSize - 1; j < i; j--, i--) {
if (!Character.isDigit(newS[j])) {
newS[i] = newS[j];
} else {
newS[i] = 'r';
newS[i - 1] = 'e';
newS[i - 2] = 'b';
newS[i - 3] = 'm';
newS[i - 4] = 'u';
newS[i - 5] = 'n';
i -= 5;
}
}
return new String(newS); // *
};
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.next();
System.out.println(replaceNumber(s));
scanner.close();
}
}
4. 翻转字符串里的单词
给定一个字符串，逐个翻转字符串中的每个单词。
示例 1：
输入: "the sky is blue"
输出: "blue is sky the"
过程中遇到的问题
-
空格只在两个单词之间，for循环没法按格式输出
答：用
flag2(=true: 之前输出过单词) 完成输出逻辑：输出一个单词后，如果还要输出下一个单词，就先输出" " -
将单词后的第一个空格作为单词结束的标志，然后输出，如果单词后没有空格，就没有办法完成判定
答：在for循环结束后加条件判断，如果
flag1= true (: 有检测到的单词未输出)，最后输出一次
我的答案
class Solution {
public String reverseWords(String s) {
char[] ch = s.toCharArray();
char[] chNew = new char[ch.length];
int index = 0; // 指向一个单词的首字母
boolean flag1 = false; // 有无新的单词被检测到
boolean flag2 = false; // 前面有没有输出的单词
String str = "";
for(int i = ch.length-1; i>=0; i--){
if(!Character.isWhitespace(ch[i])){
flag1 = true;
chNew[index++] = ch[i];
}else if(flag1){
if(flag2){
str += " ";
}
str += getString(chNew, index-1);
index = 0;
flag1 = false;
flag2 = true; // 下一次要输单词前先输入空格
}
}
if(flag1){
if(flag2){
str += " ";
}
str += getString(chNew, index-1);
}
return str;
}
public String getString(char[] arr, int index){
String str = "";
for(int i = index; i>=0; i--){
str += arr[i];
}
return str;
}
}
官方解答1
解题思路如下：
- 移除多余空格
- 将整个字符串反转
- 将每个单词反转
去除多余空格
/* 先去除首尾空格，对于中间多余的空格，如果一个字符自己不是空格，它的下一位也不是空格，就加入sb中 */
private StringBuilder removeSpace(String 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++;
}
return 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;
}
}
官方解答2
//解法二：创建新字符数组填充。时间复杂度O(n)
class Solution {
public String reverseWords(String s) {
//源字符数组
char[] initialArr = s.toCharArray();
//新字符数组
char[] newArr = new char[initialArr.length+1];//下面循环添加"单词 "，最终末尾的空格不会返回
int newArrPos = 0;
//i来进行整体对源字符数组从后往前遍历
int i = initialArr.length-1;
while(i>=0){
while(i>=0 && initialArr[i] == ' '){i--;} //跳过空格
//此时i位置是边界或!=空格，先记录当前索引，之后的while用来确定单词的首字母的位置
int right = i;
while(i>=0 && initialArr[i] != ' '){i--;}
//指定区间单词取出(由于i为首字母的前一位，所以这里+1,)，取出的每组末尾都带有一个空格
for (int j = i+1; j <= right; j++) {
newArr[newArrPos++] = initialArr[j];
if(j == right){
newArr[newArrPos++] = ' ';//空格
}
}
}
//若是原始字符串没有单词，直接返回空字符串；若是有单词，返回0-末尾空格索引前范围的字符数组(转成String返回)
if(newArrPos == 0){
return "";
}else{
return new String(newArr,0,newArrPos-1);
}
}
}
5. 右旋字符串
字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。
例如，对于输入字符串 "abcdefg" 和整数 2，函数应该将其转换为 "fgabcde"。
我的答案
使用substring
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner ms = new Scanner(System.in);
int n = Integer.parseInt(ms.next());
String s = ms.nextLine();
int end = s.length();
int start = end - n;
String s1 = s.substring(0, start);
String s2 = s.substring(start, end);
System.out.println(s2+s1);
}
}
官方解答
整体倒叙输出 --> 子串倒叙输出
6. 找出字符串中第一个匹配项的下标
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1: 输入: haystack = "hello", needle = "ll" 输出: 2
遇到的问题
- 没有考虑模式串比文本串长的问题
答：加入 if 判断，模式串比文本串长 就直接 return -1
- 当第一个字母匹配时，假设可以找到，然后匹配第二个字母，不一致则判断不匹配；但当模式串和文本串最后一个字母匹配上时，没有下一个字母了，假设的flag = true 就被保存下来了
答：不使用假设，for循环后，如果模式串的指针在字符串最后，就代表匹配成功
我的答案
/* 暴力匹配 */
class Solution {
public int strStr(String haystack, String needle) {
boolean flag = false;
if(haystack.length() < needle.length())
return -1;
for(int a = 0, b = 0; a<haystack.length(); a++){
if(haystack.charAt(a) == needle.charAt(b)){
for(int i = a; b<needle.length() && i<haystack.length(); i++, b++){
if(haystack.charAt(i) != needle.charAt(b)){
break;
}
}
}
if(b == needle.length()){
return a;
}else{
b = 0;
}
}
return -1;
}
}
KMP（应用在字符串匹配上）
主要思想：当出现字符串不匹配时，利用之前已经匹配的文本内容，避免从头做匹配
- 前缀表 - next[]数组
前缀：不包含最后一个字符 的所有 以第一个字符开头 的 连续子串
后缀：不包含第一个字符 的所有 以最后一个字符结尾 的 连续子串
最长相等前后缀：e.g. a - 0；aa - 1；aaa - 2
前缀表记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面重新匹配就可以了
next[i] = n 表示 i 之前（包括i）的模式串中，最长相等前后缀为 n，意味着 i之前（包括i）的模式串 中 前 n 个字符等于后 n 个字符
- **代码实现 **
next数组 存储子串的 最长相等前后缀
找到的不匹配的位置时，要看它的前一个字符的next[]的值是多少
next[]的值(最长相等前后缀)做下标时，指向前缀子串后一个字符
public class Test{
public static void main(String[] args){
Tool t = new Tool();
System.out.println(t.KML("butsad", "sad"));
}
}
class Tool{
public int KML(String haystack, String needle){
int[] next = computeNext(needle);
char[] chNeedle = needle.toCharArray();
char[] chHaystack = haystack.toCharArray();
int i = 0;
int j = 0;
while(i<chHaystack.length && j<chNeedle.length){
if(chHaystack[i] == chNeedle[j]){
i++;
j++;
}else{
if(j == 0){
i++;
}else
j = next[j-1];
}
}
if(j == chNeedle.length){
return i - j; // i 最后多加了一下
}else{
return -1;
}
}
public int[] computeNext(String needle){
int[] next = new int[needle.length()];
char[] ch = needle.toCharArray();
next[0] = 0;
// 每次循环往next中填入一个元素，一共循环 needle.length - 1 次
for(int i = 0, j = 1; i<next.length && j<next.length;){ // i是前缀的末尾, j是后缀的末尾
if(ch[i] == ch[j]){
next[j++] = ++i; // i+1 就是 最长相等前后缀
}else{
if(i != 0){
i = next[i-1]; // 最长相等前后缀 做下标就指向前缀子串后一个字符
}else{
next[j++] = 0;
}
}
}
return next;
}
}
7. 重复的子字符串
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1:
- 输入: "abab"
- 输出: True
- 解释: 可由子字符串 "ab" 重复两次构成。
遇到的问题
- 检测到不一致就 return false; 但如"aba"(false)，程序认为ab为子串，后面出现a，没有不一致，且判断到了最后一个字符，于是返回true
答：如果循环结束后，子串和字符串的指针都指向末尾，就返回true
- 子串和字符串的指针都指向末尾，末尾字符不相等，但仍然会返回true
答：条件判断加入 判断 子串和字符串的末尾字符是否相等（KML中指针指向 数组长度+1 判断为 true）
我的答案
/* 暴力匹配 */
class Solution {
public boolean repeatedSubstringPattern(String s) {
char[] ch = s.toCharArray();
for(int i = 0; i<ch.length/2; i++){
int j = i+1;
int m = 0;
while(j<ch.length){
if(m > i) m = 0;
if(ch[m++] != ch[j++]){
break;
}
}
if(j == ch.length && m == i+1 && ch[i] == ch[ch.length-1]) return true;
}
return false;
}
}
移动匹配
思路：如果有一个字符串s，在 s + s 拼接后， 不算首尾字符，如果能凑成s字符串，说明s 一定是重复子串组成
class Solution {
public boolean repeatedSubstringPattern(String s) {
String str = s + s;
return KML(s, str);
}
public boolean KML(String mode, String str){
int[] next = next(mode);
char[] chMode = mode.toCharArray();
char[] chStr = str.toCharArray();
int i = 1; // 去首
int j = 0; // 模式串下标
while(i<str.length()-1){ // 去尾
if(chStr[i] == chMode[j]){
i++;
j++;
if(j == chMode.length) return true;
}else{
if(j == 0){
i++;
}else j = next[j-1];
}
}
return false;
}
public int[] next(String mode){
int[] next = new int[mode.length()];
char[] ch = mode.toCharArray();
next[0] = 0;
int i = 0; // 最长相等前后缀
int j = 1; // next[]下标
while(j<next.length){
if(ch[i] == ch[j]){
next[j++] = ++i;
}else{
if(i == 0){
next[j++] = 0;
}else i = next[i-1];
}
}
return next;
}
}
最长前后缀
理论：如果一个字符串 由重复子串组成 且 存在最长相等前后缀，最长相等前后缀不包含的子串就是最小重复子串
思路：if(next[len-1] != 0 && len%(len - next[len-1]) == 0) return true;
理解：len%(len - next[len-1]) == 0 表示 最长相等前后缀包含的子串 是由n份 最长相等前后缀不包含的子串(s) 组成的，最长相等前后缀又分别占据一前一后两头，所以，如图，全部相等
class Solution {
public boolean repeatedSubstringPattern(String s) {
int[] next = next(s);
int len = s.length();
if(next[len-1] != 0 && len%(len-next[len-1]) == 0) return true;
else return false;
}
public int[] next(String mode){
int[] next = new int[mode.length()];
char[] ch = mode.toCharArray();
next[0] = 0;
int i = 0; // 最长相等前后缀
int j = 1; // next[]下标
while(j<next.length){
if(ch[i] == ch[j]){
next[j++] = ++i;
}else{
if(i == 0){
next[j++] = 0;
}else i = next[i-1];
}
}
return next;
}
}