【哈希表】算法例题

五、哈希表

39. 赎金信 ①

40. 同构字符串 ①

41. 单词规律 ①

42. 有效的字母异位词 ①

43. 字母异位词分组 ②

44. 两数之和 ①

45. 快乐数 ①

46. 存在重复元素 ①

47. 最长连续序列 ②

五、哈希表

39. 赎金信 ①

给你两个字符串：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 <= 105
ransomNote 和 magazine 由小写英文字母组成

方法1：（11ms）

    public static boolean canConstruct(String ransomNote, String magazine) {if (ransomNote.length() > magazine.length()){return false;}HashMap<Character, Integer> map = new HashMap<>();for (int i = 0; i < magazine.length(); i++) {map.put(magazine.charAt(i), map.getOrDefault(magazine.charAt(i), 0) + 1);}for (int i = 0; i < ransomNote.length(); i++) {if (map.containsKey(ransomNote.charAt(i))){Integer integer = map.get(ransomNote.charAt(i));if (map.get(ransomNote.charAt(i)) == null || integer < 1){return false;}else {map.put(ransomNote.charAt(i), integer - 1);}}else {return false;}}return true;}

方法2：

        if (magazine.length() < ransomNote.length())return false;int[] res = new int[26];for (char c : ransomNote.toCharArray()) {int index = magazine.indexOf(c, res[c - 'a']);if (index == -1)return false;res[c - 'a'] = index + 1;}return true;

方法3：

    public boolean canConstruct(String ransomNote, String magazine) {if(ransomNote.length()>magazine.length()){return false;}int []record = new int[26];for(int i=0;i<magazine.length();i++){record[magazine.charAt(i)-'a']++;}for(int i=0;i<ransomNote.length();i++){record[ransomNote.charAt(i)-'a']--;}for(int i =0;i<record.length;i++){if(record[i]<0){return false;}}return true;}

40. 同构字符串 ①

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1:

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

示例 2：

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

示例 3：

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

提示：

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

方法1：（81ms）

    public static boolean isIsomorphic(String s, String t) {int[] record = new int[2];HashMap<Character, String> map1 = new HashMap<>();HashMap<Character, String> map2 = new HashMap<>();for (int i = 0; i < s.length(); i++) {String orDefault = map1.getOrDefault(s.charAt(i), "");orDefault += i;map1.put(s.charAt(i), orDefault);String orDefault1 = map2.getOrDefault(t.charAt(i), "");orDefault1 += i;map2.put(t.charAt(i), orDefault1);if (!orDefault.equals(orDefault1)){return false;}}return true;}

方法2：（1ms）

    public boolean isIsomorphic(String s, String t) {char[] ss = s.toCharArray();char[] ts = t.toCharArray();int[] trans1 = new int[128];int[] trans2 = new int[128];for(int i=0,n = ss.length;i<n;i++){char sc = ss[i];char tc = ts[i];if(trans1[sc]!=trans2[tc]){return false;}else if(trans1[sc]==0){trans1[sc]=trans2[tc]=i+1;}}return true;}

41. 单词规律 ①

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。

这里的遵循指完全匹配，例如， pattern 里的每个字母和字符串 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

提示:

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

