Java - LeetCode面试经典150题 - 哈希表 (二)

哈希表

383. 赎金信

题目

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。

提示：

1 <= ransomNote.length, magazine.length <= 1e5
ransomNote 和 magazine 由小写英文字母组成

示例 1：

输入：ransomNote = "a", magazine = "b"
输出：false

示例 2：

输入：ransomNote = "aa", magazine = "ab"
输出：false

示例 3：

输入：ransomNote = "aa", magazine = "aab"
输出：true

解析：

将magazine中的每个字符的个数记录下来，用map映射成<字符，对应字符个数>。
然后遍历ransomNote字符，判断magazine剩下的字符是否能够组成ransomNote的字符。

代码：

class Solution {public boolean canConstruct(String ransomNote, String magazine) {Map<Character, Integer> m = new HashMap<>();for (int i=0;i<magazine.length();i++){Character c=magazine.charAt(i);if (m.containsKey(c)){m.put(c,m.get(c)+1);}else{m.put(c,1);}}for (int i=0;i<ransomNote.length();i++){Character c=ransomNote.charAt(i);if (m.containsKey(c)&&m.get(c)>0){m.put(c,m.get(c)-1);}else return false;}return true;}
}

205. 同构字符串

题目

给定两个字符串 s 和 t ，判断它们是否是同构的。
如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

提示：

1 <= s.length <= 5 * 104
t.length == s.length
s 和 t 由任意有效的 ASCII 字符组成

示例 1:

输入：s = "egg", t = "add"
输出：true

示例 2：

输入：s = "foo", t = "bar"
输出：false

示例 3：

输入：s = "paper", t = "title"
输出：true

解析：

首先判断两个字符串的长度是否相等，不相等肯定不同构。
之后就是遍历字符串，对应字符判断。
我用的两个map，记录对方信息 map<自己字符，对方字符>
当遍历字符，并从map中取出对应字符c,d时，会出现下面的情况：

1. c和d都为null，此时加入map中，continue；

2. c和d有一个为空，此时就是说明有一个被占用，false；

3. c和d都不为空，但是不相等，false；

4. c和d都不为空，且相等，continue；

能遍历完字符串，就是 true；

代码：

