leetcode——链表

前言

记录一下leetcode哈希表部分题目的刷题笔记，顺序参考代码随想录中，但不仅限于这些，可以扩展记录。

代码随想录 ——哈希表理论基础

242. 有效的字母异位词

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

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

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

思路：哈希表

思路很简单，维护一个26位数组，每次遍历s的时候，对应位置的值+1，遍历t的时候，对应字母位置值-1，当有一个小于0的时候，即数量不同，直接返回false

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;
    }
}

383. 赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

输入：ransomNote = "a", magazine = "b"
输出：false

思路：哈希

和上一题思路一样，代码也一样，唯一小改动是先添加magazine字符串，后在ransomNote中进行减操作。

49. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 1:

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]

思路：哈希+排序

两个字符串互为字母异位词，当且仅当两个字符串包含的字母相同。同一组字母异位词中的字符串具备相同点，可以使用相同点作为一组字母异位词的标志，使用哈希表存储每一组字母异位词，哈希表的键为一组字母异位词的标志，哈希表的值为一组字母异位词列表。

遍历每个字符串，对于每个字符串，得到该字符串所在的一组字母异位词的标志，将当前字符串加入该组字母异位词的列表中。遍历全部字符串之后，哈希表中的每个键值对即为一组字母异位词。

由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map = new HashMap<String,List<String>>();
        for(String str :strs){
            char[] arr = str.toCharArray();
            Arrays.sort(arr);
            String key = new String(arr);
            List<String> list = map.getOrDefault(key,new ArrayList<String>());
            list.add(str);
            map.put(key,list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

• 执行用时：5 ms, 在所有 Java 提交中击败了99.07%的用户
• 内存消耗：44 MB, 在所有 Java 提交中击败了86.11%的用户
• 通过测试用例：115 / 115

349. 两个数组的交集

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

示例 1：

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

思路：HashSet

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

• 执行用时：2 ms, 在所有 Java 提交中击败了95.92%的用户
• 内存消耗：41.6 MB, 在所有 Java 提交中击败了30.32%的用户
• 通过测试用例：55 / 55

202. 快乐数

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

「快乐数」 定义为：

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

示例 1：

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

思路：HashSet

题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！

所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<>();
        while(n !=1 && !set.contains(n)){
            set.add(n);
            n = getNextNumber(n);
        }
        return n==1;
    }

    public int getNextNumber(int n ){
        int res = 0;
        while(n > 0){
            int temp = n%10;
            res += temp*temp;
            n = n/10;
        }
        return res;
    }
}

• 执行用时：1 ms, 在所有 Java 提交中击败了80.81%的用户
• 内存消耗：38.5 MB, 在所有 Java 提交中击败了66.50%的用户
• 通过测试用例：404 / 404

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

思路：哈希

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

454. 四数相加 II

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：

1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

思路：分组+哈希表

我们可以将四个数组分成两部分，AA 和 BB 为一组，CC 和 DD 为另外一组。

对于 A 和 B，我们使用二重循环对它们进行遍历，得到所有 A[i]+B[j] 的值并存入哈希映射中。对于哈希映射中的每个键值对，每个键表示一种 A[i]+B[j]，对应的值为 A[i]+B[j] 出现的次数。

对于 C和 D，我们同样使用二重循环对它们进行遍历。当遍历到 C[k]+D[l] 时，如果 -(C[k]+D[l]) 出现在哈希映射中，那么将−(C[k]+D[l]) 对应的值累加进答案中。

最终即可得到满足 A[i]+B[j]+C[k]+D[l]=0 的四元组数目。

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer,Integer> AB = new HashMap<Integer,Integer>();
        for(int u:nums1){
            for(int v:nums2){
                AB.put(u+v,AB.getOrDefault(u+v,0)+1);
            }
        }
        int ans = 0;
        for(int u:nums3){
            for(int v:nums4){
                if(AB.containsKey(-u-v)){
                    ans += AB.get(-u-v);
                }
            }
        }
        return ans;
    }
}

15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

思路：排序+双指针

本题难点在于：如何去除重复解。

由于题目要求不可以包含重复的三元组，所以，并不适合使用哈希

算法流程：

• 1、特判，对于数组长度 nn，如果数组为 null 或者数组长度小于 33，返回 []。
• 2、对数组进行排序。
• 3、遍历排序后数组：
  • 若 nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果。
  • 对于重复元素：跳过，避免出现重复解
• 令左指针 L=i+1，右指针 R=len-1，当 L<R 时，执行循环：
  • 当 nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,R 移到下一位置，寻找新的解
  • 若和大于 0，说明 nums[R]太大，R 左移
  • 若和小于 0，说明 nums[L] 太小，L 右移

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList();
        int len = nums.length;
        if(nums == null || len < 3){
            return ans;
        }
        //对原数组进行排序
        Arrays.sort(nums);
        for(int i = 0 ; i <len ; i++){
            if(nums[i] > 0){
                break;
            }
            if(i>0 && nums[i] == nums[i-1]){
                continue; //去重
            }
            int left = i + 1 , right = len - 1;
            while(left < right){
                int sum = nums[i] + nums[left] + nums[right];
                if(sum == 0){
                    ans.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 if(sum > 0){
                    right--;
                }
            }
        }
        return ans;
    }
}

• 执行用时：20 ms, 在所有 Java 提交中击败了78.19%的用户
• 内存消耗：45.5 MB, 在所有 Java 提交中击败了47.03%的用户
• 通过测试用例：318 / 318

18. 四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

思路：排序+双指针

和三数之和一样，只是多了一层for循环。

使用四个指针(a<b<c<d)。固定最小的a和b在左边，c=b+1,d=len-1 移动两个指针包夹求解。
保存使得nums[a]+nums[b]+nums[c]+nums[d]==target的解。偏大时d左移，偏小时c右移。c和d相遇时，表示以当前的a和b为最小值的解已经全部求得。b++,进入下一轮循环b循环，当b循环结束后。 a++，进入下一轮a循环。 即(a在最外层循环，里面嵌套b循环，再嵌套双指针c,d包夹求解)。

上面的解法存在重复解的原因是因为移动指针时可能出现重复数字的情况。所以我们要确保移动指针后， 对应的数字要发生改变才行。

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList();
        int len = nums.length;
        if(nums == null || len < 4){
            return ans;
        }
        Arrays.sort(nums);	//排序
        for(int i = 0 ; i < len ; i++){
            if(i > 0 && nums[i] == nums[i-1]){	//确保nums[i] 改变了
                continue;
            }
            for(int j = i+1 ; j < len ; j++){
                if(j > i +1 && nums[j] == nums[j-1]){	//确保nums[j] 改变了
                    continue;
                }
                int left = j + 1,right = len-1;
                while(left < right){
                    int sum = nums[i] + nums[j] + nums[left] +nums[right];
                    if(sum > target ){
                        right--;
                    }
                    else if(sum < target){
                        left++;
                    }else{
                        ans.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        while(right > left && nums[right] == nums[right-1]) right--;	//确保nums[right] 改变了
                        while(right > left && nums[left] == nums[left+1])   left++;		//确保nums[left] 改变了

                        left++;
                        right--;
                    }
                }
            }
        }
        return ans;
    }
}

• 执行用时：13 ms, 在所有 Java 提交中击败了64.30%的用户
• 内存消耗：41.6 MB, 在所有 Java 提交中击败了70.32%的用户
• 通过测试用例：289 / 289