力扣爆刷第137天之哈希表五连刷（环形链表哈希表）

本文主要是介绍力扣爆刷第137天之哈希表五连刷（环形链表哈希表），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

力扣爆刷第137天之哈希表五连刷（环形链表哈希表）

一、面试题 02.07. 链表相交

题目链接：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/
思路：求链表相交的位置，很简单的题目，直接求两个链表的长度，然后长度提前走几步，走到长度相等，然后同步走，并且判断。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode pa = headA, pb = headB;int lena = 0, lenb = 0;while(pa != null) {lena++;pa = pa.next;}while(pb != null) {lenb++;pb = pb.next;}pa = headA;pb = headB;for(int i = lena; i < lenb; i++) {pb = pb.next;}for(int i = lenb; i < lena; i++) {pa = pa.next;}while(pa != null) {if(pa == pb) {return pa;}pa = pa.next;pb = pb.next;}return null;}
}

二、142. 环形链表 II

题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/description/
思路：本题求的是环形链表的环的入口，一共分为两步，第一步先判断是否成环，第二步再寻找入口。
使用快慢指针，慢指针每次走一步，快指针每次走两步，当相遇时说明链表有环。
然后快指针位置不动，慢指针改为头结点，然后快慢指针同步每次一步，相遇时就是环的入口。

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

三、242. 有效的字母异位词

题目链接：https://leetcode.cn/problems/valid-anagram/description/
思路：求字符串是否是异位词，用一个数组来代替哈希表，字符存在则对应位置+1，不存在则对应位置-1。若最后数组不全为0则非法。

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

四、349. 两个数组的交集

题目链接：https://leetcode.cn/problems/intersection-of-two-arrays/description/
思路：用两个set，第一个set收集第一个数组的元素，然后遍历第二个数组，看看元素是否存在于第一个set中，存在就加入第二个set中，第二个set中的就是交集。

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

五、202. 快乐数

题目链接：https://leetcode.cn/problems/happy-number/description/
思路：题目提到了结果可能为1可能无限循环，所以停止的边界条件就是1或者无限循环，为了停止，所以要使用set来收集中间元素，防止停不下来。

class Solution {public boolean isHappy(int n) {Set<Integer> set = new HashSet<>();while(!set.contains(n)) {set.add(n);n = fun(n);if(n == 1) return true;}return false;}int fun(int n) {int sum = 0;while(n != 0) {int i = n % 10;n = n / 10;sum += i*i;}return sum;}
}

这篇关于力扣爆刷第137天之哈希表五连刷（环形链表哈希表）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---