代码随想录

桃扇骨 2024-02-22 09:14 48阅读 0赞

## 前言 ##

代码随想录算法训练营day06

--------------------

## 一、哈希表基础知识 ##

*  【 [代码随想录][Link 1]】
 *  【[菜鸟教程][Link 2]】

## 二、Leetcode 242.有效的字母异位词 ##

### 1.题目 ###

给定两个字符串 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 仅包含小写字母

来源：力扣（LeetCode） 链接：[leetcode.cn/problems/va…][leetcode.cn_problems_va]

### 2.解题思路 ###

1.  方法一 ：

*  将两个字符串分别存储在两个hashmap中
 *  用equals方法比较两个hashmap是否相等

1.  方法二 :

*  将两个字符串用(String).toCharArray转为两个字符数组
 *  再用Arrays.sort将两个数组分别排序
 *  最后用Array.equals方法判断两个数组是否相等

1.  方法三

*  题意其实就是比较两个字符串是否相等，只有两个字符串有一个字母不一样就输出false
 *  由于都是小写英文字母，我们可以定义一个长度为26的差异数组，具体作用如下
 *  遍历第一个字符串s, 每个字母对应的差异数组的位置上元素赋值++
 *  遍历完第一个字符串s后遍历第二个字符串t, 每个字母对应的差异数组的位置上元素赋值--, --操作后并判断该字符所在差异数组的值是否不为0(由于是--操作，即是否小于0), 是，则两个字符串不同，输出false

### 3.代码实现 ###

*  方法一 ：hashmap统计

java

复制代码

`class Solution { public static boolean isAnagram(String s, String t) { if(s.length() != t.length()) { return false; } Map<Character,Integer> hashMap = new HashMap<Character,Integer>(); Map<Character,Integer> hashMap1 = new HashMap<Character,Integer>(); for(int i = 0; i < s.length(); i++) { hashMap.put(s.charAt(i), hashMap.getOrDefault(s.charAt(i), 0) + 1); hashMap1.put(t.charAt(i), hashMap1.getOrDefault(t.charAt(i), 0) + 1); } return hashMap.equals(hashMap1); } }`

*  方法二 ：转字符数组后排序

java

复制代码

`class Solution { public boolean isAnagram(String s, String t) { if (s.length() != t.length()) { return false; } char[] str1 = s.toCharArray(); char[] str2 = t.toCharArray(); Arrays.sort(str1); Arrays.sort(str2); return Arrays.equals(str1, str2); } }`

1.  方法三 ： 创建记录差异的数组

java

复制代码

`class Solution { public boolean isAnagram(String s, String t) { if (s.length() != t.length()) { return false; } int[] table = new int[26]; for (int i = 0; i < s.length(); i++) { table[s.charAt(i) - 'a']++; } for (int i = 0; i < t.length(); i++) { table[t.charAt(i) - 'a']--; if (table[t.charAt(i) - 'a'] < 0) { return false; } } return true; } }`

## 三、Leetcode 349. 两个数组的交集 ##

### 1.题目 ###

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

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

示例 2：

输入：nums1 = \[4,9,5\], nums2 = \[9,4,9,8,4\] 输出：\[9,4\] 解释：\[4,9\] 也是可通过的

提示：

*  1 <= nums1.length, nums2.length <= 1000
 *  0 <= nums1\[i\], nums2\[i\] <= 1000

来源：力扣（LeetCode） 链接：[leetcode.cn/problems/in…][leetcode.cn_problems_in]

### 2.解题思路 ###

方法一：两个集合

*  首先使用两个集合分别存储两个数组中的元素
 *  然后遍历较小的集合，判断其中的每个元素是否在另一个集合中，如果元素也在另一个集合中，则将该元素添加到返回值

### 3.代码实现 ###

*  方法一 : 两个集合

java

复制代码

