算法刷题记录-哈希表
有效的字母异位词
给定两个字符串 *s* 和 *t* ，编写一个函数来判断 *t* 是否是 *s* 的字母异位词。
注意：若 *s* 和 *t* 中每个字符出现的次数都相同，则称 *s* 和 *t* 互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
提示:
1 <= s.length, t.length <= 5 * 104s和t仅包含小写字母
思路：用两个hashmap分别存储两个字符串字符出现次数，比较两个map是不是所有的值都相同。需要注意的是字典值得比较用equals
public boolean isAnagram(String s, String t) {
HashMap<Character,Integer> map1=new HashMap<>();
HashMap<Character,Integer> map2=new HashMap<>();
for (int i = 0; i < s.length(); i++) {
if(!map1.containsKey(s.charAt(i)))map1.put(s.charAt(i),0);
else map1.put(s.charAt(i), map1.get(s.charAt(i))+1);
}
for (int i = 0; i <t.length(); i++) {
if(!map2.containsKey(t.charAt(i)))map2.put(t.charAt(i),0);
else map2.put(t.charAt(i), map2.get(t.charAt(i))+1);
}
if(map1.size()!=map2.size())return false;
for (char i:map1.keySet()) {
if(!map1.get(i).equals(map2.get(i))) {
return false;
}
}
return true;
}
解法二：用一个map，第一个循环把存s，第二个循环删t中的字符
public boolean isAnagram(String s, String t) {
HashMap<Character,Integer> map1=new HashMap<>();
for (int i = 0; i < s.length(); i++) {
if(!map1.containsKey(s.charAt(i)))map1.put(s.charAt(i),1);
else map1.put(s.charAt(i), map1.get(s.charAt(i))+1);
}
for (int i = 0; i <t.length(); i++) {
if(map1.containsKey(t.charAt(i)))map1.put(t.charAt(i),map1.get(t.charAt(i))-1);
else {
return false;
}
if(map1.get(t.charAt(i)).equals(0)) {
map1.remove(t.charAt(i));
}
}
if(map1.size()!=0)return false;
return true;
放一个他人得解法，其实思路一样，但是这种做法省去了hashmap大量得比较、判断。更快
public boolean isAnagram(String s, String t) {
if(s.length() != t.length()) return false;
int[] arr = new int[26];
for(char c : s.toCharArray())
++arr[c - 'a'];
for(char c : t.toCharArray()){
--arr[c - 'a'];
if(arr[c - 'a'] < 0) return false;
}
return true;
}
赎金信
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1：
输入：ransomNote = "a", magazine = "b"
输出：false
示例 2：
输入：ransomNote = "aa", magazine = "ab"
输出：false
示例 3：
输入：ransomNote = "aa", magazine = "aab"
输出：true
提示：
1 <= ransomNote.length, magazine.length <= 105ransomNote和magazine由小写英文字母组成
与上一题基本类似，这里加字典顺序换一下，先把第二个字符串加进去，在判断能不能满足第一个字符串
public boolean canConstruct(String ransomNote, String magazine) {
if(ransomNote.length()>magazine.length())return false;
int[] arr = new int[26];
for(char c : magazine.toCharArray()) {
++arr[c - 'a'];
}
for(char c : ransomNote.toCharArray()) {
if(arr[c-'a']<=0)return false;
else {
--arr[c - 'a'];
}
}
return true;
}
字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
思路：暴力解法，双重循环。
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> res=new ArrayList<>();
if(strs.length==0)return res;
for(String s:strs){
boolean flag=false;
if(res.size()==0){
List<String> temp=new ArrayList<>();
temp.add(s);
res.add(temp);
}
else {
for(List<String> temp:res){
if(isAnagram(s, temp.get(0))){
temp.add(s);
flag=true;
continue;
}
}
if(flag)continue;
List<String> temp=new ArrayList<>();
temp.add(s);
res.add(temp);
}
}
return res;
}
public boolean isAnagram(String s, String t) {
if(s.length() != t.length()) return false;
int[] arr = new int[26];
for(char c : s.toCharArray())
++arr[c - 'a'];
for(char c : t.toCharArray()){
--arr[c - 'a'];
if(arr[c - 'a'] < 0) return false;
}
return true;
}
找到字符串所有的字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
思路：暴力解法，以每一个索引判断字串是否有可能匹配
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res=new ArrayList<>();
if(s.length()<p.length())return res;
int low=0;
while (low<s.length()-p.length()){
if(isAnagram(s.substring(low,low+p.length()),p))res.add(low);
low++;
}
return res;
}
public boolean isAnagram(String s, String t) {
if(s.length() != t.length()) return false;
int[] arr = new int[26];
for(char c : s.toCharArray())
++arr[c - 'a'];
for(char c : t.toCharArray()){
--arr[c - 'a'];
if(arr[c - 'a'] < 0) return false;
}
return true;
}