【算法训练营Day07】字符串part1

反转字符串

题目链接：344. 反转字符串

双指针法，两个指针的元素直接调转即可

class Solution {public void reverseString(char[] s) {int head = 0;int end = s.length - 1;while(head < end) {char temp  = s[head];s[head++] = s[end];s[end--] = temp;}}
}

反转字符串II

题目链接：541. 反转字符串 II

双指针法代码逻辑：

• 初始化head、end双指针，两指针相距2k，作为操作区间
• 在操作区间中反转前k个字符
• 移动指针，head移到end，end往后移2k，继续上述操作
• 直到end指针超出界限
• 此时将多余部分分情况反转
  • 少于k全部反转
  • 大于k，反转前k个

代码如下：

class Solution {public String reverseStr(String s, int k) {int head = 0;int end = head + 2 * k;char[] charArray = s.toCharArray();while(end < s.length()) {reverseString(charArray,head,head + k - 1);head = end;end += 2 * k; }int rest = s.length() - head;if(rest >= k) {reverseString(charArray,head,head + k - 1);} else {reverseString(charArray,head,s.length() -1);}return new String(charArray);}public void reverseString(char[] s,int start,int end) {while(start < end) {char temp  = s[start];s[start++] = s[end];s[end--] = temp;}}
}

替换数字

题目链接：54. 替换数字

解题逻辑直接遍历使用StringBuilder拼接即可：

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String input = scanner.nextLine(); // 读取一整行字符串Set<Character> nums = new HashSet<>(Arrays.asList('1','2','3','4','5','6','7','8','9','0'));StringBuilder result = new StringBuilder();for(int i = 0;i < input.length();i++) {if (nums.contains(input.charAt(i)))  result.append("number");else result.append(input.charAt(i));}System.out.println(result);scanner.close();}
}

当然这么写就绕过了此题的精髓。

这道题想要体现的点在于：很多数组填充类的问题，其做法都是先预先给数组扩容带填充后的大小，然后在从后向前进行操作。

字符串的本质就是char型数组，所以这个方法当然可以沿用，其好处在于：

• 避免数据覆盖：如果从前往后填充，在填充过程中可能会覆盖尚未处理的数据。而从后向前填充，可以确保在填充新元素时，不会影响到前面尚未处理的元素，从而保证了数据的完整性和正确性。
• 提高效率：从后向前操作可以减少元素的移动次数。在数组扩容后，若从前往后填充，每插入一个新元素，后面的元素都需要向后移动一位，时间复杂度较高。而从后向前填充，只需将新元素直接放置在合适的位置，无需频繁移动其他元素，提高了填充操作的效率。

代码如下：

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();}
}