散列表相关知识及编程练习总结

目录

一、背景知识

二、应用举例

（一）Spring框架或其他框架中的应用举例

（二）实际开发中的应用举例

三、相关编程练习

（一）无重复字符的最长子串（Longest Substring Without Repeating Characters）

（二）有效的数独（Valid Sudoku）

（三）最小覆盖子串（Minimum Window Substring）

（四）字母异位词分组（Group Anagrams）

（五）有效的字母异位词（Valid Anagram）

（六）找到字符串中所有字母异位词（Find All Anagrams in a String）

（七）LRU缓存机制（LRU Cache）

（八）多数元素（Majority Element）

（九）重复的DNA序列（Repeated DNA Sequences）

（十）快乐数（Happy Number）

备注：最优解法-Floyd 判圈算法

（十一）存在重复元素（Contains Duplicate）

（十二）存在重复元素 II（Contains Duplicate II）

（十三）单词规律（Word Pattern）

（十四）前K个高频元素（Top K Frequent Elements）

（十五）字符串中的第一个唯一字符（First Unique Character in a String）

（十六）四数相加 II（4Sum II）

（十七）和为K的子数组（Subarray Sum Equals K）

（十八）最常见的单词（Most Common Word）

（十九）同构字符串（Isomorphic Strings）

（二十）两个数组的交集（Intersection of Two Arrays）

（二一）两个数组的交集 II（Intersection of Two Arrays II）

（二二）分糖果（Distribute Candies）

（二三）宝石与石头（Jewels and Stones）

干货分享，感谢您的阅读！祝你编程题必过！

一、背景知识

散列（Hashing）是一种将任意长度的数据映射为固定长度值的技术。散列函数（Hash function）是执行这种映射的算法，它将原始数据（也称为消息或输入）作为输入，并生成固定长度的输出，称为散列值（Hash value）。这个过程通常被称为“散列”或“哈希”。

当我们使用散列函数时，需要了解以下基本概念：

  1. 输入数据：输入数据是指需要进行散列的数据，也称为消息或明文。输入数据可以是任意长度的二进制数据，例如文本、图像、音频等。
  2. 散列值：散列值是指散列函数对输入数据计算后得到的固定长度的二进制值。通常，散列值的长度固定为128、160、256、384或512位。散列值也称为哈希值。
  3. 散列函数的基本要求：散列函数需要满足以下三个基本要求：一致性、不可逆性和抗碰撞性。
  • 一致性：对于同样的输入，散列函数应该始终返回相同的输出值。
  • 不可逆性：对于不同的输入数据，生成的散列值应该是唯一的，但是从散列值推导出原始数据应该是非常困难的。
  • 抗碰撞性：对于不同的输入数据，生成的散列值应该是不同的，但是在输入数据稍有不同的情况下，生成的散列值应该有很大的区别。

散列函数的基本要求决定了散列函数的应用范围，例如数据完整性检查、数字签名、安全认证等。

总的来说，使用散列函数一般需要进行以下两个步骤：

  1. 生成散列值：将输入数据通过散列函数转换为一段固定长度的散列值。生成散列值的过程一般可以通过散列函数库或编程语言提供的相关函数来实现。
  2. 验证散列值的正确性：在需要验证散列值正确性的场景下，一般需要将原始数据重新进行散列计算，并将计算得到的散列值与预先计算好的散列值进行比较。如果两个散列值相同，则说明原始数据没有被篡改或损坏。

Java中提供了相关的类库来实现散列函数的计算和验证。以下示例代码使用Java的MessageDigest类来计算SHA-256散列值。

  1. package org.zyf.javabasic.letcode.hash;
  2.  
  3. import java.security.MessageDigest;
  4. import java.security.NoSuchAlgorithmException;
  5.  
  6. /**
  7.  * @author yanfengzhang
  8.  * @description 首先指定输入数据为"Hello World"，然后通过MessageDigest类创建散列函数对象，
  9.  * 指定散列函数为SHA-256，接着通过update()方法将输入数据添加到散列函数中，
  10.  * 并通过digest()方法计算散列值，最后将散列值转换为十六进制字符串并输出。
  11.  * 
  12.  * 验证散列值的正确性可以通过类似的方式进行，即重新计算输入数据的散列值并将其与之前计算得到的散列值进行比较。
  13.  * 可以将上述代码中的"Hello World"替换为其他字符串，重新计算散列值，
  14.  * 并将其与之前计算得到的散列值进行比较，判断原始数据是否被篡改或损坏。
  15.  * @date 2023/4/9  16:51
  16.  */
  17. public class HashFunctionExample {
  18.     public static void main(String[] args) {
  19.         try {
  20.             /*输入数据*/
  21.             String data = "Hello World";
  22.  
  23.             /*创建MessageDigest对象，指定散列函数为SHA-256*/
  24.             MessageDigest md = MessageDigest.getInstance("SHA-256");
  25.  
  26.             /*计算散列值*/
  27.             md.update(data.getBytes());
  28.             byte[] hash = md.digest();
  29.  
  30.             /*将字节数组转换为十六进制字符串*/
  31.             StringBuilder hexString = new StringBuilder();
  32.             for (byte b : hash) {
  33.                 hexString.append(String.format("%02X", b));
  34.             }
  35.  
  36.             /*输出散列值*/
  37.             System.out.println(hexString.toString());
  38.  
  39.         } catch (NoSuchAlgorithmException e) {
  40.             e.printStackTrace();
  41.         }
  42.     }
  43. }
  44.

其算法可简单用下图示例：（图来自图灵社区）

更多基础的散列知识简单统计可见：散列技术自问自答

二、应用举例

（一）Spring框架或其他框架中的应用举例

散列表在许多其他框架和库中也有广泛的应用。下面是一些例子：

  1. Java集合框架中的HashMap、LinkedHashMap、HashTable和ConcurrentHashMap等集合类都是使用散列表实现的。
  2. Redis中的Hash类型就是使用散列表来实现的。Redis中的散列表叫做哈希表，可以用于存储键值对，每个哈希表最多可以包含232-1个键值对。
  3. Hadoop中的MapReduce框架就是基于散列表的。在Map阶段，MapReduce框架将输入数据分成若干个小块，每个小块由Map任务处理，Map任务使用散列表来存储中间结果。在Reduce阶段，MapReduce框架将中间结果进行合并，使用散列表来统计相同键值对的数量。
  4. Couchbase是一个基于散列表的内存数据库，可以使用它来存储键值对，每个键值对的值可以是任何数据类型，包括字符串、数字、数组、对象等。
  5. Lucene是一个文本搜索引擎，可以使用它来构建全文搜索引擎。Lucene内部使用了散列表来存储倒排索引，通过倒排索引可以快速地定位包含特定单词的文档。
  6. 在 Spring 框架中，散列（哈希）算法主要应用在 Spring Security 模块中，用于加密用户密码并进行安全认证。Spring Security 为用户提供了多种加密算法，包括 SHA-256、BCrypt、PBKDF2、SCrypt 等，这些算法都是基于哈希算法实现的。具体来说，在 Spring Security 中，通过在注册时使用哈希算法对用户密码进行加密，然后将加密后的密码存储在数据库中。在用户登录时，Spring Security 会通过哈希算法将用户输入的密码进行加密，然后与数据库中的密码进行比较，从而完成安全认证。由于哈希算法的特性，即使数据库被攻击者窃取，也无法直接获得用户的密码明文。

（二）实际开发中的应用举例

哈希表在实际开发中有广泛应用，以下是几个例子：

  1. 缓存方面。缓存是应用哈希表最常见的场景之一。缓存中存储的数据可以是任意类型的，因此使用哈希表将其按照键值对的形式存储起来是非常方便的。当需要访问某个数据时，可以通过键值快速获取到对应的值，而无需进行耗时的查询操作。
  2. 路由方面。路由是另一个常见的应用场景。在路由过程中，需要将请求映射到对应的处理程序或服务。为了实现这一目的，可以使用哈希表将请求与对应的处理程序或服务建立映射关系。当收到请求时，可以通过哈希表快速找到对应的处理程序或服务，从而实现请求的路由。
  3. 计数方面。计数是哈希表的又一个常见应用场景。在实际开发中，我们需要对某些事件或数据进行计数。例如，我们可能需要统计网站的访问量，或者统计用户的行为次数。在这种情况下，可以使用哈希表将事件或数据的值作为键，将计数器作为值，从而快速进行计数。
  4. 安全方面。在安全领域中，哈希表也得到了广泛应用。例如，密码哈希可以通过哈希表来实现。在密码哈希中，用户输入的密码会被哈希成一个固定长度的字符串，然后存储在哈希表中。当用户再次登录时，系统会将用户输入的密码哈希后与之前存储的密码哈希进行比对，从而验证用户的身份。

三、相关编程练习

（一）无重复字符的最长子串（Longest Substring Without Repeating Characters）

题目描述：给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例1:输入: "abcabcbb"     输出: 3

解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例2:输入: "bbbbb"          输出: 1

解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例3:输入: "pwwkew"       输出: 3

解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解题思路

该问题可以使用滑动窗口的方法来解决。

首先，我们需要明确什么是滑动窗口。滑动窗口指的是一个可以滑动的固定长度的窗口，通常用来解决子串或者子数组的问题。

对于本题，我们可以使用滑动窗口来维护一个无重复字符的子串。具体实现时，可以定义两个指针 left 和 right 分别表示无重复字符子串的左右边界。我们用哈希表来记录每个字符出现的位置，以便更新左指针的位置。

具体实现思路如下：

  1. 初始化 left 和 right 为 0，用一个哈希表来记录每个字符出现的位置。
  2. 从 left 开始向右遍历字符串，遍历过程中维护一个当前无重复字符子串的哈希表，并记录当前子串的最大长度。
  3. 如果当前字符 s[right] 在子串中出现过，则需要更新 left 的位置。具体来说，我们将 left 移动到 s[right] 上一次出现的位置的下一个位置。
  4. 在遍历过程中更新最大长度，并将 s[right] 的位置记录到哈希表中。
  5. 遍历完成后，返回最大长度即可。

该方法的时间复杂度为 O(n)，空间复杂度为 O(min(m,n))，其中 m 表示字符集大小，n 表示字符串长度。

具体代码展示

  1. package org.zyf.javabasic.letcode.hash;
  2.  
  3. import java.util.HashMap;
  4. import java.util.Map;
  5.  
  6. /**
  7.  * @author yanfengzhang
  8.  * @description 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
  9.  * @date 2023/4/9  17:58
  10.  */
  11. public class LongestSubstringWithoutRepeating {
  12.  
  13.     /**
  14.      * 具体实现思路如下：
  15.      * 初始化 left 和 right 为 0，用一个哈希表来记录每个字符出现的位置。
  16.      * 从 left 开始向右遍历字符串，遍历过程中维护一个当前无重复字符子串的哈希表，并记录当前子串的最大长度。
  17.      * 如果当前字符 s[right] 在子串中出现过，则需要更新 left 的位置。具体来说，我们将 left 移动到 s[right] 上一次出现的位置的下一个位置。
  18.      * 在遍历过程中更新最大长度，并将 s[right] 的位置记录到哈希表中。
  19.      * 遍历完成后，返回最大长度即可。
  20.      * 该方法的时间复杂度为 O(n)，空间复杂度为 O(min(m,n))，其中 m 表示字符集大小，n 表示字符串长度。
  21.      */
  22.     public int lengthOfLongestSubstring(String s) {
  23.         if (s == null || s.length() == 0) {
  24.             return 0;
  25.         }
  26.  
  27.         int n = s.length();
  28.         /*最大长度*/
  29.         int maxLen = 0;
  30.         /*左指针*/
  31.         int left = 0;
  32.         /*哈希表，记录每个字符的位置*/
  33.         Map map = new HashMap<>();
  34.  
  35.         /*右指针从 0 开始向右遍历字符串*/
  36.         for (int right = 0; right < n; right++) {
  37.             /*获取当前字符*/
  38.             char c = s.charAt(right);
  39.             /*如果当前字符在子串中出现过，则需要更新左指针的位置*/
  40.             if (map.containsKey(c)) {
  41.                 /*左指针移动到当前字符上一次出现的位置的下一个位置*/
  42.                 left = Math.max(left, map.get(c) + 1);
  43.             }
  44.             /*记录当前字符的位置*/
  45.             map.put(c, right);
  46.             /*更新最大长度*/
  47.             maxLen = Math.max(maxLen, right - left + 1);
  48.         }
  49.         /*返回最大长度*/
  50.         return maxLen;
  51.     }
  52.  
  53.     public static void main(String[] args) {
  54.         String s = "abcabcbb";
  55.         int res = new LongestSubstringWithoutRepeating().lengthOfLongestSubstring(s);
  56.             /*该代码输出的结果应该为3，因为在字符串 "abcabcbb" 中，
  57.             无重复字符的最长子串为 "abc"，长度为3。*/
  58.         System.out.println(res);
  59.     }
  60.  
  61. }

（二）有效的数独（Valid Sudoku）

