1.環(huán)形鏈表II

題目鏈接

思路：設(shè)置快慢雙指針

注意：（1）是否有環(huán)（快慢雙指針是否能碰面也就是相等）

（2）環(huán)形入口的判斷。從頭結(jié)點(diǎn)出發(fā)一個(gè)指針，從相遇節(jié)點(diǎn) 也出發(fā)一個(gè)指針，這兩個(gè)指針每次只走一個(gè)節(jié)點(diǎn)， 那么當(dāng)這兩個(gè)指針相遇的時(shí)候就是 環(huán)形入口的節(jié)點(diǎn)。（相遇節(jié)點(diǎn)≠環(huán)形入口）

解法一：

public ListNode detectCycle(ListNode head) {ListNode fast = head;ListNode slow = head;// 循環(huán)判斷條件中fast.next是為了杜絕一個(gè)元素不能成環(huán)while (fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if (fast == slow) // 有環(huán){ListNode index1 = fast;  //也可為slowListNode index2 = head;// 兩個(gè)指針，從頭結(jié)點(diǎn)和相遇結(jié)點(diǎn)，各走一步，直到相遇，相遇點(diǎn)即為環(huán)入口while (index1 != index2){index1 = index1.next;index2 = index2.next;}return index1;}}return null;
}

2.有效的字母異位詞

題目鏈接

思路：用一個(gè)數(shù)組記錄某一字符串的元素，再遍歷另一字符串時(shí)一一刪除，判斷數(shù)組中是否有元素為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.贖金信

題目鏈接

思路：參照上題，區(qū)別于先判斷字符串magazine，并且需要記錄每個(gè)字符出現(xiàn)的次數(shù)

注意：string.toCharArray方法的使用（將字符串轉(zhuǎn)換為字符數(shù)組），區(qū)分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;}// 如果數(shù)組中存在負(fù)數(shù)，說(shuō)明ransomNote字符串總存在magazine中沒(méi)有的字符for (int i : record) {if (i < 0) {return false;}}return true;
}

4.兩個(gè)數(shù)組的交集

題目鏈接

思路：看見最終結(jié)果無(wú)序且不重復(fù)，可以使用set，這里分別使用set和數(shù)組進(jìn)行編碼

注意：在題目未給出length時(shí)，不要盲目新建數(shù)組，也就是說(shuō)如果哈希值比較少、特別分散、跨度非常大，使用數(shù)組就造成空間的極大浪費(fèi)； set的缺點(diǎn)是 不僅占用空間比數(shù)組大，而且速度要比數(shù)組慢。

解法一（使用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：將結(jié)果集合轉(zhuǎn)為數(shù)組
//        return resSet.stream().mapToInt(x -> x).toArray();//方法2：另外申請(qǐng)一個(gè)數(shù)組存放setRes中的元素,最后返回?cái)?shù)組int[] arr = new int[resSet.size()];int j = 0;for(int i : resSet){arr[j++] = i;}return arr;
}

解法二（使用數(shù)組，這個(gè)題后來(lái)給出了length大小）：

public int[] intersection(int[] nums1, int[] nums2) {int[] res = new int[1000];
// set用來(lái)保存結(jié)果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();
}