1. 验证回文串
验证回文串
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后,短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s,如果它是 回文串 ,返回 true ;否则,返回 false 。
示例 1:
输入: s = “A man, a plan, a canal: Panama”
输出:true
解释:“amanaplanacanalpanama” 是回文串。
1.1 先转换为都是小写的字符串,然后比较是否是回文串
首先根据题目的条件,先使用StringBuilder来存储小写字符串,如果s里面不是小写那么就跳过,可以使用Character.isLetterOrDigit()判断是否为字符,然后使用toLowerCase转换成小写,然后就都是小写的字符串,进行字符串回文比较。
public boolean isPalindrome(String s) {StringBuilder sb = new StringBuilder();for(int i=0;i<s.length();i++){char c =s.charAt(i);if(Character.isLetterOrDigit(c)){sb.append(Character.toLowerCase(c));}}String str = sb.toString();int left =0;int right = str.length()-1;while(left<right){if(str.charAt(left) != str.charAt(right)){return false;}left++;right--;}return true;}
总的时间复杂度时O(n),空间复杂度O(n)
不过这里我还有个想法,就是一次循环,碰到,空格就跳过,然后将字符转为小写使用双指针进行比较,这样就可以使用一次遍历。
1.2 一次循环
public boolean isPalindrome(String s) {int n =s.length();int left =0;int right = n-1;while(left<right){while(left<right && !Character.isLetterOrDigit(s.charAt(left))){++left;}while(left<right && !Character.isLetterOrDigit(s.charAt(right))){--right;}if(left<right){if(Character.toLowerCase(s.charAt(left) ) != Character.toLowerCase(s.charAt(right))){return false;}++left;--right;}}return true;}
这一题如果知道了isLetterOrDigit,就比较简单了,不需要使用额外的判断。
2. 字符串中的第一个唯一字符
字符串中的第一个唯一字符
给定一个字符串 s ,找到 它的第一个不重复的字符,并返回它的索引 。如果不存在,则返回 -1 。
示例 1:
输入: s = “leetcode”
输出: 0
示例 2:
输入: s = “loveleetcode”
输出: 2
示例 3:
输入: s = “aabb”
输出: -1
2.1 HashMap
统计每个字符出现的次数,使用hashmap比较合适,然后遍历字符串找到对应的map里面值为1的结果,就是不重复的字符。
public int firstUniqChar(String s) {HashMap<Character,Integer> map = new HashMap<>();for(int i=0;i<s.length();i++){map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)+1);}for(int i=0;i<s.length();i++){if(map.get(s.charAt(i))==1){return i;}}return -1;}
3. 有效的字母异位词
有效的字母异位词
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。
注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词。
3.1 字符数组排序
刚看到这个方法的时候还是有点没想到,因为将字符经过排序后都是按照一定顺序排列的,只需要将两个字符串排序后的结果比较就可以了。
public boolean isAnagram(String s, String t) {char [] ch1 = s.toCharArray();char [] ch2 = t.toCharArray();Arrays.sort(ch1);Arrays.sort(ch2);return new String(ch1).equals(new String(ch2));}
3.2 哈希表
题目提示了统计字符出现的次数,很显然使用哈希表。
public boolean isAnagram(String s, String t) {if(s.length()!=t.length()) return false;char [] ch1 = s.toCharArray();Map<Character,Integer> map1 = getMapStr(s);Map<Character,Integer> map2 = getMapStr(t);for(char ch: ch1){if(!map2.containsKey(ch) || map1.get(ch) != map2.get(ch)){return false;}}return true;}private Map<Character,Integer> getMapStr(String str){char [] chars = str.toCharArray();Map<Character,Integer> map = new HashMap<>();for(char ch:chars){map.put(ch,map.getOrDefault(ch,0)+1);}return map;}
但是这个方法在力扣里面测试有个数据跑不通。
3.3 哈希映射
首先先设置一个26位长的数组,然后这个数组里面下标就对应着字符串里面的下标,然后每次遍历的时候都要将同一个位置的元素如果s里面存在那么数组对应元素的个数就自增,t里面也对应这个元素就自减,如果最后每位上的元素值都是0,就意味着是一样的。
public boolean isAnagram(String s, String t) {if(s.length()!=t.length()) return false;int [] res = new int [26];for(int i=0;i<s.length();i++){res[s.charAt(i) - 'a']++;res[t.charAt(i) - 'a']--;}for(int i=0;i<26;i++){if(res[i]!=0){return false;}}return true;
}