• 【哈希表】算法例题

      

    目录

      五、哈希表

    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）

    1.     public static boolean canConstruct(String ransomNote, String magazine) {
    2.         if (ransomNote.length() > magazine.length()){
    3.             return false;
    4.         }
    5.         HashMap map = new HashMap<>();
    6.         for (int i = 0; i < magazine.length(); i++) {
    7.             map.put(magazine.charAt(i), map.getOrDefault(magazine.charAt(i), 0) + 1);
    8.         }
    9.         for (int i = 0; i < ransomNote.length(); i++) {
    10.             if (map.containsKey(ransomNote.charAt(i))){
    11.                 Integer integer = map.get(ransomNote.charAt(i));
    12.                 if (map.get(ransomNote.charAt(i)) == null || integer < 1){
    13.                     return false;
    14.                 }else {
    15.                     map.put(ransomNote.charAt(i), integer - 1);
    16.                 }
    17.             }else {
    18.                 return false;
    19.             }
    20.         }
    21.         return true;
    22.     }

    方法2：

    1.         if (magazine.length() < ransomNote.length())
    2.             return false;
    3.         int[] res = new int[26];
    4.         for (char c : ransomNote.toCharArray()) {
    5.             int index = magazine.indexOf(c, res[c - 'a']);
    6.             if (index == -1)
    7.                 return false;
    8.             res[c - 'a'] = index + 1;
    9.         }
    10.         return true;

    方法3：

    1.     public boolean canConstruct(String ransomNote, String magazine) {
    2.         if(ransomNote.length()>magazine.length()){
    3.             return false;
    4.         }
    5.         int []record = new int[26];
    6.         for(int i=0;i
    7.             record[magazine.charAt(i)-'a']++;
    8.         }
    9.         for(int i=0;i
    10.             record[ransomNote.charAt(i)-'a']--;
    11.         }
    12.         for(int i =0;i
    13.             if(record[i]<0){
    14.                 return false;
    15.             }
    16.         }
    17.         return true;
    18.     }

    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）

    1.     public static boolean isIsomorphic(String s, String t) {
    2.         int[] record = new int[2];
    3.         HashMap map1 = new HashMap<>();
    4.         HashMap map2 = new HashMap<>();
    5.         for (int i = 0; i < s.length(); i++) {
    6.             String orDefault = map1.getOrDefault(s.charAt(i), "");
    7.             orDefault += i;
    8.             map1.put(s.charAt(i), orDefault);
    9.             String orDefault1 = map2.getOrDefault(t.charAt(i), "");
    10.             orDefault1 += i;
    11.             map2.put(t.charAt(i), orDefault1);
    12.             if (!orDefault.equals(orDefault1)){
    13.                 return false;
    14.             }
    15.         }
    16.         return true;
    17.     }

    方法2：（1ms）

    1.     public boolean isIsomorphic(String s, String t) {
    2.         char[] ss = s.toCharArray();
    3.         char[] ts = t.toCharArray();
    4.         int[] trans1 = new int[128];
    5.         int[] trans2 = new int[128];
    6.         for(int i=0,n = ss.length;i
    7.             char sc = ss[i];
    8.             char tc = ts[i];
    9.             if(trans1[sc]!=trans2[tc]){
    10.                 return false;
    11.             }else if(trans1[sc]==0){
    12.                 trans1[sc]=trans2[tc]=i+1;
    13.             }
    14.         }
    15.         return true;
    16.     }

    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）

    1.     public static boolean wordPattern(String pattern, String s) {
    2.         String[] s1 = s.split(" ");
    3.         if (pattern.length() != s1.length){
    4.             return false;
    5.         }
    6.         HashMap map = new HashMap<>();
    7.         for (int i = 0; i < pattern.length(); i++) {
    8.             char c = pattern.charAt(i);
    9.             String value = map.get(c);
    10.             if (value == null){  // || !(c + value).equals(c + s1[i])
    11.                 map.put(c, s1[i]);
    12.             }else {
    13.                 if (!value.equals(s1[i])){
    14.                     return false;
    15.                 }
    16.             }
    17.         }
    18.         ArrayList list = new ArrayList<>();
    19.         for (Map.Entry entry : map.entrySet()) {
    20.             if (list.contains(entry.getValue())){
    21.                 return false;
    22.             }
    23.             list.add(entry.getValue());
    24.         }
    25.         return true;
    26.     }

    方法2：

    1.     public boolean wordPattern(String pattern, String s) {
    2.         String[] data =s.split(" ");
    3.         if(data.length!=pattern.length()){
    4.             return false;
    5.         }
    6.         String[] p2w = new String[26];
    7.         Map w2p = new HashMap<>();
    8.         for (int i = 0; i < pattern.length(); i++) {
    9.             char c = pattern.charAt(i);
    10.             if (p2w[c - 'a'] == null) {
    11.                 p2w[c - 'a'] = data[i];
    12.             } else if (!p2w[c - 'a'].equals(data[i])) {
    13.                 return false;
    14.  
    15.             }
    16.             if (w2p.get(data[i]) == null) {
    17.                 w2p.put(data[i], c);
    18.             } else if (w2p.get(data[i]).charValue() != c) {
    19.                 return false;
    20.             }
    21.         }
    22.  
    23.         return true;
    24.     }

    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）

    1.     public boolean isAnagram(String s, String t) {
    2.         if (s.length() != t.length()){
    3.             return false;
    4.         }
    5.         int[] chars = new int[26];
    6.         for (int i = 0; i < s.length(); i++) {
    7.             char c = s.charAt(i);
    8.             chars[c - 'a']++;
    9.         }
    10.         for (int i = 0; i < t.length(); i++) {
    11.             char c = t.charAt(i);
    12.             chars[c - 'a']--;
    13.         }
    14.         for (int i = 0; i < 26; i++) {
    15.             if (chars[i] != 0){
    16.                 return false;
    17.             }
    18.         }
    19.         return true;
    20.     }

    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）

    1.     public static List> groupAnagrams(String[] strs) {
    2.         ArrayList> result = new ArrayList<>();
    3.         HashMap> map = new HashMap<>();
    4.         for (int i = 0; i < strs.length; i++) {
    5.             char[] chars = strs[i].toCharArray();
    6.             Arrays.sort(chars);
    7.             String key = Arrays.toString(chars);
    8.             List value = map.get(key);
    9.             if (value == null){
    10.                 value = new ArrayList<>();
    11.             }
    12.             value.add(strs[i]);
    13.             map.put(key, value);
    14.         }
    15.         // List> collect = new ArrayList<>(map.values());
    16.         for (Map.Entry> entry : map.entrySet()) {
    17.             result.add(entry.getValue());
    18.         }
    19.         return result;
    20.     }

    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）

    1.     public static int[] twoSum(int[] nums, int target) {
    2.         int[] result = new int[2];
    3.         int left = 0;
    4.         int right = +1;
    5.         for (int i = 0; i < nums.length; i++) {
    6.             left = i;
    7.             right = left +1;
    8.             while (right < nums.length){
    9.                 if (nums[left] + nums[right] == target){
    10.                     result[0] = left;
    11.                     result[1] = right;
    12.                     break;
    13.                 }
    14.                 right++;
    15.             }
    16.             left++;
    17.         }
    18.         return result;
    19.     }

    方法2：（0ms）

    1.     public static int[] twoSum(int[] nums, int target) {
    2.         if (nums.length == 2) {
    3.             return new int[]{0, 1};
    4.         }
    5.  
    6.         for (int i = 0, j = 1; j < nums.length; ++i) {
    7.             if (i + j >= nums.length) {
    8.                 i = -1;
    9.                 j++;
    10.             } else if (nums[i] + nums[i + j] == target) {
    11.                 return new int[]{i, j + i};
    12.             }
    13.         }
    14.         return new int[]{};
    15.     }

    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）

    1.     public static boolean isHappy(int n) {
    2.         int m = n;
    3.         ArrayList list = new ArrayList<>();
    4.         while (!list.contains(m)){
    5.             list.add(m);
    6.             if (m == 1){
    7.                 return true;
    8.             }
    9.             int sum = 0;
    10.             String str = m + "";
    11.             int length = str.length();
    12.             for (int i = 0; i < length; i++) {
    13.                 sum += Math.pow(Integer.parseInt(str.charAt(i) + "") , 2);
    14.             }
    15.             m = sum;
    16.  
    17.         }
    18.         return false;
    19.     }

    方法2：（0ms）

    1.     public int squareSum(int n) {
    2.         int sum = 0;
    3.         while(n > 0){
    4.             int digit = n % 10;
    5.             sum += digit * digit;
    6.             n /= 10;
    7.         }
    8.         return sum;
    9.     }
    10.  
    11.     public boolean isHappy(int n) {
    12.         int slow = n, fast = squareSum(n);
    13.         while (slow != fast){
    14.             slow = squareSum(slow);
    15.             fast = squareSum(squareSum(fast));
    16.         };
    17.         return slow == 1;
    18.     }

    方法2：（1ms）

    1.     public boolean isHappy(int n) 
    2.     {
    3.         Set set = new HashSet<>();
    4.         while(n!=1  &&  !set.contains(n))
    5.         {
    6.             set.add(n);
    7.             n=cal(n);
    8.         }
    9.         return n==1;
    10.     }
    11.     public int cal(int nn)
    12.     {
    13.         int sum=0;
    14.         while(nn!=0)
    15.         {
    16.             sum+=(nn%10)*(nn%10);
    17.             nn/=10;
    18.         }
    19.         return sum;
    20.     }

    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：

    1.         if (nums.length == 1){
    2.             return false;
    3.         }
    4.         boolean flag = false;
    5.         int exist = 0;
    6.         for (int i = 0; i < nums.length - 1; i++) {
    7.             for (int j = i + 1; j <= Math.min(i + k, nums.length-1); j++) {
    8.                 if (nums[i]  == nums[j]){
    9.                     flag = true;
    10.                     exist = 1;
    11.                     break;
    12.                 }
    13.             }
    14.             if (exist == 1){
    15.                 break;
    16.             }
    17.         }
    18.         return flag;
    19.     }

    方法2：

    1.     public boolean containsNearbyDuplicate(int[] nums, int k) {
    2.         Set set= new HashSet<>();
    3.         for(int i = 0;i
    4.             if(i>k){
    5.                 set.remove(nums[i-k-1]);
    6.             }
    7.             if(!set.add(nums[i])){
    8.                 return true;
    9.             }
    10.         }
    11.         return false;
    12.     }

    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：

    1.     public static int longestConsecutive(int[] nums) {
    2.         if (nums.length == 0){
    3.             return 0;
    4.         }else if (nums.length == 1){
    5.             return 1;
    6.         }
    7.         Arrays.sort(nums);
    8.         System.out.println(Arrays.toString(nums));
    9.         TreeSet set = new TreeSet<>();
    10.         int index = 1;
    11.         for (int i = 1; i < nums.length; i++) {
    12.             if (nums[i] == nums[i - 1] +1){
    13.                 index++;
    14.                 if (i == nums.length - 1){
    15.                     set.add(index);
    16.                 }
    17.             }else if (nums[i] == nums[i - 1]){
    18.                 set.add(index);
    19.                 continue;
    20.             }
    21.             else {
    22.                 set.add(index);
    23.                 index = 1;
    24.             }
    25.         }
    26.         System.out.println(set);
    27.         return set.last();
    28.     }

  • 相关阅读:
    【shell】pis_monitor.sh
    typename关键字详解(消除歧义)
    mysql 分析事务锁涉及到的几张表
    开始MySQL之路——MySQL存储引擎概念
    java String split 方法丢弃末尾的空白字符问题
    第23期 | GPTSecurity周报
    ATA-P0102压电叠堆放大器技术指标
    Elasticsearch（一）：ES简介及其发展历史与ELK
    C++【IO流】
    基础知识笔记：协程基础元素
  • 原文地址：https://blog.csdn.net/linping_wong/article/details/136852504