`class Solution { public int[] intersection(int[] nums1, int[] nums2) { Set<Integer> set1 = new HashSet<Integer>(); Set<Integer> set2 = new HashSet<Integer>(); for (int num : nums1) { set1.add(num); } for (int num : nums2) { set2.add(num); } return getIntersection(set1, set2); } public int[] getIntersection(Set<Integer> set1, Set<Integer> set2) { if (set1.size() > set2.size()) { return getIntersection(set2, set1); } Set<Integer> intersectionSet = new HashSet<Integer>(); for (int num : set1) { if (set2.contains(num)) { intersectionSet.add(num); } } int[] intersection = new int[intersectionSet.size()]; int index = 0; for (int num : intersectionSet) { intersection[index++] = num; } return intersection; } }`

## 四、Leetcode面试题 02.07. 链表相交 ##

### 1.快乐数 ###

编写一个算法来判断一个数 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

来源：力扣（LeetCode） 链接：[leetcode.cn/problems/ha…][leetcode.cn_problems_ha]

### 2.解题思路 ###

方法一 ： 哈希表+取余

详情见代码注释

### 3.代码实现 ###

*  哈希集合

java

复制代码

`class Solution { public boolean isHappy(int n) { HashSet<Integer> set = new HashSet<>(); // 计算每个数字按快乐数运算后的新数字 int sum = 0; // 个位 int single; // 循环 while(true){ // 取余得到个位 single = n%10; // 累加 sum += single*single; // 例如 n = 19, 此时 n = 1,然后再取余，则得到1,这样就取到了1和9 n = n /10; // n=0说明当前数字已经按快乐数运算了一次 if(n==0){ // 将sum也就是新的数字 赋值给n n = sum; // 如果sum=1说明已经是快乐数了返回true if(sum==1){ return true; } // 如果哈希表中包含了sum，说明出现了循环，和环形链表一个道理,返回false.不是快乐数 if(set.contains(sum)){ return false; } // 先判断再添加，否则会将自己判断进去！那么必将返回true set.add(sum); // 重置sum的值，重新累加 sum = 0; } } } }`

## 五、1. 两数之和 ##

### 1.题目 ###

给定一个整数数组 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
 *  只会存在一个有效答案

来源：力扣（LeetCode） 链接：[leetcode.cn/problems/tw…][leetcode.cn_problems_tw]

### 2.解题思路 ###

*  最容易想到的方法是枚举数组中的每一个数 x，使用哈希表寻找数组中是否存在 target - x
 *  当我们使用遍历整个数组的方式寻找 target - x 时，需要注意到每一个位于 x 之前的元素都已经和 x 匹配过，因此不需要再进行匹配
 *  而每一个元素不能被使用两次，所以我们只需要在 x 后面的元素中寻找 target - x

### 3.代码实现 ###

*  哈希集合

java

复制代码

`class Solution { public static int[] twoSum(int[] nums, int target) { Map<Integer,Integer> hashMap = new HashMap<Integer,Integer>(); for(int i = 0; i < nums.length; i++) { if(hashMap.containsKey(target - nums[i])) { return new int[] {hashMap.get(target - nums[i]), i}; } else { hashMap.put(nums[i], i); } } return new int[0]; } }`

作者：东离与糖宝  
链接：https://juejin.cn/post/7232229178278690873  
来源：稀土掘金  
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

[Link 1]: https://link.juejin.cn?target=https%3A%2F%2Fwww.programmercarl.com%2F%25E5%2593%2588%25E5%25B8%258C%25E8%25A1%25A8%25E7%2590%2586%25E8%25AE%25BA%25E5%259F%25BA%25E7%25A1%2580.html%23%25E5%2593%2588%25E5%25B8%258C%25E8%25A1%25A8
[Link 2]: https://link.juejin.cn?target=https%3A%2F%2Fwww.runoob.com%2Fjava%2Fjava-hashmap.html
[leetcode.cn_problems_va]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fvalid-anagram
[leetcode.cn_problems_in]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fintersection-of-two-arrays
[leetcode.cn_problems_ha]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fhappy-number
[leetcode.cn_problems_tw]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Ftwo-sum