刷题28-有效的变位词
32-有效的变位词
解题思路：
注意变位词的条件，当两个字符串完全相等或者长度不等时，就不是变位词。
把字符串中的字符映射成整型数组，统计每个字符出现的次数
注意数组怎么初始化：
int [] s1=new int[26]
代码如下：
class Solution {public boolean isAnagram(String s, String t) {if(s.length()!=t.length()||s.equals(t)){return false;}int [] s1=new int[26];int [] t1=new int[26];int l=s.length();for(int i=0;i<l;i++){s1[s.charAt(i)-'a']++;t1[t.charAt(i)-'a']++;}for(int i=0;i<26;i++){if(s1[i]!=t1[i]){return false;}}return true;}
}
33-变位词组
解题思路：注意返回类型为List<List<String>>，可以理解为列表中套列表
Hashmap中本来没有add用法，Hashset中有add用法，这里使用 map.get(s).add(str)表示添加不重复的元素
另外关于ArrayList<>和LinkedList<>用法：
ArrayList<>为基于数组的大小可变
LinkedList<>是基于双向链表
菜鸟教程-Java ArrayList
菜鸟教程-Java LinkedList
在本题中列表的嵌套ArrayList<>和LinkedList<>都可以实现
代码如下：
class Solution {public List<List<String>> groupAnagrams(String[] strs) {Map<String,List<String>> map=new HashMap<>();for(String str:strs){char[] ch=str.toCharArray();//字符串转化为字符数组Arrays.sort(ch);//对字符数组进行排序String s=new String(ch);//字符数组转化为字符串if(!map.containsKey(s)){map.put(s,new ArrayList<>());//map容器中不存在s的话，创建一个s对应的列表}map.get(s).add(str);//add用法没有具体找到，不允许添加重复的元素，保证了变位词是一组}return new ArrayList<>(map.values());}
}
代码二·
class Solution {public List<List<String>> groupAnagrams(String[] strs) {Map<String,List<String>> map=new HashMap<>();for(String str:strs){char[] ch=str.toCharArray();Arrays.sort(ch);String s=new String(ch);if(!map.containsKey(s)){map.put(s,new LinkedList<>());}map.get(s).add(str);}return new LinkedList<>(map.values());}
}
34-外星语言是否排序
解题思路：判定一组单词是否也按照给定的字母表的顺序排列，只需要比较两个单词中第一个不相同的字母顺序。
首先要将字母表映射到一维整形数组中，越靠前的字母数组取值越小。
需要注意的特殊情况1.只有一个单词肯定符合要求2.当两个字母前半部分完全一样时，短的单词在前面，比如app在前，apple在后。
class Solution {public boolean isAlienSorted(String[] words, String order) {if(words.length<2) return true;int[] index=new int[order.length()];for(int i=0;i<order.length();i++){index[order.charAt(i)-'a']=i;//为字母表赋顺序，靠前的下标越小}for(int i=0;i<words.length-1;i++){int len=Math.min(words[i].length(),words[i+1].length());for(int j=0;j<len;j++){char c1=words[i].charAt(j);char c2=words[i+1].charAt(j);if(index[c1-'a']<index[c2-'a']){break;}if(index[c1-'a']>index[c2-'a']){return false;} if(j==len-1&&words[i].length()>len){//判断特殊情况，当前项单词比后项长，并且后项和前项完全重合，判定后项字典序小return false;}}}return true;}
}