题目描述：判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可：

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

 示例:

 提示：

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字或者 '.'
  • 题目数据保证输入数独仅有一个解。

来源：力扣（LeetCode）

链接：力扣

解题思路

该问题可以使用哈希表实现，对于每个数字和每个行、列和子数独，分别记录是否出现过，如果出现过则说明不是有效的数独。

具体实现思路如下：

  1. 分别使用三个二维布尔数组记录每个数字在每行、每列、每个3x3子数独中是否出现过。数组初始化为false。
  2. 遍历数独，如果当前位置是数字，则在对应的行、列、子数独的布尔数组中标记该数字已出现。
  3. 每次标记前先检查当前数字是否已经在对应的行、列、子数独中出现过，如果出现过则说明不是有效的数独。
  4. 遍历结束后，如果没有出现过重复数字，则说明是有效的数独。

该算法时间复杂度为O(81)，空间复杂度为O(27)，具有较高的时间和空间效率。

具体代码展示

  1. package org.zyf.javabasic.letcode.hash;
  2.  
  3. /**
  4.  * @author yanfengzhang
  5.  * @description 判断一个 9x9 的数独是否有效。
  6.  * @date 2023/4/9  18:11
  7.  */
  8. public class ValidSudoku {
  9.  
  10.     /**
  11.      * 具体实现思路如下：
  12.      * 
  13.      * 分别使用三个二维布尔数组记录每个数字在每行、每列、每个3x3子数独中是否出现过。数组初始化为false。
  14.      * 遍历数独，如果当前位置是数字，则在对应的行、列、子数独的布尔数组中标记该数字已出现。
  15.      * 每次标记前先检查当前数字是否已经在对应的行、列、子数独中出现过，如果出现过则说明不是有效的数独。
  16.      * 遍历结束后，如果没有出现过重复数字，则说明是有效的数独。
  17.      * 
  18.      * 该算法时间复杂度为O(81)，空间复杂度为O(27)，具有较高的时间和空间效率。
  19.      */
  20.     public boolean isValidSudoku(char[][] board) {
  21.         /*行*/
  22.         boolean[][] rows = new boolean[9][9];
  23.         /*列*/
  24.         boolean[][] cols = new boolean[9][9];
  25.         /*子数独*/
  26.         boolean[][] boxes = new boolean[9][9];
  27.  
  28.         /*遍历数独中的每个数字*/
  29.         for (int i = 0; i < 9; i++) {
  30.             for (int j = 0; j < 9; j++) {
  31.                 if (board[i][j] != '.') {
  32.                     /*当前数字对应的索引*/
  33.                     int num = board[i][j] - '1';
  34.                     /*当前数字所在的子数独编号*/
  35.                     int boxIndex = (i / 3) * 3 + j / 3;
  36.  
  37.                     /*若该数字在对应的行、列或子数独中已经出现过，则说明不是有效的数独*/
  38.                     if (rows[i][num] || cols[j][num] || boxes[boxIndex][num]) {
  39.                         return false;
  40.                     }
  41.  
  42.                     /*标记该数字在对应的行、列和子数独中已经出现过*/
  43.                     rows[i][num] = true;
  44.                     cols[j][num] = true;
  45.                     boxes[boxIndex][num] = true;
  46.                 }
  47.             }
  48.         }
  49.  
  50.         /*遍历结束没有发现重复数字，则说明是有效的数独，返回true*/
  51.         return true;
  52.     }
  53.  
  54.     public static void main(String[] args) {
  55.         char[][] board = {
  56.                 {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
  57.                 {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
  58.                 {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
  59.                 {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
  60.                 {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
  61.                 {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
  62.                 {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
  63.                 {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
  64.                 {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
  65.         };
  66.         boolean isValid = new ValidSudoku().isValidSudoku(board);
  67.         System.out.println(isValid);
  68.     }
  69.  
  70. }

（三）最小覆盖子串（Minimum Window Substring）

题目描述：给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：输入: S = "ADOBECODEBANC", T = "ABC".     输出: "BANC"

说明：

  • 如果 S 中不存这样的子串，则返回空字符串 ""。
  • 如果 S 中存在这样的子串，我们保证它是唯一的答案。

来源：力扣（LeetCode）

链接：力扣

解题思路

该问题的最优解法是滑动窗口。

算法步骤如下：

  • 1.创建两个哈希表：need 和 window，其中 need 用于存储 t 中包含的字符以及每个字符的个数，window 用于存储当前窗口中包含的字符以及每个字符的个数。
  • 2.使用 left 和 right 两个指针表示窗口的左右边界。right 向右移动，直到窗口包含了 t 中所有的字符。此时记录窗口的大小和位置。
  • 3.移动 left 指针，尝试缩小窗口的大小，直到窗口中的字符串不再完全包含 t 中的所有字符。在每次移动 left 指针时，需要将 window 中对应字符的个数减去 1，并更新窗口的大小和位置。
  • 4.重复步骤 2 和 3，直到 right 指针到达 s 的末尾。

算法分析：

  • 时间复杂度：O(|s|+|t|)，其中 |s| 和 |t| 分别表示字符串 s 和 t 的长度。需要遍历两个字符串一次，因此时间复杂度是线性的。
  • 空间复杂度：O(|s|+|t|)。需要使用两个哈希表来存储字符以及字符出现的次数，因此需要额外的空间。

具体代码展示

  1. package org.zyf.javabasic.letcode.hash;
  2.  
  3. import java.util.HashMap;
  4. import java.util.Map;
  5.  
  6. /**
  7.  * @author yanfengzhang
  8.  * @description 给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。
  9.  * @date 2023/4/9  18:21
  10.  */
  11. public class MinimumWindowSubstring {
  12.  
  13.     /**
  14.      * 1.创建两个哈希表：need 和 window，其中 need 用于存储 t 中包含的字符以及每个字符的个数，window 用于存储当前窗口中包含的字符以及每个字符的个数。
  15.      * 2.使用 left 和 right 两个指针表示窗口的左右边界。right 向右移动，直到窗口包含了 t 中所有的字符。此时记录窗口的大小和位置。
  16.      * 3.移动 left 指针，尝试缩小窗口的大小，直到窗口中的字符串不再完全包含 t 中的所有字符。在每次移动 left 指针时，需要将 window 中对应字符的个数减去 1，并更新窗口的大小和位置。
  17.      * 4.重复步骤 2 和 3，直到 right 指针到达 s 的末尾。
  18.      */
  19.     public String minWindow(String s, String t) {
  20.         /*need 哈希表用于存储 t 中包含的字符以及每个字符的个数*/
  21.         Map need = new HashMap<>();
  22.         /*window 哈希表用于存储当前窗口中包含的字符以及每个字符的个数*/
  23.         Map window = new HashMap<>();
  24.         /*初始化 need 哈希表*/
  25.         for (char c : t.toCharArray()) {
  26.             need.put(c, need.getOrDefault(c, 0) + 1);
  27.         }
  28.         /*左右指针*/
  29.         int left = 0, right = 0;
  30.         /*valid 表示当前窗口中已经包含了 t 中的字符个数*/
  31.         int valid = 0;
  32.         /*记录最小覆盖子串的起始位置和长度*/
  33.         int start = 0, len = Integer.MAX_VALUE;
  34.         /*当右指针未到达 s 的末尾时循环*/
  35.         while (right < s.length()) {
  36.             /*取出当前窗口的右边界字符*/
  37.             char c = s.charAt(right);
  38.             /*右指针右移*/
  39.             right++;
  40.             /*如果 c 是 t 中的字符*/
  41.             if (need.containsKey(c)) {
  42.                 /*将 c 加入到 window 哈希表中*/
  43.                 window.put(c, window.getOrDefault(c, 0) + 1);
  44.                 /*如果 window 中 c 的数量等于 need 中 c 的数量*/
  45.                 if (window.get(c).equals(need.get(c))) {
  46.                     /*更新 valid 值*/
  47.                     valid++;
  48.                 }
  49.             }
  50.             /*当前窗口已经包含了 t 中的所有字符时*/
  51.             while (valid == need.size()) {
  52.                 /*更新最小覆盖子串的起始位置和长度*/
  53.                 if (right - left < len) {
  54.                     start = left;
  55.                     len = right - left;
  56.                 }
  57.                 /*取出当前窗口的左边界字符*/
  58.                 char d = s.charAt(left);
  59.                 /*左指针右移*/
  60.                 left++;
  61.                 /*如果 d 是 t 中的字符*/
  62.                 if (need.containsKey(d)) {
  63.                     /*如果 window 中 d 的数量等于 need 中 d 的数量*/
  64.                     if (window.get(d).equals(need.get(d))) {
  65.                         /*更新 valid 值*/
  66.                         valid--;
  67.                     }
  68.                     /*将 d 从 window 中减少一个*/
  69.                     window.put(d, window.get(d) - 1);
  70.                 }
  71.             }
  72.         }
  73.         /*返回最小覆盖子串*/
  74.         return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
  75.     }
  76.  
  77.     public static void main(String[] args) {
  78.         String s = "ADOBECODEBANC";
  79.         String t = "ABC";
  80.         String res = new MinimumWindowSubstring().minWindow(s, t);
  81.         /*输出 "BANC"*/
  82.         System.out.println(res);
  83.     }
  84.  
  85. }

（四）字母异位词分组（Group Anagrams）

题目描述：给定一个字符串数组 strs，将由相同字母异位词组成的组合在一起，返回这些组合。可以按任意顺序返回答案。

字母异位词指字母相同，但排列不同的字符串。

示例 1:输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

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

示例 2:输入: strs = [""]         输出: [[""]]

示例 3:输入: strs = ["a"]       输出: [["a"]]

提示：

  • 1 <= strs.length <= 10^4
  • 0 <= strs[i].length <= 100
  • strs[i] 仅包含小写字母

解题思路

使用哈希表思路

将每个字符串排序，相同排序后的字符串即为字母异位词，将其分到同一组中。具体实现时，可以使用哈希表来存储每个排序后的字符串对应的原始字符串集合。

时间复杂度为 O(nklogk)，其中 n 是字符串数组的长度，k 是字符串的最大长度。主要的时间消耗在排序操作上，排序的时间复杂度为 O(klogk)，而对于每个字符串，需要进行一次排序，因此总时间复杂度为 O(nklogk)。

空间复杂度为 O(nk)，其中 n 是字符串数组的长度，k 是字符串的最大长度。空间复杂度主要取决于哈希表存储的空间。

具体代码展示

  1. package org.zyf.javabasic.letcode.hash;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.Arrays;
  5. import java.util.HashMap;
  6. import java.util.List;
  7. import java.util.Map;
  8.  
  9. /**
  10.  * @author yanfengzhang
  11.  * @description 给定一个字符串数组 strs，将由相同字母异位词组成的组合在一起，返回这些组合。可以按任意顺序返回答案。
  12.  * 字母异位词指字母相同，但排列不同的字符串。
  13.  * @date 2023/4/9  18:35
  14.  */
  15. public class GroupAnagrams {
  16.  
  17.     /**
  18.      * 使用哈希表思路
  19.      * 将每个字符串排序，相同排序后的字符串即为字母异位词，将其分到同一组中。
  20.      * 具体实现时，可以使用哈希表来存储每个排序后的字符串对应的原始字符串集合。
  21.      */
  22.     public List> groupAnagrams(String[] strs) {
  23.         Map> map = new HashMap<>();
  24.         for (String s : strs) {
  25.             /*将字符串排序后作为键*/
  26.             char[] ch = s.toCharArray();
  27.             Arrays.sort(ch);
  28.             String key = new String(ch);
  29.             /*将原字符串添加到对应的值列表中*/
  30.             if (!map.containsKey(key)) {
  31.                 map.put(key, new ArrayList());
  32.             }
  33.             map.get(key).add(s);
  34.         }
  35.         /*返回哈希表中所有的值列表*/
  36.         return new ArrayList<>(map.values());
  37.     }
  38.  
  39.     public static void main(String[] args) {
  40.         String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
  41.         List> res = new GroupAnagrams().groupAnagrams(strs);
  42.         /*[[eat, tea, ate], [tan, nat], [bat]]*/
  43.         System.out.println(res);
  44.     }
  45.  
  46. }

（五）有效的字母异位词（Valid Anagram）

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

示例 1:输入: s = "anagram", t = "nagaram".     输出: true

示例 2:输入: s = "rat", t = "car".                        输出: false

说明:你可以假设字符串只包含小写字母。

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

解题思路

这道题可以使用哈希表来解决。具体实现步骤如下：

  1. 创建一个哈希表，用于记录每个字符出现的次数。
  2. 遍历字符串 s，将其中的每个字符及其出现次数加入哈希表。
  3. 遍历字符串 t，对于其中的每个字符，在哈希表中将其出现次数减一。
  4. 如果在哈希表中对应字符的出现次数已经为 0，说明字符串 t 中出现了一个字符串 s 中不存在的字符，直接返回 false。
  5. 如果遍历字符串 t 后没有出现不相等的字符，返回 true

算法分析：

  • 时间复杂度：O(n)，其中 n 是字符串 s 和字符串 t 的长度。需要遍历字符串 s 和字符串 t 各一次，因此时间复杂度是线性的。
  • 空间复杂度：O(n)，需要使用哈希表来记录每个字符出现的次数，因此需要额外的空间。

注：另外，本问题也可以使用排序的方法解决，时间复杂度也是 O(n log n)，空间复杂度为 O(1)，但排序方法需要修改字符串，因此不太实用，这里不再赘述。

具体代码展示

  1. package org.zyf.javabasic.letcode.hash;
  2.  
  3. import java.util.HashMap;
  4. import java.util.Map;
  5.  
  6. /**
  7.  * @author yanfengzhang
  8.  * @description 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
  9.  * @date 2023/4/9  18:46
  10.  */
  11. public class ValidAnagram {
  12.     /**
  13.      * 这道题可以使用哈希表来解决。具体实现步骤如下：
  14.      * 
  15.      * 创建一个哈希表，用于记录每个字符出现的次数。
  16.      * 遍历字符串 s，将其中的每个字符及其出现次数加入哈希表。
  17.      * 遍历字符串 t，对于其中的每个字符，在哈希表中将其出现次数减一。
  18.      * 如果在哈希表中对应字符的出现次数已经为 0，说明字符串 t 中出现了一个字符串 s 中不存在的字符，直接返回 false。
  19.      * 如果遍历字符串 t 后没有出现不相等的字符，返回 true
  20.      */
  21.     public boolean isAnagram(String s, String t) {
  22.         /*如果两个字符串的长度不相等，直接返回 false*/
  23.         if (s.length() != t.length()) {
  24.             return false;
  25.         }
  26.         /*创建一个哈希表，用于记录每个字符出现的次数*/
  27.         Map map = new HashMap<>();
  28.         /*遍历字符串 s，将其中的每个字符及其出现次数加入哈希表*/
  29.         for (int i = 0; i < s.length(); i++) {
  30.             char c = s.charAt(i);
  31.             map.put(c, map.getOrDefault(c, 0) + 1);
  32.         }
  33.         /*遍历字符串 t，对于其中的每个字符，在哈希表中将其出现次数减一*/
  34.         /*如果在哈希表中对应字符的出现次数已经为 0，说明字符串 t 中出现了一个字符串 s 中不存在的字符，直接返回 false*/
  35.         for (int i = 0; i < t.length(); i++) {
  36.             char c = t.charAt(i);
  37.             if (!map.containsKey(c)) {
  38.                 return false;
  39.             }
  40.             int count = map.get(c);
  41.             if (count == 0) {
  42.                 return false;
  43.             }
  44.             map.put(c, count - 1);
  45.         }
  46.         /*如果遍历字符串 t 后没有出现不相等的字符，返回 true*/
  47.         return true;
  48.     }
  49.  
  50.     public static void main(String[] args) {
  51.         String s = "anagram";
  52.         String t = "nagaram";
  53.         /*输出 true*/
  54.         System.out.println(new ValidAnagram().isAnagram(s, t));
  55.  
  56.         String s2 = "rat";
  57.         String t2 = "car";
  58.         /*输出 false*/
  59.         System.out.println(new ValidAnagram().isAnagram(s2, t2));
  60.     }
  61.  
  62. }

（六）找到字符串中所有字母异位词（Find All Anagrams in a String）

题目描述：给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

示例 1:输入:s: "cbaebabacd" p: "abc".   输出:[0, 6]

解释:起始索引等于 0 的子串是 "cba"，它是 "abc" 的字母异位词。

        起始索引等于 6 的子串是 "bac"，它是 "abc" 的字母异位词。

示例 2:输入:s: "abab" p: "ab".                输出:[0, 1, 2]

解释:起始索引等于 0 的子串是 "ab"，它是 "ab" 的字母异位词。

        起始索引等于 1 的子串是 "ba"，它是 "ab" 的字母异位词。

        起始索引等于 2 的子串是 "ab"，它是 "ab" 的字母异位词。

来源：力扣（LeetCode）

链接：力扣

解题思路

该问题可以通过哈希表来解决。具体步骤如下：

  1. 创建一个哈希表，用于存储每个字符在目标字符串 p 中出现的次数。
  2. 初始化窗口指针 left 和 right，分别指向字符串 s 的开头。
  3. 进入循环，不断移动右指针，每次将右指针指向的字符在哈希表中的计数器减 1。
  4. 当发现某个字符在哈希表中的计数器等于 0 时，说明该字符已经在窗口中出现了足够多的次数，可以将左指针向右移动，缩小窗口的大小。
  5. 如果发现当前窗口的大小等于 p 的长度，说明找到了一个字母异位词，将左指针加入结果集中。
  6. 重复步骤 3 到 5，直到右指针移动到字符串 s 的末尾。

时间复杂度分析：在最坏情况下，需要对字符串 s 中的每个字符进行两次操作，因此时间复杂度为 O(n)，其中 n 是字符串 s 的长度。同时，由于只用了常数个额外变量，空间复杂度为 O(1)。

具体代码展示

  1. package org.zyf.javabasic.letcode.hash;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.List;
  5.  
  6. /**
  7.  * @author yanfengzhang
  8.  * @description 给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
  9.  * 字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
  10.  * @date 2023/4/9  19:01
  11.  */
  12. public class FindAllAnagrams {
  13.  
  14.     /**
  15.      * 该问题可以通过哈希表来解决。具体步骤如下：
  16.      * 
  17.      * 创建一个哈希表，用于存储每个字符在目标字符串 p 中出现的次数。
  18.      * 初始化窗口指针 left 和 right，分别指向字符串 s 的开头。
  19.      * 进入循环，不断移动右指针，每次将右指针指向的字符在哈希表中的计数器减 1。
  20.      * 当发现某个字符在哈希表中的计数器等于 0 时，说明该字符已经在窗口中出现了足够多的次数，可以将左指针向右移动，缩小窗口的大小。
  21.      * 如果发现当前窗口的大小等于 p 的长度，说明找到了一个字母异位词，将左指针加入结果集中。
  22.      * 重复步骤 3 到 5，直到右指针移动到字符串 s 的末尾。
  23.      */
  24.     public List findAnagrams(String s, String p) {
  25.         List result = new ArrayList<>();
  26.         if (s == null || s.length() == 0 || p == null || p.length() == 0) {
  27.             return result;
  28.         }
  29.  
  30.         /*创建哈希表，记录 p 中每个字符出现的次数*/
  31.         int[] hash = new int[26];
  32.         for (char c : p.toCharArray()) {
  33.             hash[c - 'a']++;
  34.         }
  35.  
  36.         /*初始化窗口指针*/
  37.         int left = 0;
  38.         int right = 0;
  39.  
  40.         /*记录窗口中未匹配的字符数量*/
  41.         int count = p.length();
  42.  
  43.         /*进入循环，不断移动右指针*/
  44.         while (right < s.length()) {
  45.             char c = s.charAt(right);
  46.  
  47.             /*如果 s 中的字符在 p 中出现过，将 hash 值减 1，并且 count 减 1*/
  48.             if (hash[c - 'a'] > 0) {
  49.                 count--;
  50.             }
  51.             hash[c - 'a']--;
  52.  
  53.             /*如果窗口大小等于 p 的长度，说明找到了一个字母异位词*/
  54.             if (right - left + 1 == p.length()) {
  55.                 if (count == 0) {
  56.                     result.add(left);
  57.                 }
  58.  
  59.                 /*将左指针向右移动，缩小窗口的大小*/
  60.                 char leftChar = s.charAt(left);
  61.                 if (hash[leftChar - 'a'] >= 0) {
  62.                     count++;
  63.                 }
  64.                 hash[leftChar - 'a']++;
  65.                 left++;
  66.             }
  67.  
  68.             /*右指针向右移动*/
  69.             right++;
  70.         }
  71.  
  72.         return result;
  73.     }
  74.  
  75.     public static void main(String[] args) {
  76.         String s = "cbaebabacd";
  77.         String p = "abc";
  78.         List result = new FindAllAnagrams().findAnagrams(s, p);
  79.         /*expects [0, 6]*/
  80.         System.out.println(result);
  81.     }
  82.  
  83. }

（七）LRU缓存机制（LRU Cache）

题目描述：设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据 get 和写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。

写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶:你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

LRUCache cache = new LRUCache(2);

cache.put(1, 1);

cache.put(2, 2);

cache.get(1); // 返回 1

cache.put(3, 3); // 该操作会使得密钥 2 作废

cache.get(2); // 返回 -1 (未找到)

cache.put(4, 4); // 该操作会使得密钥 1 作废

cache.get(1); // 返回 -1 (未找到)

cache.get(3); // 返回 3

cache.get(4); // 返回 4

解题思路

LRU（Least Recently Used）缓存机制是一种常见的缓存淘汰算法。它根据数据最近被访问的时间来进行淘汰，即当缓存达到最大容量时，优先淘汰最近最少使用的数据。

为了实现 LRU 缓存机制，我们需要用到哈希表和双向链表两个数据结构。其中，哈希表用于实现快速的查找和删除操作，双向链表则用于实现有序的存储和删除操作。

具体实现步骤如下：

  1. 使用哈希表（HashMap）存储键值对，其中键为缓存的键，值为对应节点在双向链表中的位置。
  2. 使用双向链表（LinkedList）存储节点，其中每个节点包括键、值和前驱节点、后继节点。
  3. 每当缓存被访问时，将对应节点移动到双向链表的头部。
  4. 当缓存容量达到最大值时，将双向链表尾部节点删除并在哈希表中删除对应的键值对。

算法分析：

  • 时间复杂度：get 和 put 操作的时间复杂度均为 O(1)。
  • 空间复杂度：存储 n 个缓存节点的空间复杂度为 O(n)。

具体代码展示

  1. package org.zyf.javabasic.letcode.hash;
  2.  
  3. import java.util.HashMap;
  4. import java.util.Map;
  5.  
  6. /**
  7.  * @author yanfengzhang
  8.  * @description 设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据 get 和写入数据 put 。
  9.  * 获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
  10.  * 写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，
  11.  * 它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
  12.  * 
  13.  * 进阶:你是否可以在 O(1) 时间复杂度内完成这两种操作？
  14.  * @date 2023/4/9  19:11
  15.  */
  16. public class LRUCache {
  17.     class DLinkedNode {
  18.         int key;
  19.         int value;
  20.         DLinkedNode prev;
  21.         DLinkedNode next;
  22.     }
  23.  
  24.     private Map cache = new HashMap<>();
  25.     private int size;
  26.     private int capacity;
  27.     private DLinkedNode head, tail;
  28.  
  29.     public LRUCache(int capacity) {
  30.         this.size = 0;
  31.         this.capacity = capacity;
  32.         head = new DLinkedNode();
  33.         tail = new DLinkedNode();
  34.         head.next = tail;
  35.         tail.prev = head;
  36.     }
  37.  
  38.     public int get(int key) {
  39.         DLinkedNode node = cache.get(key);
  40.         if (node == null) {
  41.             return -1;
  42.         }
  43.         /*将节点移动到双向链表头部*/
  44.         moveToHead(node);
  45.         return node.value;
  46.     }
  47.  
  48.     public void put(int key, int value) {
  49.         DLinkedNode node = cache.get(key);
  50.         if (node == null) {
  51.             /*如果节点不存在，则创建一个新节点并加入到双向链表头部和哈希表中*/
  52.             DLinkedNode newNode = new DLinkedNode();
  53.             newNode.key = key;
  54.             newNode.value = value;
  55.             cache.put(key, newNode);
  56.             addToHead(newNode);
  57.             size++;
  58.             if (size > capacity) {
  59.                 /*如果超出容量，则删除双向链表尾部节点并在哈希表中删除对应的键值对*/
  60.                 DLinkedNode tail = removeTail();
  61.                 cache.remove(tail.key);
  62.                 size--;
  63.             }
  64.         } else {
  65.             /*如果节点存在，则更新节点的值，并将节点移动到双向链表头部*/
  66.             node.value = value;
  67.             moveToHead(node);
  68.         }
  69.     }
  70.  
  71.     private void addToHead(DLinkedNode node) {
  72.         /*将节点加入到双向链表头部*/
  73.         node.prev = head;
  74.         node.next = head.next;
  75.         head.next.prev = node;
  76.         head.next = node;
  77.     }
  78.  
  79.     private void removeNode(DLinkedNode node) {
  80.         /*从双向链表中删除节点*/
  81.         node.prev.next = node.next;
  82.         node.next.prev = node.prev;
  83.     }
  84.  
  85.     private void moveToHead(DLinkedNode node) {
  86.         /*将节点移动到双向链表头部*/
  87.         removeNode(node);
  88.         addToHead(node);
  89.     }
  90.  
  91.     private DLinkedNode removeTail() {
  92.         /*删除双向链表尾部节点，并返回被删除的节点*/
  93.         DLinkedNode tail = this.tail.prev;
  94.         removeNode(tail);
  95.         return tail;
  96.     }
  97.  
  98.     /**
  99.      * 可以看到，LRU 缓存机制在存储容量达到最大值时，
  100.      * 能够正确地淘汰最近最少使用的节点，
  101.      * 并保证每个节点的访问顺序符合 LRU 缓存机制的要求。
  102.      */
  103.     public static void main(String[] args) {
  104.         LRUCache cache = new LRUCache(2);
  105.         cache.put(1, 1);
  106.         cache.put(2, 2);
  107.         /*output: 1*/
  108.         System.out.println(cache.get(1));
  109.         cache.put(3, 3);
  110.         /*output: -1*/
  111.         System.out.println(cache.get(2));
  112.         cache.put(4, 4);
  113.         /*output: -1*/
  114.         System.out.println(cache.get(1));
  115.         /*output: 3*/
  116.         System.out.println(cache.get(3));
  117.         /*output: 4*/
  118.         System.out.println(cache.get(4));
  119.     }
  120.  
  121. }
  122.

（八）多数元素（Majority Element）

题目描述：给定一个大小为 n 的数组，找到其中的多数元素。多数元素指在数组中出现次数大于 ⌊n/2⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:输入: [3,2,3].                  输出: 3

示例 2:输入: [2,2,1,1,1,2,2].      输出: 2

解题思路

摩尔投票法：该算法基于一个事实，即在一个数组中，若某个元素出现次数大于数组长度的一半，则该元素必定存在。

算法步骤如下：

  1. 设置一个候选众数 candidate 和一个计数器 count，初始值分别为任意值和 0。
  2. 遍历数组 nums 中的每个元素，如果计数器 count 为 0，则将当前元素设置为候选众数 candidate，并将计数器 count 设置为 1；否则，如果当前元素等于候选众数 candidate，则将计数器 count 加 1，否则将计数器 count 减 1。
  3. 遍历完数组后，candidate 即为众数。

算法分析：

  • 时间复杂度：O(n)，其中 n 为数组的长度。遍历一遍数组即可找到众数。
  • 空间复杂度：O(1)，使用常数空间。

具体代码展示

  1. package org.zyf.javabasic.letcode.hash;
  2.  
  3. /**
  4.  * @author yanfengzhang
  5.  * @description 给定一个大小为 n 的数组，找到其中的多数元素。
  6.  * 多数元素指在数组中出现次数大于 ⌊n/2⌋ 的元素。
  7.  * @date 2023/4/9  19:21
  8.  */
  9. public class MajorityElement {
  10.  
  11.     /**
  12.      * 摩尔投票法：该算法基于一个事实，即在一个数组中，若某个元素出现次数大于数组长度的一半，则该元素必定存在。
  13.      * 
  14.      * 算法步骤如下：
  15.      * 1 设置一个候选众数 candidate 和一个计数器 count，初始值分别为任意值和 0。
  16.      * 2 遍历数组 nums 中的每个元素，如果计数器 count 为 0，则将当前元素设置为候选众数 candidate，并将计数器 count 设置为 1；
  17.      * 否则，如果当前元素等于候选众数 candidate，则将计数器 count 加 1，否则将计数器 count 减 1。
  18.      * 3 遍历完数组后，candidate 即为众数。
  19.      */
  20.     public static int findMajorityElement(int[] nums) {
  21.         // 候选元素
  22.         int candidate = 0;
  23.         // 候选元素的出现次数
  24.         int count = 0; 
  25.  
  26.         for (int num : nums) {
  27.             if (count == 0) {
  28.                 // 如果当前候选元素的出现次数为0，则将当前元素设为候选元素，并将出现次数设为1
  29.                 candidate = num;
  30.                 count = 1;
  31.             } else if (num == candidate) {
  32.                 // 如果当前元素与候选元素相同，则候选元素的出现次数加1
  33.                 count++;
  34.             } else {
  35.                 // 如果当前元素与候选元素不同，则候选元素的出现次数减1
  36.                 count--;
  37.             }
  38.         }
  39.  
  40.         // 最终候选元素可能是多数元素，需要再次验证
  41.         int countCandidate = 0;
  42.         for (int num : nums) {
  43.             if (num == candidate) {
  44.                 countCandidate++;
  45.             }
  46.         }
  47.  
  48.         // -1 表示没有多数元素
  49.         return countCandidate > nums.length / 2 ? candidate : -1;
  50.     }
  51.  
  52.  
  53.     public static void main(String[] args) {
  54.         int[] nums = {3, 3, 3, 2, 5};
  55.         int result = new MajorityElement().findMajorityElement(nums);
  56.         /*输出 3*/
  57.         System.out.println(result);
  58.     }
  59.  
  60. }

（九）重复的DNA序列（Repeated DNA Sequences）

题目描述：重复的DNA序列是指长度为10的DNA序列中出现次数大于1的子序列。

给定一个长度为 n 的字符串 s，查找其中所有长度为10的子序列中出现次数大于1的子序列并返回。

原题目链接：力扣

示例：输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

输出：["AAAAACCCCC","CCCCCAAAAA"]

输入：s = "AAAAAAAAAAAAA"

输出：["AAAAAAAAAA"]

提示：

  • 0 <= s.length <= 105
  • s[i] 为小写英文字母或大写英文字母或数字

解题思路

本题可以使用哈希表（HashMap）来解决。我们可以遍历字符串 s，每次取出长度为 10 的子串，判断该子串在哈希表中是否已经存在。如果已经存在，则将该子串加入结果集；否则，在哈希表中将该子串加入，并将对应的值设为 1。

具体实现步骤如下：

  1. 创建哈希表（HashMap），用于存储子串以及子串出现的次数。
  2. 遍历字符串 s，每次取出长度为 10 的子串。
  3. 判断子串是否在哈希表中已经存在，如果已经存在，则将该子串加入结果集；否则，在哈希表中将该子串加入，并将对应的值设为 1。
  4. 重复步骤 2 和 3，直到遍历完整个字符串 s。

算法分析：

  • 时间复杂度：O(n)，其中 n 是字符串 s 的长度。需要遍历整个字符串 s 一次，因此时间复杂度是线性的。
  • 空间复杂度：O(n)，需要使用哈希表来存储子串以及子串出现的次数，因此需要额外的空间。

具体代码展示

  1. package org.zyf.javabasic.letcode.hash;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.HashMap;
  5. import java.util.List;
  6. import java.util.Map;
  7.  
  8. /**
  9.  * @author yanfengzhang
  10.  * @description 重复的DNA序列是指长度为10的DNA序列中出现次数大于1的子序列。
  11.  * 给定一个长度为 n 的字符串 s，查找其中所有长度为10的子序列中出现次数大于1的子序列并返回。
  12.  * @date 2023/4/9  19:30
  13.  */
  14. public class RepeatedDNASequences {
  15.  
  16.     /**
  17.      * 本题可以使用哈希表（HashMap）来解决。
  18.      * 我们可以遍历字符串 s，每次取出长度为 10 的子串，判断该子串在哈希表中是否已经存在。
  19.      * 如果已经存在，则将该子串加入结果集；否则，在哈希表中将该子串加入，并将对应的值设为 1。
  20.      * 
  21.      * 具体实现步骤如下：
  22.      * 创建哈希表（HashMap），用于存储子串以及子串出现的次数。
  23.      * 遍历字符串 s，每次取出长度为 10 的子串。
  24.      * 判断子串是否在哈希表中已经存在，如果已经存在，则将该子串加入结果集；否则，在哈希表中将该子串加入，并将对应的值设为 1。
  25.      * 重复步骤 2 和 3，直到遍历完整个字符串 s。
  26.      */
  27.     public List findRepeatedDnaSequences(String s) {
  28.         /*初始化哈希表和结果集*/
  29.         Map map = new HashMap<>();
  30.         List res = new ArrayList<>();
  31.  
  32.         /*遍历字符串 s，每次取出长度为 10 的子串*/
  33.         for (int i = 0; i <= s.length() - 10; i++) {
  34.             String substr = s.substring(i, i + 10);
  35.             /*判断子串是否在哈希表中已经存在*/
  36.             if (map.containsKey(substr)) {
  37.                 /*如果已经存在，则将该子串加入结果集*/
  38.                 if (map.get(substr) == 1) {
  39.                     res.add(substr);
  40.                 }
  41.                 /*将对应的值加 1*/
  42.                 map.put(substr, map.get(substr) + 1);
  43.             } else {
  44.                 /*如果不存在，则将该子串加入哈希表，并将对应的值设为 1*/
  45.                 map.put(substr, 1);
  46.             }
  47.         }
  48.  
  49.         return res;
  50.     }
  51.  
  52.     public static void main(String[] args) {
  53.         String s1 = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT";
  54.         /*Output: [AAAAACCCCC, CCCCCAAAAA]*/
  55.         System.out.println(new RepeatedDNASequences().findRepeatedDnaSequences(s1));
  56.  
  57.         String s2 = "AAAAAAAAAAAA";
  58.         /*Output: [AAAAAAAAAA]*/
  59.         System.out.println(new RepeatedDNASequences().findRepeatedDnaSequences(s2));
  60.  
  61.         String s3 = "AAAAAAAAAAA";
  62.         /*Output: [AAAAAAAAAA]*/
  63.         System.out.println(new RepeatedDNASequences().findRepeatedDnaSequences(s3));
  64.  
  65.         String s4 = "GAGAGAGAGAGAGAGAGAGAGAGAGAGAGAGAGAGAGAGAGAGAGAGAGAGAGAGAGAGAGAGA";
  66.         /*Output: [GAGAGAGAGA]*/
  67.         System.out.println(new RepeatedDNASequences().findRepeatedDnaSequences(s4));
  68.     }
  69.  
  70. }

（十）快乐数（Happy Number）

题目描述：编写一个算法来判断一个数 n 是不是快乐数。

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

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

示例 1：输入：19.      输出：true

解释：1^2 + 9^2 = 82

           8^2 + 2^2 = 68

           6^2 + 8^2 = 100

           1^2 + 0^2 + 0^2 = 1

示例 2：输入：n = 2.  输出：false

提示：

1 <= n <= 2^31 - 1

解题思路

使用哈希集合（HashSet）来存储每一次计算得到的结果，当出现重复的结果时，就说明进入了循环，可以直接返回 false。如果计算得到的结果为 1，则说明该数是快乐数，返回 true。

具体实现步骤如下：

  1. 将给定的整数 n 转换为字符串类型，以便于对每个位上的数字进行计算。
  2. 创建一个 HashSet，用于存储每次计算得到的结果。
  3. 计算数字 n 的各位数字的平方和，并将结果存储到 HashSet 中。
  4. 重复步骤 3，直到计算得到的结果为 1，此时返回 true；或者得到的结果在 HashSet 中已经存在，此时返回 false。

算法分析：

  • 时间复杂度：O(log n)，n 表示数字 n 的位数。在每次计算平方和时，需要将数字 n 的每个位上的数字分离出来，因此时间复杂度为 O(log n)。最坏情况下，平方和会一直循环，因此时间复杂度最差情况下为 O(log n)。
  • 空间复杂度：O(log n)，需要使用 HashSet 来存储计算得到的结果，最坏情况下需要存储 O(log n) 个结果。

具体代码展示

  1. package org.zyf.javabasic.letcode.hash;
  2.  
  3. import java.util.HashSet;
  4. import java.util.Set;
  5.  
  6. /**
  7.  * @author yanfengzhang
  8.  * @description 编写一个算法来判断一个数 n 是不是快乐数。
  9.  * @date 2023/4/9  19:42
  10.  */
  11. public class HappyNumber {
  12.  
  13.     /**
  14.      * 使用哈希集合（HashSet）来存储每一次计算得到的结果，
  15.      * 当出现重复的结果时，就说明进入了循环，可以直接返回 false。
  16.      * 如果计算得到的结果为 1，则说明该数是快乐数，返回 true。
  17.      */
  18.     public boolean isHappy(int n) {
  19.         Set seen = new HashSet<>();
  20.         /*哈希集合判断循环*/
  21.         while (n != 1 && !seen.contains(n)) {
  22.             seen.add(n);
  23.             n = getNext(n);
  24.         }
  25.         return n == 1;
  26.     }
  27.  
  28.     /*计算下一个数*/
  29.     private int getNext(int n) {
  30.         int sum = 0;
  31.         while (n > 0) {
  32.             int digit = n % 10;
  33.             sum += digit * digit;
  34.             n /= 10;
  35.         }
  36.         return sum;
  37.     }
  38.  
  39.     public static void main(String[] args) {
  40.         int n1 = 19;
  41.         /*true*/
  42.         System.out.println(new HappyNumber().isHappy(n1));
  43.  
  44.         int n2 = 2;
  45.         /*false*/
  46.         System.out.println(new HappyNumber().isHappy(n2));
  47.     }
  48.  
  49. }

备注：最优解法-Floyd 判圈算法

思路

最优解法使用快慢指针（Floyd 判圈算法）来判断是否为快乐数。假设我们要判断的数字为 n，我们可以将 n 看成一个链表，每个数字位上的数字就是链表中的节点值。例如，数字 19 可以看作如下的链表：

1 -> 9 -> 81 -> 82 -> 68 -> 100 -> 1

我们可以使用快慢指针来遍历这个链表，如果最终快指针和慢指针指向了同一个节点，那么这个数字就是快乐数；否则，这个数字不是快乐数。

具体实现步骤如下：

  1. 使用快慢指针来遍历数字 n 对应的链表，慢指针每次移动一个节点，快指针每次移动两个节点。
  2. 如果快指针和慢指针指向了同一个节点，那么这个数字就是快乐数；否则，继续遍历链表。
  3. 如果遍历过程中出现了一个节点在之前已经出现过，那么这个数字就不是快乐数。

算法分析：

  • 时间复杂度：时间复杂度是 O(log n)，其中 n 是数字的位数，每次计算下一个数字的时间复杂度为 O(log n)，最坏情况下需要计算 O(log n) 次。
  • 空间复杂度：空间复杂度是 O(1)，只需要常数级别的额外空间来存储快慢指针。

代码展示

  1.     public class FloydSolution {
  2.         public boolean isHappy(int n) {
  3.             int slow = n, fast = getNext(n);
  4.             /*快慢指针判断循环*/
  5.             while (fast != 1 && slow != fast) {
  6.                 slow = getNext(slow);
  7.                 fast = getNext(getNext(fast));
  8.             }
  9.             /*如果最终得到的是 1，则 n 是快乐数*/
  10.             return fast == 1;
  11.         }
  12.  
  13.         /*计算下一个数*/
  14.         private int getNext(int n) {
  15.             int sum = 0;
  16.             while (n > 0) {
  17.                 int digit = n % 10;
  18.                 sum += digit * digit;
  19.                 n /= 10;
  20.             }
  21.             return sum;
  22.         }
  23.     }

（十一）存在重复元素（Contains Duplicate）

题目描述：给定一个整数数组，判断是否存在重复元素。

如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

示例 1:输入: [1,2,3,1].                        输出: true

示例 2:输入: [1,2,3,4].                        输出: false

示例 3:输入: [1,1,1,3,3,4,3,2,4,2].      输出: true

来源：力扣（LeetCode）

链接：力扣

解题思路

最优解法使用哈希表（HashMap）来解决，思路如下：

  1. 创建一个哈希表，用于存储数组中的元素及其出现的次数。
  2. 遍历数组中的每个元素，判断该元素是否已经在哈希表中存在。
  3. 如果该元素在哈希表中已经存在，则说明数组中存在重复元素，返回 true。
  4. 否则，在哈希表中将该元素加入，并将对应的值设为 1。
  5. 重复步骤 2、3、4，直到遍历完整个数组。

时间复杂度：O(n)，其中 n 是数组的长度。需要遍历整个数组一次，因此时间复杂度是线性的。

空间复杂度：O(n)，最坏情况下哈希表需要存储整个数组中的元素，因此需要额外的空间。

具体代码展示

  1. package org.zyf.javabasic.letcode.hash;
  2.  
  3. import java.util.HashSet;
  4. import java.util.Set;
  5.  
  6. /**
  7.  * @author yanfengzhang
  8.  * @description
  9.  * @date 2023/4/9  19:51
  10.  */
  11. public class ContainsDuplicate {
  12.     /**
  13.      * 最优解法使用哈希表（HashMap）来解决，思路如下：
  14.      * 
  15.      * 创建一个哈希表，用于存储数组中的元素及其出现的次数。
  16.      * 遍历数组中的每个元素，判断该元素是否已经在哈希表中存在。
  17.      * 如果该元素在哈希表中已经存在，则说明数组中存在重复元素，返回 true。
  18.      * 否则，在哈希表中将该元素加入，并将对应的值设为 1。
  19.      * 重复步骤 2、3、4，直到遍历完整个数组。
  20.      */
  21.     public boolean containsDuplicate(int[] nums) {
  22.         /*创建哈希表，用于存储已经遍历过的元素*/
  23.         Set set = new HashSet<>();
  24.  
  25.         /*遍历整个数组*/
  26.         for (int num : nums) {
  27.             /*如果当前元素已经在哈希表中存在，说明数组中存在重复元素，返回 true*/
  28.             if (set.contains(num)) {
  29.                 return true;
  30.             } else {
  31.                 /*否则，将当前元素加入哈希表中*/
  32.                 set.add(num);
  33.             }
  34.         }
  35.         /*如果遍历完整个数组，都没有发现重复元素，则返回 false*/
  36.         return false;
  37.     }
  38.  
  39.     public static void main(String[] args) {
  40.         int[] nums1 = {1, 2, 3, 1};
  41.         int[] nums2 = {1, 2, 3, 4};
  42.         int[] nums3 = {1, 1, 1, 3, 3, 4, 3, 2, 4, 2};
  43.         /*输出 true*/
  44.         System.out.println(new ContainsDuplicate().containsDuplicate(nums1));
  45.         /*输出 false*/
  46.         System.out.println(new ContainsDuplicate().containsDuplicate(nums2));
  47.         /*输出 true*/
  48.         System.out.println(new ContainsDuplicate().containsDuplicate(nums3));
  49.     }
  50.  
  51. }

（十二）存在重复元素 II（Contains Duplicate II）

题目描述：给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums[i] = nums[j]，并且 i 和 j 的差的绝对值最大为 k。

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

解题思路

存在重复元素 II 可以使用哈希表来解决。具体步骤如下：

  1. 创建一个哈希表用于存储元素及其下标的映射。
  2. 遍历数组 nums 中的每个元素，如果元素已经在哈希表中存在，则计算其下标与哈希表中存储的下标之差是否小于等于 k。如果满足条件，说明存在重复元素，直接返回 true。
  3. 如果元素不在哈希表中，则将其添加到哈希表中。
  4. 遍历完整个数组 nums 后，仍然没有发现符合条件的重复元素，则返回 false。

时间复杂度分析：遍历一遍数组 nums 需要 O(n) 的时间，其中 n 是数组的长度。同时，由于只用了一个哈希表，空间复杂度为 O(n)。

具体代码展示

  1. package org.zyf.javabasic.letcode.hash;
  2.  
  3. import java.util.HashMap;
  4. import java.util.Map;
  5.  
  6. /**
  7.  * @author yanfengzhang
  8.  * @description 给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，
  9.  * 使得 nums[i] = nums[j]，并且 i 和 j 的差的绝对值最大为 k。
  10.  * @date 2023/4/9  20:33
  11.  */
  12. public class ContainsDuplicateII {
  13.  
  14.     /**
  15.      * 存在重复元素 II 可以使用哈希表来解决。具体步骤如下：
  16.      * 
  17.      * 创建一个哈希表用于存储元素及其下标的映射。
  18.      * 遍历数组 nums 中的每个元素，如果元素已经在哈希表中存在，则计算其下标与哈希表中存储的下标之差是否小于等于 k。
  19.      * 如果满足条件，说明存在重复元素，直接返回 true。
  20.      * 如果元素不在哈希表中，则将其添加到哈希表中。
  21.      * 遍历完整个数组 nums 后，仍然没有发现符合条件的重复元素，则返回 false。
  22.      * 时间复杂度分析：遍历一遍数组 nums 需要 O(n) 的时间，其中 n 是数组的长度。同时，由于只用了一个哈希表，空间复杂度为 O(n)。
  23.      */
  24.     public boolean containsNearbyDuplicate(int[] nums, int k) {
  25.         /*创建一个哈希表用于存储元素及其下标的映射*/
  26.         Map map = new HashMap<>();
  27.         for (int i = 0; i < nums.length; i++) {
  28.             /*如果元素已经在哈希表中存在，则计算其下标与哈希表中存储的下标之差是否小于等于 k*/
  29.             if (map.containsKey(nums[i]) && i - map.get(nums[i]) <= k) {
  30.                 /*如果满足条件，说明存在重复元素，直接返回 true*/
  31.                 return true;
  32.             }
  33.             /*如果元素不在哈希表中，则将其添加到哈希表中*/
  34.             map.put(nums[i], i);
  35.         }
  36.         /*遍历完整个数组 nums 后，仍然没有发现符合条件的重复元素，则返回 false*/
  37.         return false;
  38.     }
  39.  
  40.     public static void main(String[] args) {
  41.         int[] nums = {1, 2, 3, 1};
  42.         int k = 3;
  43.         boolean result = new ContainsDuplicateII().containsNearbyDuplicate(nums, k);
  44.         /*输入的数组 nums 为 {1, 2, 3, 1}，k 的值为 3。
  45.         函数的返回值为 true，因为数组中有两个值为 1 的元素，
  46.         它们的下标之差为 3，满足题目要求。所以输出为 true。*/
  47.         System.out.println(result);
  48.     }
  49.  
  50. }

（十三）单词规律（Word Pattern）

题目描述：给定一种规律 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

说明:你可以假设 pattern 只包含小写字母， str 包含了由单个空格分隔的小写字母。

解题思路

主要思路是使用两个哈希表，一个用于存储 pattern 中每个字符对应的字符串，另一个用于存储字符串对应的 pattern 中的字符。在遍历 pattern 和 words 数组时，对于每个字符和字符串，都在两个哈希表中进行查找，如果存在冲突，则返回 false。如果没有出现冲突，则返回 true。

  • 时间复杂度：O(n)，其中 n 是字符串words和模式串 pattern 的长度。需要遍历整个字符串words和模式串 pattern 一次，因此时间复杂度是线性的。
  • 空间复杂度：O(n)，需要使用两个哈希表来存储字符和它们在字符串words和模式串 pattern 中出现的位置，因此需要额外的空间。

具体代码展示

  1. package org.zyf.javabasic.letcode.hash;
  2.  
  3. import java.util.HashMap;
  4. import java.util.Map;
  5.  
  6. /**
  7.  * @author yanfengzhang
  8.  * @description 给定一种规律 pattern 和一个字符串 str，判断 str 是否遵循相同的规律。
  9.  * 这里的遵循指完全匹配，
  10.  * 例如，pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。
  11.  * @date 2023/4/9  20:44
  12.  */
  13. public class WordPattern {
  14.  
  15.     /**
  16.      * 使用两个哈希表，一个用于存储 pattern 中每个字符对应的字符串，
  17.      * 另一个用于存储字符串对应的 pattern 中的字符。
  18.      * 在遍历 pattern 和 words 数组时，
  19.      * 对于每个字符和字符串，都在两个哈希表中进行查找，如果存在冲突，则返回 false。
  20.      * 如果没有出现冲突，则返回 true。
  21.      */
  22.     public boolean wordPattern(String pattern, String s) {
  23.         /*将字符串 s 按照空格分隔为字符串数组*/
  24.         String[] words = s.split(" ");
  25.         /*如果字符串 pattern 和字符串数组 words 的长度不相等，则返回 false*/
  26.         if (pattern.length() != words.length) {
  27.             return false;
  28.         }
  29.         /*创建两个哈希表，一个用于存储 pattern 中每个字符对应的字符串，另一个用于存储字符串对应的 pattern 中的字符*/
  30.         Map charToString = new HashMap<>();
  31.         Map stringToChar = new HashMap<>();
  32.         /*遍历 pattern 和 words 数组*/
  33.         for (int i = 0; i < pattern.length(); i++) {
  34.             char c = pattern.charAt(i);
  35.             String word = words[i];
  36.             /*如果哈希表 charToString 中已经包含了该字符，但是对应的字符串不是当前的 word，说明出现了冲突，返回 false*/
  37.             if (charToString.containsKey(c) && !charToString.get(c).equals(word)) {
  38.                 return false;
  39.             }
  40.             /*如果哈希表 stringToChar 中已经包含了该字符串，但是对应的字符不是当前的 c，说明出现了冲突，返回 false*/
  41.             if (stringToChar.containsKey(word) && stringToChar.get(word) != c) {
  42.                 return false;
  43.             }
  44.             /*将当前的字符和字符串加入两个哈希表中*/
  45.             charToString.put(c, word);
  46.             stringToChar.put(word, c);
  47.         }
  48.         /*如果没有出现冲突，则返回 true*/
  49.         return true;
  50.     }
  51.  
  52.     public static void main(String[] args) {
  53.         String pattern1 = "abba", str1 = "dog cat cat dog";
  54.         boolean res1 = new WordPattern().wordPattern(pattern1, str1);
  55.         /*输出 true*/
  56.         System.out.println(res1);
  57.  
  58.         String pattern2 = "abba", str2 = "dog cat cat fish";
  59.         boolean res2 = new WordPattern().wordPattern(pattern2, str2);
  60.         /*输出 false*/
  61.         System.out.println(res2);
  62.  
  63.         String pattern3 = "aaaa", str3 = "dog cat cat dog";
  64.         boolean res3 = new WordPattern().wordPattern(pattern3, str3);
  65.         /*输出 false*/
  66.         System.out.println(res3);
  67.  
  68.         String pattern4 = "abba", str4 = "dog dog dog dog";
  69.         boolean res4 = new WordPattern().wordPattern(pattern4, str4);
  70.         /*输出 false*/
  71.         System.out.println(res4);
  72.     }
  73.  
  74. }

（十四）前K个高频元素（Top K Frequent Elements）

题目描述：给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:输入: nums = [1,1,1,2,2,3], k = 2.      输出: [1,2]

示例 2:输入: nums = [1], k = 1                      输出: [1]

提示：

  • 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
  • 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

题目链接：力扣

解题思路

该问题可以使用哈希表和桶排序来解决，具体思路如下：

  1. 遍历数组，统计每个元素出现的次数，可以使用哈希表来实现，键为元素值，值为元素出现的次数。
  2. 将哈希表中的元素放入桶中，桶的下标为元素出现的次数，桶中存放的是出现次数相同的元素值。
  3. 从桶的末尾开始遍历，依次取出前 k 个出现频率最高的元素。

算法分析：

  • 时间复杂度：O(n+k)，其中 n 是数组的长度，k 是前 k 大元素的数量。需要遍历整个数组一次，统计每个元素出现的次数，时间复杂度是 O(n)。然后需要遍历每个桶，从后往前取出前 k 个元素，时间复杂度是 O(k)。因此总时间复杂度是 O(n+k)。
  • 空间复杂度：O(n)，需要使用哈希表存储每个元素出现的次数，以及使用桶来存储每个出现次数对应的元素值，需要额外的空间。

备注：

需要注意的是，桶排序中桶的数量是元素的数量加 1，因为出现频率最高的元素可能会出现 nums.length 次。同时，由于可能会有多个元素出现的频率相同，因此每个桶需要使用 ArrayList 等数据结构来存储多个元素。

使用哈希表和桶排序实现的 Java 代码中，第一步遍历数组 nums，计算每个元素出现的频率并存储到哈希表 frequencyMap 中。第二步，创建一个大小为 nums.length + 1 的桶数组 bucket，将出现频率相同的元素存储在同一个桶中。第三步，从后向前遍历桶数组，将桶中的元素加入结果集中，直到结果集中的元素数量达到 k。

具体代码展示

  1. package org.zyf.javabasic.letcode.hash;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.Arrays;
  5. import java.util.HashMap;
  6. import java.util.List;
  7. import java.util.Map;
  8.  
  9. /**
  10.  * @author yanfengzhang
  11.  * @description 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
  12.  * @date 2023/4/9  20:52
  13.  */
  14. public class TopKFrequentElements {
  15.  
  16.     /**
  17.      * 该问题可以使用哈希表和桶排序来解决，具体思路如下：
  18.      * 遍历数组，统计每个元素出现的次数，可以使用哈希表来实现，键为元素值，值为元素出现的次数。
  19.      * 将哈希表中的元素放入桶中，桶的下标为元素出现的次数，桶中存放的是出现次数相同的元素值。
  20.      * 从桶的末尾开始遍历，依次取出前 k 个出现频率最高的元素。
  21.      */
  22.     public int[] topKFrequent(int[] nums, int k) {
  23.         /*第 1 步：使用哈希表统计每个元素出现的频率*/
  24.         Map frequencyMap = new HashMap<>();
  25.         for (int num : nums) {
  26.             frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
  27.         }
  28.  
  29.         /*第 2 步：使用桶排序，将出现频率作为桶的下标*/
  30.         List[] bucket = new ArrayList[nums.length + 1];
  31.         for (int key : frequencyMap.keySet()) {
  32.             int frequency = frequencyMap.get(key);
  33.             if (bucket[frequency] == null) {
  34.                 bucket[frequency] = new ArrayList<>();
  35.             }
  36.             bucket[frequency].add(key);
  37.         }
  38.  
  39.         /*第 3 步：从后向前遍历桶，并将桶中的元素加入结果集中*/
  40.         int[] result = new int[k];
  41.         int index = 0;
  42.         for (int i = bucket.length - 1; i >= 0 && index < k; i--) {
  43.             if (bucket[i] == null) {
  44.                 continue;
  45.             }
  46.             for (int num : bucket[i]) {
  47.                 result[index++] = num;
  48.                 if (index == k) {
  49.                     break;
  50.                 }
  51.             }
  52.         }
  53.         return result;
  54.     }
  55.  
  56.     public static void main(String[] args) {
  57.         int[] nums = {1, 1, 1, 2, 2, 3};
  58.         int k = 2;
  59.         int[] res = new TopKFrequentElements().topKFrequent(nums, k);
  60.         /*[1, 2]*/
  61.         System.out.println(Arrays.toString(res));
  62.     }
  63. }

（十五）字符串中的第一个唯一字符（First Unique Character in a String）

题目描述：给定一个字符串 s ，找到 s 中第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

示例：输入：s = "leetcode".            输出：0

           输入：s = "loveleetcode".     输出：2

           输入：s = "aabb"                  输出：-1

提示：

  • 1 <= s.length <= 10^5
  • s 由小写英文字母组成

来源：力扣（LeetCode）

链接：力扣

解题思路

最优解法是使用哈希表（HashMap）来解决。我们可以先遍历一次字符串 s，统计每个字符出现的次数，并将其存储在哈希表中。然后再遍历一次字符串 s，找到第一个在哈希表中出现次数为 1 的字符，返回该字符在字符串 s 中的位置。

具体实现步骤如下：

  1. 创建哈希表（HashMap），用于存储每个字符出现的次数。
  2. 遍历字符串 s，统计每个字符出现的次数，并将其存储在哈希表中。
  3. 遍历字符串 s，找到第一个在哈希表中出现次数为 1 的字符，返回该字符在字符串 s 中的位置。
  4. 如果字符串 s 中所有字符都不满足出现次数为 1，则返回 -1。

算法分析：

  • 时间复杂度：O(n)，其中 n 是字符串 s 的长度。需要遍历字符串 s 两次，因此时间复杂度是线性的。
  • 空间复杂度：O(k)，其中 k 是字符集的大小。需要使用哈希表来存储每个字符出现的次数，因此需要额外的空间。

具体代码展示

  1. package org.zyf.javabasic.letcode.hash;
  2.  
  3. import java.util.HashMap;
  4. import java.util.Map;
  5.  
  6. /**
  7.  * @author yanfengzhang
  8.  * @description 给定一个字符串 s ，找到 s 中第一个不重复的字符，并返回它的索引。
  9.  * 如果不存在，则返回 -1。
  10.  * @date 2023/4/9  21:00
  11.  */
  12. public class FirstUniqueCharacter {
  13.     /**
  14.      * 使用哈希表（HashMap）来解决。
  15.      * 我们可以先遍历一次字符串 s，统计每个字符出现的次数，并将其存储在哈希表中。
  16.      * 然后再遍历一次字符串 s，找到第一个在哈希表中出现次数为 1 的字符，
  17.      * 返回该字符在字符串 s 中的位置。
  18.      */
  19.     public int firstUniqChar(String s) {
  20.         /*创建哈希表，用于存储每个字符出现的次数*/
  21.         Map map = new HashMap<>();
  22.         /*遍历字符串，统计每个字符出现的次数*/
  23.         for (int i = 0; i < s.length(); i++) {
  24.             char c = s.charAt(i);
  25.             /*如果哈希表中已经有该字符，则将其对应的值加 1*/
  26.             if (map.containsKey(c)) {
  27.                 map.put(c, map.get(c) + 1);
  28.             }
  29.             /*否则，在哈希表中添加该字符，并将其对应的值设为 1*/
  30.             else {
  31.                 map.put(c, 1);
  32.             }
  33.         }
  34.         /*再次遍历字符串，找到第一个出现次数为 1 的字符*/
  35.         for (int i = 0; i < s.length(); i++) {
  36.             char c = s.charAt(i);
  37.             if (map.get(c) == 1) {
  38.                 return i;
  39.             }
  40.         }
  41.         /*如果所有字符都不止出现一次，则返回 -1*/
  42.         return -1;
  43.     }
  44.  
  45.     public static void main(String[] args) {
  46.         String s1 = "leetcode";
  47.         /*xpected output: 0*/
  48.         System.out.println(new FirstUniqueCharacter().firstUniqChar(s1));
  49.  
  50.         String s2 = "loveleetcode";
  51.         /*xpected output: 2*/
  52.         System.out.println(new FirstUniqueCharacter().firstUniqChar(s2));
  53.  
  54.         String s3 = "abcabc";
  55.         /*xpected output: -1*/
  56.         System.out.println(new FirstUniqueCharacter().firstUniqChar(s3));
  57.     }
  58.  
  59. }

（十六）四数相加 II（4Sum II）

题目描述：给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

注意：答案中不可以包含重复的四元组。

例如：输入：

A = [ 1, 2]

B = [-2,-1]

C = [-1, 2]

D = [ 0, 2]

输出：2

解释：

两个元组如下：

  1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
  2. (1, 1, 0, 1) -> A[1] + B[1] + C[0] + D[1] = 2 + (-1) + (-1) + 2 = 2

解题思路

四数相加 II 问题可以通过将其分解为两个两数相加的问题来解决。具体步骤如下：

  1. 创建哈希表，分别用于存储 A 数组和 B 数组中所有两个数之和的情况。
  2. 遍历 A 数组和 B 数组，统计每个数字对应的出现次数，并将其加入哈希表中。
  3. 遍历 C 数组和 D 数组，对于每个数字，在哈希表中查找其相反数的出现次数，并将计数器累加至结果中。
  4. 返回结果。

时间复杂度分析：由于需要遍历 A、B、C、D 四个数组，因此时间复杂度为 O(n^2)，其中 n 是数组的长度。同时，由于只用了常数个额外变量，空间复杂度为 O(n^2)。

具体代码展示

  1. package org.zyf.javabasic.letcode.hash;
  2.  
  3. import java.util.HashMap;
  4. import java.util.Map;
  5.  
  6. /**
  7.  * @author yanfengzhang
  8.  * @description 给定四个包含整数的数组列表 A , B , C , D ,
  9.  * 计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
  10.  * @date 2023/4/9  21:07
  11.  */
  12. public class FourNumberSum {
  13.  
  14.     /**
  15.      * 四数相加 II 问题可以通过将其分解为两个两数相加的问题来解决。
  16.      * 具体步骤如下：
  17.      * 创建哈希表，分别用于存储 A 数组和 B 数组中所有两个数之和的情况。
  18.      * 遍历 A 数组和 B 数组，统计每个数字对应的出现次数，并将其加入哈希表中。
  19.      * 遍历 C 数组和 D 数组，对于每个数字，在哈希表中查找其相反数的出现次数，并将计数器累加至结果中。
  20.      * 返回结果。
  21.      */
  22.     public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
  23.         /*创建两个哈希表，分别用于存储 A 数组和 B 数组中所有两个数之和的情况*/
  24.         Map map = new HashMap<>();
  25.  
  26.         /*遍历 A 数组和 B 数组，统计每个数字对应的出现次数，并将其加入哈希表中*/
  27.         for (int i = 0; i < nums1.length; i++) {
  28.             for (int j = 0; j < nums2.length; j++) {
  29.                 int sum = nums1[i] + nums2[j];
  30.                 map.put(sum, map.getOrDefault(sum, 0) + 1);
  31.             }
  32.         }
  33.  
  34.         /*遍历 C 数组和 D 数组，对于每个数字，在哈希表中查找其相反数的出现次数，并将计数器累加至结果中*/
  35.         int count = 0;
  36.         for (int i = 0; i < nums3.length; i++) {
  37.             for (int j = 0; j < nums4.length; j++) {
  38.                 int sum = nums3[i] + nums4[j];
  39.                 if (map.containsKey(-sum)) {
  40.                     count += map.get(-sum);
  41.                 }
  42.             }
  43.         }
  44.  
  45.         /*返回结果*/
  46.         return count;
  47.     }
  48.  
  49.     public static void main(String[] args) {
  50.         int[] A = {1, 2};
  51.         int[] B = {-2, -1};
  52.         int[] C = {-1, 2};
  53.         int[] D = {0, 2};
  54.  
  55.         int count = new FourNumberSum().fourSumCount(A, B, C, D);
  56.         /*输出 2*/
  57.         System.out.println(count);
  58.     }
  59. }

（十七）和为K的子数组（Subarray Sum Equals K）

题目描述：给定一个整数数组 nums 和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。

示例 1：输入：nums = [1,1,1], k = 2.   输出：2

示例 2：输入：nums = [1,2,3], k = 3.    输出：2

提示：

  • 1 <= nums.length <= 2 * 10^4
  • -1000 <= nums[i] <= 1000
  • -10^7 <= k <= 10^7

来源：力扣（LeetCode）

链接：力扣

解题思路

这个问题可以通过前缀和和哈希表来解决。具体步骤如下：

  1. 创建一个哈希表，用于存储前缀和的计数器。同时初始化前缀和为 0。
  2. 初始化计数器 count 和当前前缀和为 0。
  3. 遍历整个数组 nums，对于每个数字，更新当前前缀和并计算前缀和之差。
  4. 如果发现当前前缀和已经在哈希表中出现过了，说明之前出现过一个前缀和与当前前缀和之差为 k 的位置。将这个位置出现的次数累加至结果中。
  5. 将当前前缀和的计数器加 1，继续遍历下一个数字。
  6. 最终返回结果。

时间复杂度分析：由于只需要遍历一遍数组，因此时间复杂度为 O(n)，其中 n 是数组的长度。同时，由于只用了常数个额外变量，空间复杂度为 O(n)。

具体代码展示

  1. package org.zyf.javabasic.letcode.hash;
  2.  
  3. import java.util.HashMap;
  4. import java.util.Map;
  5.  
  6. /**
  7.  * @author yanfengzhang
  8.  * @description 给定一个整数数组 nums 和一个整数 k ，
  9.  * 请找到该数组中和为 k 的连续子数组的个数。
  10.  * @date 2023/4/9  22:14
  11.  */
  12. public class SubarraySumEqualsK {
  13.  
  14.     public int subarraySum(int[] nums, int k) {
  15.         /*创建哈希表，用于存储前缀和的计数器*/
  16.         Map map = new HashMap<>();
  17.         /*初始化前缀和为 0，并将其计数器设为 1*/
  18.         map.put(0, 1);
  19.         /*初始化计数器 count 和当前前缀和为 0*/
  20.         int count = 0, sum = 0;
  21.         /*遍历整个数组 nums*/
  22.         for (int num : nums) {
  23.             /*更新当前前缀和*/
  24.             sum += num;
  25.             /*计算前缀和之差*/
  26.             int diff = sum - k;
  27.             /*如果发现当前前缀和已经在哈希表中出现过了*/
  28.             if (map.containsKey(diff)) {
  29.                 /*将这个位置出现的次数累加至结果中*/
  30.                 count += map.get(diff);
  31.             }
  32.             /*将当前前缀和的计数器加 1，并将其存入哈希表中*/
  33.             map.put(sum, map.getOrDefault(sum, 0) + 1);
  34.         }
  35.         /*返回最终结果*/
  36.         return count;
  37.     }
  38.  
  39.     public static void main(String[] args) {
  40.         int[] nums1 = {1, 1, 1};
  41.         int k1 = 2;
  42.         /*Expected output: 2*/
  43.         System.out.println(new SubarraySumEqualsK().subarraySum(nums1, k1));
  44.  
  45.         int[] nums2 = {1, 2, 3};
  46.         int k2 = 3;
  47.         /*Expected output: 2*/
  48.         System.out.println(new SubarraySumEqualsK().subarraySum(nums2, k2));
  49.  
  50.         int[] nums3 = {3, 2, 1};
  51.         int k3 = 3;
  52.         /*Expected output: 3*/
  53.         System.out.println(new SubarraySumEqualsK().subarraySum(nums3, k3));
  54.  
  55.         int[] nums4 = {1};
  56.         int k4 = 1;
  57.         /*Expected output: 1*/
  58.         System.out.println(new SubarraySumEqualsK().subarraySum(nums4, k4));
  59.  
  60.         int[] nums5 = {1, -1, 0};
  61.         int k5 = 0;
  62.         /*Expected output: 3*/
  63.         System.out.println(new SubarraySumEqualsK().subarraySum(nums5, k5));
  64.     }
  65. }

（十八）最常见的单词（Most Common Word）

题目描述：给定一个段落 (paragraph) 和一个禁用单词列表 (banned)。返回出现次数最多，同时不在禁用列表中的单词。题目保证至少有一个出现次数最多的单词。

段落中的单词不区分大小写。答案都是小写字母。

示例：

输入:paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."       banned = ["hit"]

输出: "ball"

解释:"hit" 出现了3次，但它是一个禁用的单词。

         "ball" 出现了2次（大小写不敏感），所以它是段落中出现次数最多的非禁用单词。

注意，此例中出现次数最多的单词也是答案。

提示：

  • 1 <= 段落长度 <= 1000
  • 0 <= 禁用单词个数 <= 100
  • 1 <= 禁用单词长度 <= 10

答案是唯一的，且都是小写字母 (See full description at: 力扣)

解题思路

最常见的单词问题可以通过哈希表和字符串处理来解决。具体步骤如下：

  1. 创建一个哈希表，用于存储每个单词的出现次数。
  2. 将原始字符串中所有非字母字符都替换为空格，并将整个字符串转换成小写字母形式。
  3. 将字符串按照空格分割成一个个单词，并在哈希表中统计每个单词出现的次数。
  4. 遍历禁用单词列表 banned，将其对应的出现次数都设为 0。
  5. 遍历哈希表，找到出现次数最多的单词，排除禁用单词列表中的单词。
  6. 返回出现次数最多的单词。

时间复杂度分析：由于需要遍历原始字符串、禁用单词列表和哈希表，因此时间复杂度为 O(n+m+k)，其中 n 是原始字符串的长度，m 是禁用单词列表的长度，k 是哈希表的长度。同时，由于只用了常数个额外变量，空间复杂度为 O(k)。

具体代码展示

  1. package org.zyf.javabasic.letcode.hash;
  2.  
  3. import java.util.HashMap;
  4. import java.util.Map;
  5.  
  6. /**
  7.  * @author yanfengzhang
  8.  * @description 给定一个段落 (paragraph) 和一个禁用单词列表 (banned)。
  9.  * 返回出现次数最多，同时不在禁用列表中的单词。题目保证至少有一个出现次数最多的单词。
  10.  * 段落中的单词不区分大小写。答案都是小写字母。
  11.  * @date 2023/4/9  22:21
  12.  */
  13. public class MostCommonWord {
  14.  
  15.     /**
  16.      * 通过哈希表和字符串处理来解决。具体步骤如下：
  17.      * 
  18.      * 创建一个哈希表，用于存储每个单词的出现次数。
  19.      * 将原始字符串中所有非字母字符都替换为空格，并将整个字符串转换成小写字母形式。
  20.      * 将字符串按照空格分割成一个个单词，并在哈希表中统计每个单词出现的次数。
  21.      * 遍历禁用单词列表 banned，将其对应的出现次数都设为 0。
  22.      * 遍历哈希表，找到出现次数最多的单词，排除禁用单词列表中的单词。
  23.      * 返回出现次数最多的单词。
  24.      */
  25.     public String mostCommonWord(String paragraph, String[] banned) {
  26.         /*Step 1: 创建哈希表并初始化*/
  27.         Map wordCount = new HashMap<>();
  28.         for (String word : banned) {
  29.             wordCount.put(word, 0);
  30.         }
  31.  
  32.         /*Step 2: 将字符串中所有非字母字符替换为空格，并将整个字符串转换成小写字母形式*/
  33.         paragraph = paragraph.replaceAll("[^a-zA-Z ]", " ").toLowerCase();
  34.  
  35.         /*Step 3: 统计每个单词出现的次数*/
  36.         String[] words = paragraph.split("\\s+");
  37.         for (String word : words) {
  38.             wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
  39.         }
  40.  
  41.         /*Step 4: 将禁用单词列表中的单词对应的出现次数都设为 0*/
  42.         for (String word : banned) {
  43.             wordCount.put(word, 0);
  44.         }
  45.  
  46.         /*Step 5: 找到出现次数最多的单词，排除禁用单词列表中的单词*/
  47.         int maxCount = 0;
  48.         String result = "";
  49.         for (String word : wordCount.keySet()) {
  50.             if (wordCount.get(word) > maxCount) {
  51.                 maxCount = wordCount.get(word);
  52.                 result = word;
  53.             }
  54.         }
  55.  
  56.         /*Step 6: 返回出现次数最多的单词*/
  57.         return result;
  58.     }
  59.  
  60.     public static void main(String[] args) {
  61.         String paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.";
  62.         String[] banned = {"hit"};
  63.         String result = new MostCommonWord().mostCommonWord(paragraph, banned);
  64.         System.out.println(result);
  65.     }
  66.  
  67. }

（十九）同构字符串（Isomorphic Strings）

题目描述：给定两个字符串 s 和 t，判断它们是否是同构字符串。

如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。

所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。

示例 1:输入: s = "egg", t = "add".            输出: true

示例 2:输入: s = "foo", t = "bar".               输出: false

示例 3:输入: s = "paper", t = "title".          输出: true

说明:

你可以假设 s 和 t 具有相同的长度。

来源：力扣（LeetCode）

链接：力扣

解题思路

同构字符串问题可以通过哈希表和字符映射来解决。具体步骤如下：

  1. 创建两个哈希表，分别用于记录 s 到 t 的字符映射和 t 到 s 的字符映射。
  2. 遍历字符串 s 和 t，对于每个字符，分别在两个哈希表中查找其对应的字符映射。
  3. 如果两个哈希表中都能找到对应的字符映射，但不相同，则说明 s 和 t 不是同构字符串，直接返回 false。
  4. 如果两个哈希表中只有其中一个哈希表中能找到对应的字符映射，则说明 s 和 t 不是同构字符串，直接返回 false。
  5. 如果两个哈希表中都找不到对应的字符映射，则将当前字符的映射加入两个哈希表中。
  6. 遍历结束后，没有发现不同的字符映射，则说明 s 和 t 是同构字符串，返回 true。

时间复杂度分析：由于需要遍历字符串 s 和 t，因此时间复杂度为 O(n)，其中 n 是字符串的长度。同时，由于只用了常数个额外变量，空间复杂度为 O(字符集大小)。

具体代码展示

  1. package org.zyf.javabasic.letcode.hash;
  2.  
  3. import java.util.HashMap;
  4. import java.util.Map;
  5.  
  6. /**
  7.  * @author yanfengzhang
  8.  * @description 给定两个字符串 s 和 t，判断它们是否是同构字符串。
  9.  * 如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。
  10.  * 所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。
  11.  * @date 2023/4/10  23:30
  12.  */
  13. public class IsomorphicStrings {
  14.  
  15.     /**
  16.      * 同构字符串问题可以通过哈希表和字符映射来解决。具体步骤如下：
  17.      * 
  18.      * 创建两个哈希表，分别用于记录 s 到 t 的字符映射和 t 到 s 的字符映射。
  19.      * 遍历字符串 s 和 t，对于每个字符，分别在两个哈希表中查找其对应的字符映射。
  20.      * 如果两个哈希表中都能找到对应的字符映射，但不相同，则说明 s 和 t 不是同构字符串，直接返回 false。
  21.      * 如果两个哈希表中只有其中一个哈希表中能找到对应的字符映射，则说明 s 和 t 不是同构字符串，直接返回 false。
  22.      * 如果两个哈希表中都找不到对应的字符映射，则将当前字符的映射加入两个哈希表中。
  23.      * 遍历结束后，没有发现不同的字符映射，则说明 s 和 t 是同构字符串，返回 true。
  24.      */
  25.     public boolean isIsomorphic(String s, String t) {
  26.         if (s.length() != t.length()) {
  27.             return false;
  28.         }
  29.         /*s 到 t 的字符映射*/
  30.         Map s2t = new HashMap<>();
  31.         /*t 到 s 的字符映射*/
  32.         Map t2s = new HashMap<>();
  33.         for (int i = 0; i < s.length(); i++) {
  34.             char x = s.charAt(i);
  35.             char y = t.charAt(i);
  36.             if ((s2t.containsKey(x) && s2t.get(x) != y) || (t2s.containsKey(y) && t2s.get(y) != x)) {
  37.                 /*如果两个哈希表中都能找到对应的字符映射，但不相同，则说明 s 和 t 不是同构字符串，直接返回 false。*/
  38.                 return false;
  39.             }
  40.             if (!s2t.containsKey(x) && !t2s.containsKey(y)) {
  41.                 /*如果两个哈希表中都找不到对应的字符映射，则将当前字符的映射加入两个哈希表中。*/
  42.                 s2t.put(x, y);
  43.                 t2s.put(y, x);
  44.             }
  45.         }
  46.         return true;
  47.     }
  48.  
  49.     public static void main(String[] args) {
  50.         String s1 = "egg";
  51.         String t1 = "add";
  52.         /*true*/
  53.         System.out.println(new IsomorphicStrings().isIsomorphic(s1, t1));
  54.  
  55.         String s2 = "foo";
  56.         String t2 = "bar";
  57.         /*false*/
  58.         System.out.println(new IsomorphicStrings().isIsomorphic(s2, t2));
  59.  
  60.         String s3 = "paper";
  61.         String t3 = "title";
  62.         /*true*/
  63.         System.out.println(new IsomorphicStrings().isIsomorphic(s3, t3));
  64.     }
  65. }

（二十）两个数组的交集（Intersection of Two Arrays）

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

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

示例 2：输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4].        输出：[9,4]

说明：

  • 输出结果中的每个元素一定是唯一的。
  • 我们可以不考虑输出结果的顺序。

解题思路

该问题可以通过哈希表来解决。具体步骤如下：

  1. 首先创建了一个 set，用于存储 nums1 中的元素。
  2. 然后，遍历 nums2 中的元素，如果其在 set 中存在，则将其添加到另一个 set 中。
  3. 最后，将新 set 转换为数组并返回。

时间复杂度分析：由于需要遍历 nums1 和 nums2，因此时间复杂度为 O(m+n)，其中 m 和 n 分别为 nums1 和 nums2 的长度。同时，由于使用了两个 set，空间复杂度为 O(m+n)。

具体代码展示

  1. package org.zyf.javabasic.letcode.hash;
  2.  
  3. import java.util.Arrays;
  4. import java.util.HashSet;
  5. import java.util.Set;
  6.  
  7. /**
  8.  * @author yanfengzhang
  9.  * @description 给定两个数组，编写一个函数来计算它们的交集。
  10.  * @date 2023/4/10  23:45
  11.  */
  12. public class IntersectionTwoArrays {
  13.  
  14.     /**
  15.      * 该问题可以通过哈希表来解决。具体步骤如下：
  16.      * 
  17.      * 首先创建了一个 set，用于存储 nums1 中的元素。
  18.      * 然后，遍历 nums2 中的元素，如果其在 set 中存在，则将其添加到另一个 set 中。
  19.      * 最后，将新 set 转换为数组并返回。
  20.      */
  21.     public int[] intersection(int[] nums1, int[] nums2) {
  22.         /*创建一个 set，用于存储 nums1 中的元素*/
  23.         Set set = new HashSet<>();
  24.         for (int num : nums1) {
  25.             set.add(num);
  26.         }
  27.  
  28.         /*创建一个 set，用于存储 nums2 和 nums1 中的交集*/
  29.         Set intersect = new HashSet<>();
  30.         for (int num : nums2) {
  31.             /*如果 num 存在于 set 中，则将其添加到 intersect 中*/
  32.             if (set.contains(num)) {
  33.                 intersect.add(num);
  34.             }
  35.         }
  36.  
  37.         /*将 intersect 转换为数组*/
  38.         int[] res = new int[intersect.size()];
  39.         int i = 0;
  40.         for (int num : intersect) {
  41.             res[i++] = num;
  42.         }
  43.  
  44.         return res;
  45.     }
  46.  
  47.     public static void main(String[] args) {
  48.         int[] nums1 = {1, 2, 2, 1};
  49.         int[] nums2 = {2, 2};
  50.         int[] result = new IntersectionTwoArrays().intersection(nums1, nums2);
  51.         System.out.println("Intersection of nums1 and nums2: " + Arrays.toString(result));
  52.     }
  53. }

（二一）两个数组的交集 II（Intersection of Two Arrays II）

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

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

示例 2:输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]         输出：[4,9]

说明：

  • 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
  • 我们可以不考虑输出结果的顺序。

进阶:

  • 如果给定的数组已经排好序呢？你将如何优化你的算法？
  • 如果 nums1 的大小比 nums2 小很多，哪种方法更优？
  • 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

解题思路

思路如下：

  1. 创建一个哈希表，用于存储 nums1 中的所有数及其出现次数。
  2. 遍历 nums2，对于每个数，判断其是否在哈希表中出现过。
  3. 如果当前数在哈希表中出现过，则将其添加到列表中，并将哈希表中该数的出现次数减一。
  4. 将列表转换成数组，并返回。

时间复杂度分析：由于需要遍历 nums1 和 nums2，因此时间复杂度为 O(n+m)，其中 n 和 m 分别是 nums1 和 nums2 的长度。同时，由于需要使用哈希表存储 nums1 中的数及其出现次数，空间复杂度为 O(n)。

具体代码展示

  1. package org.zyf.javabasic.letcode.hash;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.Arrays;
  5. import java.util.HashMap;
  6. import java.util.List;
  7. import java.util.Map;
  8.  
  9. /**
  10.  * @author yanfengzhang
  11.  * @description 给定两个数组，编写一个函数来计算它们的交集。
  12.  * @date 2023/4/10  23:32
  13.  */
  14. public class IntersectionTwoArrays {
  15.  
  16.     /**
  17.      * 该问题可以通过哈希表来解决。具体步骤如下：
  18.      * 
  19.      * 遍历 nums1 数组，将其中的每个元素加入哈希表中，并记录其出现次数。
  20.      * 遍历 nums2 数组，对于其中的每个元素，如果在哈希表中出现过，则将该元素加入答案数组，并在哈希表中将其出现次数减 1。
  21.      * 遍历结束后，返回答案数组。
  22.      */
  23.     public int[] intersect(int[] nums1, int[] nums2) {
  24.         /*创建一个哈希表，用于存储 nums1 中的所有数及其出现次数*/
  25.         Map map = new HashMap<>();
  26.         for (int num : nums1) {
  27.             map.put(num, map.getOrDefault(num, 0) + 1);
  28.         }
  29.  
  30.         /*创建一个列表，用于存储 nums1 和 nums2 的交集*/
  31.         List list = new ArrayList<>();
  32.         for (int num : nums2) {
  33.             if (map.containsKey(num) && map.get(num) > 0) {
  34.                 /*如果当前数在哈希表中出现过，则将其添加到列表中，并将哈希表中该数的出现次数减一*/
  35.                 list.add(num);
  36.                 map.put(num, map.get(num) - 1);
  37.             }
  38.         }
  39.  
  40.         /*将列表转换成数组，并返回*/
  41.         int[] result = new int[list.size()];
  42.         for (int i = 0; i < list.size(); i++) {
  43.             result[i] = list.get(i);
  44.         }
  45.         return result;
  46.     }
  47.  
  48.  
  49.     public static void main(String[] args) {
  50.         int[] nums1 = {1, 2, 2, 1};
  51.         int[] nums2 = {2, 2};
  52.         int[] intersection = new IntersectionTwoArrays().intersect(nums1, nums2);
  53.         /*[2, 2]*/
  54.         System.out.println(Arrays.toString(intersection));
  55.  
  56.         int[] nums3 = {4, 9, 5};
  57.         int[] nums4 = {9, 4, 9, 8, 4};
  58.         intersection = new IntersectionTwoArrays().intersect(nums3, nums4);
  59.         /*[4, 9]*/
  60.         System.out.println(Arrays.toString(intersection));
  61.  
  62.     }
  63.  
  64. }

（二二）分糖果（Distribute Candies）

题目描述：给定一个偶数长度的数组，其中不同的数字代表着不同种类的糖果，每个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。

示例 1:输入: candies = [1,1,2,2,3,3].       输出: 3

解析: 一共有三种种类的糖果，每一种都有两个。

         只能将其中一种分给妹妹，所以最大种类数为 3。

示例 2:输入: candies = [1,1,2,3].             输出: 2

解析: 只有两种不同种类的糖果，每一种都有两个。

          妹妹分别分到了一种和二种的糖果，所以最大种类数为 2。

提示：

  • 2 <= candies.length <= 10^4
  • candies.length 是偶数
  • -10^5 <= candies[i] <= 10^5

解题思路

分糖果问题可以使用哈希表来解决。具体步骤如下：

  1. 遍历糖果数组 candies，使用哈希表统计糖果的种类数。
  2. 如果糖果的种类数大于糖果数组长度的一半，则最多只能拥有糖果数组长度的一半种糖果。否则，能够拥有所有的糖果种类。
  3. 返回最终结果。

时间复杂度分析：遍历一遍糖果数组需要 O(n) 的时间，其中 n 是糖果数组的长度。同时，由于只用了一个哈希表，空间复杂度为 O(n)。

具体代码展示

  1. package org.zyf.javabasic.letcode.hash;
  2.  
  3. import java.util.HashSet;
  4. import java.util.Set;
  5.  
  6. /**
  7.  * @author yanfengzhang
  8.  * @description 给定一个偶数长度的数组，其中不同的数字代表着不同种类的糖果，每个数字代表一个糖果。
  9.  * 你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。
  10.  * @date 2023/4/10  23:50
  11.  */
  12. public class DistributeCandies {
  13.  
  14.     /**
  15.      * 分糖果问题可以使用哈希表来解决。具体步骤如下：
  16.      * 
  17.      * 遍历糖果数组 candies，使用哈希表统计糖果的种类数。
  18.      * 如果糖果的种类数大于糖果数组长度的一半，则最多只能拥有糖果数组长度的一半种糖果。否则，能够拥有所有的糖果种类。
  19.      * 返回最终结果。
  20.      */
  21.     public int distributeCandies(int[] candies) {
  22.         /*统计糖果的种类数*/
  23.         Set set = new HashSet<>();
  24.         for (int candy : candies) {
  25.             set.add(candy);
  26.         }
  27.         /*如果糖果的种类数大于糖果数组长度的一半，最多只能拥有糖果数组长度的一半种糖果*/
  28.         int n = candies.length;
  29.         int maxNum = n / 2;
  30.         int candyType = set.size();
  31.         return candyType >= maxNum ? maxNum : candyType;
  32.     }
  33.  
  34.     public static void main(String[] args) {
  35.         int[] candies1 = {1, 1, 2, 2, 3, 3};
  36.         int[] candies2 = {1, 1, 2, 3};
  37.         int[] candies3 = {6, 6, 6, 6};
  38.         int[] candies4 = {1, 1, 1, 1, 2, 2, 2, 3, 3, 3};
  39.  
  40.         /*Output: 3*/
  41.         System.out.println(new DistributeCandies().distributeCandies(candies1));
  42.         /*Output: 2*/
  43.         System.out.println(new DistributeCandies().distributeCandies(candies2));
  44.         /*Output: 1*/
  45.         System.out.println(new DistributeCandies().distributeCandies(candies3));
  46.         /*Output: 3*/
  47.         System.out.println(new DistributeCandies().distributeCandies(candies4));
  48.     }
  49.  
  50. }

（二三）宝石与石头（Jewels and Stones）

题目描述：给定字符串 J 代表石头中宝石的类型，和字符串 S 代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。

J 中的字母不重复，J 和 S 中的所有字符都是字母。字母区分大小写，因此"a"和"A"是不同类型的石头。

示例 1:输入: J = "aA", S = "aAAbbbb".         输出: 3

示例 2:输入: J = "z", S = "ZZ"                       输出: 0

注意:

  • S 和 J 最多含有50个字母。
  •  J 中的字符不重复。

解题思路

宝石与石头问题可以使用哈希表来解决。具体步骤如下：

  1. 遍历字符串 J 中的每个字符，使用哈希表记录宝石的种类和数量。
  2. 遍历字符串 S 中的每个字符，如果该字符是宝石，则更新计数器。
  3. 返回计数器的值即为宝石的数量。

时间复杂度分析：遍历一遍字符串 J 和 S 需要 O(n) 的时间，其中 n 是字符串的长度。同时，由于只用了一个哈希表，空间复杂度为 O(n)。

具体代码展示

  1. package org.zyf.javabasic.letcode.hash;
  2.  
  3. import java.util.HashMap;
  4. import java.util.Map;
  5.  
  6. /**
  7.  * @author yanfengzhang
  8.  * @description 给定字符串 J 代表石头中宝石的类型，和字符串 S 代表你拥有的石头。
  9.  * S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
  10.  * 
  11.  * J中的字母不重复，J和S 中的所有字符都是字母。字母区分大小写，因此"a"和"A"是不同类型的石头。
  12.  * @date 2023/4/10  23:53
  13.  */
  14. public class JewelsAndStones {
  15.  
  16.     /**
  17.      * 宝石与石头问题可以使用哈希表来解决。具体步骤如下：
  18.      * 
  19.      * 遍历字符串 J 中的每个字符，使用哈希表记录宝石的种类和数量。
  20.      * 遍历字符串 S 中的每个字符，如果该字符是宝石，则更新计数器。
  21.      * 返回计数器的值即为宝石的数量。
  22.      */
  23.     public int numJewelsInStones(String J, String S) {
  24.         /*创建哈希表用于记录宝石的种类和数量*/
  25.         Map map = new HashMap<>();
  26.  
  27.         /*遍历字符串 J 中的每个字符，记录宝石的种类和数量*/
  28.         for (char c : J.toCharArray()) {
  29.             map.put(c, map.getOrDefault(c, 0) + 1);
  30.         }
  31.         /*计数器，用于记录宝石的数量*/
  32.         int count = 0;
  33.  
  34.         /*遍历字符串 S 中的每个字符，如果该字符是宝石，则更新计数器*/
  35.         for (char c : S.toCharArray()) {
  36.             if (map.containsKey(c)) {
  37.                 count++;
  38.             }
  39.         }
  40.         /*返回计数器的值即为宝石的数量*/
  41.         return count;
  42.     }
  43.  
  44.     public static void main(String[] args) {
  45.         String J = "aA";
  46.         String S = "aAAbbbb";
  47.         int result = new JewelsAndStones().numJewelsInStones(J, S);
  48.         /*Output: 3*/
  49.         System.out.println(result);
  50.     }
  51. }

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览62532 人正在系统学习中
注：本文转载自blog.csdn.net的张彦峰ZYF的文章"https://zyfcodes.blog.csdn.net/article/details/127559869"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！