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