class Solution {public boolean isIsomorphic(String s, String t) {int n=s.length(),m=t.length();if (n!=m){return false;}HashMap<Character,Character> q=new HashMap<>();HashMap<Character,Character> p=new HashMap<>();boolean flag=true;for (int i=0,j=0;i<n;i++,j++){Character c=q.get(s.charAt(i));Character d=p.get(t.charAt(j));// System.out.println(c);if (c==null&&d==null){q.put(s.charAt(i),t.charAt(j));p.put(t.charAt(j),s.charAt(i));}else if (c==null||d==null){flag=false;return flag;}else if (c==t.charAt(j)){continue;}else{flag=false;return flag;}}return flag;}
}

290. 单词规律

题目

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。
这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

提示:

1 <= pattern.length <= 300
pattern 只包含小写英文字母
1 <= s.length <= 3000
s 只包含小写英文字母和 ' '
s 不包含 任何前导或尾随对空格
s 中每个单词都被 单个空格 分隔

示例1:

输入: pattern = "abba", s = "dog cat cat dog"
输出: true

示例 2:

输入:pattern = "abba", s = "dog cat cat fish"
输出: false

示例 3:

输入: pattern = "aaaa", s = "dog cat cat dog"
输出: false

解析：

可以使用两个map，做到字符和字符串相互映射，保证同时合法。

代码：

class Solution {public boolean wordPattern(String pattern, String s) {String[] str=s.split(" ");int n=pattern.length();if (n!=str.length) return false;HashMap<Character, String> q = new HashMap<>();HashMap<String, Character> p = new HashMap<>();for (int i=0;i<n;i++){Character cha=p.get(str[i]);String st=q.get(pattern.charAt(i));if (cha==null&&st==null){q.put(pattern.charAt(i),str[i]);p.put(str[i],pattern.charAt(i));continue;}else if (cha!=null&&st!=null&&cha==pattern.charAt(i)&&st.equals(str[i])){continue;}else{return false;}}return true;}
}

242. 有效的字母异位词

题目

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 字母异位词。

提示:

1 <= s.length, t.length <= 5 * 1e4
s 和 t 仅包含小写字母

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

解析：

用map<Character,Integer>，将字符串 s 的一个字符出现的次数记录下来。
遍历t串，看剩下的相同字符是否大于0。

代码：

class Solution {public boolean isAnagram(String s, String t) {int n=s.length();if (n!=t.length()) return false;HashMap<Character, Integer> q = new HashMap<>();for (int i=0;i<n;i++){Integer x=q.get(s.charAt(i));if (x==null) x=1;else x++;q.put(s.charAt(i),x);}for (int i=0;i<n;i++){if (q.containsKey(t.charAt(i))&&q.get(t.charAt(i))>0){Integer x=q.get(t.charAt(i));q.put(t.charAt(i),x-1);}else return false;}return true;}
}

49. 字母异位词分组

题目

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

提示：

1 <= strs.length <= 1e4
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

解析：

用map哈希，<String,List<String>>
遍历字符串数组，将其中的字符串，进行排序，这样就形成一个唯一的字符串了，之后将原字符串追加到这个排序完的字符串映射的String列表中。

代码：

import java.util.*;
class Solution {public List<List<String>> groupAnagrams(String[] strs) {int n=strs.length;Map<String, List<String>> m = new HashMap<>();for (int i=0;i<n;i++){String s=strs[i];char[] q=s.toCharArray();Arrays.sort(q);String ss=Arrays.toString(q);// if (m.containsKey(ss)){//     var p=m.get(ss);//     p.add(s);// }// else{//     List<String> p = new ArrayList<>();//     m.put(ss,p);//     p.add(s);// }//下方代码可替换上面注释掉的代码List<String> list = m.getOrDefault(ss, new ArrayList<String>());list.add(s);m.put(ss, list);}// List<List<String>> ans = new ArrayList<>();// Collection<List<String>> values = m.values();// for (var x:values){//     ans.add(x);//     for (var y:x){//         System.out.print(y+" ");//     }//     System.out.println();// }// return ans;//下方代码可替换上面注释掉的代码return new ArrayList<List<String>>(m.values());}
}

1. 两数之和

题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。

提示：

2 <= nums.length <= 1e4
-1e9 <= nums[i] <= 1e9
-1e9 <= target <= 1e9
只会存在一个有效答案

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

解析：

没使用双for循环，也不知道会不会暴。
使用 Map<Integer, List<Integer>>，遍历数组将相同数字的下标放在一个列表中。
之后通过遍历数组，判断能不能找到target-nums[i]这个值得数，且要判断该值所在的这些ID，是否等于 i。
找到之后，i和ID就是答案。

代码：

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, List<Integer>> m = new HashMap<>();int n=nums.length;int[] ans=new int[2];for (int i=0;i<n;i++) {// if (m.containsKey(nums[i])){//     var q=m.get(nums[i]);//     q.add(i);// }// else{//     ArrayList<Integer> q = new ArrayList<>();//     m.put(nums[i],q);//     q.add(i);// }List<Integer> list = m.getOrDefault(nums[i], new ArrayList<Integer>());list.add(i);m.put(nums[i], list);}for (int i=0;i<n;i++) {int k=target-nums[i];if (m.containsKey(k)){List<Integer> q=m.get(k);for (Integer x:q){if (x!=i){ans[0]=i;ans[1]=x;return ans;}}}}return ans;}
}

202. 快乐数

题目

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

提示：

1 <= n <= 231 - 1

示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

输入：n = 2
输出：false

解析：

按照题意进行编写即可。
将出现过的数记录下来，如果该数再次出现，就说明这是一个无限循环，false了。

代码：

class Solution {public static boolean isHappy(int n) {HashSet<Integer> k = new HashSet<Integer>();boolean flag=false;while (true){
//            System.out.println(n);if (n==1){flag=true;break;}if (k.contains(n)) break;k.add(n);int res=0;while (n>0){int l=n%10;res=res+l*l;n /=10;}n=res;}return flag;}
}

219. 存在重复元素 II

题目

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

提示：

1 <= nums.length <= 1e5
-1e9 <= nums[i] <= 1e9
0 <= k <= 1e5

示例 1：

输入：nums = [1,2,3,1], k = 3
输出：true

示例 2：

输入：nums = [1,0,1,1], k = 1
输出：true

示例 3：

输入：nums = [1,2,3,1,2,3], k = 2
输出：false

解析：

遍历数组，将值相同的id，放在一个列表中。因为遍历数组，所以同一个列表中的id值，肯定是递增的。所以只需要判断一个列表中相邻的id大小即可。
判断存在就是存在；如果没有，最近的都没有了，就肯定没有了。

代码：

import java.util.Collection;
class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) {int n=nums.length;HashMap<Integer, List<Integer>> m = new HashMap<Integer, List<Integer>>();for (int i=0;i<n;i++){if (m.containsKey(nums[i])){var q=m.get(nums[i]);q.add(i);}else{ArrayList<Integer> q = new ArrayList<>();m.put(nums[i],q);q.add(i);}}boolean flag=false;Collection<List<Integer>> res = m.values();for (List<Integer> q:res){for (int i=0;i<q.size()-1;i++){if (Math.abs(q.get(i)-q.get(i+1))<=k){flag=true;return true;}}}return flag;}
}

128. 最长连续序列

题目

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

提示：

0 <= nums.length <= 1e5
-1e9 <= nums[i] <= 1e9

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

解析：

利用TreeSet的不可重复性，和能内置一个比较器的特点，就可以解决该题，但是时间复杂度是O(nlog(n))。

代码：

class Solution {public int longestConsecutive(int[] nums) {TreeSet<Integer> k = new TreeSet<>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o1-o2;}});int n=nums.length;for (int i=0;i<n;i++) k.add(nums[i]);
//        System.out.println(k);List<Integer> ans = new ArrayList<>(k);if (ans.size()==0){return 0;}int cnt=1,res=1;for (int i=1;i<ans.size();i++){if (ans.get(i)==ans.get(i-1)+1){cnt++;}else{res=Math.max(res,cnt);cnt=1;}}res=Math.max(res,cnt);return res;}
}