文章目录

一、替换空格（1版面试题4）1.题目2.思路3.代码4.笔记 二、正则表达式匹配1.题目2.思路 三、表示数值的字符串1.题目2.思路 四、字符流中第一个不重复的字符（与五思路同）1.题目2.思路3.代码 五、第一个只出现一次的字符（与四思路同）1.题目2.思路3.代码 六、左旋字符串1.题目2.思路3.代码 七、把字符串转换为整数1.题目2.思路3.代码

一、替换空格（1版面试题4）

1.题目

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

2.思路

找到空格，替换空格。

3.代码

public class Solution { public String replaceSpace(StringBuffer str) { int i = 0; while(i<str.length()){ int temp = str.indexOf(" "); if(temp != -1){ str.replace(temp,temp+1,"%20"); } i++; } return str.toString(); //方法2：更简洁 //return str.toString().replaceAll(" ", "%20"); } }

4.笔记

合并两个数组（包括字符串）时，若从前往后复制每个数字（字符串）需要重复移动多次，那么可以考虑从后往前复制。

二、正则表达式匹配

1.题目

请实现一个函数用来匹配包括’.‘和’‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配。

2.思路

三、表示数值的字符串

1.题目

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100",“5e2”,"-123",“3.1416"和”-1E-16"都表示数值。 但是"12e",“1a3.14”,“1.2.3”,"±5"和"12e+4.3"都不是。

2.思路

四、字符流中第一个不重复的字符（与五思路同）

1.题目

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。 **注：**如果当前字符流没有存在出现一次的字符，返回#字符。

2.思路

用一个链表来保存每次收到的字符。然后用hash表来存储每个字符出现的次数。最后在找第一次出现的字符时，只需要遍历链表，找到第一个出现次数为1的字符即可。

3.代码

import java.util.ArrayList; import java.util.HashMap; public class Solution { ArrayList<Character> arr = new ArrayList<>(); HashMap<Character,Integer> hm = new HashMap<>(); public void Insert(char ch) { if(hm.containsKey(ch)){ //若字符已出现多次，则把次数改为2（2代表多次） hm.remove(ch); hm.put(ch,2); }else{ hm.put(ch,1); //若字符第一次出现，把次数改为1次 } arr.add(ch); //用链表保存收到的所有字符 } public char FirstAppearingOnce() { for(char c: arr){ //遍历链表，找到第一次出现一次的字符 if(hm.get(c) == 1){ return c; } } return '#'; //没找到，返回'#' } }

五、第一个只出现一次的字符（与四思路同）

1.题目

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）。

2.思路

用一个链表来保存每次收到的字符。然后用hash表来存储每个字符出现的次数。最后在找第一次出现的字符时，只需要遍历链表，找到第一个出现次数为1的字符即可。

3.代码

import java.util.HashMap; //和字符流中第一个不重复的字符这题思路一样 public class Solution { public int FirstNotRepeatingChar(String str) { char[] arr = str.toCharArray(); HashMap<Character,Integer> hm = new HashMap<>(); for(int i=0;i<arr.length;i++){ //该循环记录每个字符出现的次数 if(hm.containsKey(arr[i])){ hm.remove(arr[i]); hm.put(arr[i],2); }else{ hm.put(arr[i],1); } } for(int i=0;i<arr.length;i++){ //该循环寻找第一个出现一次的字符 if(hm.get(arr[i]) == 1){ return i; } } return -1; } }

六、左旋字符串

1.题目

对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。

2.思路

（1）用额外的数组存放结果 把原数组分为需要反转的部分和后移的部分。然后分别放在额外的数组中即可。

（2）不用额外数组空间

前n位反转，后几位反转，最后总的反转。 先反转前n位，再反转后几位，变为了cbafedZYX，再整体反转变为XYZdefabc。

3.代码

（1）用额外的数组存放结果

public class Solution { public String LeftRotateString(String str,int n) { if(str.length()==0){return "";} n = n % str.length(); //防止n大于字符串长度 char[] arr = str.toCharArray(); char[] result = new char[arr.length]; //存放结果 for(int i=n;i<arr.length;i++){ //先存放需要后移的元素 result[i-n] = arr[i]; } for(int i=0;i<n;i++){ //在存放需要反转的元素 result[arr.length-n+i] = arr[i]; } return String.valueOf(result); //将字符数组转为字符串输出 } }

（2）少用额外数组空间

public class Solution { public String LeftRotateString(String str,int n) { if(str.length()==0){return "";} n = n % str.length(); //防止n大于字符串长度 char[] charstr = str.toCharArray(); reverse(charstr, 0, n-1); //先旋转前面的 reverse(charstr, n, str.length() -1); //再旋转后面的字符串 reverse(charstr, 0, str.length()-1); //最后整体反转 return String.valueOf(charstr); } //实现的是charstrs从start到end的反转，也可以使用stringbuffer自带的反转方法 public static void reverse(char[] arr, int start, int end) { while(start < end) { char temp = arr[start]; arr[start] =arr[end]; arr[end] = temp; start++; end--; } } }

七、把字符串转换为整数

1.题目

将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。

2.思路

字符asc码+43-450~948~57 先将字符串放入字符数组中。设置一个状态位start。专门判断首位是+还是-还是数字。根据asc码来判断。有除了数字的其他字符直接返回0.根据start的状态来进行迭代求和。 其中将char型转换为数字的方法是“” (arr[i]-48) //这样就是char对应的asc码-48.得到的结果就是数字减0 若是负数，进行取反。最后判断数字是否int越界。

3.代码

public class Solution { public int StrToInt(String str) { if(str.length() == 0){return 0;} //特殊情况 char[] arr = str.toCharArray(); //把字符串放入一个字符数组中 long result = 0; //最终结果（设置为long型，防止越界导致出错，最后再转换为int） int start = 0; //start为0代表首位无符号，1代表有符号 if(arr[0] == 43 || arr[0] == 45){ //start为0代表首位无符号，1代表有符号 start = 1; } for(int i=start;i<arr.length;i++){ //如果发现数组中有非数组，直接返回0 if (arr[i]<48 || arr[i]>57){ return 0; } } for(int i=start;i<arr.length;i++){ //求和 result = 10*result + (arr[i]-48); } result = (arr[0]==45 ? -result: result); //如果是负数，进行取反 if(result > Integer.MAX_VALUE || result < Integer.MIN_VALUE){ //如果越界，返回0 return 0; } return (int)result; } }