【代码随想录】第二、三章-链表、哈希表

第二章 链表

1 环形链表II

142.环形链表II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点

思路：
使用两个指针 slow 和 fast：slow 每次移动一步。fast 每次移动两步。
如果链表有环，那么 slow 和 fast 终会相遇（在环中某点）。当相遇时，将其中一个指针（例如 slow）移到链表头部，另一个指针保持在相遇点。两指针均每次移动一步。
两指针再次相遇时的位置就是环的起点。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            if (fast == slow) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}

第三章 哈希表

1 有效的字母异位词

242.有效的字母异位词

给定两个字符串s和t，编写一个函数来判断t是否是s的字母异位词。
输入：s = “anagram”, t = “nagaram” 输出：true

思路：
定义一个数组26个字母长度的叫做record用来上记录字符串s里字符出现的次数。S串给record增加，t串给record减少，最后检查record即可

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

383.赎金信

给定一个赎金信(ransom)字符串和一个杂志(magazine)字符串，判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成。如果可以构成，返回true；否则返回false。为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。
输入：ransom = “aa”, magazine = “aab” 输出：true

思路：
与上一个类似，只不过是用magazine来增加，ransom进行减少，最后看record中是否有负数即可。

49.字母异位词分组

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词是由重新排列源单词的所有字母得到的一个新单词。
输入：strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] 输出：[[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

思路：
先对字符串排序，对排好序的字符串以字符串为key构建哈希表，value是相同排序序列所对应的list集合。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> strToListMap = new HashMap<>();
        for (String str : strs) {
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            String sortedStr = new String(charArray);
            if (!strToListMap.containsKey(sortedStr)) {
                strToListMap.put(sortedStr, new ArrayList<>());
            }
            strToListMap.get(sortedStr).add(str);
        }
        return new ArrayList<>(strToListMap.values());
    }
}

438.找到字符串中所有字母异位词（哈希表结合滑动窗口）

给定两个字符串s和p，找到s中所有p的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
输入：s = “cbaebabacd”, p = “abc” 输出：[0,6]

思路：
与76类似，只不过是76是要最小长度，而本题是只要左右指针差值为p的长度，就把他们放入list中。
设置两个hashmap，一个为映射p的map，一个是滑动窗口的map叫window。将p先放入map集合中，使用vaild来记录当前有效的字符，只有当字符在window的key和map中的key一致时，我们才增加vaild。如果当前有效的字符跟map的大小相同时，对windows中的字符串开始收缩。注意vaild增加和减少的条件，只有当字符在map和windows中一致时，才进行vaild的加减。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if (p.length() > s.length()) {
            return new ArrayList<>();
        }
        int sn = s.length();int pn = p.length();
        char[] sc = s.toCharArray();char[] pc = p.toCharArray();
        int vaild = 0;int start = 0;
        Map<Character, Integer> map = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        for (char c : p.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        int l = 0, r = 0;
        List<Integer> list=new ArrayList<>();
        while (r < sn) {
            char a = sc[r];
            r++;
            if (map.containsKey(a)) {
                window.put(a, window.getOrDefault(a, 0) + 1);
                if (map.get(a).equals(window.get(a))) {
                    vaild++;
                }
            }
            while (vaild == map.size()) {
                if (r - l == p.length()) {
                    list.add(l);
                }
                char b = sc[l];
                l++;
                if (map.containsKey(b)) {
                    if (map.get(b).equals(window.get(b))) {
                        vaild--;
                    }
                    window.put(b, window.get(b) - 1);
                }
            }
        }
        return list;
    }
}

2 两个数组的交集

349.两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。
输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2]

思路：
自定义hashmap即可。

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int[] map = new int[1001];
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums1.length; i++) {
            map[nums1[i]] = -1;
        }
        for (int i = 0; i < nums2.length; i++) {
            if (map[nums2[i]] == -1)    map[nums2[i]] = 1;
        }
        for (int i = 0; i < 1001; i++) {
            if (map[i] == 1)    list.add(i);
        }
        int[] arr = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            arr[i] = list.get(i);
        }
        return arr;
    }
}

350.两个数组的交集II

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
输入：nums1 = [4,4,4,9,5], nums2 = [9,4,9,8,4] 输出：[4,4,9]

