Day8补代码随想录 字符串part1 344.反转字符串|541.反转字符串II|卡码网：54.替换数字
论文差不多搞定了，开始补落下的这几天的算法题
344.反转字符串
链接
https://programmercarl.com/0344.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.html
题目
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：[“h”,“e”,“l”,“l”,“o”]
输出：[“o”,“l”,“l”,“e”,“h”]
示例 2：
输入：[“H”,“a”,“n”,“n”,“a”,“h”]
输出：[“h”,“a”,“n”,“n”,“a”,“H”]
思路
- 解读
- 难点，原地修改输入数组，O(1)的额外空间
- 考察字符串reverse函数的实现，要明确什么时候用库函数，什么时候不用库函数
- Karl思路
- 首尾交换→向中间移动→两个指针
- code1
class Solution { public void reverseString(char[] s) { int length=s.length; for (int i=0,j=length-1;i<length/2;i++,j--){ char temp=s[i]; s[i]=s[j]; s[j]=temp; } } }
- Carl给的答案是：用while 循环
class Solution { public void reverseString(char[] s) { int length=s.length; int l=0; int r=length-1; while(l<r){ char temp=s[l]; s[l]=s[r]; s[r]=temp; l++; r--; } } } - 两个循环体
- for(初始化；条件；更新){/循环体}
- while(条件){//循环体 更新;}
总结
- 字符串和数组的区别？
- 库函数reverse()；普通函数：swap();（C++）语言，
- 在JAVA中用临时变量手动实现交换逻辑。
- 低级错误
- 变量必须声明；
- 返回类型是void的，并且是原地变换数组，不用设置返回值
- 在for中如果声明for (int i=0,int j=length-1;i<length/2;i++,j–)是不对的，在for循环的初始化部分，如果要声明多个变量，不能重复写数据类型，只能声明一次数据类型。
541.反转字符串II
题目
给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
示例:
输入: s = “abcdefg”, k = 2
输出: “bacdfeg”
思路
- 我的思路
- 两层循环，一层循环全部，里层每循环2k个就翻转一次，然后2k再加一次2k。
- 剩余的值再进行一次for循环，确定范围。但是我的方法非常繁杂，确定循环的始末很容易错
-
class Solution { public String reverseStr(String s, int k) { size=s.length (); //最后一个不满足2k的序列怎么处理 int leaf=size%(2*k); int leafstart=size-leaf; for(int i=0;i<leafstart;i++){ int l=0; int r=2k-1; if(i=2k-1){ while(l<r){ String temp=s[l]; s[l]=s[r]; s[r]=temp; l++; r--; //abcdefghijk k-2, 3,6 l=l+2k; r=r+2k; } } else{continue;} } while(leafstart!=size-1){ for(int i=leafstart,j=size-1;i<size-1;i++,j--){ String temp_leaf=s[leafstart]; s[leaftstart]=s[j]; s[j]=temp_leaf; } } } }
- gpt修改后
class Solution { public String reverseStr(String s, int k) { // 将字符串转换为字符数组 char[] chars = s.toCharArray(); int size = chars.length; int leaf = size % (2 * k); // 计算不满2k的剩余部分 int leafstart = size - leaf; // 剩余部分的起始位置 int l = 0; int r = 2 * k - 1; // 遍历每个2k块，反转前k个字符 for (int i = 0; i < leafstart; i++) { if (i % (2 * k) == 0) { // 每2k块进行一次反转，找起点，而不是找2k块的终点 l = i; r = Math.min(i + k - 1, size - 1); // 确保右边界不越界 // 反转[l, r]区间的字符 while (l < r) { char temp = chars[l]; chars[l] = chars[r]; chars[r] = temp; l++; r--; } } } // 处理剩余字符 if (leaf > 0) { l = leafstart; r = Math.min(leafstart + k - 1, size - 1); // 确保右边界不越界 while (l < r) { char temp = chars[l]; chars[l] = chars[r]; chars[r] = temp; l++; r--; } } // 将字符数组转换回字符串并返回 return new String(chars); } } - Karl
- 更新：我的代码的问题：选择i++遍历有冗余(需要加if (i % (2 * k) == 0)) 解决办法：i+=2k就可以了
- 翻转始末[i,i+k)区间，i+k不能超过边界条件，对边界的处理问题
-
class Solution { public String reverseStr(String s, int k) { char[] ch=s.toCharArray(); for(int i=0;i<ch.length;i+=2*k){ //始末条件限制,还需要不满足2k的时候，很巧妙，用了个min函数 int start=i; int end=Math.min(ch.length-1,i+k-1);//左闭右开 while(start<end){ char temp=ch[start]; ch[start]=ch[end]; ch[end]=temp; start++; end--; } } return new String(ch); } }
总结
- String要转换成数组，char[] ch=s.toCharArray();
- 获取长度 .length获取数组的长度;.length()是一个方法，获取字符串的长度。
- 【很关键】解决不满足2k的剩余数组的时候，用了个很巧妙的方法,int end=Math.min(ch.length-1,i+k-1);//左闭右开,确定了即使不足2k，可以翻转剩余的数组。
- 【很关键】i+=2k循环思路
- 低级错误
- end++顺手写成end–;
- i<ch.length写成了-1
卡码网：54.替换数字
题目
给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。
例如，对于输入字符串 “a1b2c3”，函数应该将其转换为 “anumberbnumbercnumber”。
对于输入字符串 “a5b”，函数应该将其转换为 “anumberb”
输入：一个字符串 s,s 仅包含小写字母和数字字符。
输出：打印一个新的字符串，其中每个数字字符都被替换为了number
样例输入：a1b2c3
样例输出：anumberbnumbercnumber
数据范围：1 <= s.length < 10000。
【对于线性数据结构的填充或删除，后序处理会高效的多】
思路
- 我的思路
- 识别数字后，替换为number
- 问题，
- 如果替换的话，数组长度就变了，后续的字母的位置都要变，怎么处理
- 替换是直接用==吗？怎么识别数数字？
- Carl
- 预先扩充在数组尾部填充number的大小
- 从后向前重新放入字母和数字，当遇到数字时，从后向前放入number
- 双指针，i指向新长度的末尾，j指向旧长度的末尾
- ×从前向后填充O(n^2) ；从后向前填充的好处：1.不用申请新数组 2.从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要讲添加元素之后的所有元素向后移动的问题。
- CODE
-
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(); } }
-
总结
- s.charAt(i) 去字符串String在i处的字符Char。(Char)在某处(at)
- Character.isDigit(a) 判断(Character类)是否(is)为数字(Digit)
- char[] newArray = new char[length]; char[] newS = new char[s.length() + count * 5];
这道题对我来说难度太大，有一些语法记不住，二刷再学一遍