String类相关oj练习
1.第一次只出现一次的字符
做题首先看清要求和提示：
给定一个字符串
s，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回-1。
提示：
1 <= s.length <= 105s只包含小写字母
这就要用到我们所学的字符串的知识了，我们可以通过String的常用方法chatAt,直接查找当前位置的字符。
接下来有两种思路，一种就是暴力求解，另外一种就是运用哈希的思想
暴力求解:
定义两个变量，i和j，i从0下标开始遍历，j从1下标开始遍历，当j遍历完之后,没有找到相同的,直接退出循环。如果找到相同的，则i++。如下图（这种方式极力不推荐，因为时间复杂度较大，我们说另一种方式）
哈希思想
可以先，定义一个0到122的count数组。
由题目可知，s只包含小写字母，a的Ascii码值为97，可以将字符存在对应下标下面。
通过字符对应的数组下标自增加1，做好标记。
然后找到数组中为1，且第一次出现的字符。
1.1定义一个计数数组
下标0~96的空间无法利用，可以对他进行优化
通过当前字符与‘a’相减，从而缩小数组范围
代码如下：
int[] count = new int [26];1.2.遍历字符串 记录次数
//遍历字符串，记录次数for(int i = 0;i < n;i++){count[s.charAt(i) - 'a']++;} 
1.3.再次遍历字符串
这时不要遍历count数组，这个做法是错误的。
//再次遍历for(int i = 0;i < n;i++){if(count[s.charAt(i)-'a']==1)return i;}return -1; 跳出循环，没有只出现一次的字符，返回-1.
1.4 代码实例
public static int firstUniqChar(String s) {//定义一个计数数组int[] chars = new int[26];//遍历字符串，记录次数for(int i = 0; i < s.length(); i++){chars[s.charAt(i) - 'a']++;}//再次遍历for (int i = 0; i < s.length(); i++) {if(chars[s.charAt(i) - 'a'] == 1)return i;}return -1;} 
我们可以看到通过时间是6ms，但我觉得还有改进的空间。
于是进行了下列的改进：
1. 我直接求出字符串的长度，并通过ch接收，减少循环条件求字符串长度的时间
2.将定义数组放在后面，可以减少一毫秒的运算速度，这个原因，现在还不知道。zu
改进的代码如下：
int ch = s.length();int[] count = new int [26];//遍历字符串，记录次数for(int i = 0;i < ch;i++){count[s.charAt(i) - 'a']++;}//再次遍历for(int i = 0;i < ch;i++){if(count[s.charAt(i)-'a']==1)return i;}return -1; } 
2.最后一个单词的长度
题目：
计算字符串最后一个单词的长度，单词以空格隔开，字符串长度小于5000。（注：字符串末尾不以空格为结尾）
本题我采用三种方式来做，当然还有更多的方式可供大家探索。
2.1.第一种方式运用String常用方法split进行分割
通过split函数将原字符串分割为字符串数组。如下图示例：
字符串数组最后一个元素即是原字符串的最后一个单词，直接输出其长度。
代码如下：
import java.util.Scanner;public class Main{public static void main(String[] args){//标准输入Scanner sc=new Scanner(System.in);//键盘输入字符串String str=sc.nextLine();//以空格分割为字符串数组String[] arr=str.split(" ");//字符串数组最后一个元素即是原字符串的最后一个单词，直接输出其长度System.out.println(arr[arr.length-1].length());}
}
- 时间复杂度：字符串分割需要遍历整个字符串，所以时间复杂度为O(n)。
- 空间复杂度：最坏情况下需要大小为n-1的字符串数组存储所有的单词，所以空间复杂度为O(n)。
2.2.第二种方法指针
解题思路
- 定义一个指针变量。
- 从后往前遍历字符串，当遇到空格时，用指针记录位置信息，并终止循环。
- 总长度减去指针到开头一段的长度，即得到最后一个单词的长度。
代码实例：
import java.util.Scanner;public class Main{public static void main(String[] args){//标准输入Scanner sc=new Scanner(System.in);//键盘输入字符串String str=sc.nextLine();//定义指针变量int index=-1;for(int i=s.length()-1;i>=0;i--){//从后往前第一个空格的位置if(s.charAt(i)==' '){index=i;break;}}//总长度减去指针到开头一段的长度，即得到最后一个单词的长度System.out.println(s.length()-index-1);}
}
- 时间复杂度：最坏情况下遍历整个字符串，所以时间复杂度为O(n)。
- 空间复杂度：需要额外常数级别的空间，所以空间复杂度为O(1)。
2.3 第三种方式，用lastlndexOf和substring方法
解题思路
- 用lastlndexOf找最后一个空格出现的位置,将位置传给index
- 然后用substring方法，从index+1,截取到str字符串末尾
- 最后一个单词长度就为，截取的字符串ret的长度
代码实例：
public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextInt());// 注意 while 处理多个 caseString str = in.nextLine();int index = str.lastIndexOf(" ");String ret = str.substring(index+1);System.out.println(ret.length());}3.检查字符串是否为回文
3.1题目：
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
这题采用双指针的做法来做
3.2解题思路：
初始时，左右指针分别指向 字符串 的两侧，随后我们不断地将这两个指针相向移动，每次移动一步，并判断这两个指针指向的字符是否相同。当这两个指针相遇时，就说明 字符串 是回文串。
先判断条件，由题目可知。移除所有非字母数字字符，字母数字都属于字母数字字符
if((ch >= 'a' && ch <= 'z')||(ch >= '0' && ch <= '9')){return false;}运用toLowerCase:方法将字符串转换为小写字母，以便在判断回文时不区分大小写。
3.3代码示例
public boolean isPalindrome(String s) {s = s.toLowerCase();int left = 0;int right = s.length()-1;while(left < right){while(left < right && isCharacterNum(s.charAt(left))){left ++;}while(left < right && isCharacterNum(s.charAt(right))){right --;}if(s.charAt(left)!= s.charAt(right)){return false;}else{left++;right--;}}return true; }private boolean isCharacterNum(char ch){if((ch >= 'a' && ch <= 'z') ||(ch >= '0' && ch <= '9')){return false;}return true;}通过以下两种方法，可以直接获取字母和数字
优化代码如下：
public boolean isPalindrome(String s) {s = s.toLowerCase();int left = 0;int right = s.length()-1;while(left < right){while(left < right && isCharacterNum(s.charAt(left))){left ++;}while(left < right && isCharacterNum(s.charAt(right))){right --;}if(s.charAt(left)!= s.charAt(right)){return false;}else{left++;right--;}}return true; }private boolean isCharacterNum(char ch){if(Character.isDigit(ch) || Character.isLetter(ch)){return false;}return true;}