方法1：（1ms）

    public static boolean wordPattern(String pattern, String s) {String[] s1 = s.split(" ");if (pattern.length() != s1.length){return false;}HashMap<Character, String> map = new HashMap<>();for (int i = 0; i < pattern.length(); i++) {char c = pattern.charAt(i);String value = map.get(c);if (value == null){  // || !(c + value).equals(c + s1[i])map.put(c, s1[i]);}else {if (!value.equals(s1[i])){return false;}}}ArrayList<String> list = new ArrayList<>();for (Map.Entry<Character, String> entry : map.entrySet()) {if (list.contains(entry.getValue())){return false;}list.add(entry.getValue());}return true;}

方法2：

    public boolean wordPattern(String pattern, String s) {String[] data =s.split(" ");if(data.length!=pattern.length()){return false;}String[] p2w = new String[26];Map<String, Character> w2p = new HashMap<>();for (int i = 0; i < pattern.length(); i++) {char c = pattern.charAt(i);if (p2w[c - 'a'] == null) {p2w[c - 'a'] = data[i];} else if (!p2w[c - 'a'].equals(data[i])) {return false;}if (w2p.get(data[i]) == null) {w2p.put(data[i], c);} else if (w2p.get(data[i]).charValue() != c) {return false;}}return true;}

42. 有效的字母异位词 ①

给定两个字符串 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 * 104
s 和 t 仅包含小写字母

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

方法1：（3ms）

    public boolean isAnagram(String s, String t) {if (s.length() != t.length()){return false;}int[] chars = new int[26];for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);chars[c - 'a']++;}for (int i = 0; i < t.length(); i++) {char c = t.charAt(i);chars[c - 'a']--;}for (int i = 0; i < 26; i++) {if (chars[i] != 0){return false;}}return true;}

43. 字母异位词分组 ②

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

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

示例 2:

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

示例 3:

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

提示：

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

方法1：（9ms）

    public static List<List<String>> groupAnagrams(String[] strs) {ArrayList<List<String>> result = new ArrayList<>();HashMap<String, List<String>> map = new HashMap<>();for (int i = 0; i < strs.length; i++) {char[] chars = strs[i].toCharArray();Arrays.sort(chars);String key = Arrays.toString(chars);List<String> value = map.get(key);if (value == null){value = new ArrayList<>();}value.add(strs[i]);map.put(key, value);}// List<List<String>> collect = new ArrayList<>(map.values());for (Map.Entry<String, List<String>> entry : map.entrySet()) {result.add(entry.getValue());}return result;}

44. 两数之和 ①

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 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]

提示：

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

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

方法1：（41ms）

    public static int[] twoSum(int[] nums, int target) {int[] result = new int[2];int left = 0;int right = +1;for (int i = 0; i < nums.length; i++) {left = i;right = left +1;while (right < nums.length){if (nums[left] + nums[right] == target){result[0] = left;result[1] = right;break;}right++;}left++;}return result;}

方法2：（0ms）

    public static int[] twoSum(int[] nums, int target) {if (nums.length == 2) {return new int[]{0, 1};}for (int i = 0, j = 1; j < nums.length; ++i) {if (i + j >= nums.length) {i = -1;j++;} else if (nums[i] + nums[i + j] == target) {return new int[]{i, j + i};}}return new int[]{};}

45. 快乐数 ①

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

「快乐数」 定义为：

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

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

示例 1：

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

示例 2：

输入：n = 2
输出：false

提示：

1 <= n <= 231 - 1

方法1：（3ms）

    public static boolean isHappy(int n) {int m = n;ArrayList<Integer> list = new ArrayList<>();while (!list.contains(m)){list.add(m);if (m == 1){return true;}int sum = 0;String str = m + "";int length = str.length();for (int i = 0; i < length; i++) {sum += Math.pow(Integer.parseInt(str.charAt(i) + "") , 2);}m = sum;}return false;}

方法2：（0ms）

    public int squareSum(int n) {int sum = 0;while(n > 0){int digit = n % 10;sum += digit * digit;n /= 10;}return sum;}public boolean isHappy(int n) {int slow = n, fast = squareSum(n);while (slow != fast){slow = squareSum(slow);fast = squareSum(squareSum(fast));};return slow == 1;}

方法2：（1ms）

    public boolean isHappy(int n) {Set<Integer> set = new HashSet<>();while(n!=1  &&  !set.contains(n)){set.add(n);n=cal(n);}return n==1;}public int cal(int nn){int sum=0;while(nn!=0){sum+=(nn%10)*(nn%10);nn/=10;}return sum;}

46. 存在重复元素 ①

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

示例 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

提示：

1 <= nums.length <= 105
-109 <= nums[i] <= 109
0 <= k <= 105

方法1：

        if (nums.length == 1){return false;}boolean flag = false;int exist = 0;for (int i = 0; i < nums.length - 1; i++) {for (int j = i + 1; j <= Math.min(i + k, nums.length-1); j++) {if (nums[i]  == nums[j]){flag = true;exist = 1;break;}}if (exist == 1){break;}}return flag;}

方法2：

    public boolean containsNearbyDuplicate(int[] nums, int k) {Set<Integer> set= new HashSet<>();for(int i = 0;i<nums.length;i++){if(i>k){set.remove(nums[i-k-1]);}if(!set.add(nums[i])){return true;}}return false;}

47. 最长连续序列 ②

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

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 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

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109

方法1：

    public static int longestConsecutive(int[] nums) {if (nums.length == 0){return 0;}else if (nums.length == 1){return 1;}Arrays.sort(nums);System.out.println(Arrays.toString(nums));TreeSet<Integer> set = new TreeSet<>();int index = 1;for (int i = 1; i < nums.length; i++) {if (nums[i] == nums[i - 1] +1){index++;if (i == nums.length - 1){set.add(index);}}else if (nums[i] == nums[i - 1]){set.add(index);continue;}else {set.add(index);index = 1;}}System.out.println(set);return set.last();}