【哈希表】算法例题

五、哈希表

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();
    }