游戏网站开发设计报告,联派网站建设,拉新推广怎么做,国外网站参考前言#xff1a;
此处练习对应博客文章#xff1a;公主#xff0c;王子#xff0c;请点击
1.第一次只出现一次的字符
做题首先看清要求和提示#xff1a; 给定一个字符串 s #xff0c;找到 它的第一个不重复的字符#xff0c;并返回它的索引 。如果不… 前言
此处练习对应博客文章公主王子请点击
1.第一次只出现一次的字符
做题首先看清要求和提示 给定一个字符串 s 找到 它的第一个不重复的字符并返回它的索引 。如果不存在则返回 -1 。 提示 1 s.length 105s 只包含小写字母 这就要用到我们所学的字符串的知识了我们可以通过String的常用方法chatAt,直接查找当前位置的字符。
接下来有两种思路一种就是暴力求解另外一种就是运用哈希的思想 暴力求解: 定义两个变量i和ji从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 scnew Scanner(System.in);//键盘输入字符串String strsc.nextLine();//以空格分割为字符串数组String[] arrstr.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 scnew Scanner(System.in);//键盘输入字符串String strsc.nextLine();//定义指针变量int index-1;for(int is.length()-1;i0;i--){//从后往前第一个空格的位置if(s.charAt(i) ){indexi;break;}}//总长度减去指针到开头一段的长度即得到最后一个单词的长度System.out.println(s.length()-index-1);}
}时间复杂度最坏情况下遍历整个字符串所以时间复杂度为O(n)。空间复杂度需要额外常数级别的空间所以空间复杂度为O(1)。
2.3 第三种方式用lastlndexOf和substring方法 解题思路 用lastlndexOf找最后一个空格出现的位置,将位置传给index然后用substring方法从index1,截取到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(index1);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;}
