数据结构刷题（六）：142环形链表II、242有效的字母异位词、383赎金信、349两个数组的交集

1.环形链表II

题目链接

思路：设置快慢双指针

注意：（1）是否有环（快慢双指针是否能碰面也就是相等）

（2）环形入口的判断。从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。（相遇节点≠环形入口）

解法一：

public ListNode detectCycle(ListNode head) {ListNode fast = head;ListNode slow = head;// 循环判断条件中fast.next是为了杜绝一个元素不能成环while (fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if (fast == slow) // 有环{ListNode index1 = fast;  //也可为slowListNode index2 = head;// 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口while (index1 != index2){index1 = index1.next;index2 = index2.next;}return index1;}}return null;
}

2.有效的字母异位词

题目链接

思路：用一个数组记录某一字符串的元素，再遍历另一字符串时一一删除，判断数组中是否有元素为0

注意：string.chatAt方法的使用（表示返回指定索引处的字符）

解法：

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

3.赎金信

题目链接

思路：参照上题，区别于先判断字符串magazine，并且需要记录每个字符出现的次数

注意：string.toCharArray方法的使用（将字符串转换为字符数组），区分chatAt

解法：

 public boolean canConstruct(String ransomNote, String magazine) {int[] record = new int[26];// 遍历for (char c : magazine.toCharArray()) {record[c - 'a'] += 1;}for (char c : ransomNote.toCharArray()) {record[c - 'a'] -= 1;}// 如果数组中存在负数，说明ransomNote字符串总存在magazine中没有的字符for (int i : record) {if (i < 0) {return false;}}return true;
}

4.两个数组的交集

题目链接

思路：看见最终结果无序且不重复，可以使用set，这里分别使用set和数组进行编码

注意：在题目未给出length时，不要盲目新建数组，也就是说如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费； set的缺点是 不仅占用空间比数组大，而且速度要比数组慢。

解法一（使用set）：

public int[] intersection(int[] nums1, int[] nums2) {if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {return new int[0];}Set<Integer> set1 = new HashSet<>();Set<Integer> resSet = new HashSet<>();for (int i : nums1) {set1.add(i);}for (int i : nums2) {if (set1.contains(i)){resSet.add(i);}}//方法1：将结果集合转为数组
//        return resSet.stream().mapToInt(x -> x).toArray();//方法2：另外申请一个数组存放setRes中的元素,最后返回数组int[] arr = new int[resSet.size()];int j = 0;for(int i : resSet){arr[j++] = i;}return arr;
}

解法二（使用数组，这个题后来给出了length大小）：

public int[] intersection(int[] nums1, int[] nums2) {int[] res = new int[1000];
// set用来保存结果Set<Integer> result = new HashSet<>();for (int i : nums1) {res[i] = 1;}for (int i : nums2) {if (res[i] == 1) {result.add(i);}}return result.stream().mapToInt(x -> x).toArray();
}