论文差不多搞定了，开始补落下的这几天的算法题

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,6l=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];

这道题对我来说难度太大，有一些语法记不住，二刷再学一遍