【LeetCode】查找表问题：Map 常见典例

系统管理员 2022-10-29 09:11 182阅读 0赞

### Map ###

#### [350. 两个数组的交集 II][350. _ II] ####

难度简单443收藏分享切换为英文接收动态反馈

给定两个数组，编写一个函数来计算它们的交集。

**示例 1：**

输入：nums1 = [1,2,2,1], nums2 = [2,2]
    输出：[2,2]

**示例 2:**

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
    输出：[4,9]

**题解**

跟数据库原理中交运算的计算方法很类似

*  对于无序：hash 表
 *  对于有序：多路归并

class Solution { 
        public int[] intersect(int[] nums1, int[] nums2) { 
            Map<Integer , Integer> map = new HashMap<>();
            List<Integer> resList = new ArrayList<>();
    
            for(int i : nums1){ 
                map.put(i , map.getOrDefault(i , 0) + 1);
            }
            for(int i : nums2){ 
                if(map.get(i) != null && map.get(i) != 0){ 
                    map.put(i , map.get(i) - 1);
                    resList.add(i);
                }
            }
    
            int[] res = new int[resList.size()];
            for(int i = 0 ;i < resList.size() ; i ++){ 
                res[i] = resList.get(i);
            }
    
            return res;
        }
    }

#### [242. 有效的字母异位词][242.] ####

难度简单336收藏分享切换为英文接收动态反馈

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

**示例 1:**

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

**示例 2:**

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

**题解**

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

#### [202. 快乐数][202.] ####

难度简单526收藏分享切换为英文接收动态反馈

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

「快乐数」定义为：

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

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

**示例 1：**

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

**示例 2：**

输入：n = 2
    输出：false

**题解**

*  对于看似有无限可能的，最后一定会成为循环。

class Solution { 
        public boolean isHappy(int n) { 
            Set<Integer> record = new HashSet<>();
    
            while(true){ 
                record.add(n);
    
                int sum = 0;
                while(n != 0){ 
                    sum = sum + (n % 10) * (n % 10);
                    n /= 10;
                }
    
                if(sum == 1){ 
                    return true;
                }
                if(record.contains(sum)){ 
                    return false;
                }
                n = sum;
            }
        }
    }

#### [290. 单词规律][290.] ####

难度简单305收藏分享切换为英文接收动态反馈

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

这里的 **遵循** 指完全匹配，例如， `pattern` 里的每个字母和字符串 `str` 中的每个非空单词之间存在着双向连接的对应规律。

**示例1:**

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

**示例 2:**

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

**示例 3:**

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

**示例 4:**

输入: pattern = "abba", str = "dog dog dog dog"
    输出: false

**题解**

class Solution { 
        public boolean wordPattern(String pattern, String s) { 
            Map<Character , String> record = new HashMap<>();
            Set<String> distinct = new HashSet<>();
    
            String[] arrs = s.split(" ");
            if(pattern.length() != arrs.length){ 
                return false;
            }
    
            for(int i = 0 ; i < pattern.length() ; i ++){ 
                if(record.get(pattern.charAt(i)) != null){ 
                    if(! record.get(pattern.charAt(i)).equals(arrs[i])){ 
                        return false;
                    }
                }else { 
                    record.put(pattern.charAt(i) , arrs[i]);
                    if(distinct.contains(arrs[i])){ 
                        return false;
                    }
                    distinct.add(arrs[i]);
                }
            }
    
            return true;
        }
    }

#### [205. 同构字符串][205.] ####

难度简单327收藏分享切换为英文接收动态反馈

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

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

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

**示例 1:**

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

**示例 2：**

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

**示例 3：**

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

#### [205. 同构字符串][205.] ####

难度简单327收藏分享切换为英文接收动态反馈

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

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

**示例 1:**

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

**示例 2：**

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

**示例 3：**

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

**题解**

class Solution { 
        public boolean isIsomorphic(String s, String t) { 
            if(s.length() != t.length()){ 
                return false;
            }
            Map<Character , Character> record = new HashMap<>();
            Set<Character> distinct = new HashSet<>();
    
            for(int i = 0 ; i < s.length() ; i ++){ 
                if(record.get(t.charAt(i)) != null){ 
                    if(record.get(t.charAt(i)) != s.charAt(i)){ 
                        return false;
                    }
                }else { 
                    if(distinct.contains(s.charAt(i))){ 
                        return false;
                    }
                    record.put(t.charAt(i) , s.charAt(i));
                    distinct.add(s.charAt(i));
                }
            }
    
            return true;
        }
    }

#### [451. 根据字符出现频率排序][451.] ####

难度中等213收藏分享切换为英文接收动态反馈

给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

**示例 1:**

输入:
    "tree"
    
    输出:
    "eert"
    
    解释:
    'e'出现两次，'r'和't'都只出现一次。
    因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。

**示例 2:**

输入:
    "cccaaa"
    
    输出:
    "cccaaa"
    
    解释:
    'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
    注意"cacaca"是不正确的，因为相同的字母必须放在一起。

**题解**

class Solution { 
        public String frequencySort(String s) { 
            Map<Character , Integer> record = new HashMap<>();
    
            for(int i = 0 ; i < s.length() ; i ++){ 
                record.put(s.charAt(i) , record.getOrDefault(s.charAt(i) , 0) + 1);
            }
    
            PriorityQueue<Character> queue = new PriorityQueue<>((o1 , o2) -> record.get(o2) - record.get(o1));
            queue.addAll(record.keySet());
    
            char[] res = new char[s.length()];
            int idx = 0;
            while(queue.size() != 0){ 
                Character c = queue.poll();
                int times = record.get(c);
                for(int i = 0 ; i < times ; i ++){ 
                    res[idx ++] = c;
                }
            }
    
            return new String(res);
        }
    }

[350. _ II]: https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/
[242.]: https://leetcode-cn.com/problems/valid-anagram/
[202.]: https://leetcode-cn.com/problems/happy-number/
[290.]: https://leetcode-cn.com/problems/word-pattern/
[205.]: https://leetcode-cn.com/problems/isomorphic-strings/
[451.]: https://leetcode-cn.com/problems/sort-characters-by-frequency/