String类相关oj练习

 前言：

此处练习对应博客文章：公主，王子，请点击​​​​​​​

1.第一次只出现一次的字符

做题首先看清要求和提示：

给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。

提示：

• 1 <= s.length <= 105
• s 只包含小写字母

 这就要用到我们所学的字符串的知识了，我们可以通过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.第二种方法指针

 解题思路

1. 定义一个指针变量。
2. 从后往前遍历字符串，当遇到空格时，用指针记录位置信息，并终止循环。
3. 总长度减去指针到开头一段的长度，即得到最后一个单词的长度。

代码实例：  

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方法

  解题思路

1. 用lastlndexOf找最后一个空格出现的位置,将位置传给index
2. 然后用substring方法，从index+1,截取到str字符串末尾
3. 最后一个单词长度就为，截取的字符串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;}