哈希表
哈希表相关题目
哈希表使用 O(N) 空间复杂度存储数据，并且以 O(1) 时间复杂度求解问题。
- Java 中的 HashSet 用于存储一个集合，可以查找元素是否在集合中。如果元素有穷，并且范围不大，那么可以用一个布尔数组来存储一个元素是否存在。例如对于只有小写字符的元素，就可以用一个长度为 26 的布尔数组来存储一个字符集合，使得空间复杂度降低为 O(1)。
- Java 中的 HashMap 主要用于映射关系，从而把两个元素联系起来。HashMap 也可以用来对元素进行计数统计，此时键为元素，值为计数。和 HashSet 类似，如果元素有穷并且范围不大，可以用整型数组来进行统计。在对一个内容进行压缩或者其它转换时，利用 HashMap 可以把原始内容和转换后的内容联系起来。例如在一个简化 url 的系统中 Leetcdoe : 535. Encode and Decode TinyURL (Medium)，利用 HashMap 就可以存储精简后的 url 到原始 url 的映射，使得不仅可以显示简化的 url，也可以根据简化的 url 得到原始 url 从而定位到正确的资源。
数组中两个数的和为给定值
可以先对数组进行排序，然后使用双指针方法或者二分查找方法。这样做的时间复杂度为 O(NlogN)，空间复杂度为 O(1)。
用 HashMap 存储数组元素和索引的映射，在访问到 nums[i] 时，判断 HashMap 中是否存在 target - nums[i]，如果存在说明 target - nums[i] 所在的索引和 i 就是要找的两个数。该方法的时间复杂度为 O(N)，空间复杂度为 O(N)，使用空间来换取时间。
public int[] twoSum(int[] nums, int target) { HashMap<Integer, Integer> indexForNum = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (indexForNum.containsKey(target - nums[i])) { return new int[]{indexForNum.get(target - nums[i]), i}; } else { indexForNum.put(nums[i], i); } } return null; }
判断数组是否含有重复元素
217. Contains Duplicate (Easy)
public boolean containsDuplicate(int[] nums) { Set<Integer> set = new HashSet<>(); for (int num : nums) { set.add(num); } return set.size() < nums.length; }
最长和谐序列
594. Longest Harmonious Subsequence (Easy)
Input: [1,3,2,2,5,2,3,7] Output: 5 Explanation: The longest harmonious subsequence is [3,2,2,2,3].
和谐序列中最大数和最小数只差正好为 1，应该注意的是序列的元素不一定是数组的连续元素。
public int findLHS(int[] nums) { Map<Integer, Integer> countForNum = new HashMap<>(); for (int num : nums) { countForNum.put(num, countForNum.getOrDefault(num, 0) + 1); } int longest = 0; for (int num : countForNum.keySet()) { if (countForNum.containsKey(num + 1)) { longest = Math.max(longest, countForNum.get(num + 1) + countForNum.get(num)); } } return longest; }
最长连续序列
128. Longest Consecutive Sequence (Hard)
Given [100, 4, 200, 1, 3, 2], The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
要求以 O(N) 的时间复杂度求解。
public int longestConsecutive(int[] nums) { Map<Integer, Integer> countForNum = new HashMap<>(); for (int num : nums) { countForNum.put(num, 1); } for (int num : nums) { forward(countForNum, num); } return maxCount(countForNum); } private int forward(Map<Integer, Integer> countForNum, int num) { if (!countForNum.containsKey(num)) { return 0; } int cnt = countForNum.get(num); if (cnt > 1) { return cnt; } cnt = forward(countForNum, num + 1) + 1; countForNum.put(num, cnt); return cnt; } private int maxCount(Map<Integer, Integer> countForNum) { int max = 0; for (int num : countForNum.keySet()) { max = Math.max(max, countForNum.get(num)); } return max; }
链表
链表相关题目
链表是空节点，或者有一个值和一个指向下一个链表的指针，因此很多链表问题可以用递归来处理。
找出两个链表的交点
160. Intersection of Two Linked Lists (Easy)
A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3
要求：时间复杂度为 O(N)，空间复杂度为 O(1)
设 A 的长度为 a + c，B 的长度为 b + c，其中 c 为尾部公共部分长度，可知 a + c + b = b + c + a。
当访问 A 链表的指针访问到链表尾部时，令它从链表 B 的头部开始访问链表 B；同样地，当访问 B 链表的指针访问到链表尾部时，令它从链表 A 的头部开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode l1 = headA, l2 = headB; while (l1 != l2) { l1 = (l1 == null) ? headB : l1.next; l2 = (l2 == null) ? headA : l2.next; } return l1; }
如果只是判断是否存在交点，那么就是另一个问题，即 编程之美 3.6 的问题。有两种解法：
- 把第一个链表的结尾连接到第二个链表的开头，看第二个链表是否存在环；
- 或者直接比较两个链表的最后一个节点是否相同。
链表反转
206. Reverse Linked List (Easy)
递归
public ListNode reverseList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode next = head.next; ListNode newHead = reverseList(next); next.next = head; head.next = null; return newHead; }
头插法
public ListNode reverseList(ListNode head) { ListNode newHead = new ListNode(-1); while (head != null) { ListNode next = head.next; head.next = newHead.next; newHead.next = head; head = next; } return newHead.next; }
归并两个有序的链表
21. Merge Two Sorted Lists (Easy)
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) return l2; if (l2 == null) return l1; if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; } }
从有序链表中删除重复节点
83. Remove Duplicates from Sorted List (Easy)
Given 1->1->2, return 1->2. Given 1->1->2->3->3, return 1->2->3.
public ListNode deleteDuplicates(ListNode head) { if (head == null || head.next == null) return head; head.next = deleteDuplicates(head.next); return head.val == head.next.val ? head.next : head; }
删除链表的倒数第 n 个节点
19. Remove Nth Node From End of List (Medium)
Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5.
public ListNode removeNthFromEnd(ListNode head, int n) { ListNode fast = head; while (n-- > 0) { fast = fast.next; } if (fast == null) return head.next; ListNode slow = head; while (fast.next != null) { fast = fast.next; slow = slow.next; } slow.next = slow.next.next; return head; }
交换链表中的相邻结点
24. Swap Nodes in Pairs (Medium)
Given 1->2->3->4, you should return the list as 2->1->4->3.
题目要求：不能修改结点的 val 值，O(1) 空间复杂度。
public ListNode swapPairs(ListNode head) { ListNode node = new ListNode(-1); node.next = head; ListNode pre = node; while (pre.next != null && pre.next.next != null) { ListNode l1 = pre.next, l2 = pre.next.next; ListNode next = l2.next; l1.next = next; l2.next = l1; pre.next = l2; pre = l1; } return node.next; }
链表求和
445. Add Two Numbers II (Medium)
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 8 -> 0 -> 7
题目要求：不能修改原始链表。
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { Stack<Integer> l1Stack = buildStack(l1); Stack<Integer> l2Stack = buildStack(l2); ListNode head = new ListNode(-1); int carry = 0; while (!l1Stack.isEmpty() || !l2Stack.isEmpty() || carry != 0) { int x = l1Stack.isEmpty() ? 0 : l1Stack.pop(); int y = l2Stack.isEmpty() ? 0 : l2Stack.pop(); int sum = x + y + carry; ListNode node = new ListNode(sum % 10); node.next = head.next; head.next = node; carry = sum / 10; } return head.next; } private Stack<Integer> buildStack(ListNode l) { Stack<Integer> stack = new Stack<>(); while (l != null) { stack.push(l.val); l = l.next; } return stack; }
回文链表
234. Palindrome Linked List (Easy)
题目要求：以 O(1) 的空间复杂度来求解。
切成两半，把后半段反转，然后比较两半是否相等。
public boolean isPalindrome(ListNode head) { if (head == null || head.next == null) return true; ListNode slow = head, fast = head.next; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } if (fast != null) slow = slow.next; // 偶数节点，让 slow 指向下一个节点 cut(head, slow); // 切成两个链表 return isEqual(head, reverse(slow)); } private void cut(ListNode head, ListNode cutNode) { while (head.next != cutNode) { head = head.next; } head.next = null; } private ListNode reverse(ListNode head) { ListNode newHead = null; while (head != null) { ListNode nextNode = head.next; head.next = newHead; newHead = head; head = nextNode; } return newHead; } private boolean isEqual(ListNode l1, ListNode l2) { while (l1 != null && l2 != null) { if (l1.val != l2.val) return false; l1 = l1.next; l2 = l2.next; } return true; }
分隔链表
725. Split Linked List in Parts(Medium)
Input: root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3 Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]] Explanation: The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.
题目描述：把链表分隔成 k 部分，每部分的长度都应该尽可能相同，排在前面的长度应该大于等于后面的。
public ListNode[] splitListToParts(ListNode root, int k) { int N = 0; ListNode cur = root; while (cur != null) { N++; cur = cur.next; } int mod = N % k; int size = N / k; ListNode[] ret = new ListNode[k]; cur = root; for (int i = 0; cur != null && i < k; i++) { ret[i] = cur; int curSize = size + (mod-- > 0 ? 1 : 0); for (int j = 0; j < curSize - 1; j++) { cur = cur.next; } ListNode next = cur.next; cur.next = null; cur = next; } return ret; }
链表元素按奇偶聚集
328. Odd Even Linked List (Medium)
Example: Given 1->2->3->4->5->NULL, return 1->3->5->2->4->NULL.
public ListNode oddEvenList(ListNode head) { if (head == null) { return head; } ListNode odd = head, even = head.next, evenHead = even; while (even != null && even.next != null) { odd.next = odd.next.next; odd = odd.next; even.next = even.next.next; even = even.next; } odd.next = evenHead; return head; }
