网站内容分析,产品设计个人作品集,可画在线设计平台,wordpress汉字验证码1. 验证回文串
验证回文串 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后#xff0c;短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s#xff0c;如果它是 回文串 #xff0c;返回 t…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 i0;is.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(leftright){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(leftright){while(leftright !Character.isLetterOrDigit(s.charAt(left))){left;}while(leftright !Character.isLetterOrDigit(s.charAt(right))){--right;}if(leftright){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) {HashMapCharacter,Integer map new HashMap();for(int i0;is.length();i){map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)1);}for(int i0;is.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();MapCharacter,Integer map1 getMapStr(s);MapCharacter,Integer map2 getMapStr(t);for(char ch: ch1){if(!map2.containsKey(ch) || map1.get(ch) ! map2.get(ch)){return false;}}return true;}private MapCharacter,Integer getMapStr(String str){char [] chars str.toCharArray();MapCharacter,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 i0;is.length();i){res[s.charAt(i) - a];res[t.charAt(i) - a]--;}for(int i0;i26;i){if(res[i]!0){return false;}}return true;
}
