坚持啊！给自己自由！
当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。
但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。
242. 有效的字母异位词
因为string 只包含小写字母 ，所以可以创建数组来存储各个字母,再循环判断
class Solution {
public boolean isAnagram(String s, String t) {
int []num1 = new int[128];
int []num2 = new int[128];
for(int i = 0; i <s.length(); i++){
char c= s.charAt(i);
num1[c]++;
}
for( int i = 0; i< t.length(); i++){
char c = t.charAt(i);
num2[c]++;
}
for(int i = 0; i<128;i++){
if(num1[i] != num2[i])
return false;
}
return true;
}
383. 赎金信
改进版，只用一个数组，通过对这一个数组加减判断
小写字母是128以内的数字，主要magazine里字母存在，就让相应的下标的值加一，
在到ransomNote匹配，只要是ransomNote里的字母，就让相应下标的值减一，只要存在
哪个下标的值大于0，说明magazine里存在ransomNote没有的字母，那就return false
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int num[] = new int[128];
for(char i : ransomNote.toCharArray()){
num[i]++;
}
for(char i : magazine.toCharArray()){
num[i]--;
}
for(int i : num ){
if(i > 0)
return false;
}
return true;
}
}
49. 字母异位词分组
方法一：字母排序
理解字母异位词，具有相同的字母特征，所以可以利用散列表map来存储，键为一组异位字母词的标志， 值为一组字母异位词列表
1.首先，遍历每一个的string，得到每一个字符串所在组的字母异位词的标志
2将当前字符串加入该组字母异位词的列表中，遍历全部字符串之后，哈希表中的每一键值对即为一组字母异位词
这道题运用了好多集合的API，首先是定义上的套娃，map<String,List>
再着是运用字符串的toCharArray();,toCharArray() 方法将字符串转换为字符数组。
再使用Arrays.sort(),排序 是Arrays 不是Array，（这里我踩了坑，呜呜呜）
接着是，再将排序好的字符数组 创建成 字符串
下一步是，运用map.getOrDefault 获取 map的值 也就是List
说明一下map.getOrDefault方法:
Java中map.getOrDefault()方法的使用
Map.getOrDefault(Object key, V defaultValue)方法的作用是：
当Map集合中有这个key时，就使用这个key值；
如果没有就使用默认值defaultValue。
HashMap<String, String> map = new HashMap<>();
map.put("name", "cookie");
map.put("age", "18");
map.put("sex", "女");
String name = map.getOrDefault("name", "random");
System.out.println(name);// cookie，map中存在name,获得name对应的value
int score = map.getOrDefault("score", 80);
System.out.println(score);// 80，map中不存在score,使用默认值80
了解了map.getOrDefault()后，我们就知道我们得到了 一个List ，这个List有两种情况，一种是map 里已经有key存在，那么直接获取key所对应的value值，不然就直接返回 新的ArrayList ，泛型为String。
接着，把一开始没有排序过的字符串加入List里，运用了List,add()的api
再把List放进map里，用的是map.put()的API；
最后一步是，退出循环后，返回ArrayList<List>(map.values());，这句话的意思是 创建ArrayList数组，类型是List，他的值为map.values值，map.values()取出来的值就是value，没有key.
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String ,List<String>> map =new HashMap<String,List<String>>();
for(String str: strs){
char[] c = str.toCharArray();
Arrays.sort(c);
String key = new String(c);//构造单词的字符排序,作为键
List<String> List = map.getOrDefault(key,new ArrayList<String>());
List.add(str);
map.put(key,List);//将单词加入散列表中
}
return new ArrayList<List<String>>(map.values());
}
}
第二种方法：
改变map的key值，由字母和字母出现的次数组成
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> map = new HashMap<String,List<String>>();
for(String str :strs){
int []num = new int[26];
for(int i = 0; i< str.length();i++){//统计字符出现次数
num[str.charAt(i)-'a']++;
}
StringBuffer stringBuffer = new StringBuffer();
for(int i = 0; i <26;i++){
if(num[i] > 0){
stringBuffer.append((char)('a' +i));
stringBuffer.append(num[i]);//创建键值
}
}
String s = new String(stringBuffer);
List<String> list = map.getOrDefault(s,new ArrayList<String>());
list.add(str);//将具有相同特征的字母放在一起
map.put(s,list);
}
return new ArrayList<List<String>>(map.values());
}
}
438. 找到字符串中所有字母异位词
呜呜呜，超时了！
快慢指针法：
如果遇到没有的字符，high原地等待；low++遍历到这个字符后（即low比high多1后），下一次high也会消耗掉这个没有的字符
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int num1[] = new int[128];
List<Integer> list = new ArrayList<>();
for(char i: p.toCharArray()) num1[i]++;
int low = 0 ,high = 0;
while(high <s.length()){
if(num1[s.charAt(high)] >0){
num1[s.charAt(high++)]--;
if(high -low == p.length()) list.add(low);
}else{
num1[s.charAt(low++)]++;
}
}
return list;
}
}
相关文章
