-
算法（三）
哈希表算法章节
(1)
- 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
- 注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
class Solution { public boolean isAnagram(String s, String t) { //先说明一下字母异位词的定义： //两个字符串的字母组成完全相同 //这里使用哈希法 //简单创建一个哈希数组：int[] hash int hash[] =new int[26];//默认初始化都为0 //因为表示26个小写字母（'a'到'z'） //'a'-'a'=0存储在hash[0], 'b'-'a'=1存储在hash[1]以此类推 //开始分别遍历两个字符串 for(int i=0;i<s.length();i++){ hash[s.charAt(i)-'a']++; } for(int j=0;j<t.length();j++){ hash[t.charAt(j)-'a']--; } //检查hash数组中是否有不为0的元素 for(int i=0;i<hash.length;i++){ if(hash[i]!=0){ return false; } } return true; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
(2)
当我们需要存储一组元素，并且要求元素不重复时，可以使用Set集合。
- Set是Java中的一个接口，它的实现类有HashSet、TreeSet和LinkedHashSet。
- HashSet：使用哈希表实现，不保证元素的顺序，是最常用的Set实现类。
- TreeSet：使用红黑树实现，可以对元素进行排序，但插入和查找操作的时间复杂度较高。
- LinkedHashSet：使用链表和哈希表实现，保证元素的插入顺序。
- 当我们向Set集合中添加元素时，Set会根据元素的hashCode值来判断是否已存在相同的元素。
如果两个元素的hashCode值相等，Set会调用它们的equals方法进行进一步比较。
具体步骤如下：
- 创建两个Set集合，分别用来存储两个数组的元素。
- 遍历第一个数组，将每个元素添加到第一个Set集合中。
- 遍历第二个数组，对于每个元素，判断是否存在于第一个Set集合中。
- 如果存在，则将该元素添加到结果集合中。
- 最后，将结果集合转换为整数数组并返回。
class Solution { public int[] intersection(int[] nums1, int[] nums2) { // 创建两个Set集合，用于存储数组元素 Set<Integer> set1 = new HashSet<>(); Set<Integer> resultSet = new HashSet<>(); // 将nums1数组的元素添加到set1集合中 for (int num : nums1) { set1.add(num); } // 遍历nums2数组，判断元素是否存在于set1集合中 for (int num : nums2) { if (set1.contains(num)) { resultSet.add(num); } } // 将结果集合转换为整数数组 int[] resultArray = new int[resultSet.size()]; int index = 0; for (int num : resultSet) { resultArray[index] = num; index++; } return resultArray; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
（3）双指针法——快乐数
- 编写一个算法来判断一个数 n 是不是快乐数。
- 「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环，但始终变不到 1。
- 如果 可以变为 1，那么这个数就是快乐数。
- 如果 n 是快乐数就返回 True ；不是，则返回 False 。
解释一下快乐数：
- 不是所有的正整数都会进入循环。事实上，只有一部分正整数会进入循环，而另一部分正整数最终会收敛到1。
- 对于那些会进入循环的正整数，它们的平方和计算过程会在某个特定的数值上循环，而不是收敛到1。这些数被称为“不快乐数”。
- 例如，考虑数字4。计算过程如下：4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4。可以看到，进入了一个循环。因此，4被认为是一个不快乐数，因为它最终无法收敛到1。
- 另一方面，如果一个正整数最终收敛到1，那么它被称为“快乐数”。例如，数字19通过计算平方和的过程最终收敛到1：19 -> 82 -> 68-> 100 -> 1。因此，19被认为是一个快乐数。
class Solution { public boolean isHappy(int n) { int slow = n; // 慢指针从n开始 int fast = n; // 快指针从n开始 do { slow = calculateSquareSum(slow); // 慢指针每次计算平方和 fast = calculateSquareSum(calculateSquareSum(fast)); // 快指针每次计算两次平方和 } while (slow != fast); // 当慢指针和快指针相等时，表示进入了循环 return slow == 1; // 如果最终平方和等于1，说明是快乐数 } private static int calculateSquareSum(int num) { int sum = 0; while (num > 0) { int digit = num % 10; // 取出个位数 sum += digit * digit; // 平方和累加 num /= 10; // 去除个位数 } return sum; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
以前觉得算法可无聊了，突然发现，这玩意挺上瘾啊，虽然很菜，但很解困啊🍚🍚🍚🍚🍚🍚🍚🍗🍗🍗🍗🍭🍭🍭🍭🍭🍭🍭🍭🧃🧃🧃🧃🧃🍵🍵🍵🍵🍵🍵💫💫💫💫😋😋😋😋😋😋
（4）两数之和
题目：
- 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
- 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
- 你可以按任意顺序返回答案。
class Solution { public int[] twoSum(int[] nums, int target) { // 创建一个HashMap，用于存储数组元素与其下标的映射关系 Map<Integer, Integer> map = new HashMap<>(); // 遍历数组 for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; // 判断当前元素的补数是否已经存在于HashMap中 // 如果存在，则返回对应的下标 if (map.containsKey(complement)) { return new int[] {map.get(complement), i}; } // 如果补数不存在于HashMap中，则将当前元素与其下标存入HashMap map.put(nums[i], i); } // 如果未找到符合条件的两个数，则返回一个空数组 return new int[0]; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
（5）四数相加
- 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
- 为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。
map.getOrDefault(sum, 0) + 1
是Java中的一个表达式，用于获取Map中指定键的值，如果键不存在则返回默认值。在这个表达式中，sum是作为键，0是作为默认值。如果sum这个键存在于map中，则返回与该键对应的值加1；如果sum这个键不存在，则返回默认值0加1。
class Solution { public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { int res = 0; Map<Integer, Integer> map = new HashMap<Integer, Integer>(); //统计两个数组中的元素之和，同时统计出现的次数，放入map for (int i : nums1) { for (int j : nums2) { int sum = i + j; map.put(sum, map.getOrDefault(sum, 0) + 1); } } //统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数 for (int i : nums3) { for (int j : nums4) { res += map.getOrDefault(0 - i - j, 0); } } return res; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
（6）三数之和
- 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0
- 请你找出所有满足条件且不重复的三元组。
- 注意： 答案中不可以包含重复的三元组。
class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> result = new ArrayList<>(); Arrays.sort(nums); for (int i = 0; i < nums.length - 2; i++) { if (i > 0 && nums[i] == nums[i-1]) { continue; } int left = i + 1; int right = nums.length - 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum == 0) { result.add(Arrays.asList(nums[i], nums[left], nums[right])); while (left < right && nums[left] == nums[left+1]) { left++; } while (left < right && nums[right] == nums[right-1]) { right--; } left++; right--; } else if (sum < 0) { left++; } else { right--; } } } return result; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
（7）四数之和
- 题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？
- 找出所有满足条件且不重复的四元组。
- 注意：答案中不可以包含重复的四元组。
class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> result = new ArrayList<>(); if (nums == null || nums.length < 4) { return result; } Arrays.sort(nums); for (int i = 0; i < nums.length - 3; i++) { // 避免重复的元素 if (i > 0 && nums[i] == nums[i - 1]) { continue; } for (int j = i + 1; j < nums.length - 2; j++) { // 避免重复的元素 if (j > i + 1 && nums[j] == nums[j - 1]) { continue; } int left = j + 1; int right = nums.length - 1; while (left < right) { int sum = nums[i] + nums[j] + nums[left] + nums[right]; if (sum == target) { result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right])); // 避免重复的元素 while (left < right && nums[left] == nums[left + 1]) { left++; } while (left < right && nums[right] == nums[right - 1]) { right--; } left++; right--; } else if (sum < target) { left++; } else { right--; } } } } return result; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
-
相关阅读:
数据链路层【Linux网络复习版】
npm简单介绍
姓祝男孩名字简单大气
SpringBoot实现基于token的登录验证
MySQL数据库
看完不会来揍我 | R包的下载与安装 | 再也没有一个包可以逃出你的手掌心啦
Python表格处理模块xlrd在Anaconda中的安装
简易的安卓天气app(二)——适配器、每小时数据展示
【论文整理1】On the Continuity of Rotation Representations in Neural Networks
汽车软件的模糊测试
- 原文地址：https://blog.csdn.net/m0_59076472/article/details/133020430