思路：
针对hashmap进行处理，将长的数组放入map中，然后短的数组对map进行减减，每次减减的时候放入交集数组，如果减为0，就将其从map中移除。

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : nums1) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        int[] intersection = new int[nums1.length];
        int index = 0;
        for (int num : nums2) {
            int count = map.getOrDefault(num, 0);
            if (count > 0) {
                intersection[index++] = num;
                count--;
                if (count > 0) {
                    map.put(num, count);
                } else {
                    map.remove(num);
                }
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}

3 快乐数

202.快乐数

编写一个算法来判断一个数n是不是快乐数。「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为1，也可能是无限循环但始终变不到1。如果可以变为1，那么这个数就是快乐数。如果n是快乐数就返回True；不是，则返回False。
输入：19 输出：true
解释：1² + 9² = 82 8² + 2² = 68 6² + 8² = 100 1² + 0² + 0² =1

思路：
为了防止循环的出现，使用hashset记录数字，如果是1就返回true，如果在hashmap出现过，就说明已经开始循环，返回false。每回对num进行处理即可。

class Solution {
    public boolean isHappy(int n) {
        HashSet<Integer> hash = new HashSet<>();
        return fn(hash, n);
    }
    public boolean fn(HashSet<Integer> hash, int n) {
        if (n == 1) {
            return true;
        }
        if (hash.contains(n)) {
            return false;
        }
        hash.add(n);
        int ans = 0;
        while (n > 0) {
            ans += (n % 10) * (n % 10);
            n /= 10;
        }
        return fn(hash, ans);
    }
}

4 两数之和

1.两数之和

给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。
输入：nums=[2,7,11,15],target=9 输出：[0,1]

思路：
遍历一个存一个哈希，然后用target减一下，为0就输出，不为0就放进去。

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

15.三数之和

给你一个整数数组nums，判断是否存在三元组[nums[i],nums[j],nums[k]]满足i!=j、i!=k且j!=k，同时还满足nums[i]+nums[j]+nums[k]==0。请你返回所有和为0且不重复的三元组。
输入：nums=[-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]]

思路：
固定一个，剩下俩双指针就好。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        int len = nums.length;
        int target=0;
        for (int i = 0; i < len - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            int m = i + 1;
            int n = len - 1;
            while (m < n) {
                long sum = (long) nums[i] + nums[m] + nums[n];
                if (sum > target) {
                    n--;
                } else if (sum < target) {
                    m++;
                } else {
                    res.add(Arrays.asList(nums[i], nums[m], nums[n]));
                    while (m < n && nums[n] == nums[n - 1])n--;
                    while (m < n && nums[m] == nums[m + 1])m++;
                    n--;
                    m++;
                }
            }
        }
        return res;
    }
}

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
输入：nums=[1,0,-1,0,-2,2],target=0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

思路：
固定俩，剩下俩双指针。

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        int len = nums.length;
        for (int i = 0; i < len - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < len - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                int m = j + 1;
                int n = len - 1;
                while (m < n) {
                    long sum = (long) nums[i] + nums[j] + nums[m] + nums[n];
                    if (sum > target) {
                        n--;
                    } else if (sum < target) {
                        m++;
                    } else {
                        res.add(Arrays.asList(nums[i], nums[j], nums[m], nums[n]));
                        while (m < n && nums[m] == nums[m + 1]) m++;
                        while (m < n && nums[n] == nums[n - 1]) n--;
                        m++;
                        n--;
                    }
                }
            }
        }
        return res;
    }
}

454.四数相加II

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
输入：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

思路：
将nums1和nums2先放入hashmap中，然后将nums3和nums4的和作为相反数，对hashmap进行扫描，与两数之和的hashmap思路类似，只不过是这里的两个数之和充当其中一个加数。

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int count = 0;
        int len = nums1.length;
        Map<Integer,Integer>m=new HashMap<>();
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                m.put(nums1[i] + nums2[j],m.getOrDefault(nums1[i] + nums2[j],0)+1);
            }
        }
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                int sum=nums3[i]+nums4[j];
                if(m.containsKey(-1*sum)){
                    count+=m.get(-1*sum);
                }
            }
        }
        return count;
    }
}