# git-demo **Repository Path**: xuwei5580/git-demo ## Basic Information - **Project Name**: git-demo - **Description**: gitee的第一个仓库 - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2021-08-01 - **Last Updated**: 2024-10-16 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 010_CodeTop ## 第一页3.7~3.13 ### [206. 反转链表](https://leetcode-cn.com/problems/reverse-linked-list/) 难度简单2340 给你单链表的头节点 `head` ,请你反转链表,并返回反转后的链表。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2021/02/19/rev1ex1.jpg) ``` 输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1] ``` **示例 2:** ![img](https://assets.leetcode.com/uploads/2021/02/19/rev1ex2.jpg) ``` 输入:head = [1,2] 输出:[2,1] ``` **示例 3:** ``` 输入:head = [] 输出:[] ``` **提示:** - 链表中节点的数目范围是 `[0, 5000]` - `-5000 <= Node.val <= 5000` **进阶:**链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题? 通过次数912,225 提交次数1,254,078 **方法一:迭代法:链表反转** 假设存在链表 1→2→3→∅,我们∅←1←2←3。 在遍历列表时,将当前节点的next 指针改为指向前一个元素。由于节点没有引用其上一个节点,因此必须事先存储其前一个元素。在更改引用之前,还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用! ```java class Solution { public ListNode reverseList(ListNode head) { ListNode curr = head; ListNode prev = null; while(curr != null){ ListNode temp = curr.next; curr.next = prev; prev = curr; curr = temp; } return prev; } } ``` **方法二:递归:后序遍历** 递归的意思:我子节点下的所有节点都已经反转好了,现在就剩我和我的子节点 没有完成最后的反转了,所以反转一下我和我的子节点。 ```java reverseList: head=1 reverseList: head=2 reverseList: head=3 reverseList:head=4 reverseList:head=5 终止返回 cur = 5 4.next.next->4,即5->4 cur=5 3.next.next->3,即4->3 cur = 5 2.next.next->2,即3->2 cur = 5 1.next.next->1,即2->1 最后返回cur ``` ```java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { //相信这个函数的定义:返回反转后链表的头结点 public ListNode reverseList(ListNode head) { if (head == null || head.next == null){ return head; } //可以将链表看作当前节点和子节点两部分来看 ListNode curr = reverseList(head.next); head.next.next = head; head.next = null; return curr; } } ``` ### [146. LRU 缓存](https://leetcode-cn.com/problems/lru-cache/) 难度中等1990 请你设计并实现一个满足 [LRU (最近最少使用) 缓存](https://baike.baidu.com/item/LRU) 约束的数据结构。 实现 `LRUCache` 类: - `LRUCache(int capacity)` 以 **正整数** 作为容量 `capacity` 初始化 LRU 缓存 - `int get(int key)` 如果关键字 `key` 存在于缓存中,则返回关键字的值,否则返回 `-1` 。 - `void put(int key, int value)` 如果关键字 `key` 已经存在,则变更其数据值 `value` ;如果不存在,则向缓存中插入该组 `key-value` 。如果插入操作导致关键字数量超过 `capacity` ,则应该 **逐出** 最久未使用的关键字。 函数 `get` 和 `put` 必须以 `O(1)` 的平均时间复杂度运行。 **示例:** ``` 输入 ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 输出 [null, null, null, 1, null, -1, null, -1, 3, 4] 解释 LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {1=1} lRUCache.put(2, 2); // 缓存是 {1=1, 2=2} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4 ``` **提示:** - `1 <= capacity <= 3000` - `0 <= key <= 10000` - `0 <= value <= 105` - 最多调用 `2 * 105` 次 `get` 和 `put` 方法一:Hash Map + 双向链表 ```java public class LRUCache { class DLinkedNode { int key; int value; DLinkedNode prev; DLinkedNode next; public DLinkedNode() {} public DLinkedNode(int _key, int _value) {key = _key; value = _value;} } private Map cache = new HashMap(); private int size; private int capacity; private DLinkedNode head, tail; public LRUCache(int capacity) { this.size = 0; this.capacity = capacity; // 使用伪头部和伪尾部节点 head = new DLinkedNode(); tail = new DLinkedNode(); head.next = tail; tail.prev = head; } public int get(int key) { DLinkedNode node = cache.get(key); if (node == null) { return -1; } // 如果 key 存在,先通过哈希表定位,再移到头部 moveToHead(node); return node.value; } public void put(int key, int value) { DLinkedNode node = cache.get(key); if (node == null) { // 如果 key 不存在,创建一个新的节点 DLinkedNode newNode = new DLinkedNode(key, value); // 添加进哈希表 cache.put(key, newNode); // 添加至双向链表的头部 addToHead(newNode); ++size; if (size > capacity) { // 如果超出容量,删除双向链表的尾部节点 DLinkedNode tail = removeTail(); // 删除哈希表中对应的项 cache.remove(tail.key); --size; } } else { // 如果 key 存在,先通过哈希表定位,再修改 value,并移到头部 node.value = value; moveToHead(node); } } private void addToHead(DLinkedNode node) { node.prev = head; node.next = head.next; head.next.prev = node; head.next = node; } private void removeNode(DLinkedNode node) { node.prev.next = node.next; node.next.prev = node.prev; } private void moveToHead(DLinkedNode node) { removeNode(node); addToHead(node); } private DLinkedNode removeTail() { DLinkedNode res = tail.prev; removeNode(res); return res; } } class LRUCache { private int capacity; private DLinkNode head, tail; private Map cache; public LRUCache(int capacity) { this.capacity = capacity; head = new DLinkNode(); tail = new DLinkNode(); head.next = tail; tail.prev = head; cache = new HashMap<>(); } public int get(int key) { DLinkNode node = cache.get(key); if (node == null){ return -1; } removeNode(node); addToHead(node); return node.value; } public void put(int key, int value) { DLinkNode node = cache.get(key); if (node == null){ DLinkNode newNode = new DLinkNode(key, value); cache.put(key, newNode); addToHead(newNode); if (cache.size() > capacity){ DLinkNode tail = removeTail(); cache.remove(tail.key); } } else { node.value = value; removeNode(node); addToHead(node); } } public void removeNode(DLinkNode node){ node.prev.next = node.next; node.next.prev = node.prev; } public void addToHead(DLinkNode node){ node.prev = head.next.prev; node.next = head.next; head.next.prev = node; head.next = node; } public DLinkNode removeTail(){ DLinkNode res = tail.prev; removeNode(res); return res; } } class DLinkNode{ int key; int value; DLinkNode prev; DLinkNode next; public DLinkNode(){ } public DLinkNode(int key, int value){ this.key = key; this.value = value; } } /** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */ ``` ### [3. 无重复字符的最长子串](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/) 难度中等7080 给定一个字符串 `s` ,请你找出其中不含有重复字符的 **最长子串** 的长度。 **示例 1:** ``` 输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。 ``` **示例 2:** ``` 输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。 ``` **示例 3:** ``` 输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。 ``` **提示:** - `0 <= s.length <= 5 * 104` - `s` 由英文字母、数字、符号和空格组成 **方法一:暴力** ```java class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(); int maxCount = 0; for (int i = 0; i < n; i++) { //遍历每个起点都重新创建一个set集合 Set set = new HashSet<>(); for (int j = i; j < n; j++) { if (set.contains(s.charAt(j))){ break; } set.add(s.charAt(j)); } maxCount = Math.max(maxCount, set.size()); } return maxCount; } } ``` **方法二:滑动窗口** ```java //最好理解的做法 class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(); int maxCount = 0; Set set = new HashSet<>(); int j = 0; //遍历每个元素i作为元素起点位置 for (int i = 0; i < n; i++) { //从第二次遍历开始,删除set集合中当前起点的前一个元素 if (i > 0){ set.remove(s.charAt(i - 1)); } //找到当前元素i的无重复最长字串 while (j < n && !set.contains(s.charAt(j))){ set.add(s.charAt(j)); j++; } maxCount = Math.max(maxCount, set.size()); } return maxCount; } } //下面两种只是for循环和while之间的变形 class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(); int maxCount = 0; Set set = new HashSet<>(); int j = 0; for (int i = 0; i < n; i++) { if (i > 0){ set.remove(s.charAt(i - 1)); } for (; j < n && !set.contains(s.charAt(j)); j++){ set.add(s.charAt(j)); } maxCount = Math.max(maxCount, set.size()); } return maxCount; } } class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(); int maxCount = 0; Set set = new HashSet<>(); int left = 0, right = 0; while (left < n){ if (left > 0){ set.remove(s.charAt(left - 1)); } while (right < n && !set.contains(s.charAt(right))){ set.add(s.charAt(right)); right++; } maxCount = Math.max(maxCount, set.size()); left++; } return maxCount; } } ``` - 时间复杂度:O(n) ### [215. 数组中的第K个最大元素](https://leetcode-cn.com/problems/kth-largest-element-in-an-array/) 难度中等1516 给定整数数组 `nums` 和整数 `k`,请返回数组中第 `**k**` 个最大的元素。 请注意,你需要找的是数组排序后的第 `k` 个最大的元素,而不是第 `k` 个不同的元素。 **示例 1:** ``` 输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 ``` **示例 2:** ``` 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4 ``` **提示:** - `1 <= k <= nums.length <= 104` - `-104 <= nums[i] <= 104` 通过次数550,155 提交次数850,460 **题意分析:** 题目要求我们找到「数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素」。「数组排序后的第 k 个最大的元素」换句话说:从右边往左边数第 k 个元素(从 1 开始),那么从左向右数是第几个呢,我们列出几个找找规律就好了。 一共 6 个元素,找第 2 大,下标是 4; 一共 6 个元素,找第 4 大,下标是 2。 因此升序排序以后,目标元素的下标是 N - k,这里 N 是输入数组的长度。 **方法一:api** ```java class Solution { public int findKthLargest(int[] nums, int k) { int n = nums.length; Arrays.sort(nums); return nums[n - k]; } } ``` 复杂度分析: 时间复杂度:O(NlogN),这里 NN 是数组的长度,算法的性能消耗主要在排序,JDK 默认使用快速排序,因此时间复杂度为O(NlogN); 空间复杂度:O(logN),这里认为编程语言使用的排序方法是「快速排序」,空间复杂度为递归调用栈的高度,为 logN。 **方法二:单路快排** ```java class Solution { public int findKthLargest(int[] nums, int k) { int n = nums.length; quickSort(nums, 0, n - 1); return nums[n - k]; } public void quickSort(int[] nums, int low, int high){ if (low >= high){ return; } int p = partition(nums, low, high); quickSort(nums, low, p - 1); quickSort(nums, p + 1, high); } public int partition(int[] nums, int low, int high){ int pivot = nums[high]; int i = low; for (int j = low; j < high; j++) { if(nums[j] < pivot){ swap(nums, i, j); i++; } } swap(nums, i, high); return i; } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } ``` 时间复杂度:最坏O(N2),平均或者最好时间复杂度为O(nlogn) **方法三:归并** ```java class Solution { public int findKthLargest(int[] nums, int k) { mergeSort(nums, 0, nums.length - 1); return nums[nums.length - k]; } public void mergeSort(int[] arr, int left, int right){ if (left >= right){ return; } int mid = (left + right) >>> 1; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); } //合并两个有序序列代码 public void merge(int[] arr, int left, int mid, int right){ int[] temp = new int[arr.length]; int p1 = left, p2 = mid + 1; int k = left; while (p1 <= mid && p2 <= right){ if (arr[p1] < arr[p2]){ temp[k++] = arr[p1++]; } else { temp[k++] = arr[p2++]; } } while (p1 <= mid) temp[k++] = arr[p1++];//如果第一个序列未检测完,直接将后面所有元素加到合并的序列中 while (p2 <= right) temp[k++] = arr[p2++];//同上 //复制回原素组 for (int i = left; i <= right; i++){ arr[i] = temp[i]; } } } ``` **方法四:堆排序** **方法五:优先队列(堆的应用)** ### [25. K 个一组翻转链表(类比反转链表II)](https://leetcode-cn.com/problems/reverse-nodes-in-k-group/) 难度困难1516 给你一个链表,每 *k* 个节点一组进行翻转,请你返回翻转后的链表。 *k* 是一个正整数,它的值小于或等于链表的长度。 如果节点总数不是 *k* 的整数倍,那么请将最后剩余的节点保持原有顺序。 **进阶:** - 你可以设计一个只使用常数额外空间的算法来解决此问题吗? - **你不能只是单纯的改变节点内部的值**,而是需要实际进行节点交换。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2020/10/03/reverse_ex1.jpg) ``` 输入:head = [1,2,3,4,5], k = 2 输出:[2,1,4,3,5] ``` **示例 2:** ![img](https://assets.leetcode.com/uploads/2020/10/03/reverse_ex2.jpg) ``` 输入:head = [1,2,3,4,5], k = 3 输出:[3,2,1,4,5] ``` **示例 3:** ``` 输入:head = [1,2,3,4,5], k = 1 输出:[1,2,3,4,5] ``` **示例 4:** ``` 输入:head = [1], k = 1 输出:[1] ``` **提示:** - 列表中节点的数量在范围 `sz` 内 - `1 <= sz <= 5000` - `0 <= Node.val <= 1000` - `1 <= k <= sz` ```java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseKGroup(ListNode head, int k) { if (head == null || head.next == null){ return head; } //定义一个假的节点。 ListNode dummy=new ListNode(0); //假节点的next指向head。 // dummy->1->2->3->4->5 dummy.next=head; //初始化pre和end都指向dummy。pre指每次要翻转的链表的头结点的上一个节点。end指每次要翻转的链表的尾节点 ListNode pre=dummy; ListNode end=dummy; while(end.next!=null){ //循环k次,找到需要翻转的链表的结尾,这里每次循环要判断end是否等于空,因为如果为空,end.next会报空指针异常。 //dummy->1->2->3->4->5 若k为2,循环2次,end指向2 for(int i=0;i2 变成2->1。 dummy->2->1 pre.next=reverse(start); //翻转后头节点变到最后。通过.next把断开的链表重新链接。 start.next=next; //将pre换成下次要翻转的链表的头结点的上一个节点。即start pre=start; //翻转结束,将end置为下次要翻转的链表的头结点的上一个节点。即start end=start; } return dummy.next; } //链表翻转 // 例子: head: 1->2->3->4 public ListNode reverse(ListNode head) { //单链表为空或只有一个节点,直接返回原单链表 if (head == null || head.next == null){ return head; } //前一个节点指针 ListNode preNode = null; //当前节点指针 ListNode curNode = head; //下一个节点指针 ListNode nextNode = null; while (curNode != null){ nextNode = curNode.next;//nextNode 指向下一个节点,保存当前节点后面的链表。 curNode.next=preNode;//将当前节点next域指向前一个节点 null<-1<-2<-3<-4 preNode = curNode;//preNode 指针向后移动。preNode指向当前节点。 curNode = nextNode;//curNode指针向后移动。下一个节点变成当前节点 } return preNode; } } public class Solution { /** * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ public ListNode reverseKGroup (ListNode head, int k) { // write code here ListNode dummy = new ListNode(-1); dummy.next = head; ListNode prev = dummy, end = dummy; while(end.next != null){ //从prev走k步到达带反转链表尾结点 for(int i = 0; i < k && end != null; i++){ end = end.next; } if (end == null){ break; } //截取待反转链表 ListNode start = prev.next; ListNode next = end.next; //切断连接 prev.next = null; end.next = null; //反转链表 reverseList(start); //接回原来链表 prev.next = end; start.next = next; prev = start; end = start; } return dummy.next; } public ListNode reverseList(ListNode head) { ListNode curr = head; ListNode prev = null; while(curr != null){ ListNode temp = curr.next; curr.next = prev; prev = curr; curr = temp; } return prev; } } ``` ### [15. 三数之和](https://leetcode-cn.com/problems/3sum/) 难度中等4448 给你一个包含 `n` 个整数的数组 `nums`,判断 `nums` 中是否存在三个元素 *a,b,c ,*使得 *a + b + c =* 0 ?请你找出所有和为 `0` 且不重复的三元组。 **注意:**答案中不可以包含重复的三元组。 **示例 1:** ``` 输入:nums = [-1,0,1,2,-1,-4] 输出:[[-1,-1,2],[-1,0,1]] ``` **示例 2:** ``` 输入:nums = [] 输出:[] ``` **示例 3:** ``` 输入:nums = [0] 输出:[] ``` **提示:** - `0 <= nums.length <= 3000` - `-105 <= nums[i] <= 105` **方法一:for + 双指针** ```java class Solution { public static List> threeSum(int[] nums) { List> res = new ArrayList<>(); int n = nums.length; if (nums == null || n < 3) return res; Arrays.sort(nums); for(int i = 0; i < n - 2; i++){ if(nums[i] > 0) break;//优化:可省略 //剪枝:保证第一个数不重复 if (i > 0 && nums[i] == nums[i - 1]){ continue; } int left = i + 1, right = n - 1; while(left < right){ int sum = nums[i] + nums[left] + nums[right]; if (sum == 0){ res.add(Arrays.asList(nums[i], nums[left], nums[right])); //剪枝:为了保证三元组不重复:第一个数确定的情况下: //保证第二个数不重复 while (left < right && nums[left++] == nums[left]); //保证第三个数不重复 while (left < right && nums[right--] == nums[right]); } else if (sum < 0){ while (left < right && nums[left++] == nums[left]); //left++; } else { while (left < right && nums[right--] == nums[right]); //right--; } } } return res; } } ``` 复杂度分析: 时间复杂度 O(N^2),其中固定指针k循环复杂度 O(N),双指针 i,j 复杂度 O(N)。 空间复杂度 O(1):指针使用常数大小的额外空间。 **方法二:暴力超时** ```java //三个continue是为了避免重复 class Solution { public static List> threeSum(int[] nums) { int n = nums.length; List> res = new ArrayList<>(); if (nums == null || n < 3) { return res; } Arrays.sort(nums); for (int i = 0; i < n - 2; i++) { if (i > 0 && nums[i] == nums[i - 1]) continue; for (int j = i + 1; j < n - 1; j++) { if (j > i + 1 && nums[j] == nums[j - 1]) continue; for (int k = j + 1; k < n; k++) { if (k > j + 1 && nums[k] == nums[k - 1]) continue; if (nums[i] + nums[j] + nums[k] == 0) { res.add(Arrays.asList(nums[i], nums[j], nums[k])); } } } } return res; } } ``` ### [912. 排序数组](https://leetcode-cn.com/problems/sort-an-array/) 难度中等492 给你一个整数数组 `nums`,请你将该数组升序排列。 **示例 1:** ``` 输入:nums = [5,2,3,1] 输出:[1,2,3,5] ``` **示例 2:** ``` 输入:nums = [5,1,1,2,0,0] 输出:[0,0,1,1,2,5] ``` **提示:** - `1 <= nums.length <= 5 * 104` - `-5 * 104 <= nums[i] <= 5 * 104` 方法一:api ```java class Solution { public int findKthLargest(int[] nums, int k) { int n = nums.length; Arrays.sort(nums); return nums[n - k]; } } ``` 复杂度分析: 时间复杂度:O(NlogN),这里 NN 是数组的长度,算法的性能消耗主要在排序,JDK 默认使用快速排序,因此时间复杂度为O(NlogN); 空间复杂度:O(logN),这里认为编程语言使用的排序方法是「快速排序」,空间复杂度为递归调用栈的高度,为 logN。 方法二:单路快排 ```java class Solution { public int findKthLargest(int[] nums, int k) { int n = nums.length; quickSort(nums, 0, n - 1); return nums[n - k]; } public void quickSort(int[] nums, int low, int high){ if (low >= high){ return; } int p = partition(nums, low, high); quickSort(nums, low, p - 1); quickSort(nums, p + 1, high); } public int partition(int[] nums, int low, int high){ int pivot = nums[high]; int i = low; for (int j = low; j < high; j++) { if(nums[j] < pivot){ swap(nums, i, j); i++; } } swap(nums, i, high); return i; } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } ``` 时间复杂度:最坏O(N2),平均或者最好时间复杂度为O(nlogn) 方法三:归并 ```java class Solution { public int findKthLargest(int[] nums, int k) { mergeSort(nums, 0, nums.length - 1); return nums[nums.length - k]; } public void mergeSort(int[] arr, int left, int right){ if (left >= right){ return; } int mid = (left + right) >>> 1; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); } public void merge(int[] arr, int left, int mid, int right){ int[] temp = new int[arr.length]; int p1 = left, p2 = mid + 1; //p1和p2的起点 int k = left; //需要注意k的起点 while (p1 <= mid && p2 <= right){ if (arr[p1] <= arr[p2]){// <=保证归并排序是稳定的排序 temp[k++] = arr[p1++]; } else { temp[k++] = arr[p2++]; } } while (p1 <= mid) temp[k++] = arr[p1++];//如果第一个序列未检测完,直接将后面所有元素加到合并的序列中 while (p2 <= right) temp[k++] = arr[p2++];//同上 //复制回原素组 for (int i = left; i <= right; i++){ //注意i的起点和终点i = left i <= right arr[i] = temp[i]; } } } ``` 方法四:堆排序 方法五:优先队列(堆的应用) ### [53. 最大子数组和 类比力扣300题:最长上升子序列](https://leetcode-cn.com/problems/maximum-subarray/) 难度简单4494 给你一个整数数组 `nums` ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 **子数组** 是数组中的一个连续部分。 **示例 1:** ``` 输入:nums = [-2,1,-3,4,-1,2,1,-5,4] 输出:6 解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。 ``` **示例 2:** ``` 输入:nums = [1] 输出:1 ``` **示例 3:** ``` 输入:nums = [5,4,-1,7,8] 输出:23 ``` **提示:** - `1 <= nums.length <= 105` - `-104 <= nums[i] <= 104` **进阶:**如果你已经实现复杂度为 `O(n)` 的解法,尝试使用更为精妙的 **分治法** 求解。 **方法一:动态规划** - 状态定义:`dp[i]`:表示以 `nums[i]` **结尾** 的 **连续** 子数组的最大和。 - 状态转移方程 ![image-20220310200913090](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220310200913090.png) - 状态初始值:`dp[0]` 根据定义,只有 1 个数,一定以 `nums[0]` 结尾,因此 `dp[0] = nums[0]`。 - 返回问题所需要的状态 ```java //重点掌握 class Solution { public int maxSubArray(int[] nums) { int n = nums.length; //1、状态定义:dp[i]:表示以 nums[i]结尾的连续子数组的最大和。 int[] dp = new int[n]; //2、状态初始值 dp[0] = nums[0]; int res = dp[0]; //3、状态转移方程 for(int i = 1; i < n; i++){ dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]); res = Math.max(res, dp[i]); } //4、返回所需状态值 return res; } } ``` **时间复杂度**:O(N),这里 N*N* 是输入数组的长度。 空间复杂度:O(N) 可以优化空间: 根据「状态转移方程」,`dp[i]` 的值只和 `dp[i - 1]` 有关,因此可以使用「滚动变量」的方式将代码进行优化。 ```java public class Solution { public int maxSubArray(int[] nums) { int pre = 0; int res = nums[0]; for (int num : nums) { pre = Math.max(pre + num, num); res = Math.max(res, pre); } return res; } } ``` ### [21. 合并两个有序链表 类比合并两个有序数组(归并)](https://leetcode-cn.com/problems/merge-two-sorted-lists/) 难度简单2254 将两个升序链表合并为一个新的 **升序** 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2020/10/03/merge_ex1.jpg) ``` 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] ``` **示例 2:** ``` 输入:l1 = [], l2 = [] 输出:[] ``` **示例 3:** ``` 输入:l1 = [], l2 = [0] 输出:[0] ``` **提示:** - 两个链表的节点数目范围是 `[0, 50]` - `-100 <= Node.val <= 100` - `l1` 和 `l2` 均按 **非递减顺序** 排列 ```java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(-1); ListNode prev = dummy; ListNode p1 = l1, p2 = l2; while(p1 != null && p2 != null){ if (p1.val <= p2.val){ prev.next = p1; p1 = p1.next; } else { prev.next = p2; p2 = p2.next; } prev = prev.next; } prev.next = p1 == null ? p2 : p1; return dummy.next; } } ``` ### [1. 两数之和](https://leetcode-cn.com/problems/two-sum/) 难度简单13690 给定一个整数数组 `nums` 和一个整数目标值 `target`,请你在该数组中找出 **和为目标值** *`target`* 的那 **两个** 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 **示例 1:** ``` 输入:nums = [2,7,11,15], target = 9 输出:[0,1] 解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。 ``` **示例 2:** ``` 输入:nums = [3,2,4], target = 6 输出:[1,2] ``` **示例 3:** ``` 输入:nums = [3,3], target = 6 输出:[0,1] ``` **提示:** - `2 <= nums.length <= 104` - `-109 <= nums[i] <= 109` - `-109 <= target <= 109` - **只会存在一个有效答案** **进阶:**你可以想出一个时间复杂度小于 `O(n2)` 的算法吗? **只有这两种方法** **方法一:hashmap** ```java class Solution { public int[] twoSum(int[] nums, int target) { Map map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (map.containsKey(target - nums[i])){ return new int[]{map.get(target - nums[i]), i}; } map.put(nums[i], i); } return new int[0]; } } ``` **方法二:暴力** ```java class Solution { public int[] twoSum(int[] nums, int target) { int n = nums.length; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { if (nums[i] == target - nums[j]){ return new int[]{i, j}; } } } return new int[0]; } } ``` ### [102. 二叉树的层序遍历](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/) 难度中等1214 给你二叉树的根节点 `root` ,返回其节点值的 **层序遍历** 。 (即逐层地,从左到右访问所有节点)。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2021/02/19/tree1.jpg) ``` 输入:root = [3,9,20,null,null,15,7] 输出:[[3],[9,20],[15,7]] ``` **示例 2:** ``` 输入:root = [1] 输出:[[1]] ``` **示例 3:** ``` 输入:root = [] 输出:[] ``` **提示:** - 树中节点数目在范围 `[0, 2000]` 内 - `-1000 <= Node.val <= 1000` ```java class Solution { public List> levelOrder(TreeNode root) { List> res = new ArrayList<>(); if (root == null) return res; Queue q = new LinkedList<>(); q.offer(root); while(!q.isEmpty()){ List level = new ArrayList<>(); int size = q.size(); for (int i = 0; i < size; i++){ TreeNode node = q.poll(); level.add(node.val); if (node.left != null) q.offer(node.left); if (node.right != null) q.offer(node.right); } res.add(level); } return res; } } ``` ### [141. 环形链表](https://leetcode-cn.com/problems/linked-list-cycle/) 难度简单1392 给你一个链表的头节点 `head` ,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 `next` 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 `pos` 来表示链表尾连接到链表中的位置(索引从 0 开始)。**注意:`pos` 不作为参数进行传递** 。仅仅是为了标识链表的实际情况。 *如果链表中存在环* ,则返回 `true` 。 否则,返回 `false` 。 **示例 1:** ![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist.png) ``` 输入:head = [3,2,0,-4], pos = 1 输出:true 解释:链表中有一个环,其尾部连接到第二个节点。 ``` **示例 2:** ![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist_test2.png) ``` 输入:head = [1,2], pos = 0 输出:true 解释:链表中有一个环,其尾部连接到第一个节点。 ``` **示例 3:** ![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist_test3.png) ``` 输入:head = [1], pos = -1 输出:false 解释:链表中没有环。 ``` **提示:** - 链表中节点的数目范围是 `[0, 104]` - `-105 <= Node.val <= 105` - `pos` 为 `-1` 或者链表中的一个 **有效索引** 。 **进阶:**你能用 `O(1)`(即,常量)内存解决此问题吗? **方法一:Set验重** ```java public class Solution { public boolean hasCycle(ListNode head) { Set seen = new HashSet(); while (head != null) { if (!seen.add(head)) { return true; } head = head.next; } return false; } } ``` **方法二:快慢指针** ![image-20220310214947129](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220310214947129.png) ![image-20220310215001476](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220310215001476.png) **如果存在环,则快指针不管快多少,始终会在环上跑,当慢指针也进入到环中时,两个指针都会无限在环中跑,跑N次之后,总有快慢指针相遇的时候,所以说,fast = fast.next.next,最好再把fast.next也拿出来当做判断条件,防止环过大导致快慢指针总是不相遇,节省点内存** ```java public class Solution { public boolean hasCycle(ListNode head) { if (head == null || head.next == null) { return false; } ListNode slow = head; ListNode fast = head.next; while (slow != fast) { if (fast == null || fast.next == null) { return false; } slow = slow.next; fast = fast.next.next; } return true; } } /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { if (head == null) return false; //快慢两个指针 ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { //慢指针每次走一步 slow = slow.next; //快指针每次走两步 fast = fast.next.next; //如果相遇,说明有环,直接返回true if (slow == fast) return true; } //否则就是没环 return false; } } ``` ![image-20220310215046583](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220310215046583.png) ### [121. 买卖股票的最佳时机 类比53题](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/) 难度简单2179 给定一个数组 `prices` ,它的第 `i` 个元素 `prices[i]` 表示一支给定股票第 `i` 天的价格。 你只能选择 **某一天** 买入这只股票,并选择在 **未来的某一个不同的日子** 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 `0` 。 **示例 1:** ``` 输入:[7,1,5,3,6,4] 输出:5 解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。 ``` **示例 2:** ``` 输入:prices = [7,6,4,3,1] 输出:0 解释:在这种情况下, 没有交易完成, 所以最大利润为 0。 ``` **提示:** - `1 <= prices.length <= 105` - `0 <= prices[i] <= 104` ![image-20220310220245052](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220310220245052.png) **方法一:动态规划一** ```java public class Solution { public int maxProfit(int[] prices) { int n = prices.length; //1、状态定义:dp[i]:表示第i天卖出股票利润的最大和。 int[] dp = new int[n]; //2、状态初始值 dp[0] = 0; int res = 0; //3、状态转移方程:第i天卖出可以获得的最大利润 = 第i-1天卖出的最大利润 + 利润差(不可能小于0) for(int i = 1; i < n; i++){ dp[i] = Math.max(dp[i - 1] + prices[i] - prices[i - 1], 0); res = Math.max(res, dp[i]); } //4、返回所需状态值 return res; } } ``` **方法二:动态规划二** **方法三:暴力超时** ```java public class Solution { public int maxProfit(int[] prices) { int len = prices.length; if (len < 2) { return 0; } // 有可能不发生交易,因此结果集的初始值设置为 0 int res = 0; // 枚举所有发生一次交易的股价差 for (int i = 0; i < len - 1; i++) { for (int j = i + 1; j < len; j++) { res = Math.max(res, prices[j] - prices[i]); } } return res; } } ``` ### [160. 相交链表](https://leetcode-cn.com/problems/intersection-of-two-linked-lists/) 难度简单1587 给你两个单链表的头节点 `headA` 和 `headB` ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 `null` 。 图示两个链表在节点 `c1` 开始相交**:** [![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_statement.png)](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_statement.png) 题目数据 **保证** 整个链式结构中不存在环。 **注意**,函数返回结果后,链表必须 **保持其原始结构** 。 **自定义评测:** **评测系统** 的输入如下(你设计的程序 **不适用** 此输入): - `intersectVal` - 相交的起始节点的值。如果不存在相交节点,这一值为 `0` - `listA` - 第一个链表 - `listB` - 第二个链表 - `skipA` - 在 `listA` 中(从头节点开始)跳到交叉节点的节点数 - `skipB` - 在 `listB` 中(从头节点开始)跳到交叉节点的节点数 评测系统将根据这些输入创建链式数据结构,并将两个头节点 `headA` 和 `headB` 传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 **视作正确答案** 。 **示例 1:** [![img](https://assets.leetcode.com/uploads/2021/03/05/160_example_1_1.png)](https://assets.leetcode.com/uploads/2018/12/13/160_example_1.png) ``` 输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3 输出:Intersected at '8' 解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。 从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,6,1,8,4,5]。 在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。 ``` **示例 2:** [![img](https://assets.leetcode.com/uploads/2021/03/05/160_example_2.png)](https://assets.leetcode.com/uploads/2018/12/13/160_example_2.png) ``` 输入:intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出:Intersected at '2' 解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。 从各自的表头开始算起,链表 A 为 [1,9,1,2,4],链表 B 为 [3,2,4]。 在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。 ``` **示例 3:** [![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_example_3.png)](https://assets.leetcode.com/uploads/2018/12/13/160_example_3.png) ``` 输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出:null 解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。 由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。 这两个链表不相交,因此返回 null 。 ``` **提示:** - `listA` 中节点数目为 `m` - `listB` 中节点数目为 `n` - `1 <= m, n <= 3 * 104` - `1 <= Node.val <= 105` - `0 <= skipA <= m` - `0 <= skipB <= n` - 如果 `listA` 和 `listB` 没有交点,`intersectVal` 为 `0` - 如果 `listA` 和 `listB` 有交点,`intersectVal == listA[skipA] == listB[skipB]` **进阶:**你能否设计一个时间复杂度 `O(m + n)` 、仅用 `O(1)` 内存的解决方案? **方法一:Set** ```java public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { Set set = new HashSet<>(); while(headA != null){ set.add(headA); headA = headA.next; } while(headB != null){ if (set.contains(headB)){ return headB; } set.add(headB); headB = headB.next; } return null; } } ``` **方法二:快慢指针** ![Picture1.png](https://pic.leetcode-cn.com/1615224578-EBRtwv-Picture1.png) ![image-20220311075856441](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220311075856441.png) ```java public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode A = headA, B = headB; while(A != B){ //因为A,B走的节点数一样,所以A,B必然重合:要么同时指向第一个公共节点,要么同时指向null A = (A != null) ? A.next : headB; B = (B != null) ? B.next : headA; } return A; } } ``` 复杂度分析: 时间复杂度 O(a + b) : 最差情况下(即 |a - b| = 1 , c = 0 ),此时需遍历 a + b 个节点。 空间复杂度 O(1): 节点指针 A , B 使用常数大小的额外空间。 ### [20. 有效的括号](https://leetcode-cn.com/problems/valid-parentheses/) 难度简单3058 给定一个只包括 `'('`,`')'`,`'{'`,`'}'`,`'['`,`']'` 的字符串 `s` ,判断字符串是否有效。 有效字符串需满足: 1. 左括号必须用相同类型的右括号闭合。 2. 左括号必须以正确的顺序闭合。 **示例 1:** ``` 输入:s = "()" 输出:true ``` **示例 2:** ``` 输入:s = "()[]{}" 输出:true ``` **示例 3:** ``` 输入:s = "(]" 输出:false ``` **示例 4:** ``` 输入:s = "([)]" 输出:false ``` **示例 5:** ``` 输入:s = "{[]}" 输出:true ``` **提示:** - `1 <= s.length <= 104` - `s` 仅由括号 `'()[]{}'` 组成 **方法一:Stack或Deque模拟栈** ```java class Solution { public boolean isValid(String s) { int n = s.length(); if (n % 2 == 1){ return false; } Map map = new HashMap<>(); map.put('(', ')'); map.put('{', '}'); map.put('[', ']'); //Stack stack = new Stack<>(); Deque stack = new LinkedList<>(); for(Character c : s.toCharArray()){ if (c == '(' || c == '{' || c == '['){ stack.push(c); } else if (stack.isEmpty() || map.get(stack.pop()) != c){ return false; } } if (!stack.isEmpty()){ return false; } return true; } } ``` ### [103. 二叉树的锯齿形层序遍历](https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/) 难度中等601 给你二叉树的根节点 `root` ,返回其节点值的 **锯齿形层序遍历** 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2021/02/19/tree1.jpg) ``` 输入:root = [3,9,20,null,null,15,7] 输出:[[3],[20,9],[15,7]] ``` **示例 2:** ``` 输入:root = [1] 输出:[[1]] ``` **示例 3:** ``` 输入:root = [] 输出:[] ``` **提示:** - 树中节点数目在范围 `[0, 2000]` 内 - `-100 <= Node.val <= 100` 通过次数210,664 提交次数368,342 ```java class Solution { public List> zigzagLevelOrder(TreeNode root) { List> ans = new LinkedList<>(); if (root == null) return ans; Queue q = new LinkedList<>(); q.offer(root); boolean isOrderLeft = true; while (!q.isEmpty()) { Deque level = new LinkedList(); int size = q.size(); for (int i = 0; i < size; ++i) { TreeNode node = q.poll(); if (isOrderLeft) { level.offerLast(node.val); } else { level.offerFirst(node.val); } if (node.left != null) { q.offer(node.left); } if (node.right != null) { q.offer(node.right); } } // ans.add(new LinkedList(level)); isOrderLeft = !isOrderLeft; } return ans; } } class Solution { public List> zigzagLevelOrder(TreeNode root) { List> ans = new LinkedList<>(); if (root == null) return ans; Queue q = new LinkedList<>(); q.offer(root); while (!q.isEmpty()) { List level = new ArrayList(); int size = q.size(); for (int i = 0; i < size; ++i) { TreeNode node = q.poll(); level.add(node.val); if(node.left != null) q.offer(node.left); if(node.right != null) q.offer(node.right); } if (ans.size() % 2 == 1){ Collections.reverse(level); } ans.add(level); } return ans; } } ``` ### [88. 合并两个有序数组](https://leetcode-cn.com/problems/merge-sorted-array/) 难度简单1320 给你两个按 **非递减顺序** 排列的整数数组 `nums1` 和 `nums2`,另有两个整数 `m` 和 `n` ,分别表示 `nums1` 和 `nums2` 中的元素数目。 请你 **合并** `nums2` 到 `nums1` 中,使合并后的数组同样按 **非递减顺序** 排列。 **注意:**最终,合并后数组不应由函数返回,而是存储在数组 `nums1` 中。为了应对这种情况,`nums1` 的初始长度为 `m + n`,其中前 `m` 个元素表示应合并的元素,后 `n` 个元素为 `0` ,应忽略。`nums2` 的长度为 `n` 。 **示例 1:** ``` 输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出:[1,2,2,3,5,6] 解释:需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6] ,其中斜体加粗标注的为 nums1 中的元素。 ``` **示例 2:** ``` 输入:nums1 = [1], m = 1, nums2 = [], n = 0 输出:[1] 解释:需要合并 [1] 和 [] 。 合并结果是 [1] 。 ``` **示例 3:** ``` 输入:nums1 = [0], m = 0, nums2 = [1], n = 1 输出:[1] 解释:需要合并的数组是 [] 和 [1] 。 合并结果是 [1] 。 注意,因为 m = 0 ,所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。 ``` **提示:** - `nums1.length == m + n` - `nums2.length == n` - `0 <= m, n <= 200` - `1 <= m + n <= 200` - `-109 <= nums1[i], nums2[j] <= 109` **进阶:**你可以设计实现一个时间复杂度为 `O(m + n)` 的算法解决此问题吗? **方法一:同向双指针** 算法 方法一没有利用数组 nums 1与nums2已经被排序的性质。为了利用这一性质,我们可以使用双指针方法。这一方法将两个数组看作队列,每次从两个数组头部取出比较小的数字放到结果中。如下面的动画所示: ![gif1](https://assets.leetcode-cn.com/solution-static/88/1.gif) 我们为两个数组分别设置一个指针*p*1 与 p2 来作为队列的头部指针。代码实现如下: ```java class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int[] temp = new int[m + n]; int p1 = 0, p2 = 0, k = 0; while(p1 < m && p2 < n){ if (nums1[p1] <= nums2[p2]){ temp[k++] = nums1[p1++]; } else { temp[k++] = nums2[p2++]; } } while(p1 < m) temp[k++] = nums1[p1++]; while(p2 < n) temp[k++] = nums2[p2++]; for(int i = 0; i < m + n; i++){ nums1[i] = temp[i]; } } } ``` 复杂度分析 时间复杂度:O(m+n)。 指针移动单调递增,最多移动 m+n 次,因此时间复杂度为 O(m+n)。 空间复杂度:O(m+n) 需要建立长度为 m+n 的中间数组 temp。 **方法二:先合并再排序** ```java class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { for(int i = m; i < m + n; i++){ nums1[i] = nums2[i - m]; } Arrays.sort(nums1); } } ``` 复杂度分析 时间复杂度:O((m+n)log(m+n))。 排序序列长度为 m+n,套用快速排序的时间复杂度即可,平均情况为 O((m+n)log(m+n))。 空间复杂度:O(log(m+n))。 排序序列长度为 m+n,套用快速排序的空间复杂度即可,平均情况为 O(log(m+n))。 **方法三:相向双指针** ### [236. 二叉树的最近公共祖先](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/) 难度中等1603 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 [百度百科](https://baike.baidu.com/item/最近公共祖先/8918834?fr=aladdin)中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(**一个节点也可以是它自己的祖先**)。” **示例 1:** ![img](https://assets.leetcode.com/uploads/2018/12/14/binarytree.png) ``` 输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出:3 解释:节点 5 和节点 1 的最近公共祖先是节点 3 。 ``` **示例 2:** ![img](https://assets.leetcode.com/uploads/2018/12/14/binarytree.png) ``` 输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出:5 解释:节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。 ``` **示例 3:** ``` 输入:root = [1,2], p = 1, q = 2 输出:1 ``` **提示:** - 树中节点数目在范围 `[2, 105]` 内。 - `-109 <= Node.val <= 109` - 所有 `Node.val` `互不相同` 。 - `p != q` - `p` 和 `q` 均存在于给定的二叉树中。 **方法一:后续遍历(回溯)过程** 思路 遇到这个题目首先想的是要是能自底向上查找就好了,这样就可以找到公共祖先了。 那么**二叉树如何可以自底向上查找**呢? 回溯啊,**二叉树回溯的过程就是从低到上**。 **后序遍历就是天然的回溯过程,最先处理的一定是叶子节点。** ![image-20220313104906425](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220313104906425.png) PPT思路非常直观 ![image-20220313105004789](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220313105004789.png) **递归三部曲:** - **确定递归函数返回值以及参数** - **确定终止条件** - **确定单层递归逻辑** ```java class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { //递归终止条件:root为空或者为p节点或者为q节点,直接返回root if (root == null || root == p || root == q) return root; //后序遍历框架 TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); //递归主体(单层逻辑) ,返回值 if(left == null && right == null) return null; // 1. if(left == null) return right; // 3. if(right == null) return left; // 4. return root; // 2. if(left != null and right != null) } } //优化写法 class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root == null || root == p || root == q) return root; TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if(left == null) return right; if(right == null) return left; return root; } } ``` ### [5. 最长回文子串](https://leetcode-cn.com/problems/longest-palindromic-substring/) 难度中等4839 给你一个字符串 `s`,找到 `s` 中最长的回文子串。 **示例 1:** ``` 输入:s = "babad" 输出:"bab" 解释:"aba" 同样是符合题意的答案。 ``` **示例 2:** ``` 输入:s = "cbbd" 输出:"bb" ``` **提示:** - `1 <= s.length <= 1000` - `s` 仅由数字和英文字母组成 **方法一:暴力** ```java public class Solution { public String longestPalindrome(String s) { int len = s.length(); if (len < 2) { return s; } int maxLen = 1; int begin = 0; // s.charAt(i) 每次都会检查数组下标越界,因此先转换成字符数组 char[] charArray = s.toCharArray(); // 枚举所有长度大于 1 的子串 charArray[i..j] for (int i = 0; i < len - 1; i++) { for (int j = i + 1; j < len; j++) { //要满足两个条件:1、回文 2、最长回文子串 if (j - i + 1 > maxLen && validPalindromic(charArray, i, j)) { maxLen = j - i + 1; begin = i; } } } return s.substring(begin, begin + maxLen); } /** * 验证子串 s[left..right] 是否为回文串 */ private boolean validPalindromic(char[] charArray, int left, int right) { while (left < right) { if (charArray[left] != charArray[right]) { return false; } left++; right--; } return true; } } ``` 复杂度分析: 时间复杂度:O(N^3 ),这里 N 是字符串的长度,枚举字符串的左边界、右边界,然后继续验证子串是否是回文子串,都与N 相关; 空间复杂度:O(1),只使用到常数个临时变量,与字符串长度无关。 **方法二:动态规划** ```java public class Solution { //动态规划求解。 public String longestPalindrome(String s) { //定义一个表示字符长度 int len = s.length(); //如果字符小于2,直接返回 if (len < 2) { return s; } //定义一个表示回文字符数量的变量 int maxlen = 1; //回文字串的开始索引 int begin = 0; //定义一个存储所有可能的结果,一个二维数组 boolean[][] dp = new boolean[len][len]; //单个字符本身就是回文串 for (int i = 0; i < len; i++) { dp[i][i] = true; } //递归遍历,二维数组的对角线上方的所有元素 for (int j = 1; j < len; j++) { for (int i = 0; i < j; i++) { //如果两个字符相等,就说明不是回文串 if (s.charAt(i) != s.charAt(j)) { dp[i][j] = false; } else { //当是回文串时,字符个数小于等于3个,就是回文串 if (j - i < 3) { dp[i][j] = true; } else { //递归判断当边界两边的字符相等时,继续判断内层的字符是否相等 dp[i][j] = dp[i + 1][j - 1]; } } //对比所有的回文串,取出长度最大的,回文串的起始位置 if (dp[i][j] && j - i + 1 > maxlen) { maxlen = j - i + 1; begin = i; } } } //字符串的切割 return s.substring(begin, begin + maxlen); } } ``` **方法三:中心扩散** ### [33. 搜索旋转排序数组](https://leetcode-cn.com/problems/search-in-rotated-sorted-array/) 难度中等1902 整数数组 `nums` 按升序排列,数组中的值 **互不相同** 。 在传递给函数之前,`nums` 在预先未知的某个下标 `k`(`0 <= k < nums.length`)上进行了 **旋转**,使数组变为 `[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]`(下标 **从 0 开始** 计数)。例如, `[0,1,2,4,5,6,7]` 在下标 `3` 处经旋转后可能变为 `[4,5,6,7,0,1,2]` 。 给你 **旋转后** 的数组 `nums` 和一个整数 `target` ,如果 `nums` 中存在这个目标值 `target` ,则返回它的下标,否则返回 `-1` 。 **示例 1:** ``` 输入:nums = [4,5,6,7,0,1,2], target = 0 输出:4 ``` **示例 2:** ``` 输入:nums = [4,5,6,7,0,1,2], target = 3 输出:-1 ``` **示例 3:** ``` 输入:nums = [1], target = 0 输出:-1 ``` **提示:** - `1 <= nums.length <= 5000` - `-10^4 <= nums[i] <= 10^4` - `nums` 中的每个值都 **独一无二** - 题目数据保证 `nums` 在预先未知的某个下标上进行了旋转 - `-10^4 <= target <= 10^4` **进阶:**你可以设计一个时间复杂度为 `O(log n)` 的解决方案吗? **方法一:二分查找** **题目要求世间复杂度 `O(log n)`,基本锁定二分查找** **有序数组用二分** ![image-20220313113327656](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220313113327656.png) ```java class Solution { public int search(int[] nums, int target) { int n = nums.length; int left = 0, right = n - 1; while (left <= right){ int mid = left + (right - left) / 2; if (nums[mid] == target){ return mid; } if (nums[left] <= nums[mid]){ //如果前半部分有序 if (target >= nums[left] && target < nums[mid]){ right = mid - 1; } else { left = mid + 1; } } else { //如果后半部分有序 if (target > nums[mid] && target <= nums[right]){ left = mid + 1; } else { right = mid - 1; } } } return -1; } } ``` 复杂度分析 时间复杂度: O(logn),其中 n 为nums 数组的大小。整个算法时间复杂度即为二分查找的时间复杂度O(logn)。 空间复杂度: O(1) 。我们只需要常数级别的空间存放变量。 #### [81. 搜索旋转排序数组 II](https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/) 难度中等558 已知存在一个按非降序排列的整数数组 `nums` ,数组中的值不必互不相同。 在传递给函数之前,`nums` 在预先未知的某个下标 `k`(`0 <= k < nums.length`)上进行了 **旋转** ,使数组变为 `[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]`(下标 **从 0 开始** 计数)。例如, `[0,1,2,4,4,4,5,6,6,7]` 在下标 `5` 处经旋转后可能变为 `[4,5,6,6,7,0,1,2,4,4]` 。 给你 **旋转后** 的数组 `nums` 和一个整数 `target` ,请你编写一个函数来判断给定的目标值是否存在于数组中。如果 `nums` 中存在这个目标值 `target` ,则返回 `true` ,否则返回 `false` 。 你必须尽可能减少整个操作步骤。 **示例 1:** ``` 输入:nums = [2,5,6,0,0,1,2], target = 0 输出:true ``` **示例 2:** ``` 输入:nums = [2,5,6,0,0,1,2], target = 3 输出:false ``` **提示:** - `1 <= nums.length <= 5000` - `-104 <= nums[i] <= 104` - 题目数据保证 `nums` 在预先未知的某个下标上进行了旋转 - `-104 <= target <= 104` **进阶:** - 这是 [搜索旋转排序数组](https://leetcode-cn.com/problems/search-in-rotated-sorted-array/description/) 的延伸题目,本题中的 `nums` 可能包含重复元素。 - 这会影响到程序的时间复杂度吗?会有怎样的影响,为什么? # 第一部分:链表专题 #### [206. 反转链表](https://leetcode-cn.com/problems/reverse-linked-list/) 难度简单2340 给你单链表的头节点 `head` ,请你反转链表,并返回反转后的链表。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2021/02/19/rev1ex1.jpg) ``` 输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1] ``` **示例 2:** ![img](https://assets.leetcode.com/uploads/2021/02/19/rev1ex2.jpg) ``` 输入:head = [1,2] 输出:[2,1] ``` **示例 3:** ``` 输入:head = [] 输出:[] ``` **提示:** - 链表中节点的数目范围是 `[0, 5000]` - `-5000 <= Node.val <= 5000` **进阶:**链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题? 通过次数912,225 提交次数1,254,078 **方法一:迭代法:链表反转** 假设存在链表 1→2→3→∅,我们∅←1←2←3。 在遍历列表时,将当前节点的next 指针改为指向前一个元素。由于节点没有引用其上一个节点,因此必须事先存储其前一个元素。在更改引用之前,还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用! ```java class Solution { public ListNode reverseList(ListNode head) { ListNode curr = head; ListNode prev = null; while(curr != null){ ListNode temp = curr.next; curr.next = prev; prev = curr; curr = temp; } return prev; } } ``` **方法二:递归:后序遍历** 递归的意思:我子节点下的所有节点都已经反转好了,现在就剩我和我的子节点 没有完成最后的反转了,所以反转一下我和我的子节点。 ```java reverseList: head=1 reverseList: head=2 reverseList: head=3 reverseList:head=4 reverseList:head=5 终止返回 cur = 5 4.next.next->4,即5->4 cur=5 3.next.next->3,即4->3 cur = 5 2.next.next->2,即3->2 cur = 5 1.next.next->1,即2->1 最后返回cur ``` ```java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { //相信这个函数的定义:返回反转后链表的头结点 public ListNode reverseList(ListNode head) { if (head == null || head.next == null){ return head; } //可以将链表看作当前节点和子节点两部分来看 ListNode curr = reverseList(head.next); head.next.next = head; head.next = null; return curr; } } ``` #### [92. 反转链表 II](https://leetcode-cn.com/problems/reverse-linked-list-ii/) 难度中等1185 给你单链表的头指针 `head` 和两个整数 `left` 和 `right` ,其中 `left <= right` 。请你反转从位置 `left` 到位置 `right` 的链表节点,返回 **反转后的链表** 。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2021/02/19/rev2ex2.jpg) ``` 输入:head = [1,2,3,4,5], left = 2, right = 4 输出:[1,4,3,2,5] ``` **示例 2:** ``` 输入:head = [5], left = 1, right = 1 输出:[5] ``` **提示:** - 链表中节点数目为 `n` - `1 <= n <= 500` - `-500 <= Node.val <= 500` - `1 <= left <= right <= n` **进阶:** 你可以使用一趟扫描完成反转吗? **算法步骤:** 第 1 步:先将待反转的区域反转; 第 2 步:把 pre 的 next 指针指向反转以后的链表头节点,把反转以后的链表的尾节点的 next 指针指向 succ。 ![image.png](https://pic.leetcode-cn.com/1615105168-ZQRZew-image.png) **方法一:定位指针 + 截取 + 翻转 + 拼接** ```java class Solution { public ListNode reverseBetween(ListNode head, int left, int right) { // 因为头节点有可能发生变化,使用虚拟头节点可以避免复杂的分类讨论 ListNode dummy = new ListNode(-1); dummy.next = head; ListNode pre = dummy; // 第 1 步:从虚拟头节点走 left - 1 步,来到 left 节点的前一个节点 // 建议写在 for 循环里,语义清晰 for (int i = 0; i < left - 1; i++) { pre = pre.next; } // 第 2 步:从 pre 再走 right - left + 1 步,来到 right 节点 ListNode rightNode = pre; for (int i = 0; i < right - left + 1; i++) { rightNode = rightNode.next; } // 第 3 步:切断出一个子链表(截取链表) ListNode leftNode = pre.next; ListNode curr = rightNode.next; // 注意:切断链接 pre.next = null; rightNode.next = null; // 第 4 步:同第 206 题,反转链表的子区间 reverseLinkedList(leftNode); // 第 5 步:接回到原来的链表中 pre.next = rightNode; leftNode.next = curr; return dummy.next; } private void reverseLinkedList(ListNode head) { // 也可以使用递归反转一个链表 ListNode pre = null; ListNode cur = head; while (cur != null) { ListNode next = cur.next; cur.next = pre; pre = cur; cur = next; } } } ``` **复杂度分析** - 时间复杂度:O(N)*O*(*N*),其中 N*N* 是链表总节点数。最坏情况下,需要遍历整个链表。 - 空间复杂度:O(1)*O*(1)。只使用到常数个变量。 **方法二:头插法** #### [160. 相交链表(Y型链表)](https://leetcode-cn.com/problems/intersection-of-two-linked-lists/) 难度简单1587 给你两个单链表的头节点 `headA` 和 `headB` ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 `null` 。 图示两个链表在节点 `c1` 开始相交**:** [![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_statement.png)](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_statement.png) 题目数据 **保证** 整个链式结构中不存在环。 **注意**,函数返回结果后,链表必须 **保持其原始结构** 。 **自定义评测:** **评测系统** 的输入如下(你设计的程序 **不适用** 此输入): - `intersectVal` - 相交的起始节点的值。如果不存在相交节点,这一值为 `0` - `listA` - 第一个链表 - `listB` - 第二个链表 - `skipA` - 在 `listA` 中(从头节点开始)跳到交叉节点的节点数 - `skipB` - 在 `listB` 中(从头节点开始)跳到交叉节点的节点数 评测系统将根据这些输入创建链式数据结构,并将两个头节点 `headA` 和 `headB` 传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 **视作正确答案** 。 **示例 1:** [![img](https://assets.leetcode.com/uploads/2021/03/05/160_example_1_1.png)](https://assets.leetcode.com/uploads/2018/12/13/160_example_1.png) ``` 输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3 输出:Intersected at '8' 解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。 从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,6,1,8,4,5]。 在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。 ``` **示例 2:** [![img](https://assets.leetcode.com/uploads/2021/03/05/160_example_2.png)](https://assets.leetcode.com/uploads/2018/12/13/160_example_2.png) ``` 输入:intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出:Intersected at '2' 解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。 从各自的表头开始算起,链表 A 为 [1,9,1,2,4],链表 B 为 [3,2,4]。 在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。 ``` **示例 3:** [![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_example_3.png)](https://assets.leetcode.com/uploads/2018/12/13/160_example_3.png) ``` 输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出:null 解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。 由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。 这两个链表不相交,因此返回 null 。 ``` **提示:** - `listA` 中节点数目为 `m` - `listB` 中节点数目为 `n` - `1 <= m, n <= 3 * 104` - `1 <= Node.val <= 105` - `0 <= skipA <= m` - `0 <= skipB <= n` - 如果 `listA` 和 `listB` 没有交点,`intersectVal` 为 `0` - 如果 `listA` 和 `listB` 有交点,`intersectVal == listA[skipA] == listB[skipB]` **进阶:**你能否设计一个时间复杂度 `O(m + n)` 、仅用 `O(1)` 内存的解决方案? **方法一:Set** ```java public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { Set set = new HashSet<>(); while(headA != null){ set.add(headA); headA = headA.next; } while(headB != null){ if (set.contains(headB)){ return headB; } set.add(headB); headB = headB.next; } return null; } } ``` **方法二:快慢指针** ![Picture1.png](https://pic.leetcode-cn.com/1615224578-EBRtwv-Picture1.png) ![image-20220311075856441](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220311075856441.png) ```java public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode A = headA, B = headB; while(A != B){ //因为A,B走的节点数一样,所以A,B最后必然:要么同时指向第一个公共节点,要么同时指向null A = (A != null) ? A.next : headB; B = (B != null) ? B.next : headA; } return A; } } ``` 复杂度分析: 时间复杂度 O(a + b) : 最差情况下(即 |a - b| = 1 , c = 0 ),此时需遍历 a + b 个节点。 空间复杂度 O(1): 节点指针 A , B 使用常数大小的额外空间。 #### [141. 环形链表](https://leetcode-cn.com/problems/linked-list-cycle/) 难度简单1392 给你一个链表的头节点 `head` ,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 `next` 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 `pos` 来表示链表尾连接到链表中的位置(索引从 0 开始)。**注意:`pos` 不作为参数进行传递** 。仅仅是为了标识链表的实际情况。 *如果链表中存在环* ,则返回 `true` 。 否则,返回 `false` 。 **示例 1:** ![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist.png) ``` 输入:head = [3,2,0,-4], pos = 1 输出:true 解释:链表中有一个环,其尾部连接到第二个节点。 ``` **示例 2:** ![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist_test2.png) ``` 输入:head = [1,2], pos = 0 输出:true 解释:链表中有一个环,其尾部连接到第一个节点。 ``` **示例 3:** ![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist_test3.png) ``` 输入:head = [1], pos = -1 输出:false 解释:链表中没有环。 ``` **提示:** - 链表中节点的数目范围是 `[0, 104]` - `-105 <= Node.val <= 105` - `pos` 为 `-1` 或者链表中的一个 **有效索引** 。 **进阶:**你能用 `O(1)`(即,常量)内存解决此问题吗? **方法一:Set验重** ```java public class Solution { public boolean hasCycle(ListNode head) { Set seen = new HashSet(); while (head != null) { if (!seen.add(head)) { return true; } head = head.next; } return false; } } ``` **方法二:快慢指针** ![image-20220310214947129](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220310214947129.png) ![image-20220310215001476](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220310215001476.png) **如果存在环,则快指针不管快多少,始终会在环上跑,当慢指针也进入到环中时,两个指针都会无限在环中跑,跑N次之后,总有快慢指针相遇的时候,所以说,fast = fast.next.next,最好再把fast.next也拿出来当做判断条件,防止环过大导致快慢指针总是不相遇,节省点内存** ```java public class Solution { public boolean hasCycle(ListNode head) { if (head == null || head.next == null) { return false; } ListNode slow = head; ListNode fast = head.next; while (slow != fast) { if (fast == null || fast.next == null) { return false; } slow = slow.next; fast = fast.next.next; } return true; } } /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { if (head == null) return false; //快慢两个指针 ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) {//如果fast.next == null表示链表无环 //慢指针每次走一步 slow = slow.next; //快指针每次走两步 fast = fast.next.next; //如果相遇,说明有环,结束循环,直接返回true if (slow == fast) return true; } //否则就是没环 return false; } } ``` ![image-20220310215046583](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220310215046583.png) #### [86. 分隔链表 类比合并两个有序链表](https://leetcode-cn.com/problems/partition-list/) 难度中等535 给你一个链表的头节点 `head` 和一个特定值 `x` ,请你对链表进行分隔,使得所有 **小于** `x` 的节点都出现在 **大于或等于** `x` 的节点之前。 你应当 **保留** 两个分区中每个节点的初始相对位置。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2021/01/04/partition.jpg) ``` 输入:head = [1,4,3,2,5,2], x = 3 输出:[1,2,2,4,3,5] ``` **示例 2:** ``` 输入:head = [2,1], x = 2 输出:[1,2] ``` **提示:** - 链表中节点的数目在范围 `[0, 200]` 内 - `-100 <= Node.val <= 100` - `-200 <= x <= 200` 通过次数140,022 提交次数221,257 ![image-20220315150330887](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220315150330887.png) ```java class Solution { public ListNode partition(ListNode head, int x) { ListNode smallHead = new ListNode(0); ListNode small = smallHead; ListNode largeHead = new ListNode(0); ListNode large = largeHead; while (head != null) { if (head.val < x) { small.next = head; //小于x的链表指针 small = small.next; } else { large.next = head; //大于x的链表指针 large = large.next; } head = head.next; //指向原链表的指针 } large.next = null;, //关键:切断原链表的引用 small.next = largeHead.next; return smallHead.next; } } ``` **复杂度分析** - 时间复杂度: O(n),其中 n 是原链表的长度。我们对该链表进行了一次遍历。 - 空间复杂度: O(1)。 #### [138. 复制带随机指针的链表](https://leetcode-cn.com/problems/copy-list-with-random-pointer/) 难度中等835 给你一个长度为 `n` 的链表,每个节点包含一个额外增加的随机指针 `random` ,该指针可以指向链表中的任何节点或空节点。 构造这个链表的 **[深拷贝](https://baike.baidu.com/item/深拷贝/22785317?fr=aladdin)**。 深拷贝应该正好由 `n` 个 **全新** 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 `next` 指针和 `random` 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。**复制链表中的指针都不应指向原链表中的节点** 。 例如,如果原链表中有 `X` 和 `Y` 两个节点,其中 `X.random --> Y` 。那么在复制链表中对应的两个节点 `x` 和 `y` ,同样有 `x.random --> y` 。 返回复制链表的头节点。 用一个由 `n` 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 `[val, random_index]` 表示: - `val`:一个表示 `Node.val` 的整数。 - `random_index`:随机指针指向的节点索引(范围从 `0` 到 `n-1`);如果不指向任何节点,则为 `null` 。 你的代码 **只** 接受原链表的头节点 `head` 作为传入参数。 **示例 1:** ![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/09/e1.png) ``` 输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出:[[7,null],[13,0],[11,4],[10,2],[1,0]] ``` **示例 2:** ![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/09/e2.png) ``` 输入:head = [[1,1],[2,1]] 输出:[[1,1],[2,1]] ``` **示例 3:** **![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/09/e3.png)** ``` 输入:head = [[3,null],[3,0],[3,null]] 输出:[[3,null],[3,0],[3,null]] ``` **提示:** - `0 <= n <= 1000` - `-104 <= Node.val <= 104` - `Node.random` 为 `null` 或指向链表中的节点。 ![image-20220315155628723](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220315155628723.png) ![image-20220315155645684](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220315155645684.png) ```java /* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } } */ class Solution { public Node copyRandomList(Node head) { //第一步,在每个原节点后面创建一个新节点 //1->1'->2->2'->3->3' Node curr = head; while(curr != null){ Node newNode = new Node(curr.val); newNode.next = curr.next; curr.next = newNode; curr = newNode.next; } //第二步,设置新节点的随机节点 curr = head; while(curr != null){ if (curr.random != null){ curr.next.random = curr.random.next; } curr = curr.next.next; } //第三步,将两个链表分离 Node dummy = new Node(-1); Node prev = dummy; curr = head; while(curr != null){ prev.next = curr.next; curr.next = curr.next.next; //原链表为偶数个节点curr.next一定不为空 prev = prev.next; curr = curr.next; } return dummy.next; } } ``` #### [21. 合并两个有序链表 类比合并两个有序数组(归并)](https://leetcode-cn.com/problems/merge-two-sorted-lists/) 难度简单2254 将两个升序链表合并为一个新的 **升序** 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2020/10/03/merge_ex1.jpg) ``` 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] ``` **示例 2:** ``` 输入:l1 = [], l2 = [] 输出:[] ``` **示例 3:** ``` 输入:l1 = [], l2 = [0] 输出:[0] ``` **提示:** - 两个链表的节点数目范围是 `[0, 50]` - `-100 <= Node.val <= 100` - `l1` 和 `l2` 均按 **非递减顺序** 排列 ```java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(-1); ListNode prev = dummy; ListNode p1 = l1, p2 = l2; while(p1 != null && p2 != null){ if (p1.val <= p2.val){ prev.next = p1; p1 = p1.next; } else { prev.next = p2; p2 = p2.next; } prev = prev.next; } prev.next = p1 == null ? p2 : p1; return dummy.next; } } ``` #### [23. 合并K个升序链表](https://leetcode-cn.com/problems/merge-k-sorted-lists/) 难度困难1805 给你一个链表数组,每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中,返回合并后的链表。 **示例 1:** ``` 输入:lists = [[1,4,5],[1,3,4],[2,6]] 输出:[1,1,2,3,4,4,5,6] 解释:链表数组如下: [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6 ``` **示例 2:** ``` 输入:lists = [] 输出:[] ``` **示例 3:** ``` 输入:lists = [[]] 输出:[] ``` **提示:** - `k == lists.length` - `0 <= k <= 10^4` - `0 <= lists[i].length <= 500` - `-10^4 <= lists[i][j] <= 10^4` - `lists[i]` 按 **升序** 排列 - `lists[i].length` 的总和不超过 `10^4` 通过次数412,375 提交次数728,737 **方法一:顺序合并** ```java class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists.length == 0){ return null; } //思路:数组横向两两链表合并 int n = lists.length; ListNode ans = null; for(int i = 0; i < n; i++){ ans = mergeLinkedList(ans, lists[i]); } return ans; } //合并两个升序链表 public ListNode mergeLinkedList(ListNode l1, ListNode l2){ //使用哑节点来简化边界条件的处理 ListNode dummy = new ListNode(0); //待插入节点的前驱节点 ListNode prev = dummy; while (l1 != null && l2 != null){ if (l1.val <= l2.val){ prev.next = l1; l1 = l1.next; } else { prev.next = l2; l2 = l2.next; } prev = prev.next; } prev.next = l1 == null ? l2 : l1; return dummy.next; } } ``` ![image-20220316112732052](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220316112732052.png) **方法二:分治合并** **方法三:使用优先队列合并** #### [143. 重排链表](https://leetcode-cn.com/problems/reorder-list/) 难度中等826 给定一个单链表 `L` 的头节点 `head` ,单链表 `L` 表示为: ``` L0 → L1 → … → Ln - 1 → Ln ``` 请将其重新排列后变为: ``` L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … ``` 不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。 **示例 1:** ![img](https://pic.leetcode-cn.com/1626420311-PkUiGI-image.png) ``` 输入:head = [1,2,3,4] 输出:[1,4,2,3] ``` **示例 2:** ![img](https://pic.leetcode-cn.com/1626420320-YUiulT-image.png) ``` 输入:head = [1,2,3,4,5] 输出:[1,5,2,4,3] ``` **提示:** - 链表的长度范围为 `[1, 5 * 104]` - `1 <= node.val <= 1000` **方法一:三步走:寻找链表中间节点 + 反转链表 + 合并链表** ```java class Solution { public void reorderList(ListNode head) { if(head == null || head.next == null){ return; } ListNode midNode = middleNode(head); ListNode l1 = head, l2 = midNode.next; //这里必须断开,否则会出现环 midNode.next = null; l2 = reverse(l2); merge(l1, l2); } //1、寻找链表中间节点 public ListNode middleNode(ListNode head){ if (head == null) return head; ListNode slow = head; ListNode fast = head; while (fast.next != null && fast.next.next != null){ slow = slow.next; fast = fast.next.next; } return slow; } //2、反转链表 public ListNode reverse(ListNode head){ ListNode prev = null; ListNode curr = head; while(curr != null){ ListNode temp = curr.next; curr.next = prev; prev = curr; curr = temp; } return prev; } //3、合并链表 public void merge(ListNode l1, ListNode l2){ //l1和l2只相差一个节点 while (l1 != null && l2 != null){ ListNode temp1 = l1.next; l1.next = l2; l1 = temp1; ListNode temp2 = l2.next; l2.next = l1; l2 = temp2; } } } ``` **复杂度分析** - 时间复杂度:O(N)*O*(*N*),其中 N*N* 是链表中的节点数。 - 空间复杂度:O(1)*O*(1)。 **方法二:线性表** 因为链表不支持下标访问,所以我们无法随机访问链表中任意位置的元素。 因此比较容易想到的一个方法是,我们利用线性表存储该链表,然后利用线性表可以下标访问的特点,直接按顺序访问指定元素,重建该链表即可。 ```java class Solution { public void reorderList(ListNode head) { if (head == null) { return; } List list = new ArrayList(); ListNode node = head; while (node != null) { list.add(node); node = node.next; } int i = 0, j = list.size() - 1; while (i < j) { list.get(i).next = list.get(j); i++; if (i == j) { break; } list.get(j).next = list.get(i); j--; } list.get(i).next = null; } } ``` **复杂度分析** - 时间复杂度:O(N)*O*(*N*),其中 N*N* 是链表中的节点数。 - 空间复杂度:O(N)*O*(*N*),其中 N*N* 是链表中的节点数。主要为线性表的开销。 #### [876. 链表的中间结点](https://leetcode-cn.com/problems/middle-of-the-linked-list/) 难度简单513 给定一个头结点为 `head` 的非空单链表,返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。 **示例 1:** ``` 输入:[1,2,3,4,5] 输出:此列表中的结点 3 (序列化形式:[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。 注意,我们返回了一个 ListNode 类型的对象 ans,这样: ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL. ``` **示例 2:** ``` 输入:[1,2,3,4,5,6] 输出:此列表中的结点 4 (序列化形式:[4,5,6]) 由于该列表有两个中间结点,值分别为 3 和 4,我们返回第二个结点。 ``` **提示:** - 给定链表的结点数介于 `1` 和 `100` 之间。 **方法一:快慢指针** ![876-1.png](https://pic.leetcode-cn.com/2b7a4130111600cf615b5584b3cc7f863d289a9a7d43b90147c79f51f68a5aa6-876-1.png) ```java class Solution { public ListNode middleNode(ListNode head) { if (head == null) return head; ListNode slow = head, fast = head; //如果有两个中间结点,则返回第二个中间结点。 while(fast != null && fast.next != null){ slow = slow.next; fast = fast.next.next; } return slow; } } ``` ### ![876-2.png](https://pic.leetcode-cn.com/5c3f88cc6b312b7193a6e071cef93ec5eb3070005af23cad22a11e10ea0aca3e-876-2.png) ```java class Solution { public ListNode middleNode(ListNode head) { if (head == null) return head; //走到这里说明链表至少有一个节点 ListNode slow = head, fast = head; //如果有两个中间结点,则返回第一个中间结点。 while(fast.next != null && fast.next.next != null){ //走到这里说明链表至少有三个节点,所以fast不会等于null slow = slow.next; fast = fast.next.next; } return slow; } } ``` **方法二:遍历链表获取长度** ![image-20220319084208041](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220319084208041.png) #### liweiwei链表专题 https://leetcode-cn.com/problems/middle-of-the-linked-list/solution/kuai-man-zhi-zhen-zhu-yao-zai-yu-diao-shi-by-liwei/ ![image-20220319084453384](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220319084453384.png) ![image-20220319084603123](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220319084603123.png) #### [24. 两两交换链表中的节点 类比k个一组反转链表](https://leetcode-cn.com/problems/swap-nodes-in-pairs/) 难度中等1292 给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2020/10/03/swap_ex1.jpg) ``` 输入:head = [1,2,3,4] 输出:[2,1,4,3] ``` **示例 2:** ``` 输入:head = [] 输出:[] ``` **示例 3:** ``` 输入:head = [1] 输出:[1] ``` **提示:** - 链表中节点的数目在范围 `[0, 100]` 内 - `0 <= Node.val <= 100` **方法一:k个一组反转链表** ```java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode swapPairs(ListNode head) { ListNode dummy = new ListNode(-1); dummy.next = head; ListNode prev = dummy, end = dummy; while(end.next != null){//循环中保证了至少有2个节点,所以end不会为空 //找到待反转链表的尾节点 for(int i = 0; i < 2 && end != null; i++){ end = end.next; } //end为空说明链表长度小于2 if (end == null){ break; } //记录待反转链表末尾的下一个节点 ListNode next = end.next; //断开链表 end.next = null; //记录待反转链表的头节点 ListNode start = prev.next; //反转链表,并且重新连接 prev.next = reverse(start); start.next = next; //将prev、end指向下一个将要反转链表头节点的前一个节点 prev = start; end = start; } return dummy.next; } public ListNode reverse(ListNode head){ ListNode prev = null; ListNode curr = head; while(curr != null){ ListNode temp = curr.next; curr.next = prev; prev = curr; curr = temp; } return prev; } } ``` 方法二:迭代法 ```java class Solution { public ListNode swapPairs(ListNode head) { ListNode dummy = new ListNode(-1); dummy.next = head; ListNode prev = dummy; ListNode curr = head; while(curr != null && curr.next != null){//至少保证链表有两个节点才能反转 //待反转链表头节点的前一个节点指向待反转链表尾节点 prev.next = curr.next; //记录待反转链表尾节点的下一个节点 ListNode temp = curr.next.next; //反转操作 curr.next.next = curr; curr.next = temp; //prev指向下一个待反转链表头节点的前一个节点 prev = curr; //curr指向下一个待反转链表的头节点 curr = curr.next; } return dummy.next; } } ``` #### [328. 奇偶链表](https://leetcode-cn.com/problems/odd-even-linked-list/) 难度中等551 给定单链表的头节点 `head` ,将所有索引为奇数的节点和索引为偶数的节点分别组合在一起,然后返回重新排序的列表。 **第一个**节点的索引被认为是 **奇数** , **第二个**节点的索引为 **偶数** ,以此类推。 请注意,偶数组和奇数组内部的相对顺序应该与输入时保持一致。 你必须在 `O(1)` 的额外空间复杂度和 `O(n)` 的时间复杂度下解决这个问题。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2021/03/10/oddeven-linked-list.jpg) ``` 输入: head = [1,2,3,4,5] 输出: [1,3,5,2,4] ``` **示例 2:** ![img](https://assets.leetcode.com/uploads/2021/03/10/oddeven2-linked-list.jpg) ``` 输入: head = [2,1,3,5,6,4,7] 输出: [2,3,6,7,1,5,4] ``` **提示:** - `n == ` 链表中的节点数 - `0 <= n <= 104` - `-106 <= Node.val <= 106` ```java class Solution { public ListNode oddEvenList(ListNode head) { ListNode dummy1 = new ListNode(-1); ListNode prev1 = dummy1; ListNode dummy2 = new ListNode(-1); ListNode prev2 = dummy2; boolean flag = true; while(head != null){ if (flag){ prev1.next = head; prev1 = prev1.next; } else { prev2.next = head; prev2 = prev2.next; } head = head.next; flag = !flag; } //一定要切断链表,否则户籍产生循环 prev2.next = null; prev1.next = dummy2.next; return dummy1.next; } } ``` #### [203. 移除链表元素](https://leetcode-cn.com/problems/remove-linked-list-elements/) 难度简单842 给你一个链表的头节点 `head` 和一个整数 `val` ,请你删除链表中所有满足 `Node.val == val` 的节点,并返回 **新的头节点** 。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2021/03/06/removelinked-list.jpg) ``` 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5] ``` **示例 2:** ``` 输入:head = [], val = 1 输出:[] ``` **示例 3:** ``` 输入:head = [7,7,7,7], val = 7 输出:[] ``` **提示:** - 列表中的节点数目在范围 `[0, 104]` 内 - `1 <= Node.val <= 50` - `0 <= val <= 50` ```java class Solution { public ListNode removeElements(ListNode head, int val) { ListNode dummy = new ListNode(-1); dummy.next = head; ListNode prev = dummy, curr = head; while(curr != null){ if (curr.val == val){ prev.next = curr.next; curr = curr.next; } else { prev = curr; curr = curr.next; } } return dummy.next; } } ``` #### [2. 两数相加 类比字符串相加](https://leetcode-cn.com/problems/add-two-numbers/) 难度中等7712 给你两个 **非空** 的链表,表示两个非负的整数。它们每位数字都是按照 **逆序** 的方式存储的,并且每个节点只能存储 **一位** 数字。 请你将两个数相加,并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外,这两个数都不会以 0 开头。 **示例 1:** ![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/01/02/addtwonumber1.jpg) ``` 输入:l1 = [2,4,3], l2 = [5,6,4] 输出:[7,0,8] 解释:342 + 465 = 807. ``` **示例 2:** ``` 输入:l1 = [0], l2 = [0] 输出:[0] ``` **示例 3:** ``` 输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出:[8,9,9,9,0,0,0,1] ``` **提示:** - 每个链表中的节点数在范围 `[1, 100]` 内 - `0 <= Node.val <= 9` - 题目数据保证列表表示的数字不含前导零 ```java class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(-1); ListNode prev = dummy; int carry = 0; while(l1 != null || l2 != null){ int n1 = l1 != null ? l1.val : 0; int n2 = l2 != null ? l2.val : 0; int temp = n1 + n2 + carry; carry = temp / 10; prev.next = new ListNode(temp % 10); prev = prev.next; l1 = l1 != null ? l1.next : l1; l2 = l2 != null ? l2.next : l2; } if (carry > 0){ prev.next = new ListNode(carry); } return dummy.next; } } ``` #### [82. 删除排序链表中的重复元素 II](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/) 难度中等839 给定一个已排序的链表的头 `head` , *删除原始链表中所有重复数字的节点,只留下不同的数字* 。返回 *已排序的链表* 。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2021/01/04/linkedlist1.jpg) ``` 输入:head = [1,2,3,3,4,4,5] 输出:[1,2,5] ``` **示例 2:** ![img](https://assets.leetcode.com/uploads/2021/01/04/linkedlist2.jpg) ``` 输入:head = [1,1,1,2,3] 输出:[2,3] ``` **提示:** - 链表中节点数目在范围 `[0, 300]` 内 - `-100 <= Node.val <= 100` - 题目数据保证链表已经按升序 **排列** 通过次数231,251 提交次数434,000 ```java class Solution { public ListNode deleteDuplicates(ListNode head) { ListNode dummy = new ListNode(-1); dummy.next = head; ListNode prev = dummy, curr = head; while(curr != null && curr.next != null){ //至少存在两个节点才可能重复 if (curr.val != curr.next.val){ prev = curr; curr = curr.next; } else { //这里curr != null也是可以省略的,因为curr.next != null这个条件会先到达 while(curr != null && curr.next != null && curr.val == curr.next.val){ curr = curr.next; } //要求删除所有重复元素,所以curr还得向后移动一位 curr = curr.next; //这里curr不会为空 prev.next = curr; } } return dummy.next; } } ``` #### [83. 删除排序链表中的重复元素](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/) 难度简单749 给定一个已排序的链表的头 `head` , *删除所有重复的元素,使每个元素只出现一次* 。返回 *已排序的链表* 。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2021/01/04/list1.jpg) ``` 输入:head = [1,1,2] 输出:[1,2] ``` **示例 2:** ![img](https://assets.leetcode.com/uploads/2021/01/04/list2.jpg) ``` 输入:head = [1,1,2,3,3] 输出:[1,2,3] ``` **提示:** - 链表中节点数目在范围 `[0, 300]` 内 - `-100 <= Node.val <= 100` - 题目数据保证链表已经按升序 **排 ```java class Solution { public ListNode deleteDuplicates(ListNode head) { ListNode dummy = new ListNode(-1); dummy.next = head; ListNode prev = dummy, curr = head; while(curr != null && curr.next != null){ //至少存在两个节点才可能重复 if (curr.val != curr.next.val){ prev = curr; curr = curr.next; } else { //这里curr != null也是可以省略的,因为curr.next != null这个条件会先到达 while(curr != null && curr.next != null && curr.val == curr.next.val){ curr = curr.next; } prev.next = curr; } } return dummy.next; } } ``` #### [148. 排序链表 类比归并排序](https://leetcode-cn.com/problems/sort-list/) 难度中等1514 给你链表的头结点 `head` ,请将其按 **升序** 排列并返回 **排序后的链表** 。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2020/09/14/sort_list_1.jpg) ``` 输入:head = [4,2,1,3] 输出:[1,2,3,4] ``` **示例 2:** ![img](https://assets.leetcode.com/uploads/2020/09/14/sort_list_2.jpg) ``` 输入:head = [-1,5,3,4,0] 输出:[-1,0,3,4,5] ``` **示例 3:** ``` 输入:head = [] 输出:[] ``` **提示:** - 链表中节点的数目在范围 `[0, 5 * 104]` 内 - `-105 <= Node.val <= 105` **进阶:**你可以在 `O(n log n)` 时间复杂度和常数级空间复杂度下,对链表进行排序吗? 通过次数263,567 提交次数396,406 **方法一:归并排序 + 寻找链表中间节点** ```java class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null){ return head; } ListNode l1 = head; ListNode mid = middleNode(l1); ListNode l2 = mid.next; mid.next = null; l1 = sortList(l1); l2 = sortList(l2); return merge(l1, l2); } //合并两个有序链表 private ListNode merge(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(-1); ListNode prev = dummy; while (l1 != null && l2 != null){ if (l1.val <= l2.val){ prev.next = l1; l1 = l1.next; } else { prev.next = l2; l2 = l2.next; } prev = prev.next; } prev.next = l1 != null ? l1 : l2; return dummy.next; } //找到链表的中间节点(如果有两个中间节点,找第一个) private ListNode middleNode(ListNode head) { if (head == null){ return head; } ListNode slow = head, fast = head; while (fast.next != null && fast.next.next != null){ slow = slow.next; fast = fast.next.next; } return slow; } } ``` ### ## 第二页3.14~3.20 ### [200. 岛屿数量](https://leetcode-cn.com/problems/number-of-islands/) 难度中等1593 给你一个由 `'1'`(陆地)和 `'0'`(水)组成的的二维网格,请你计算网格中岛屿的数量。 岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外,你可以假设该网格的四条边均被水包围。 **示例 1:** ``` 输入:grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] 输出:1 ``` **示例 2:** ``` 输入:grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] 输出:3 ``` **提示:** - `m == grid.length` - `n == grid[i].length` - `1 <= m, n <= 300` - `grid[i][j]` 的值为 `'0'` 或 `'1'` **方法一:DFS** ![image-20220313165459671](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220313165459671.png) ```java class Solution { //利用深度递归解决,可以看图,并加记住这个模板,他可以解决岛屿中的问题,还有一题岛屿面积问题也是这个模板。 public int numIslands(char[][] grid) { int count = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == '1'){ dfs(grid, i, j); count++; } } } return count; } private void dfs(char[][] grid, int i, int j) { //1、递归终止条件 if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0'){ return; } //2、递归主体 grid[i][j] = '0'; //3、前序遍历框架 dfs(grid, i + 1, j); dfs(grid, i, j + 1); dfs(grid, i - 1, j); dfs(grid, i, j - 1); } } ``` 复杂度分析 时间复杂度:O(MN)O(MN),其中 M 和 N 分别为行数和列数。 空间复杂度:O(MN)O(MN),在最坏情况下,整个网格均为陆地,深度优先搜索的深度达到 M NMN。 **方法二:BFS(层序遍历相似)** ```java class Solution { public int numIslands(char[][] grid) { int count = 0; for(int i = 0; i < grid.length; i++) { for(int j = 0; j < grid[0].length; j++) { if(grid[i][j] == '1'){ bfs(grid, i, j); count++; } } } return count; } private void bfs(char[][] grid, int i, int j){ Queue q = new LinkedList<>(); q.offer(new int[] { i, j}); //add while(!q.isEmpty()){ int[] cur = q.poll(); //remove i = cur[0]; j = cur[1]; if(0 <= i && i < grid.length && 0 <= j && j < grid[0].length && grid[i][j] == '1') { grid[i][j] = '0'; q.offer(new int[] { i + 1, j }); q.offer(new int[] { i - 1, j }); q.offer(new int[] { i, j + 1 }); q.offer(new int[] { i, j - 1 }); } } } } class Solution { public int numIslands(char[][] grid) { int count = 0; for(int i = 0; i < grid.length; i++) { for(int j = 0; j < grid[0].length; j++) { if(grid[i][j] == '1'){ bfs(grid, i, j); count++; } } } return count; } private void bfs(char[][] grid, int i, int j) { Queue q = new LinkedList<>(); q.offer(new int[]{i, j}); while (!q.isEmpty()){ int[] cur = q.poll(); int r = cur[0], c = cur[1]; if (r >= 0 && r < grid.length && c >= 0 && c < grid[0].length && grid[r][c] == '1'){ grid[r][c] = '0'; q.offer(new int[] {r + 1, c}); q.offer(new int[] {r - 1, c}); q.offer(new int[] {r, c + 1}); q.offer(new int[] {r, c - 1}); } } } } ``` 复杂度分析 时间复杂度:O(MN),其中 M 和 N 分别为行数和列数。 空间复杂度:O(min(M,N)),在最坏情况下,整个网格均为陆地,队列的大小可以达到min(M,N)。 #### [463. 岛屿的周长](https://leetcode-cn.com/problems/island-perimeter/) 难度简单517 给定一个 `row x col` 的二维网格地图 `grid` ,其中:`grid[i][j] = 1` 表示陆地, `grid[i][j] = 0` 表示水域。 网格中的格子 **水平和垂直** 方向相连(对角线方向不相连)。整个网格被水完全包围,但其中恰好有一个岛屿(或者说,一个或多个表示陆地的格子相连组成的岛屿)。 岛屿中没有“湖”(“湖” 指水域在岛屿内部且不和岛屿周围的水相连)。格子是边长为 1 的正方形。网格为长方形,且宽度和高度均不超过 100 。计算这个岛屿的周长。 **示例 1:** ![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/10/12/island.png) ``` 输入:grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]] 输出:16 解释:它的周长是上面图片中的 16 个黄色的边 ``` **示例 2:** ``` 输入:grid = [[1]] 输出:4 ``` **示例 3:** ``` 输入:grid = [[1,0]] 输出:4 ``` **提示:** - `row == grid.length` - `col == grid[i].length` - `1 <= row, col <= 100` - `grid[i][j]` 为 `0` 或 `1` #### [695. 岛屿的最大面积](https://leetcode-cn.com/problems/max-area-of-island/) 难度中等719 给你一个大小为 `m x n` 的二进制矩阵 `grid` 。 **岛屿** 是由一些相邻的 `1` (代表土地) 构成的组合,这里的「相邻」要求两个 `1` 必须在 **水平或者竖直的四个方向上** 相邻。你可以假设 `grid` 的四个边缘都被 `0`(代表水)包围着。 岛屿的面积是岛上值为 `1` 的单元格的数目。 计算并返回 `grid` 中最大的岛屿面积。如果没有岛屿,则返回面积为 `0` 。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2021/05/01/maxarea1-grid.jpg) ``` 输入:grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]] 输出:6 解释:答案不应该是 11 ,因为岛屿只能包含水平或垂直这四个方向上的 1 。 ``` **示例 2:** ``` 输入:grid = [[0,0,0,0,0,0,0,0]] 输出:0 ``` **提示:** - `m == grid.length` - `n == grid[i].length` - `1 <= m, n <= 50` - `grid[i][j]` 为 `0` 或 `1` ### [46. 全排列](https://leetcode-cn.com/problems/permutations/) 难度中等1698 给定一个不含重复数字的数组 `nums` ,返回其 **所有可能的全排列** 。你可以 **按任意顺序** 返回答案。 **示例 1:** ``` 输入:nums = [1,2,3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] ``` **示例 2:** ``` 输入:nums = [0,1] 输出:[[0,1],[1,0]] ``` **示例 3:** ``` 输入:nums = [1] 输出:[[1]] ``` **提示:** - `1 <= nums.length <= 6` - `-10 <= nums[i] <= 10` - `nums` 中的所有整数 **互不相同** **方法一:DFS+回溯(liweiwei1419题解)** ![image.png](https://pic.leetcode-cn.com/0bf18f9b86a2542d1f6aa8db6cc45475fce5aa329a07ca02a9357c2ead81eec1-image.png) **理解回溯** 从 [1, 2, 3] 到 [1, 3, 2] ,深度优先遍历是这样做的,从 [1, 2, 3] 回到 [1, 2] 的时候,需要撤销刚刚已经选择的数 3,因为在这一层只有一个数 3 我们已经尝试过了,因此程序回到上一层,需要撤销对 2 的选择,好让后面的程序知道,选择 3 了以后还能够选择 2。 用`res.add(new linkedList(path))`而不是`res.add(path)`。因为`path`是个引用,所指向的对象在不断地增加和删除元素,最后会变成空。得到的结果会变成`[[][][][][]]`所以要用`new linkedList(path)`拷贝一个对象加入`res` ```java class Solution { List> res = new LinkedList<>();//所有排列集合,也可以是new ArrayList<>() LinkedList path = new LinkedList<>();//单个排列集合,需要方法removeLast(); public List> permute(int[] nums) { if (nums == null || nums.length == 0) return res; boolean[] visited = new boolean[nums.length];//默认全为false dfs(nums, visited); return res; } void dfs(int[] nums, boolean[] visited){ //path集合容量和数组长度相同时,添加到res集合中,并返回至上一层 if (path.size() == nums.length){ res.add(new LinkedList<>(path)); return; } for (int i = 0; i < nums.length; i++){ if (!visited[i]){ // 没有访问过才可以访问 visited[i] = true; //将当前节点标记为已访问 path.add(nums[i]); dfs(nums, visited); path.removeLast(); //回溯,删除path最后一个节点, 也可以是pollLast() visited[i] = false; // 将当前删除的节点再重新标记为未访问过 } } } } class Solution { List> res = new LinkedList<>();//所有排列集合,也可以是new ArrayList<>() LinkedList path = new LinkedList<>();//单个排列集合,需要方法removeLast(); public List> permute(int[] nums) { if (nums == null || nums.length == 0) return res; boolean[] visited = new boolean[nums.length];//默认全为false dfs(nums, visited, 0); return res; } void dfs(int[] nums, boolean[] visited, int depth){ //path集合容量和数组长度相同时,添加到res集合中,并返回至上一层 if (depth == nums.length){ res.add(new LinkedList<>(path)); return; } for (int i = 0; i < nums.length; i++){ if (!visited[i]){ // 没有访问过才可以访问 visited[i] = true; //将当前节点标记为已访问 path.add(nums[i]); dfs(nums, visited, depth + 1); path.removeLast(); //回溯,删除path最后一个节点 visited[i] = false; // 将当前删除的节点再重新标记为未访问过 } } } } ``` ```java import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Deque; import java.util.List; public class Solution { public List> permute(int[] nums) { int len = nums.length; // 使用一个动态数组保存所有可能的全排列 List> res = new ArrayList<>(); if (len == 0) { return res; } boolean[] used = new boolean[len]; Deque path = new ArrayDeque<>(len); dfs(nums, len, 0, path, used, res); return res; } private void dfs(int[] nums, int len, int depth, Deque path, boolean[] used, List> res) { if (depth == len) { res.add(new ArrayList<>(path)); return; } for (int i = 0; i < len; i++) { if (!used[i]) { path.addLast(nums[i]); used[i] = true; System.out.println(" 递归之前 => " + path); dfs(nums, len, depth + 1, path, used, res); used[i] = false; path.removeLast(); System.out.println("递归之后 => " + path); } } } public static void main(String[] args) { int[] nums = {1, 2, 3}; Solution solution = new Solution(); List> lists = solution.permute(nums); System.out.println(lists); } } 控制台输出: 递归之前 => [1] 递归之前 => [1, 2] 递归之前 => [1, 2, 3] 递归之后 => [1, 2] 递归之后 => [1] 递归之前 => [1, 3] 递归之前 => [1, 3, 2] 递归之后 => [1, 3] 递归之后 => [1] 递归之后 => [] 递归之前 => [2] 递归之前 => [2, 1] 递归之前 => [2, 1, 3] 递归之后 => [2, 1] 递归之后 => [2] 递归之前 => [2, 3] 递归之前 => [2, 3, 1] 递归之后 => [2, 3] 递归之后 => [2] 递归之后 => [] 递归之前 => [3] 递归之前 => [3, 1] 递归之前 => [3, 1, 2] 递归之后 => [3, 1] 递归之后 => [3] 递归之前 => [3, 2] 递归之前 => [3, 2, 1] 递归之后 => [3, 2] 递归之后 => [3] 递归之后 => [] 输出 => [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] ``` **复杂度分析** - 时间复杂度:*O*(*N*×*N*!)。 - 空间复杂度:*O*(*N*×*N*!) - 递归树深度 log*N*; - 全排列个数 N!,每个全排列占空间 N。取较大者。 ### [415. 字符串相加](https://leetcode-cn.com/problems/add-strings/) 难度简单517 给定两个字符串形式的非负整数 `num1` 和`num2` ,计算它们的和并同样以字符串形式返回。 你不能使用任何內建的用于处理大整数的库(比如 `BigInteger`), 也不能直接将输入的字符串转换为整数形式。 **示例 1:** ``` 输入:num1 = "11", num2 = "123" 输出:"134" ``` **示例 2:** ``` 输入:num1 = "456", num2 = "77" 输出:"533" ``` **示例 3:** ``` 输入:num1 = "0", num2 = "0" 输出:"0" ``` **提示:** - `1 <= num1.length, num2.length <= 104` - `num1` 和`num2` 都只包含数字 `0-9` - `num1` 和`num2` 都不包含任何前导零 **方法一:双指针** ```java class Solution { public String addStrings(String num1, String num2) { StringBuilder res = new StringBuilder(); int i = num1.length() - 1, j = num2.length() - 1, carry = 0; while (i >= 0 || j >= 0) { int n1 = i >= 0 ? num1.charAt(i) - '0' : 0; int n2 = j >= 0 ? num2.charAt(j) - '0' : 0; int tmp = n1 + n2 + carry; //当前位 carry = tmp / 10; //进位 res.append(tmp % 10); i--; j--; } if (carry == 1) res.append(1); return res.reverse().toString(); } } ``` ### [92. 反转链表 II](https://leetcode-cn.com/problems/reverse-linked-list-ii/) 难度中等1185 给你单链表的头指针 `head` 和两个整数 `left` 和 `right` ,其中 `left <= right` 。请你反转从位置 `left` 到位置 `right` 的链表节点,返回 **反转后的链表** 。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2021/02/19/rev2ex2.jpg) ``` 输入:head = [1,2,3,4,5], left = 2, right = 4 输出:[1,4,3,2,5] ``` **示例 2:** ``` 输入:head = [5], left = 1, right = 1 输出:[5] ``` **提示:** - 链表中节点数目为 `n` - `1 <= n <= 500` - `-500 <= Node.val <= 500` - `1 <= left <= right <= n` **进阶:** 你可以使用一趟扫描完成反转吗? **算法步骤:** 第 1 步:先将待反转的区域反转; 第 2 步:把 pre 的 next 指针指向反转以后的链表头节点,把反转以后的链表的尾节点的 next 指针指向 succ。 ![image.png](https://pic.leetcode-cn.com/1615105168-ZQRZew-image.png) **方法一:定位指针 + 截取 + 翻转 + 拼接** ```java class Solution { public ListNode reverseBetween(ListNode head, int left, int right) { // 因为头节点有可能发生变化,使用虚拟头节点可以避免复杂的分类讨论 ListNode dummyNode = new ListNode(-1); dummyNode.next = head; ListNode pre = dummyNode; // 第 1 步:从虚拟头节点走 left - 1 步,来到 left 节点的前一个节点 // 建议写在 for 循环里,语义清晰 for (int i = 0; i < left - 1; i++) { pre = pre.next; } // 第 2 步:从 pre 再走 right - left + 1 步,来到 right 节点 ListNode rightNode = pre; for (int i = 0; i < right - left + 1; i++) { rightNode = rightNode.next; } // 第 3 步:切断出一个子链表(截取链表) ListNode leftNode = pre.next; ListNode curr = rightNode.next; // 注意:切断链接 pre.next = null; rightNode.next = null; // 第 4 步:同第 206 题,反转链表的子区间 reverseLinkedList(leftNode); // 第 5 步:接回到原来的链表中 pre.next = rightNode; leftNode.next = curr; return dummyNode.next; } private void reverseLinkedList(ListNode head) { // 也可以使用递归反转一个链表 ListNode pre = null; ListNode cur = head; while (cur != null) { ListNode next = cur.next; cur.next = pre; pre = cur; cur = next; } } } ``` **复杂度分析** - 时间复杂度:O(N)*O*(*N*),其中 N*N* 是链表总节点数。最坏情况下,需要遍历整个链表。 - 空间复杂度:O(1)*O*(1)。只使用到常数个变量。 **方法二:头插法** ### [23. 合并K个升序链表](https://leetcode-cn.com/problems/merge-k-sorted-lists/) 难度困难1805 给你一个链表数组,每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中,返回合并后的链表。 **示例 1:** ``` 输入:lists = [[1,4,5],[1,3,4],[2,6]] 输出:[1,1,2,3,4,4,5,6] 解释:链表数组如下: [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6 ``` **示例 2:** ``` 输入:lists = [] 输出:[] ``` **示例 3:** ``` 输入:lists = [[]] 输出:[] ``` **提示:** - `k == lists.length` - `0 <= k <= 10^4` - `0 <= lists[i].length <= 500` - `-10^4 <= lists[i][j] <= 10^4` - `lists[i]` 按 **升序** 排列 - `lists[i].length` 的总和不超过 `10^4` 通过次数412,375 提交次数728,737 ```java class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists.length == 0){ return null; } //思路:数组横向两两链表合并 int n = lists.length; ListNode ans = null; for(int i = 0; i < n; i++){ ans = mergeLinkedList(ans, lists[i]); } return ans; } //合并两个升序链表 public ListNode mergeLinkedList(ListNode l1, ListNode l2){ //使用哑节点来简化边界条件的处理 ListNode dummy = new ListNode(0); //待插入节点的前驱节点 ListNode prev = dummy; while (l1 != null && l2 != null){ if (l1.val <= l2.val){ prev.next = l1; l1 = l1.next; } else { prev.next = l2; l2 = l2.next; } prev = prev.next; } prev.next = l1 == null ? l2 : l1; return dummy.next; } } ``` ### [142. 环形链表 II](https://leetcode-cn.com/problems/linked-list-cycle-ii/) 难度中等1446 给定一个链表的头节点 `head` ,返回链表开始入环的第一个节点。 *如果链表无环,则返回 `null`。* 如果链表中有某个节点,可以通过连续跟踪 `next` 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 `pos` 来表示链表尾连接到链表中的位置(**索引从 0 开始**)。如果 `pos` 是 `-1`,则在该链表中没有环。**注意:`pos` 不作为参数进行传递**,仅仅是为了标识链表的实际情况。 **不允许修改** 链表。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist.png) ``` 输入:head = [3,2,0,-4], pos = 1 输出:返回索引为 1 的链表节点 解释:链表中有一个环,其尾部连接到第二个节点。 ``` **示例 2:** ![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist_test2.png) ``` 输入:head = [1,2], pos = 0 输出:返回索引为 0 的链表节点 解释:链表中有一个环,其尾部连接到第一个节点。 ``` **示例 3:** ![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist_test3.png) ``` 输入:head = [1], pos = -1 输出:返回 null 解释:链表中没有环。 ``` **提示:** - 链表中节点的数目范围在范围 `[0, 104]` 内 - `-105 <= Node.val <= 105` - `pos` 的值为 `-1` 或者链表中的一个有效索引 **进阶:**你是否可以使用 `O(1)` 空间解决此题? **方法一:Set判重** ```java public class Solution { public ListNode detectCycle(ListNode head) { Set set = new HashSet<>(); while(head != null){ if (set.contains(head)){ return head; } set.add(head); head = head.next; } return null; } } ``` **方法二:快慢指针** ```java ``` ### [54. 螺旋矩阵](https://leetcode-cn.com/problems/spiral-matrix/) 难度中等1017 给你一个 `m` 行 `n` 列的矩阵 `matrix` ,请按照 **顺时针螺旋顺序** ,返回矩阵中的所有元素。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2020/11/13/spiral1.jpg) ``` 输入:matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出:[1,2,3,6,9,8,7,4,5] ``` **示例 2:** ![img](https://assets.leetcode.com/uploads/2020/11/13/spiral.jpg) ``` 输入:matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 输出:[1,2,3,4,8,12,11,10,9,5,6,7] ``` **提示:** - `m == matrix.length` - `n == matrix[i].length` - `1 <= m, n <= 10` - `-100 <= matrix[i][j] <= 100` 通过次数235,283 提交次数485,236 ```java class Solution { public List spiralOrder(int[][] matrix) { //m表示多少行,n表示多少列 int m = matrix.length, n = matrix[0].length; //l:表示左边界 r:表示又边界 t:表示上边界 b:表示右边界 int l = 0, r = n - 1, t = 0, b = m - 1; int num = 1, tar = m * n; List res = new ArrayList<>(); while(num <= tar){ //1、从左到右 for(int i = l; i <= r && num <= tar; i++){ res.add(matrix[t][i]); num++; } t++; //2、从上到下 for(int i = t; i <= b && num <= tar; i++){ res.add(matrix[i][r]); num++; } r--; //3、从右到左 for(int i = r; i >= l && num <= tar; i--){ res.add(matrix[b][i]); num++; } b--; //4、从下到上 for(int i = b; i >= t && num <= tar; i--){ res.add(matrix[i][l]); num++; } l++; } return res; } } ``` 复杂度分析 时间复杂度:O(mn),其中 mm 和 nn 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。 空间复杂度:O(1) #### [59. 螺旋矩阵 II](https://leetcode-cn.com/problems/spiral-matrix-ii/) 难度中等631 给你一个正整数 `n` ,生成一个包含 `1` 到 `n2` 所有元素,且元素按顺时针顺序螺旋排列的 `n x n` 正方形矩阵 `matrix` 。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2020/11/13/spiraln.jpg) ``` 输入:n = 3 输出:[[1,2,3],[8,9,4],[7,6,5]] ``` **示例 2:** ``` 输入:n = 1 输出:[[1]] ``` **提示:** - `1 <= n <= 20` ![image-20220316194932379](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220316194932379.png) ```java class Solution { public int[][] generateMatrix(int n) { int l = 0, r = n - 1, t = 0, b = n - 1; int num = 1, tar = n * n; int[][] arr = new int[n][n]; while(num <= tar){ //从左到右 for(int i = l; i <= r; i++){ arr[l][i] = num++; } t++; //从上到下 for(int i = t; i <= b; i++){ arr[i][r] = num++; } r--; //从右到左 for(int i = r; i >= l; i--){ arr[b][i] = num++; } b--; //从下到上 for(int i = b; i >= t; i--){ arr[i][l] = num++; } l++; } return arr; } } ``` ### [300. 最长递增子序列](https://leetcode-cn.com/problems/longest-increasing-subsequence/) 难度中等2316 给你一个整数数组 `nums` ,找到其中最长严格递增子序列的长度。 **子序列** 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,`[3,6,2,7]` 是数组 `[0,3,1,6,2,2,7]` 的子序列。 **示例 1:** ``` 输入:nums = [10,9,2,5,3,7,101,18] 输出:4 解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。 ``` **示例 2:** ``` 输入:nums = [0,1,0,3,2,3] 输出:4 ``` **示例 3:** ``` 输入:nums = [7,7,7,7,7,7,7] 输出:1 ``` **提示:** - `1 <= nums.length <= 2500` - `-104 <= nums[i] <= 104` **进阶:** - 你能将算法的时间复杂度降低到 `O(n log(n))` 吗? **方法一:动态规划** ![image-20220316202957692](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220316202957692.png) ```java class Solution { public int lengthOfLIS(int[] nums) { int n = nums.length; int res = 0; //1、状态定义:dp[i]表示以nums[i]结尾的最长递增子序列的长度 int[] dp = new int[n]; //2、状态初始化 Arrays.fill(dp, 1); //3、状态转移方程 for(int i = 0; i < n; i++){ for(int j = 0; j < i; j++){ if (nums[j] < nums[i]){ dp[i] = Math.max(dp[i], dp[j] + 1); } } res = Math.max(res, dp[i]); } //4、返回所需要的状态 return res; } } ``` 复杂度分析: 时间复杂度 O(N^2),遍历计算 dp列表需 O(N),计算每个 dp[i]需 O(N)。 空间复杂度 O(N): dp 列表占用线性大小额外空间。 **方法二:动态规划 + 二分查找** ### [704. 二分查找](https://leetcode-cn.com/problems/binary-search/) 难度简单710 给定一个 `n` 个元素有序的(升序)整型数组 `nums` 和一个目标值 `target` ,写一个函数搜索 `nums` 中的 `target`,如果目标值存在返回下标,否则返回 `-1`。 **示例 1:** ``` 输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4 ``` **示例 2:** ``` 输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1 ``` **提示:** 1. 你可以假设 `nums` 中的所有元素是不重复的。 2. `n` 将在 `[1, 10000]`之间。 3. `nums` 的每个元素都将在 `[-9999, 9999]`之间。 ```java class Solution { public int search(int[] nums, int target) { int n = nums.length; int left = 0, right = n - 1; //二分查找只有一个思想,那就是:逐步缩小搜搜空间 //写成 while(left < right) ,退出循环的时候有 left == right 成立,好处是:不用判断应该返回 left 还是 right; while(left < right){//上限和下限仅仅代表取到的范围,不表示左闭右开 int mid = left + (right - left) / 2; //只把区间分为两部分 if (nums[mid] < target){ left = mid + 1; }else { right = mid; } } //如果可以确定区间 [left..right] 一定有解,直接返回 left 就可以,否则还需要对 left 这个位置单独做一次判断; if (nums[left] == target){ return left; } else { return -1; } } } class Solution { public int search(int[] nums, int target) { int n = nums.length; int left = 0, right = n - 1; //二分查找只有一个思想,那就是:逐步缩小搜搜空间 //写成 while(left < right) ,退出循环的时候有 left == right 成立,好处是:不用判断应该返回 left 还是 right; while(left < right){//上限和下限仅仅代表取到的范围,不表示左闭右开 int mid = left + (right - left + 1) / 2; //只把区间分为两部分 if (nums[mid] <= target){ left = mid; }else { right = mid - 1; } } //如果可以确定区间 [left..right] 一定有解,直接返回 left 就可以,否则还需要对 left 这个位置单独做一次判断; if (nums[left] == target){ return left; } else { return -1; } } } class Solution { public int search(int[] nums, int target) { int n = nums.length; int left = 0, right = n - 1; while(left <= right){ int mid = left + (right - left) / 2; if (target == nums[mid]){ return mid; } else if (target < nums[mid]){ right = mid - 1; } else { left = mid + 1; } } return -1; } } ``` **复杂度分析** - 时间复杂度:O*(log*n),其中 n 是数组的长度。 - 空间复杂度:O(1)。 ### [42. 接雨水](https://leetcode-cn.com/problems/trapping-rain-water/) 难度困难3230 给定 `n` 个非负整数表示每个宽度为 `1` 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 **示例 1:** ![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/10/22/rainwatertrap.png) ``` 输入:height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出:6 解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 ``` **示例 2:** ``` 输入:height = [4,2,0,3,2,5] 输出:9 ``` **提示:** - `n == height.length` - `1 <= n <= 2 * 104` - `0 <= height[i] <= 105` **方法一:暴力** ![image-20220318112613914](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220318112613914.png) ```java class Solution { public int trap(int[] height) { int n = height.length; int ans = 0; for (int i = 1; i < n - 1; i++) { int maxLeft = 0, maxRight = 0; for (int j = 0; j <= i; j++) { maxLeft = Math.max(maxLeft, height[j]); } for (int j = i; j < n; j++) { maxRight = Math.max(maxRight, height[j]); } ans += Math.min(maxLeft, maxRight) - height[i]; } return ans; } } ``` **复杂性分析** - 时间复杂度: O(n^2)。数组中的每个元素都需要向左向右扫描。 - 空间复杂度 O(1) 的额外空间。 **方法二:动态规划** ![image-20220318155604120](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220318155604120.png) ```java class Solution { public int trap(int[] height) { int n = height.length; if (n == 0) { return 0; } int[] leftMax = new int[n]; leftMax[0] = height[0]; for (int i = 1; i < n; ++i) { leftMax[i] = Math.max(leftMax[i - 1], height[i]); } int[] rightMax = new int[n]; rightMax[n - 1] = height[n - 1]; for (int i = n - 2; i >= 0; --i) { rightMax[i] = Math.max(rightMax[i + 1], height[i]); } int ans = 0; for (int i = 0; i < n; ++i) { ans += Math.min(leftMax[i], rightMax[i]) - height[i]; } return ans; } } ``` **方法二:双指针** ```java class Solution { public int trap(int[] height) { int ans = 0; int left = 0, right = height.length - 1; int leftMax = 0, rightMax = 0; //从数组左右两边开始同时接水 //不需要相等,相等时,同时指向最大值,在最高点不会有雨水的 while (left < right){ leftMax = Math.max(leftMax, height[left]); rightMax = Math.max(rightMax, height[right]); if (leftMax < rightMax){//说明left左边的最大值小于其右边的最大值 ans += leftMax - height[left]; left++; } else {//说明right右边的最大值小于其左边的最大值 ans += rightMax - height[right]; right--; } } return ans; } } ``` ### [94. 二叉树的中序遍历](https://leetcode-cn.com/problems/binary-tree-inorder-traversal/) 难度简单1314 给定一个二叉树的根节点 `root` ,返回它的 **中序** 遍历。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2020/09/15/inorder_1.jpg) ``` 输入:root = [1,null,2,3] 输出:[1,3,2] ``` **示例 2:** ``` 输入:root = [] 输出:[] ``` **示例 3:** ``` 输入:root = [1] 输出:[1] ``` **示例 4:** ![img](https://assets.leetcode.com/uploads/2020/09/15/inorder_5.jpg) ``` 输入:root = [1,2] 输出:[2,1] ``` **示例 5:** ![img](https://assets.leetcode.com/uploads/2020/09/15/inorder_4.jpg) ``` 输入:root = [1,null,2] 输出:[1,2] ``` **提示:** - 树中节点数目在范围 `[0, 100]` 内 - `-100 <= Node.val <= 100` **进阶:** 递归算法很简单,你可以通过迭代算法完成吗? **方法一:递归法** ```java class Solution { List res = new ArrayList<>(); public List inorderTraversal(TreeNode root) { //1、递归终止条件 if (root == null) return res; //2、中序遍历框架 inorderTraversal(root.left); res.add(root.val); //3、递归主体 inorderTraversal(root.right); //4、返回值 return res; } } ``` 复杂度分析 时间复杂度:O(n),其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。 空间复杂度:O(logn)或者O(n)。空间复杂度取决于栈深度,而栈深度在二叉树为一条链的情况下会达到 O(n)的级别。 **方法二:迭代法** ```java class Solution { public List inorderTraversal(TreeNode root) { List res = new ArrayList<>();//res集合用于存储结果 if (root == null) return res; Deque stack = new LinkedList<>(); //stack用于维护一个栈 TreeNode node = root; while(!stack.isEmpty() || node != null){ while(node != null){ stack.push(node); node = node.left; } node = stack.pop(); res.add(node.val); node = node.right; } return res; } } ``` 复杂度分析 时间复杂度:O(n),其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。 空间复杂度:O(logn)或者O(n)。空间复杂度取决于栈深度,而栈深度在二叉树为一条链的情况下会达到 O(n)的级别。 ### [232. 用栈实现队列](https://leetcode-cn.com/problems/implement-queue-using-stacks/) 难度简单593 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(`push`、`pop`、`peek`、`empty`): 实现 `MyQueue` 类: - `void push(int x)` 将元素 x 推到队列的末尾 - `int pop()` 从队列的开头移除并返回元素 - `int peek()` 返回队列开头的元素 - `boolean empty()` 如果队列为空,返回 `true` ;否则,返回 `false` **说明:** - 你 **只能** 使用标准的栈操作 —— 也就是只有 `push to top`, `peek/pop from top`, `size`, 和 `is empty` 操作是合法的。 - 你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。 **示例 1:** ``` 输入: ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []] 输出: [null, null, null, 1, 1, false] 解释: MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false ``` **提示:** - `1 <= x <= 9` - 最多调用 `100` 次 `push`、`pop`、`peek` 和 `empty` - 假设所有操作都是有效的 (例如,一个空的队列不会调用 `pop` 或者 `peek` 操作) **进阶:** - 你能否实现每个操作均摊时间复杂度为 `O(1)` 的队列?换句话说,执行 `n` 个操作的总时间复杂度为 `O(n)` ,即使其中一个操作可能花费较长时间。 ### [143. 重排链表](https://leetcode-cn.com/problems/reorder-list/) 难度中等826 给定一个单链表 `L` 的头节点 `head` ,单链表 `L` 表示为: ``` L0 → L1 → … → Ln - 1 → Ln ``` 请将其重新排列后变为: ``` L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … ``` 不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。 **示例 1:** ![img](https://pic.leetcode-cn.com/1626420311-PkUiGI-image.png) ``` 输入:head = [1,2,3,4] 输出:[1,4,2,3] ``` **示例 2:** ![img](https://pic.leetcode-cn.com/1626420320-YUiulT-image.png) ``` 输入:head = [1,2,3,4,5] 输出:[1,5,2,4,3] ``` **提示:** - 链表的长度范围为 `[1, 5 * 104]` - `1 <= node.val <= 1000` **方法一:三步走:寻找链表中间节点 + 反转链表 + 合并链表** ```java class Solution { public void reorderList(ListNode head) { if(head == null || head.next == null){ return; } ListNode midNode = middleNode(head); ListNode l1 = head, l2 = midNode.next; //这里必须断开,否则会出现环 midNode.next = null; l2 = reverse(l2); merge(l1, l2); } //1、寻找链表中间节点 public ListNode middleNode(ListNode head){ if (head == null) return head; ListNode slow = head; ListNode fast = head; while (fast.next != null && fast.next.next != null){ slow = slow.next; fast = fast.next.next; } return slow; } //2、反转链表 public ListNode reverse(ListNode head){ ListNode prev = null; ListNode curr = head; while(curr != null){ ListNode temp = curr.next; curr.next = prev; prev = curr; curr = temp; } return prev; } //3、合并链表 public void merge(ListNode l1, ListNode l2){ //l1和l2只相差一个节点 while (l1 != null && l2 != null){ ListNode temp1 = l1.next; l1.next = l2; l1 = temp1; ListNode temp2 = l2.next; l2.next = l1; l2 = temp2; } } } ``` **复杂度分析** - 时间复杂度:O(N)*O*(*N*),其中 N*N* 是链表中的节点数。 - 空间复杂度:O(1)*O*(1)。 **方法二:线性表** 因为链表不支持下标访问,所以我们无法随机访问链表中任意位置的元素。 因此比较容易想到的一个方法是,我们利用线性表存储该链表,然后利用线性表可以下标访问的特点,直接按顺序访问指定元素,重建该链表即可。 ```java class Solution { public void reorderList(ListNode head) { if (head == null) { return; } List list = new ArrayList(); ListNode node = head; while (node != null) { list.add(node); node = node.next; } int i = 0, j = list.size() - 1; while (i < j) { list.get(i).next = list.get(j); i++; if (i == j) { break; } list.get(j).next = list.get(i); j--; } list.get(i).next = null; } } ``` **复杂度分析** - 时间复杂度:O(N)*O*(*N*),其中 N*N* 是链表中的节点数。 - 空间复杂度:O(N)*O*(*N*),其中 N*N* 是链表中的节点数。主要为线性表的开销。 ### [199. 二叉树的右视图](https://leetcode-cn.com/problems/binary-tree-right-side-view/) 难度中等638 给定一个二叉树的 **根节点** `root`,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2021/02/14/tree.jpg) ``` 输入: [1,2,3,null,5,null,4] 输出: [1,3,4] ``` **示例 2:** ``` 输入: [1,null,3] 输出: [1,3] ``` **示例 3:** ``` 输入: [] 输出: [] ``` **提示:** - 二叉树的节点个数的范围是 `[0,100]` - `-100 <= Node.val <= 100` 通过次数182,148 提交次数278,436 请问您在哪类招聘中遇到此题? **方法一:层序遍历** ```java class Solution { public List rightSideView(TreeNode root) { List res = new ArrayList<>(); //res集合用于存储结果 if (root == null) return res; Queue q = new LinkedList<>(); // q用于维护一个队列 q.offer(root); while(!q.isEmpty()){ int size = q.size(); for(int i = 0; i < size; i++){ TreeNode node = q.poll(); if (i == 0){ res.add(node.val); } if (node.right != null) q.offer(node.right); //先入队右子节点 if (node.left != null) q.offer(node.left); //再入队左子节点 } } return res; } } ``` **方法二:DFS** ```java class Solution { List res = new ArrayList<>(); public List rightSideView(TreeNode root) { dfs(root, 0); // 从根节点开始访问,根节点深度是0 return res; } public void dfs(TreeNode root, int depth){ //base case if (root == null) return ; //root递归主体 // 如果当前节点所在深度还没有出现在res里,说明在该深度下当前节点是第一个被访问的节点,因此将当前节点加入res中。 if (depth == res.size()){ res.add(root.val); } // 先访问 当前节点,再递归地访问 右子树 和 左子树。 dfs(root.right, depth + 1); dfs(root.left, depth + 1); } } ``` 时间复杂度: O(N),每个节点都访问了 1 次。 空间复杂度: O(N),因为这不是一棵平衡二叉树,二叉树的深度最少是 logN, 最坏的情况下会退化成一条链表,深度就是 NN,因此递归时使用的栈空间是 O(N)的。 ### [124. 二叉树中的最大路径和](https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/) 难度困难1471 **路径** 被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。同一个节点在一条路径序列中 **至多出现一次** 。该路径 **至少包含一个** 节点,且不一定经过根节点。 **路径和** 是路径中各节点值的总和。 给你一个二叉树的根节点 `root` ,返回其 **最大路径和** 。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2020/10/13/exx1.jpg) ``` 输入:root = [1,2,3] 输出:6 解释:最优路径是 2 -> 1 -> 3 ,路径和为 2 + 1 + 3 = 6 ``` **示例 2:** ![img](https://assets.leetcode.com/uploads/2020/10/13/exx2.jpg) ``` 输入:root = [-10,9,20,null,null,15,7] 输出:42 解释:最优路径是 15 -> 20 -> 7 ,路径和为 15 + 20 + 7 = 42 ``` **提示:** - 树中节点数目范围是 `[1, 3 * 104]` - `-1000 <= Node.val <= 1000` ### [70. 爬楼梯](https://leetcode-cn.com/problems/climbing-stairs/) 难度简单2260 假设你正在爬楼梯。需要 `n` 阶你才能到达楼顶。 每次你可以爬 `1` 或 `2` 个台阶。你有多少种不同的方法可以爬到楼顶呢? **示例 1:** ``` 输入:n = 2 输出:2 解释:有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶 ``` **示例 2:** ``` 输入:n = 3 输出:3 解释:有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶 ``` **提示:** - `1 <= n <= 45` 通过次数741,797 提交次数1,386,351 ### [56. 合并区间](https://leetcode-cn.com/problems/merge-intervals/) 难度中等1375 以数组 `intervals` 表示若干个区间的集合,其中单个区间为 `intervals[i] = [starti, endi]` 。请你合并所有重叠的区间,并返回 *一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间* 。 **示例 1:** ``` 输入:intervals = [[1,3],[2,6],[8,10],[15,18]] 输出:[[1,6],[8,10],[15,18]] 解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. ``` **示例 2:** ``` 输入:intervals = [[1,4],[4,5]] 输出:[[1,5]] 解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。 ``` **提示:** - `1 <= intervals.length <= 104` - `intervals[i].length == 2` - `0 <= starti <= endi <= 104` ### [19. 删除链表的倒数第 N 个结点](https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/) 难度中等1867 给你一个链表,删除链表的倒数第 `n` 个结点,并且返回链表的头结点。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2020/10/03/remove_ex1.jpg) ``` 输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5] ``` **示例 2:** ``` 输入:head = [1], n = 1 输出:[] ``` **示例 3:** ``` 输入:head = [1,2], n = 1 输出:[1] ``` **提示:** - 链表中结点的数目为 `sz` - `1 <= sz <= 30` - `0 <= Node.val <= 100` - `1 <= n <= sz` **进阶:**你能尝试使用一趟扫描实现吗? **方法一:用栈模拟** ```java class Solution { //本质还是找到待删除节点的前驱节点 public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(-1, head); ListNode prev = dummy; Deque stack = new LinkedList<>(); while(prev != null){//为了防止删除head节点,所以将dummy节点也压入栈中 stack.push(prev); prev = prev.next; } for (int i = 0; i < n; i++){ stack.pop(); } prev = stack.peek(); prev.next = prev.next.next; return dummy.next; } } ``` **方法二:遍历链表长度** ```java class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(-1, head); ListNode prev = dummy; //1、获取链表长度 int len = length(head); //2、找到待删除节点的前一个节点 for(int i = 0; i < len - n; i++){ prev = prev.next; } prev.next = prev.next.next; return dummy.next; } public int length(ListNode head){ int len = 0; while(head != null){ len++; head = head.next; } return len; } } ``` ### [剑指 Offer 22. 链表中倒数第k个节点](https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/) 难度简单336 输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。 例如,一个链表有 `6` 个节点,从头节点开始,它们的值依次是 `1、2、3、4、5、6`。这个链表的倒数第 `3` 个节点是值为 `4` 的节点。 **示例:** ``` 给定一个链表: 1->2->3->4->5, 和 k = 2. 返回链表 4->5. ``` 通过次数321,436 提交次数401,051 **方法一:快慢指针** ![image-20220316222636149](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220316222636149.png) ```java class Solution { public ListNode getKthFromEnd(ListNode head, int k) { ListNode former = head, latter = head; for(int i = 0; i < k; i++) former = former.next; while(former != null) { former = former.next; latter = latter.next; } return latter; } } ``` **方法二:遍历链表长度** ```java class Solution { public ListNode getKthFromEnd(ListNode head, int k) { ListNode dummy = new ListNode(-1, head); ListNode prev = dummy; //1、获取链表长度 int len = length(head); //2、找到待返回节点的前一个节点 for(int i = 0; i < len - k; i++){ prev = prev.next; } return prev.next; } public int length(ListNode head){ int len = 0; while(head != null){ len++; head = head.next; } return len; } } ``` **方法三:用栈模拟** ```java class Solution { public ListNode getKthFromEnd(ListNode head, int k) { ListNode dummy = new ListNode(-1, head); ListNode prev = dummy; Deque stack = new LinkedList<>(); while(prev != null){//为了防止返回head节点,所以将dummy节点也压入栈中 stack.push(prev); prev = prev.next; } for (int i = 0; i < k; i++){ stack.pop(); } prev = stack.peek(); return prev.next; } } ``` ### [69. x 的平方根 ](https://leetcode-cn.com/problems/sqrtx/) 难度简单927 给你一个非负整数 `x` ,计算并返回 `x` 的 **算术平方根** 。 由于返回类型是整数,结果只保留 **整数部分** ,小数部分将被 **舍去 。** **注意:**不允许使用任何内置指数函数和算符,例如 `pow(x, 0.5)` 或者 `x ** 0.5` 。 **示例 1:** ``` 输入:x = 4 输出:2 ``` **示例 2:** ``` 输入:x = 8 输出:2 解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。 ``` **提示:** - `0 <= x <= 231 - 1` 通过次数482,072 提交次数1,240,020 **方法一:二分** ```java public class Solution { /** * * @param x int整型 * @return int整型 */ public int sqrt (int x) { // write code here if(x < 2){ return x; } int left = 0, right = x / 2; while(left < right){ int mid = left + (right - left + 1) / 2; if (mid > x / mid){ right = mid - 1; } else { left = mid; } } return left; } } ``` # 第二部分:二分专题 https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/ 所有二分题目,都是采用两变夹的方式,每一轮把待搜索区间分成两个部分,排除掉一定不是答案的区间,最后左右指针重合的地方就是我们要找的元素 ![image-20220320085023097](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220320085023097.png) ## 题型一:二分求下标(在数组中查找符合条件的元素的下标) 说明: 第 704 题:二分查找的最原始问题,使用两边夹的二分查找方法需要后处理(退出循环以后,还需要判断 left 或 right 位置的值是不是问题的答案); 第 34 题、第 35 题:需要明白这一类问题的共同特点,请见 这里; 第 300 题:特别经典的一道「动态规划」,二分查找的思路基于「动态规划」的状态定义得到,代码很像第 35 题; 第 658 题:这个问题二分的写法需要做复杂的分类讨论,可以放在以后做; 第 4 题:二分查找里最难的问题,重点在于理解:① 为什么是在短数组里找边界;② 深刻理解搜索边界的意义。 ![image-20220320083845017](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220320083845017.png) #### [704. 二分查找](https://leetcode-cn.com/problems/binary-search/) 难度简单716 给定一个 `n` 个元素有序的(升序)整型数组 `nums` 和一个目标值 `target` ,写一个函数搜索 `nums` 中的 `target`,如果目标值存在返回下标,否则返回 `-1`。 **示例 1:** ``` 输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4 ``` **示例 2:** ``` 输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1 ``` **提示:** 1. 你可以假设 `nums` 中的所有元素是不重复的。 2. `n` 将在 `[1, 10000]`之间。 3. `nums` 的每个元素都将在 `[-9999, 9999]`之间。` ```java class Solution { public int search(int[] nums, int target) { int n = nums.length; int left = 0, right = n - 1; //二分查找只有一个思想,那就是:逐步缩小搜搜空间 //写成 while(left < right) ,退出循环的时候有 left == right 成立,好处是:不用判断应该返回 left 还是 right; while(left < right){//上限和下限仅仅代表取到的范围,不表示左闭右开 int mid = left + (right - left) / 2; //只把区间分为两部分 if (nums[mid] < target){ left = mid + 1; }else { right = mid; } } //如果可以确定区间 [left..right] 一定有解,直接返回 left 就可以,否则还需要对 left 这个位置单独做一次判断; if (nums[left] == target){ return left; } else { return -1; } } } class Solution { public int search(int[] nums, int target) { int n = nums.length; int left = 0, right = n - 1; //二分查找只有一个思想,那就是:逐步缩小搜搜空间 //写成 while(left < right) ,退出循环的时候有 left == right 成立,好处是:不用判断应该返回 left 还是 right; while(left < right){//上限和下限仅仅代表取到的范围,不表示左闭右开 int mid = left + (right - left + 1) / 2; //只把区间分为两部分 if (nums[mid] <= target){ left = mid; }else { right = mid - 1; } } //如果可以确定区间 [left..right] 一定有解,直接返回 left 就可以,否则还需要对 left 这个位置单独做一次判断; if (nums[left] == target){ return left; } else { return -1; } } } class Solution { public int search(int[] nums, int target) { int n = nums.length; int left = 0, right = n - 1; while(left <= right){ int mid = left + (right - left) / 2; if (target == nums[mid]){ return mid; } else if (target < nums[mid]){ right = mid - 1; } else { left = mid + 1; } } return -1; } } ``` #### [34. 在排序数组中查找元素的第一个和最后一个位置](https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/) 难度中等1544 给定一个按照升序排列的整数数组 `nums`,和一个目标值 `target`。找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 `target`,返回 `[-1, -1]`。 **进阶:** - 你可以设计并实现时间复杂度为 `O(log n)` 的算法解决此问题吗? **示例 1:** ``` 输入:nums = [5,7,7,8,8,10], target = 8 输出:[3,4] ``` **示例 2:** ``` 输入:nums = [5,7,7,8,8,10], target = 6 输出:[-1,-1] ``` **示例 3:** ``` 输入:nums = [], target = 0 输出:[-1,-1] ``` **提示:** - `0 <= nums.length <= 105` - `-109 <= nums[i] <= 109` - `nums` 是一个非递减数组 - `-109 <= target <= 109` 题解 https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/tu-jie-er-fen-zui-qing-xi-yi-dong-de-jia-ddvc/ img 两次二分,第一次二分查找第一个>=target的位置,第二次二分查找最后一个<=target的位置。查找成功则返回两个位置下标,否则返回[-1,-1][−1,−1]。 ```java //第一种思路 class Solution { public int[] searchRange(int[] nums, int target) { if (nums.length == 0) return new int[]{-1, -1}; int left = 0, right = nums.length - 1; //二分范围 while (left < right) //查找元素的开始位置 { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else { right = mid; } } if (nums[right] != target) return new int[]{-1, -1}; //查找失败 int L = right; left = 0; right = nums.length - 1; //二分范围 while (left < right) //查找target的最后结束位置 { int mid = left + (right - left) / 2 + 1; if (nums[mid] <= target){ left = mid; } else { //等号不能放这里,因为是查找target的最后结束位置,放在这里无法控制右边界 right = mid - 1; } } return new int[]{L, right}; } } //第二种思路 class Solution { public int[] searchRange(int[] nums, int target) { int n = nums.length; if (n == 0) return new int[]{-1, -1}; int left = 0, right = n - 1; //二分范围,查找第一个大于等于target的元素下标(注意在数组下标范围内) while (left < right){ int mid = left + (right - left) / 2; if (nums[mid] < target){ left = mid + 1; } else { right = mid; } } if (nums[right] != target){ //如果不相等,说明数组中不存在target return new int[]{-1, -1}; } //走到这说明数组中一定有目标值 int L = right; left = 0; //二分范围,查找第一个大于target的元素下标(因为已经确定target存在,注意范围在0~n) right = n; while (left < right){ int mid = left + (right - left) / 2; if (nums[mid] <= target){ //nums[mid] == target时,继续向右找 left = mid + 1; } else { right = mid; } } return new int[]{L, right - 1}; } } //第三种思路 class Solution { public int[] searchRange(int[] nums, int target) { int n = nums.length; if (n == 0) { return new int[]{-1, -1}; } int left = 0, right = n - 1; while(left < right){ int mid = left + (right - left) / 2; if (nums[mid] < target){ left = mid + 1; } else { right = mid; } } if (nums[right] == target){//如果存在target int last = left; while(last < n && nums[last] == nums[left]){ last++; } last--; return new int[]{left, last}; } else { return new int[]{-1, -1}; } } } ``` #### [35. 搜索插入位置](https://leetcode-cn.com/problems/search-insert-position/) 难度简单1424 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 `O(log n)` 的算法。 **示例 1:** ``` 输入: nums = [1,3,5,6], target = 5 输出: 2 ``` **示例 2:** ``` 输入: nums = [1,3,5,6], target = 2 输出: 1 ``` **示例 3:** ``` 输入: nums = [1,3,5,6], target = 7 输出: 4 ``` **示例 4:** ``` 输入: nums = [1,3,5,6], target = 0 输出: 0 ``` **示例 5:** ``` 输入: nums = [1], target = 0 输出: 0 ``` **提示:** - `1 <= nums.length <= 104` - `-104 <= nums[i] <= 104` - `nums` 为**无重复元素**的**升序**排列数组 - `-104 <= target <= 104` ```java public class Solution { //返回第一个大于等于target的数组元素下标 public int searchInsert(int[] nums, int target) { int len = nums.length; // 特殊判断 if (nums[len - 1] < target) { return len; } // 程序走到这里一定有 nums[len - 1] >= target,插入位置在区间 [0..len - 1] int left = 0; int right = len - 1; // 在区间 nums[left..right] 里查找第 1 个大于等于 target 的元素的下标 while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < target){ // 下一轮搜索的区间是 [mid + 1..right] left = mid + 1; } else { // 下一轮搜索的区间是 [left..mid] right = mid; } } return left; } } //既然 len 也有可能是答案,可以在初始化的时候,把 right 设置成 len,在一开始的时候就不需要特殊判断了。 public class Solution { public int searchInsert(int[] nums, int target) { int len = nums.length; int left = 0; int right = len; // 在区间 nums[left..right] 里查找第 1 个大于等于 target 的元素的下标 while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < target){ // 下一轮搜索的区间是 [mid + 1..right] left = mid + 1; } else { // 下一轮搜索的区间是 [left..mid] right = mid; } } return left; } } //以下代码不适用 class Solution { public int searchInsert(int[] nums, int target) { int n = nums.length; int left = 0, right = n; //返回第一个大于等于target的数组元素下标 while (left < right){ int mid = left + (right - left + 1) / 2; if (nums[mid] <= target){ left = mid; } else { right = mid; //不适用,两个区间有重合 } } return left; } } ``` #### [300. 最长递增子序列](https://leetcode-cn.com/problems/longest-increasing-subsequence/) 难度中等2327 给你一个整数数组 `nums` ,找到其中最长严格递增子序列的长度。 **子序列** 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,`[3,6,2,7]` 是数组 `[0,3,1,6,2,2,7]` 的子序列。 **示例 1:** ``` 输入:nums = [10,9,2,5,3,7,101,18] 输出:4 解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。 ``` **示例 2:** ``` 输入:nums = [0,1,0,3,2,3] 输出:4 ``` **示例 3:** ``` 输入:nums = [7,7,7,7,7,7,7] 输出:1 ``` **提示:** - `1 <= nums.length <= 2500` - `-104 <= nums[i] <= 104` **进阶:** - 你能将算法的时间复杂度降低到 `O(n log(n))` 吗? **方法一:动态规划** image-20220322100840373 ```java class Solution { public int lengthOfLIS(int[] nums) { int n = nums.length; int res = 0; //1、状态定义:dp[i]表示以nums[i]结尾的递增子序列的长度 int[] dp = new int[n]; //2、状态初始化 Arrays.fill(dp, 1); //3、状态转移方程 for(int i = 0; i < n; i++){ for(int j = 0; j < i; j++){ if (nums[j] < nums[i]){ dp[i] = Math.max(dp[i], dp[j] + 1); } } res = Math.max(res, dp[i]); } return res; } } ``` 复杂度分析: 时间复杂度:O(N^2),这里 N 是数组的长度,我们写了两个 for 循环,每个 for 循环的时间复杂度都是线性的; 空间复杂度:O(N),要使用和输入数组长度相等的状态数组,因此空间复杂度是 O(N)。 **方法二:贪心 + 二分** ```java ``` #### [611. 有效三角形的个数(类比三数之和)](https://leetcode-cn.com/problems/valid-triangle-number/) 难度中等357 给定一个包含非负整数的数组 `nums` ,返回其中可以组成三角形三条边的三元组个数。 **示例 1:** ``` 输入: nums = [2,2,3,4] 输出: 3 解释:有效的组合是: 2,3,4 (使用第一个 2) 2,3,4 (使用第二个 2) 2,2,3 ``` **示例 2:** ``` 输入: nums = [4,2,3,4] 输出: 4 ``` **提示:** - `1 <= nums.length <= 1000` - `0 <= nums[i] <= 1000` **方法一:暴力** ```java class Solution { public int triangleNumber(int[] nums) { int n = nums.length; if (n < 3) return 0; Arrays.sort(nums); int ans = 0; for (int i = 0; i < n - 2; i++) { for (int j = i + 1; j < n - 1; j++) { for (int k = j + 1; k < n; k++) { if (nums[i] + nums[j] > nums[k]){ ans++; } } } } return ans; } ``` **方法二:排序 + 二分** https://leetcode-cn.com/problems/valid-triangle-number/solution/er-fen-cha-zhao-python-dai-ma-java-dai-ma-by-liwei/ ![image-20220322102125056](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220322102125056.png) ```java class Solution { public int triangleNumber(int[] nums) { int n = nums.length; if (n < 3) return 0; Arrays.sort(nums); int ans = 0; for (int i = 0; i < n - 2; i++) { for (int j = i + 1; j < n - 1; j++) { //返回第一个大于等于两边之和的元素下标 int left = j + 1, right = n; //因为二分法找到的下标对应元素是第一个不能组成三角形的元素下标,而数组中最后一个元素是可能组成三角形的,所以右侧下标要扩展一位 while (left < right){ int mid = left + (right - left) / 2; int target = nums[i] + nums[j]; if (nums[mid] < target){ left = mid + 1; } else { right = mid; } } ans += right - j - 1; } } return ans; } } ``` ![image-20220320111036539](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220320111036539.png) **方法三:排序 + 双指针(固定最大边,因为最大边是比较对象不能变动)** ```java class Solution { public int triangleNumber(int[] nums) { int n = nums.length; if (n < 3) return 0; Arrays.sort(nums); int ans = 0; //相等于先固定最大的一边 for (int i = n - 1; i >= 2; i--) { int left = 0, right = i - 1; while (left < right){ int sum = nums[left] + nums[right]; if (sum <= nums[i]){ left++; } else{ ans += right - left; right--; } } } return ans; } } ``` #### [658. 找到 K 个最接近的元素](https://leetcode-cn.com/problems/find-k-closest-elements/) 难度中等303 给定一个 **排序好** 的数组 `arr` ,两个整数 `k` 和 `x` ,从数组中找到最靠近 `x`(两数之差最小)的 `k` 个数。返回的结果必须要是按升序排好的。 整数 `a` 比整数 `b` 更接近 `x` 需要满足: - `|a - x| < |b - x|` 或者 - `|a - x| == |b - x|` 且 `a < b` **示例 1:** ``` 输入:arr = [1,2,3,4,5], k = 4, x = 3 输出:[1,2,3,4] ``` **示例 2:** ``` 输入:arr = [1,2,3,4,5], k = 4, x = -1 输出:[1,2,3,4] ``` **提示:** - `1 <= k <= arr.length` - `1 <= arr.length <= 104` - `arr` 按 **升序** 排列 - `-104 <= arr[i], x <= 104` **方法一:双指针** ```java class Solution { public List findClosestElements(int[] arr, int k, int x) { int left = 0, right = arr.length - 1; while (left < right){ if (right - left + 1 == k){ break; } if (Math.abs(arr[left] - x) <= Math.abs(arr[right] - x)){ right--; } else if (Math.abs(arr[left] - x) > Math.abs(arr[right] - x)){ left++; } } List res = new ArrayList<>(); for (int i = left; i <= right; i++) { res.add(arr[i]); } return res; } } ``` **复杂度分析**: - 时间复杂度:O(N),这里 N*N* 是数组的长度。 - 空间复杂度:O(1),只使用了常数个额外的辅助空间。 **方法二:二分** ```java import java.util.ArrayList; import java.util.List; public class Solution { public List findClosestElements(int[] arr, int k, int x) { int size = arr.length; int left = 0; int right = size - k; while (left < right) { // int mid = left + (right - left) / 2; int mid = (left + right) >>> 1; // 尝试从长度为 k + 1 的连续子区间删除一个元素 // 从而定位左区间端点的边界值 if (x - arr[mid] > arr[mid + k] - x) { left = mid + 1; } else { right = mid; } } List res = new ArrayList<>(); for (int i = left; i < left + k; i++) { res.add(arr[i]); } return res; } } ``` 复杂度分析: 时间复杂度:O(logN+K),这里 NN 是数组的长度,使用二分法的时间复杂度是对数级别的。感谢 @a-wen-u 朋友的指正。 空间复杂度:O(1),只使用了常数个额外的辅助空间。 #### [436. 寻找右区间](https://leetcode-cn.com/problems/find-right-interval/) 难度中等100 给你一个区间数组 `intervals` ,其中 `intervals[i] = [starti, endi]` ,且每个 `starti` 都 **不同** 。 区间 `i` 的 **右侧区间** 可以记作区间 `j` ,并满足 `startj`` >= endi` ,且 `startj` **最小化** 。 返回一个由每个区间 `i` 的 **右侧区间** 的最小起始位置组成的数组。如果某个区间 `i` 不存在对应的 **右侧区间** ,则下标 `i` 处的值设为 `-1` 。 **示例 1:** ``` 输入:intervals = [[1,2]] 输出:[-1] 解释:集合中只有一个区间,所以输出-1。 ``` **示例 2:** ``` 输入:intervals = [[3,4],[2,3],[1,2]] 输出:[-1,0,1] 解释:对于 [3,4] ,没有满足条件的“右侧”区间。 对于 [2,3] ,区间[3,4]具有最小的“右”起点; 对于 [1,2] ,区间[2,3]具有最小的“右”起点。 ``` **示例 3:** ``` 输入:intervals = [[1,4],[2,3],[3,4]] 输出:[-1,2,-1] 解释:对于区间 [1,4] 和 [3,4] ,没有满足条件的“右侧”区间。 对于 [2,3] ,区间 [3,4] 有最小的“右”起点。 ``` **提示:** - `1 <= intervals.length <= 2 * 104` - `intervals[i].length == 2` - `-106 <= starti <= endi <= 106` - 每个间隔的起点都 **不相同** **方法一:二分** ```java import java.util.Arrays; import java.util.HashMap; import java.util.Map; public class Solution { public int[] findRightInterval(int[][] intervals) { int len = intervals.length; if (len == 0) { return new int[0]; } // 对原始区间进行预处理,key:起点,value:索引 // 题目中说:你可以假定这些区间都不具有相同的起始点 Map hashMap = new HashMap<>(len); int[] arr = new int[len]; int[] res = new int[len]; for (int i = 0; i < len; i++) { hashMap.put(intervals[i][0], i); arr[i] = intervals[i][0]; } Arrays.sort(arr); for (int i = 0; i < len; i++) { //查找的是大于等于区间右端点的第一个值 int index = binarySearch(arr, intervals[i][1]); if (index == -1) { res[i] = -1; } else { res[i] = hashMap.get(arr[index]); } } return res; } /** * 查找第 1 个大于等于 target 的元素的索引 * * @param arr * @param target * @return */ private int binarySearch(int[] arr, int target) { int len = arr.length; // 特判 if (arr[len - 1] < target) { return -1; } int left = 0; int right = len - 1; while (left < right) { int mid = (left + right) >>> 1; if (arr[mid] < target) { left = mid + 1; } else { right = mid; } } return left; } } ``` #### [1237. 找出给定方程的正整数解](https://leetcode-cn.com/problems/find-positive-integer-solution-for-a-given-equation/) 难度中等54 给你一个函数 `f(x, y)` 和一个目标结果 `z`,函数公式未知,请你计算方程 `f(x,y) == z` 所有可能的正整数 **数对** `x` 和 `y`。满足条件的结果数对可以按任意顺序返回。 尽管函数的具体式子未知,但它是单调递增函数,也就是说: - `f(x, y) < f(x + 1, y)` - `f(x, y) < f(x, y + 1)` 函数接口定义如下: ``` interface CustomFunction { public: // Returns some positive integer f(x, y) for two positive integers x and y based on a formula. int f(int x, int y); }; ``` 你的解决方案将按如下规则进行评判: - 判题程序有一个由 `CustomFunction` 的 `9` 种实现组成的列表,以及一种为特定的 `z` 生成所有有效数对的答案的方法。 - 判题程序接受两个输入:`function_id`(决定使用哪种实现测试你的代码)以及目标结果 `z` 。 - 判题程序将会调用你实现的 `findSolution` 并将你的结果与答案进行比较。 - 如果你的结果与答案相符,那么解决方案将被视作正确答案,即 `Accepted` 。 **示例 1:** ``` 输入:function_id = 1, z = 5 输出:[[1,4],[2,3],[3,2],[4,1]] 解释:function_id = 1 暗含的函数式子为 f(x, y) = x + y 以下 x 和 y 满足 f(x, y) 等于 5: x=1, y=4 -> f(1, 4) = 1 + 4 = 5 x=2, y=3 -> f(2, 3) = 2 + 3 = 5 x=3, y=2 -> f(3, 2) = 3 + 2 = 5 x=4, y=1 -> f(4, 1) = 4 + 1 = 5 ``` **示例 2:** ``` 输入:function_id = 2, z = 5 输出:[[1,5],[5,1]] 解释:function_id = 2 暗含的函数式子为 f(x, y) = x * y 以下 x 和 y 满足 f(x, y) 等于 5: x=1, y=5 -> f(1, 5) = 1 * 5 = 5 x=5, y=1 -> f(5, 1) = 5 * 1 = 5 ``` **提示:** - `1 <= function_id <= 9` - `1 <= z <= 100` - 题目保证 `f(x, y) == z` 的解处于 `1 <= x, y <= 1000` 的范围内。 - 在 `1 <= x, y <= 1000` 的前提下,题目保证 `f(x, y)` 是一个 32 位有符号整数。 **方法一:二分** ```java class Solution { /* 根据单调递增性,可画出类似于如下的矩阵,横向纵向都是递增的 从右上角看类似于一颗二叉搜索树 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 */ public List> findSolution(CustomFunction fun, int z) { List> ans = new ArrayList<>(); int x = 1, y = 1000; // 从右上根节点开始搜索 while (x <= 1000 && y >= 1) {//横纵坐标的取值范围 int f = fun.f(x, y); if (f == z){ ans.add(Arrays.asList(x, y)); x++; y--; } else if (f < z){ x++; } else { y--; } } return ans; } } ``` #### [1300. 转变数组后最接近目标值的数组和](https://leetcode-cn.com/problems/sum-of-mutated-array-closest-to-target/) 难度中等154 给你一个整数数组 `arr` 和一个目标值 `target` ,请你返回一个整数 `value` ,使得将数组中所有大于 `value` 的值变成 `value` 后,数组的和最接近 `target` (最接近表示两者之差的绝对值最小)。 如果有多种使得和最接近 `target` 的方案,请你返回这些整数中的最小值。 请注意,答案不一定是 `arr` 中的数字。 **示例 1:** ``` 输入:arr = [4,9,3], target = 10 输出:3 解释:当选择 value 为 3 时,数组会变成 [3, 3, 3],和为 9 ,这是最接近 target 的方案。 ``` **示例 2:** ``` 输入:arr = [2,3,5], target = 10 输出:5 ``` **示例 3:** ``` 输入:arr = [60864,25176,27249,21296,20204], target = 56803 输出:11361 ``` **提示:** - `1 <= arr.length <= 10^4` - `1 <= arr[i], target <= 10^5` **暂时放弃** #### [4. 寻找两个正序数组的中位数](https://leetcode-cn.com/problems/median-of-two-sorted-arrays/) 难度困难5169 给定两个大小分别为 `m` 和 `n` 的正序(从小到大)数组 `nums1` 和 `nums2`。请你找出并返回这两个正序数组的 **中位数** 。 算法的时间复杂度应该为 `O(log (m+n))` 。 **示例 1:** ``` 输入:nums1 = [1,3], nums2 = [2] 输出:2.00000 解释:合并数组 = [1,2,3] ,中位数 2 ``` **示例 2:** ``` 输入:nums1 = [1,2], nums2 = [3,4] 输出:2.50000 解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5 ``` **提示:** - `nums1.length == m` - `nums2.length == n` - `0 <= m <= 1000` - `0 <= n <= 1000` - `1 <= m + n <= 2000` - `-106 <= nums1[i], nums2[i] <= 106` 方法一:二分 ```java ``` **方法二:合并两个有序数组(时间复杂度O(m + n)不符合要求)** ```java class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int[] temp = mergeSort(nums1, nums2); int n = temp.length; if (n % 2 == 1){ return temp[(n - 1) / 2] * 1.0; } else { return (temp[(n - 1) / 2] + temp[(n - 1) / 2 + 1]) / 2.0; } } //合并两个有序数组 public int[] mergeSort(int[] arr1, int[] arr2){ int m = arr1.length, n = arr2.length; int[] temp = new int[m + n]; int p1 = 0, p2 = 0, k = 0; while (p1 < m && p2 < n){ if (arr1[p1] <= arr2[p2]){ temp[k++] = arr1[p1++]; } else { temp[k++] = arr2[p2++]; } } while (p1 < m) temp[k++] = arr1[p1++]; while (p2 < n) temp[k++] = arr2[p2++]; return temp; } } ``` **方法三:暴力O((m+ n)(log(m +n)))** ```java class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m = nums1.length, n = nums2.length; int[] temp = new int[m + n]; for (int i = 0; i < m; i++) { temp[i] = nums1[i]; } for (int i = m; i < m + n; i++) { temp[i] = nums2[i - m]; } Arrays.sort(temp); n = temp.length; if (n % 2 == 1){ return temp[(n - 1) / 2] * 1.0; } else { return (temp[(n - 1) / 2] + temp[(n - 1) / 2 + 1]) / 2.0; } } } ``` 使用二分查找的前提不一定非要是「有序数组」。旋转有序数组(下表前 4 题)、山脉数组(下表后 2 题)里的查找问题也可以使用「二分查找」。这些问题的解决思路是:利用 局部单调性,逐步缩小搜索区间。 ![image-20220320083911390](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220320083911390.png) #### [33. 搜索旋转排序数组](https://leetcode-cn.com/problems/search-in-rotated-sorted-array/) 难度中等1931 整数数组 `nums` 按升序排列,数组中的值 **互不相同** 。 在传递给函数之前,`nums` 在预先未知的某个下标 `k`(`0 <= k < nums.length`)上进行了 **旋转**,使数组变为 `[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]`(下标 **从 0 开始** 计数)。例如, `[0,1,2,4,5,6,7]` 在下标 `3` 处经旋转后可能变为 `[4,5,6,7,0,1,2]` 。 给你 **旋转后** 的数组 `nums` 和一个整数 `target` ,如果 `nums` 中存在这个目标值 `target` ,则返回它的下标,否则返回 `-1` 。 **示例 1:** ``` 输入:nums = [4,5,6,7,0,1,2], target = 0 输出:4 ``` **示例 2:** ``` 输入:nums = [4,5,6,7,0,1,2], target = 3 输出:-1 ``` **示例 3:** ``` 输入:nums = [1], target = 0 输出:-1 ``` **提示:** - `1 <= nums.length <= 5000` - `-10^4 <= nums[i] <= 10^4` - `nums` 中的每个值都 **独一无二** - 题目数据保证 `nums` 在预先未知的某个下标上进行了旋转 - `-10^4 <= target <= 10^4` **进阶:**你可以设计一个时间复杂度为 `O(log n)` 的解决方案吗? 方法一:二分 ```java //向上取整写法 public class Solution { public int search(int[] nums, int target) { int len = nums.length; if (len == 0) { return -1; } int left = 0; int right = len - 1; while (left < right) { // 根据分支的逻辑将中间数改成上取整 int mid = left + (right - left + 1) / 2; if (nums[mid] < nums[right]) { // 此时 [mid..right] 有序 if (nums[mid] <= target && target <= nums[right]) { // 如果 target 的值落在这个区间里,下一轮搜索区间是 [mid..right],此时设置 left = mid; left = mid; } else { // 否则,下一轮搜索区间是 [left..mid - 1],此时设置 right = mid - 1; right = mid - 1; } } else { // 此时 nums[mid] >= nums[right],注意此时 mid 可能与 right 重合 // 数组前半部分有序,即 [left..mid] 有序,为了与上一个分支的逻辑一致,认为 [left..mid - 1] 有序 if (nums[left] <= target && target <= nums[mid - 1]) { // 如果 target 的值落在区间 [left..mid - 1] 里,设置 right = mid - 1; right = mid - 1; } else { // 否则,下一轮搜索区间是 [mid..right],此时设置 left = mid; left = mid; } // 补充说明:由于中间数上取整,在区间只剩下两个元素的时候,mid 与 right 重合,逻辑走到 else 分支里 // 此时恰好 if 这个分支看到的是 left 和 mid - 1 ,用到的都是 == 号,等价于判断 nums[left] == target // 因此依然可以缩减区间,注意这里 if 里面的 nums[left] <= target && target <= nums[mid - 1] , // 不可以写成 nums[left] <= target && target < nums[mid] } } if (nums[left] == target) { return left; } return -1; } } //向下取整写法 class Solution { public int search(int[] nums, int target) { int n = nums.length; int left = 0, right = n - 1; while (left < right){ int mid = left + (right - left) / 2; if (nums[mid] > nums[left]){ if (target >= nums[left] && target <= nums[mid]){ right = mid; } else { left = mid + 1; } } else { if (target >= nums[mid + 1] && target <= nums[right]){ left = mid + 1; } else { right = mid; } } } if (nums[left] == target){ return left; } else { return -1; } } } ``` #### [81. 搜索旋转排序数组 II](https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/) 难度中等560 已知存在一个按非降序排列的整数数组 `nums` ,数组中的值不必互不相同。 在传递给函数之前,`nums` 在预先未知的某个下标 `k`(`0 <= k < nums.length`)上进行了 **旋转** ,使数组变为 `[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]`(下标 **从 0 开始** 计数)。例如, `[0,1,2,4,4,4,5,6,6,7]` 在下标 `5` 处经旋转后可能变为 `[4,5,6,6,7,0,1,2,4,4]` 。 给你 **旋转后** 的数组 `nums` 和一个整数 `target` ,请你编写一个函数来判断给定的目标值是否存在于数组中。如果 `nums` 中存在这个目标值 `target` ,则返回 `true` ,否则返回 `false` 。 你必须尽可能减少整个操作步骤。 **示例 1:** ``` 输入:nums = [2,5,6,0,0,1,2], target = 0 输出:true ``` **示例 2:** ``` 输入:nums = [2,5,6,0,0,1,2], target = 3 输出:false ``` **提示:** - `1 <= nums.length <= 5000` - `-104 <= nums[i] <= 104` - 题目数据保证 `nums` 在预先未知的某个下标上进行了旋转 - `-104 <= target <= 104` **进阶:** - 这是 [搜索旋转排序数组](https://leetcode-cn.com/problems/search-in-rotated-sorted-array/description/) 的延伸题目,本题中的 `nums` 可能包含重复元素。 - 这会影响到程序的时间复杂度吗?会有怎样的影响,为什么? **方法一:二分** 明确了思路以后,我们就需要确定「有序数组」存在于「原始数组」的哪个子区间里,下面提供了两个比较标准: 二分查找算法看到的中间元素 nums[mid] 的值和左边界 nums[left] 的值比较; 二分查找算法看到的中间元素 nums[mid] 的值和右边界 nums[right] 的值比较。 由这两个比较标准就能写出两版不同的代码。 **情况 1**:二分查找算法看到的中间元素 `nums[mid]` 的值和左边界 `nums[left]` 的值比较 ```java public class Solution { // 中间的数与左边界比较 public boolean search(int[] nums, int target) { int len = nums.length; if (len == 0) { return false; } int left = 0; int right = len - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] > nums[left]) { if (nums[left] <= target && target <= nums[mid]) { // 落在前有序数组里 right = mid; } else { left = mid + 1; } } else if (nums[mid] < nums[left]) { // 让分支和上面分支一样 if (nums[mid] < target && target <= nums[right]) { left = mid + 1; } else { right = mid; } } else { // 要排除掉左边界之前,先看一看左边界可以不可以排除 if (nums[left] == target) { return true; } else { left = left + 1; } } } // 后处理,夹逼以后,还要判断一下,是不是 target return nums[left] == target; } } //向上取整 public class Solution { // 中间的数与右边界比较 public boolean search(int[] nums, int target) { int len = nums.length; int left = 0; int right = len - 1; while (left < right) { int mid = left + (right - left + 1) / 2; if (nums[mid] < nums[right]) { // 具体例子:[10, 11, 4, 5, 6, 7, 8, 9],mid 右边的一定是顺序数组,包括 nums[mid] if (nums[mid] <= target && target <= nums[right]) { left = mid; } else { right = mid - 1; } } else if (nums[mid] > nums[right]) { // 具体例子:[4, 5, 9, 2],mid 左边是一定是顺序数组,包括 nums[mid] if (nums[left] <= target && target < nums[mid]) { right = mid - 1; } else { left = mid; } } else { if (nums[right] == target) { return true; } right = right - 1; } } return nums[left] == target; } } ``` #### [153. 寻找旋转排序数组中的最小值](https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/) 难度中等700 已知一个长度为 `n` 的数组,预先按照升序排列,经由 `1` 到 `n` 次 **旋转** 后,得到输入数组。例如,原数组 `nums = [0,1,2,4,5,6,7]` 在变化后可能得到: - 若旋转 `4` 次,则可以得到 `[4,5,6,7,0,1,2]` - 若旋转 `7` 次,则可以得到 `[0,1,2,4,5,6,7]` 注意,数组 `[a[0], a[1], a[2], ..., a[n-1]]` **旋转一次** 的结果为数组 `[a[n-1], a[0], a[1], a[2], ..., a[n-2]]` 。 给你一个元素值 **互不相同** 的数组 `nums` ,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 **最小元素** 。 你必须设计一个时间复杂度为 `O(log n)` 的算法解决此问题。 **示例 1:** ``` 输入:nums = [3,4,5,1,2] 输出:1 解释:原数组为 [1,2,3,4,5] ,旋转 3 次得到输入数组。 ``` **示例 2:** ``` 输入:nums = [4,5,6,7,0,1,2] 输出:0 解释:原数组为 [0,1,2,4,5,6,7] ,旋转 4 次得到输入数组。 ``` **示例 3:** ``` 输入:nums = [11,13,15,17] 输出:11 解释:原数组为 [11,13,15,17] ,旋转 4 次得到输入数组。 ``` **提示:** - `n == nums.length` - `1 <= n <= 5000` - `-5000 <= nums[i] <= 5000` - `nums` 中的所有整数 **互不相同** - `nums` 原来是一个升序排序的数组,并进行了 `1` 至 `n` 次旋转 ![image-20220324103053559](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220324103053559.png) ```java public class Solution { public int findMin(int[] nums) { int len = nums.length; if (len == 0) { throw new IllegalArgumentException("数组为空,无最小元素"); } int left = 0; int right = len - 1; while (left < right) { int mid = left + (right - left) / 2; // int mid = (left + right) >>> 1; if (nums[mid] > nums[right]) { left = mid + 1; } else { // 因为题目中说:你可以假设数组中不存在重复元素。 // 此时一定有 nums[mid] < nums[right] right = mid; } } // 一定存在最小元素,因此无需再做判断 return nums[left]; } } ``` #### [154. 寻找旋转排序数组中的最小值 II](https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/) 难度困难471 已知一个长度为 `n` 的数组,预先按照升序排列,经由 `1` 到 `n` 次 **旋转** 后,得到输入数组。例如,原数组 `nums = [0,1,4,4,5,6,7]` 在变化后可能得到: - 若旋转 `4` 次,则可以得到 `[4,5,6,7,0,1,4]` - 若旋转 `7` 次,则可以得到 `[0,1,4,4,5,6,7]` 注意,数组 `[a[0], a[1], a[2], ..., a[n-1]]` **旋转一次** 的结果为数组 `[a[n-1], a[0], a[1], a[2], ..., a[n-2]]` 。 给你一个可能存在 **重复** 元素值的数组 `nums` ,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 **最小元素** 。 你必须尽可能减少整个过程的操作步骤。 **示例 1:** ``` 输入:nums = [1,3,5] 输出:1 ``` **示例 2:** ``` 输入:nums = [2,2,2,0,1] 输出:0 ``` **提示:** - `n == nums.length` - `1 <= n <= 5000` - `-5000 <= nums[i] <= 5000` - `nums` 原来是一个升序排序的数组,并进行了 `1` 至 `n` 次旋转 **进阶:**这道题与 [寻找旋转排序数组中的最小值](https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/description/) 类似,但 `nums` 可能包含重复元素。允许重复会影响算法的时间复杂度吗?会如何影响,为什么? ```java class Solution { public int findMin(int[] nums) { int n = nums.length; if (n == 0){ throw new IllegalArgumentException("数组长度为0,不存在最小值"); } int left = 0, right = n - 1; while (left < right){ int mid = left + (right - left) / 2; if (nums[mid] < nums[right]){ right = mid; } else if (nums[mid] > nums[right]){ left = mid + 1; } else { right--; } } return nums[left]; } } ``` #### [852. 山脉数组的峰顶索引](https://leetcode-cn.com/problems/peak-index-in-a-mountain-array/) 难度简单238 符合下列属性的数组 `arr` 称为 **山脉数组** : - `arr.length >= 3` - 存在 ``` i ``` ( ``` 0 < i < arr.length - 1 ``` )使得: - `arr[0] < arr[1] < ... arr[i-1] < arr[i]` - `arr[i] > arr[i+1] > ... > arr[arr.length - 1]` 给你由整数组成的山脉数组 `arr` ,返回任何满足 `arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1]` 的下标 `i` 。 **示例 1:** ``` 输入:arr = [0,1,0] 输出:1 ``` **示例 2:** ``` 输入:arr = [0,2,1,0] 输出:1 ``` **示例 3:** ``` 输入:arr = [0,10,5,2] 输出:1 ``` **示例 4:** ``` 输入:arr = [3,4,5,1] 输出:2 ``` **示例 5:** ``` 输入:arr = [24,69,100,99,79,78,67,36,26,19] 输出:2 ``` **提示:** - `3 <= arr.length <= 104` - `0 <= arr[i] <= 106` - 题目数据保证 `arr` 是一个山脉数组 **进阶:**很容易想到时间复杂度 `O(n)` 的解决方案,你可以设计一个 `O(log(n))` 的解决方案吗? **方法一:二分** ```java class Solution { public int peakIndexInMountainArray(int[] arr) { int n = arr.length; if (n < 3) { throw new IllegalArgumentException("数组长度小于3,不存在顶峰索引"); } int left = 0, right = n - 1; //这里根据题目意思也可以设置为int left = 1, right = n - 2; while (left < right){ int mid = left + (right - left) / 2; if (arr[mid] < arr[mid + 1]){//因为mid向下取整,所以mid + 1不会下标越界 left = mid + 1; } else { right = mid; } } return left; } } ``` #### [1095. 山脉数组中查找目标值](https://leetcode-cn.com/problems/find-in-mountain-array/) 难度困难146 (这是一个 **交互式问题** ) 给你一个 **山脉数组** `mountainArr`,请你返回能够使得 `mountainArr.get(index)` **等于** `target` **最小** 的下标 `index` 值。 如果不存在这样的下标 `index`,就请返回 `-1`。 何为山脉数组?如果数组 `A` 是一个山脉数组的话,那它满足如下条件: **首先**,`A.length >= 3` **其次**,在 `0 < i < A.length - 1` 条件下,存在 `i` 使得: - `A[0] < A[1] < ... A[i-1] < A[i]` - `A[i] > A[i+1] > ... > A[A.length - 1]` 你将 **不能直接访问该山脉数组**,必须通过 `MountainArray` 接口来获取数据: - `MountainArray.get(k)` - 会返回数组中索引为`k` 的元素(下标从 0 开始) - `MountainArray.length()` - 会返回该数组的长度 **注意:** 对 `MountainArray.get` 发起超过 `100` 次调用的提交将被视为错误答案。此外,任何试图规避判题系统的解决方案都将会导致比赛资格被取消。 为了帮助大家更好地理解交互式问题,我们准备了一个样例 “**答案**”:https://leetcode-cn.com/playground/RKhe3ave,请注意这 **不是一个正确答案**。 **示例 1:** ``` 输入:array = [1,2,3,4,5,3,1], target = 3 输出:2 解释:3 在数组中出现了两次,下标分别为 2 和 5,我们返回最小的下标 2。 ``` **示例 2:** ``` 输入:array = [0,1,2,4,2,1], target = 3 输出:-1 解释:3 在数组中没有出现,返回 -1。 ``` **提示:** - `3 <= mountain_arr.length() <= 10000` - `0 <= target <= 10^9` - `0 <= mountain_arr.get(index) <= 10^9` **方法一:二分三步走()** ```java public class Solution { public int findInMountainArray(int target, MountainArray mountainArr) { int len = mountainArr.length(); int peakIndex = findMountainTop(mountainArr, 0, len - 1); int res = findSortedArray(mountainArr, 0, peakIndex, target); if (res != -1) { return res; } return findReverseArray(mountainArr, peakIndex + 1, len - 1, target); } /** * 在 [left..right] 查找 target 的下标 * * @param mountainArr * @param left * @param right * @param target * @return */ private int findReverseArray(MountainArray mountainArr, int left, int right, int target) { while (left < right) { int mid = left + (right - left + 1) / 2; if (mountainArr.get(mid) < target) { // 下一轮搜索区间 [left..mid - 1] right = mid - 1; } else { // 下一轮搜索区间 [mid..right] // [left..right(mid)] left = mid; } } if (mountainArr.get(left) == target) { return left; } return -1; } /** * 在 [left..right] 查找 target 的下标 * * @param mountainArr * @param left * @param right * @param target * @return */ private int findSortedArray(MountainArray mountainArr, int left, int right, int target) { while (left < right) { int mid = left + (right - left) / 2; if (mountainArr.get(mid) < target) { // 下一轮搜索区间 [mid + 1..right] left = mid + 1; } else { // 下一轮搜索区间 [left..mid] right = mid; } } if (mountainArr.get(left) == target) { return left; } return -1; } /** * 在 [left..right] 查找山顶元素的下标 * * @param mountainArr * @param left * @param right * @return */ private int findMountainTop(MountainArray mountainArr, int left, int right) { while (left < right) { int mid = left + (right - left) / 2; if (mountainArr.get(mid) < mountainArr.get(mid + 1)) { // 下一轮搜索区间 [mid + 1..right] left = mid + 1; } else { // 下一轮搜索区间 [left..mid] right = mid; } } // left == right return left; } } ``` ## 题型二:二分答案(在一个有范围的区间里搜索一个整数) 如果题目要我们找一个整数,这个整数有确定的范围,可以通过二分查找逐渐缩小范围,最后逼近到一个数。 定位一个有范围的整数,这件事情也叫「二分答案」或者叫「二分结果」。如果题目要求的是一个整数,这个整数有明确的范围,可以考虑使用二分查找。 事实上,二分答案是我们最早接触的二分查找的场景。「幸运 52」里猜价格游戏,就是「二分查找」算法的典型应用:先随便猜一个数,如果猜中,游戏结束。如果猜大了,往小猜;如果猜小了,往大猜。 说明: 第 69 题:在一个整数范围里查找一个整数,也是二分查找法的应用场景; 第 275 题:这个问题题解题意得花很多时间,可以跳过不做; 第 287 题:在一个整数范围里查找一个整数,不是在输入数组里使用二分查找。这个问题二分查找的解法很反常规(不应该用时间换空间),知道即可。 ![image-20220320083934321](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220320083934321.png) #### [69. x 的平方根 ](https://leetcode-cn.com/problems/sqrtx/) 难度简单927 给你一个非负整数 `x` ,计算并返回 `x` 的 **算术平方根** 。 由于返回类型是整数,结果只保留 **整数部分** ,小数部分将被 **舍去 。** **注意:**不允许使用任何内置指数函数和算符,例如 `pow(x, 0.5)` 或者 `x ** 0.5` 。 **示例 1:** ``` 输入:x = 4 输出:2 ``` **示例 2:** ``` 输入:x = 8 输出:2 解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。 ``` **提示:** - `0 <= x <= 231 - 1` 通过次数482,072 提交次数1,240,020 **方法一:二分** 题解 https://leetcode-cn.com/problems/sqrtx/solution/er-fen-cha-zhao-niu-dun-fa-python-dai-ma-by-liweiw/ 思路:找到最大满足mid * mid <= x的整数mid,这整数的范围在0到输入整数的一半之间 ```java public class Solution { public int mySqrt(int x) { // 特殊值判断 if (x == 0) { return 0; } if (x == 1) { return 1; } int left = 1; int right = x / 2; // 在区间 [left..right] 查找目标元素 while (left < right) { int mid = left + (right - left + 1) / 2; // 注意:这里为了避免乘法溢出,改用除法 if (mid > x / mid) { //1、如果这个整数的平方严格大于输出整数,这个整数以及比它大的数一定不符合要求 // 下一轮搜索区间是 [left..mid - 1] right = mid - 1; } else { //2、如果这个整数的平方小于等于输出整数,这个整数以及比它大的数可能符合要求 // 下一轮搜索区间是 [mid..right] left = mid; } } return left; } } ``` #### [287. 寻找重复数](https://leetcode-cn.com/problems/find-the-duplicate-number/) 难度中等1640 给定一个包含 `n + 1` 个整数的数组 `nums` ,其数字都在 `[1, n]` 范围内(包括 `1` 和 `n`),可知至少存在一个重复的整数。 假设 `nums` 只有 **一个重复的整数** ,返回 **这个重复的数** 。 你设计的解决方案必须 **不修改** 数组 `nums` 且只用常量级 `O(1)` 的额外空间。 **示例 1:** ``` 输入:nums = [1,3,4,2,2] 输出:2 ``` **示例 2:** ``` 输入:nums = [3,1,3,4,2] 输出:3 ``` **提示:** - `1 <= n <= 105` - `nums.length == n + 1` - `1 <= nums[i] <= n` - `nums` 中 **只有一个整数** 出现 **两次或多次** ,其余整数均只出现 **一次** **进阶:** - 如何证明 `nums` 中至少存在一个重复的数字? - 你可以设计一个线性级时间复杂度 `O(n)` 的解决方案吗? **方法一:二分答案** ```java public class Solution { public int findDuplicate(int[] nums) { int len = nums.length; int left = 1; int right = len - 1; while (left < right) { int mid = left + (right - left) / 2; int cnt = 0; for (int num : nums) { if (num <= mid) { cnt += 1; } } // 根据抽屉原理,小于等于 4 的个数如果严格大于 4 个,此时重复元素一定出现在 [1..4] 区间里 if (cnt > mid) { // 重复元素位于区间 [left..mid] right = mid; } else { // if 分析正确了以后,else 搜索的区间就是 if 的反面区间 [mid + 1..right] left = mid + 1; } } return left; } } ``` 复杂度分析: 时间复杂度:O(NlogN),二分法的时间复杂度为 O(logN),在二分法的内部,执行了一次 for 循环,时间复杂度为 O(N),故时间复杂度为 O(NlogN)。 空间复杂度:O(1),使用了一个 cnt 变量,因此空间复杂度为O(1)。 **方法二:快慢指针** ```java ``` **方法三:哈希表(不符合题目要求)** ```java class Solution { public int findDuplicate(int[] nums) { int n = nums.length; int[] cnts = new int[n + 1]; for(int num : nums){ cnts[num]++; } for (int i = 1; i <= n; i++) { if (cnts[i] > 1){ return i; } } return -1; } } ``` #### [374. 猜数字大小](https://leetcode-cn.com/problems/guess-number-higher-or-lower/) 难度简单177 猜数字游戏的规则如下: - 每轮游戏,我都会从 **1** 到 ***n*** 随机选择一个数字。 请你猜选出的是哪个数字。 - 如果你猜错了,我会告诉你,你猜测的数字比我选出的数字是大了还是小了。 你可以通过调用一个预先定义好的接口 `int guess(int num)` 来获取猜测结果,返回值一共有 3 种可能的情况(`-1`,`1` 或 `0`): - -1:我选出的数字比你猜的数字小 `pick < num` - 1:我选出的数字比你猜的数字大 `pick > num` - 0:我选出的数字和你猜的数字一样。恭喜!你猜对了!`pick == num` 返回我选出的数字。 **示例 1:** ``` 输入:n = 10, pick = 6 输出:6 ``` **示例 2:** ``` 输入:n = 1, pick = 1 输出:1 ``` **示例 3:** ``` 输入:n = 2, pick = 1 输出:1 ``` **示例 4:** ``` 输入:n = 2, pick = 2 输出:2 ``` **提示:** - `1 <= n <= 231 - 1` - `1 <= pick <= n` #### [1283. 使结果不超过阈值的最小除数](https://leetcode-cn.com/problems/find-the-smallest-divisor-given-a-threshold/) 难度中等62 给你一个整数数组 `nums` 和一个正整数 `threshold` ,你需要选择一个正整数作为除数,然后将数组里每个数都除以它,并对除法结果求和。 请你找出能够使上述结果小于等于阈值 `threshold` 的除数中 **最小** 的那个。 每个数除以除数后都向上取整,比方说 7/3 = 3 , 10/2 = 5 。 题目保证一定有解。 **示例 1:** ``` 输入:nums = [1,2,5,9], threshold = 6 输出:5 解释:如果除数为 1 ,我们可以得到和为 17 (1+2+5+9)。 如果除数为 4 ,我们可以得到和为 7 (1+1+2+3) 。如果除数为 5 ,和为 5 (1+1+1+2)。 ``` **示例 2:** ``` 输入:nums = [2,3,5,7,11], threshold = 11 输出:3 ``` **示例 3:** ``` 输入:nums = [19], threshold = 5 输出:4 ``` **提示:** - `1 <= nums.length <= 5 * 10^4` - `1 <= nums[i] <= 10^6` - `nums.length <= threshold <= 10^6` #### [1292. 元素和小于等于阈值的正方形的最大边长](https://leetcode-cn.com/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/) 难度中等86 给你一个大小为 `m x n` 的矩阵 `mat` 和一个整数阈值 `threshold`。 请你返回元素总和小于或等于阈值的正方形区域的最大边长;如果没有这样的正方形区域,则返回 **0** 。 **示例 1:** ![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/12/15/e1.png) ``` 输入:mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4 输出:2 解释:总和小于或等于 4 的正方形的最大边长为 2,如图所示。 ``` **示例 2:** ``` 输入:mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1 输出:0 ``` **示例 3:** ``` 输入:mat = [[1,1,1,1],[1,0,0,0],[1,0,0,0],[1,0,0,0]], threshold = 6 输出:3 ``` **示例 4:** ``` 输入:mat = [[18,70],[61,1],[25,85],[14,40],[11,96],[97,96],[63,45]], threshold = 40184 输出:2 ``` **提示:** - `1 <= m, n <= 300` - `m == mat.length` - `n == mat[i].length` - `0 <= mat[i][j] <= 10000` - `0 <= threshold <= 10^5` ## 题型三:二分答案的升级版(每一次缩小区间的时候都需要遍历数组) 说明:这一类问题本质上还是「题型二」(二分答案),但是初学的时候会觉得有一些绕。这一类问题的问法都差不多,关键字是「连续」、「正整数」,请大家注意捕捉题目中这样的关键信息。 这里给出的问题解法都一样,会一题等于会其它题。问题的场景会告诉我们:目标变量和另一个变量有相关关系(一般是线性关系),目标变量的性质不好推测,但是另一个变量的性质相对容易推测(满足某种意义上的单调性)。这样的问题的判别函数通常会写成一个函数的形式。 这一类问题可以统称为「 最大值极小化 」问题,最原始的问题场景是木棍切割问题,这道题的原始问题是「力扣」第 410 题(分割数组的最大值(困难))。 思路是这样的: 分析出题目要我们找一个整数,这个整数有范围,所以可以用二分查找; 分析出 单调性,一般来说是一个变量 a 的值大了,另一个变量 b 的值就变小,而「另一个变量的值」 b 有限制,因此可以通过调整 a 的值达到控制 b 的效果; 这一类问题的题目条件一定会给出 连续、正整数 这样的关键字。如果没有,问题场景也一定蕴含了这两个关键信息。 以下给出的问题无一例外。 ![image-20220320084011131](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220320084011131.png) 补充:「力扣」第 209 题:长度最小的子数组(中等),这道题可以使用「前缀和 + 二分查找」或者「滑动窗口」来做,一定要想清楚,为什么可以使用这些方法。 ## 第三页3.21~3.27 ### [82. 删除排序链表中的重复元素 II](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/) 难度中等839 给定一个已排序的链表的头 `head` , *删除原始链表中所有重复数字的节点,只留下不同的数字* 。返回 *已排序的链表* 。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2021/01/04/linkedlist1.jpg) ``` 输入:head = [1,2,3,3,4,4,5] 输出:[1,2,5] ``` **示例 2:** ![img](https://assets.leetcode.com/uploads/2021/01/04/linkedlist2.jpg) ``` 输入:head = [1,1,1,2,3] 输出:[2,3] ``` **提示:** - 链表中节点数目在范围 `[0, 300]` 内 - `-100 <= Node.val <= 100` - 题目数据保证链表已经按升序 **排列** 通过次数231,251 提交次数434,000 ```java class Solution { public ListNode deleteDuplicates(ListNode head) { ListNode dummy = new ListNode(-1); dummy.next = head; ListNode prev = dummy, curr = head; while(curr != null && curr.next != null){ if (curr.val != curr.next.val){ prev = curr; curr = curr.next; } else { while(curr != null && curr.next != null && curr.val == curr.next.val){ curr = curr.next; } curr = curr.next; prev.next = curr; } } return dummy.next; } } ``` ### [8. 字符串转换整数 (atoi)](https://leetcode-cn.com/problems/string-to-integer-atoi/) 难度中等1382 请你来实现一个 `myAtoi(string s)` 函数,使其能将字符串转换成一个 32 位有符号整数(类似 C/C++ 中的 `atoi` 函数)。 函数 `myAtoi(string s)` 的算法如下: 1. 读入字符串并丢弃无用的前导空格 2. 检查下一个字符(假设还未到字符末尾)为正还是负号,读取该字符(如果有)。 确定最终结果是负数还是正数。 如果两者都不存在,则假定结果为正。 3. 读入下一个字符,直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。 4. 将前面步骤读入的这些数字转换为整数(即,"123" -> 123, "0032" -> 32)。如果没有读入数字,则整数为 `0` 。必要时更改符号(从步骤 2 开始)。 5. 如果整数数超过 32 位有符号整数范围 `[−231, 231 − 1]` ,需要截断这个整数,使其保持在这个范围内。具体来说,小于 `−231` 的整数应该被固定为 `−231` ,大于 `231 − 1` 的整数应该被固定为 `231 − 1` 。 6. 返回整数作为最终结果。 **注意:** - 本题中的空白字符只包括空格字符 `' '` 。 - 除前导空格或数字后的其余字符串外,**请勿忽略** 任何其他字符。 **示例 1:** ``` 输入:s = "42" 输出:42 解释:加粗的字符串为已经读入的字符,插入符号是当前读取的字符。 第 1 步:"42"(当前没有读入字符,因为没有前导空格) ^ 第 2 步:"42"(当前没有读入字符,因为这里不存在 '-' 或者 '+') ^ 第 3 步:"42"(读入 "42") ^ 解析得到整数 42 。 由于 "42" 在范围 [-231, 231 - 1] 内,最终结果为 42 。 ``` **示例 2:** ``` 输入:s = " -42" 输出:-42 解释: 第 1 步:" -42"(读入前导空格,但忽视掉) ^ 第 2 步:" -42"(读入 '-' 字符,所以结果应该是负数) ^ 第 3 步:" -42"(读入 "42") ^ 解析得到整数 -42 。 由于 "-42" 在范围 [-231, 231 - 1] 内,最终结果为 -42 。 ``` **示例 3:** ``` 输入:s = "4193 with words" 输出:4193 解释: 第 1 步:"4193 with words"(当前没有读入字符,因为没有前导空格) ^ 第 2 步:"4193 with words"(当前没有读入字符,因为这里不存在 '-' 或者 '+') ^ 第 3 步:"4193 with words"(读入 "4193";由于下一个字符不是一个数字,所以读入停止) ^ 解析得到整数 4193 。 由于 "4193" 在范围 [-231, 231 - 1] 内,最终结果为 4193 。 ``` **提示:** - `0 <= s.length <= 200` - `s` 由英文字母(大写和小写)、数字(`0-9`)、`' '`、`'+'`、`'-'` 和 `'.'` 组成 通过次数421,442 提交次数1,940,845 **![image-20220322105536986](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220322105536986.png) ```java public class Solution { public int myAtoi(String str) { int len = str.length(); // str.charAt(i) 方法回去检查下标的合法性,一般先转换成字符数组 char[] charArray = str.toCharArray(); // 1、去除前导空格 int index = 0; while (index < len && charArray[index] == ' ') { index++; } // 2、如果已经遍历完成(针对极端用例 " ") if (index == len) { return 0; } // 3、如果出现符号字符,仅第 1 个有效,并记录正负 int sign = 1; char firstChar = charArray[index]; if (firstChar == '+') { index++; } else if (firstChar == '-') { index++; sign = -1; } // 4、将后续出现的数字字符进行转换 // 不能使用 long 类型,这是题目说的 int res = 0; while (index < len) { char currChar = charArray[index]; // 4.1 先判断不合法的情况 if (currChar > '9' || currChar < '0') { break; } // 题目中说:环境只能存储 32 位大小的有符号整数,因此,需要提前判:断乘以 10 以后是否越界 if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && (currChar - '0') > Integer.MAX_VALUE % 10)) { return Integer.MAX_VALUE; } if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && (currChar - '0') > -(Integer.MIN_VALUE % 10))) { return Integer.MIN_VALUE; } // 4.2 合法的情况下,才考虑转换,每一步都把符号位乘进去 res = res * 10 + sign * (currChar - '0'); index++; } return res; } public static void main(String[] args) { Solution solution = new Solution(); String str = "2147483646"; int res = solution.myAtoi(str); System.out.println(res); System.out.println(Integer.MAX_VALUE); System.out.println(Integer.MIN_VALUE); } } 2147483646 2147483647 -2147483648 ``` ### [148. 排序链表](https://leetcode-cn.com/problems/sort-list/) 难度中等1518 给你链表的头结点 `head` ,请将其按 **升序** 排列并返回 **排序后的链表** 。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2020/09/14/sort_list_1.jpg) ``` 输入:head = [4,2,1,3] 输出:[1,2,3,4] ``` **示例 2:** ![img](https://assets.leetcode.com/uploads/2020/09/14/sort_list_2.jpg) ``` 输入:head = [-1,5,3,4,0] 输出:[-1,0,3,4,5] ``` **示例 3:** ``` 输入:head = [] 输出:[] ``` **提示:** - 链表中节点的数目在范围 `[0, 5 * 104]` 内 - `-105 <= Node.val <= 105` **进阶:**你可以在 `O(n log n)` 时间复杂度和常数级空间复杂度下,对链表进行排序吗? **方法一:归并排序 + 寻找链表中间节点** ```java class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null){ return head; } ListNode l1 = head; ListNode mid = middleNode(l1); ListNode l2 = mid.next; mid.next = null; l1 = sortList(l1); l2 = sortList(l2); return merge(l1, l2); } //合并两个有序链表 private ListNode merge(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(-1); ListNode prev = dummy; while (l1 != null && l2 != null){ if (l1.val <= l2.val){ prev.next = l1; l1 = l1.next; } else { prev.next = l2; l2 = l2.next; } prev = prev.next; } prev.next = l1 != null ? l1 : l2; return dummy.next; } //找到链表的中间节点(如果有两个中间节点,找第一个) private ListNode middleNode(ListNode head) { if (head == null){ return head; } ListNode slow = head, fast = head; while (fast.next != null && fast.next.next != null){ slow = slow.next; fast = fast.next.next; } return slow; } } ``` ### [72. 编辑距离](https://leetcode-cn.com/problems/edit-distance/) 难度困难2212 给你两个单词 `word1` 和 `word2`, *请返回将 `word1` 转换成 `word2` 所使用的最少操作数* 。 你可以对一个单词进行如下三种操作: - 插入一个字符 - 删除一个字符 - 替换一个字符 **示例 1:** ``` 输入:word1 = "horse", word2 = "ros" 输出:3 解释: horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e') ``` **示例 2:** ``` 输入:word1 = "intention", word2 = "execution" 输出:5 解释: intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u') ``` **提示:** - `0 <= word1.length, word2.length <= 500` - `word1` 和 `word2` 由小写英文字母组成 **方法一:动态规划** ```java ``` ### [2. 两数相加](https://leetcode-cn.com/problems/add-two-numbers/) 难度中等7719 给你两个 **非空** 的链表,表示两个非负的整数。它们每位数字都是按照 **逆序** 的方式存储的,并且每个节点只能存储 **一位** 数字。 请你将两个数相加,并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外,这两个数都不会以 0 开头。 **示例 1:** ![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/01/02/addtwonumber1.jpg) ``` 输入:l1 = [2,4,3], l2 = [5,6,4] 输出:[7,0,8] 解释:342 + 465 = 807. ``` **示例 2:** ``` 输入:l1 = [0], l2 = [0] 输出:[0] ``` **示例 3:** ``` 输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出:[8,9,9,9,0,0,0,1] ``` **提示:** - 每个链表中的节点数在范围 `[1, 100]` 内 - `0 <= Node.val <= 9` - 题目数据保证列表表示的数字不含前导零 通过次数1,234,228 提交次数2,977,821 方法一: ```java class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(-1); ListNode prev = dummy; int carry = 0; while(l1 != null || l2 != null){ int n1 = l1 != null ? l1.val : 0; int n2 = l2 != null ? l2.val : 0; int temp = n1 + n2 + carry; carry = temp / 10; prev.next = new ListNode(temp % 10); prev = prev.next; l1 = l1 != null ? l1.next : l1; l2 = l2 != null ? l2.next : l2; } if (carry > 0){ prev.next = new ListNode(carry); } return dummy.next; } } ``` ### [4. 寻找两个正序数组的中位数](https://leetcode-cn.com/problems/median-of-two-sorted-arrays/) 难度困难5166 给定两个大小分别为 `m` 和 `n` 的正序(从小到大)数组 `nums1` 和 `nums2`。请你找出并返回这两个正序数组的 **中位数** 。 算法的时间复杂度应该为 `O(log (m+n))` 。 **示例 1:** ``` 输入:nums1 = [1,3], nums2 = [2] 输出:2.00000 解释:合并数组 = [1,2,3] ,中位数 2 ``` **示例 2:** ``` 输入:nums1 = [1,2], nums2 = [3,4] 输出:2.50000 解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5 ``` **提示:** - `nums1.length == m` - `nums2.length == n` - `0 <= m <= 1000` - `0 <= n <= 1000` - `1 <= m + n <= 2000` - `-106 <= nums1[i], nums2[i] <= 106` 方法一:二分 ```java ``` **方法二:合并两个有序数组(时间复杂度O(m + n)不符合要求)** ```java class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int[] temp = mergeSort(nums1, nums2); int n = temp.length; if (n % 2 == 1){ return temp[(n - 1) / 2] * 1.0; } else { return (temp[(n - 1) / 2] + temp[(n - 1) / 2 + 1]) / 2.0; } } //合并两个有序数组 public int[] mergeSort(int[] arr1, int[] arr2){ int m = arr1.length, n = arr2.length; int[] temp = new int[m + n]; int p1 = 0, p2 = 0, k = 0; while (p1 < m && p2 < n){ if (arr1[p1] <= arr2[p2]){ temp[k++] = arr1[p1++]; } else { temp[k++] = arr2[p2++]; } } while (p1 < m) temp[k++] = arr1[p1++]; while (p2 < n) temp[k++] = arr2[p2++]; return temp; } } ``` **方法三:暴力O((m+ n)(log(m +n)))** ```java class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m = nums1.length, n = nums2.length; int[] temp = new int[m + n]; for (int i = 0; i < m; i++) { temp[i] = nums1[i]; } for (int i = m; i < m + n; i++) { temp[i] = nums2[i - m]; } Arrays.sort(temp); n = temp.length; if (n % 2 == 1){ return temp[(n - 1) / 2] * 1.0; } else { return (temp[(n - 1) / 2] + temp[(n - 1) / 2 + 1]) / 2.0; } } } ``` ### [144. 二叉树的前序遍历](https://leetcode-cn.com/problems/binary-tree-preorder-traversal/) 难度简单760 给你二叉树的根节点 `root` ,返回它节点值的 **前序** 遍历。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2020/09/15/inorder_1.jpg) ``` 输入:root = [1,null,2,3] 输出:[1,2,3] ``` **示例 2:** ``` 输入:root = [] 输出:[] ``` **示例 3:** ``` 输入:root = [1] 输出:[1] ``` **示例 4:** ![img](https://assets.leetcode.com/uploads/2020/09/15/inorder_5.jpg) ``` 输入:root = [1,2] 输出:[1,2] ``` **示例 5:** ![img](https://assets.leetcode.com/uploads/2020/09/15/inorder_4.jpg) ``` 输入:root = [1,null,2] 输出:[1,2] ``` **提示:** - 树中节点数目在范围 `[0, 100]` 内 - `-100 <= Node.val <= 100` **进阶:**递归算法很简单,你可以通过迭代算法完成吗? **方法一 :递归法** ```java class Solution { List res = new ArrayList<>(); public List preorderTraversal(TreeNode root) { //1、递归终止条件 if(root == null) return res; //2、递归主体 res.add(root.val); //3、前序遍历框架 preorderTraversal(root.left); preorderTraversal(root.right); //4、返回值 return res; } } ``` **方法二:迭代法** ```java class Solution { public List preorderTraversal(TreeNode root) { List res = new ArrayList<>(); if (root == null) return res; Deque stack = new LinkedList<>(); TreeNode node = root; while(!stack.isEmpty() || node != null){ while(node != null){ //前序遍历先访问 res.add(node.val); //再压栈 stack.push(node); node = node.left; } node = stack.pop(); node = node.right; } return res; } } ``` ### [151. 颠倒字符串中的单词](https://leetcode-cn.com/problems/reverse-words-in-a-string/) 难度中等487 给你一个字符串 `s` ,颠倒字符串中 **单词** 的顺序。 **单词** 是由非空格字符组成的字符串。`s` 中使用至少一个空格将字符串中的 **单词** 分隔开。 返回 **单词** 顺序颠倒且 **单词** 之间用单个空格连接的结果字符串。 **注意:**输入字符串 `s`中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中,单词间应当仅用单个空格分隔,且不包含任何额外的空格。 **示例 1:** ``` 输入:s = "the sky is blue" 输出:"blue is sky the" ``` **示例 2:** ``` 输入:s = " hello world " 输出:"world hello" 解释:颠倒后的字符串中不能存在前导空格和尾随空格。 ``` **示例 3:** ``` 输入:s = "a good example" 输出:"example good a" 解释:如果两个单词间有多余的空格,颠倒后的字符串需要将单词间的空格减少到仅有一个。 ``` **提示:** - `1 <= s.length <= 104` - `s` 包含英文大小写字母、数字和空格 `' '` - `s` 中 **至少存在一个** 单词 **进阶:**如果字符串在你使用的编程语言中是一种可变数据类型,请尝试使用 `O(1)` 额外空间复杂度的 **原地** 解法。 **方法一:同向双指针** ![image-20220324154325177](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220324154325177.png) ```java class Solution { public String reverseWords(String s) { s = s.trim(); // 删除首尾空格 int j = s.length() - 1, i = j; StringBuilder res = new StringBuilder(); while(i >= 0) { while(i >= 0 && s.charAt(i) != ' ') i--; // 搜索首个空格 res.append(s.substring(i + 1, j + 1) + " "); // 添加单词 while(i >= 0 && s.charAt(i) == ' ') i--; // 跳过单词间空格 j = i; // j 指向下个单词的尾字符 } return res.toString().trim(); // 转化为字符串并返回 } } class Solution { public String reverseWords(String s) { s = trim(s); // 删除首尾空格 int j = s.length() - 1, i = j; StringBuilder res = new StringBuilder(); while(i >= 0) { while(i >= 0 && s.charAt(i) != ' ') i--; // 搜索首个空格 res.append(s.substring(i + 1, j + 1) + " "); // 添加单词 while(i >= 0 && s.charAt(i) == ' ') i--; // 跳过单词间空格 j = i; // j 指向下个单词的尾字符 } return trim(res.toString()); // 转化为字符串并返回 } //取出字符串首尾空白 public String trim(String s){ int left = 0, right = s.length() - 1; while (left <= right && s.charAt(left) == ' '){ left++; } while (left <= right && s.charAt(right) == ' '){ right--; } return s.substring(left, right + 1); } } ``` **方法二:双指针** ```java class Solution { /** * 不使用Java内置方法实现 *

* 1.去除首尾以及中间多余空格 * 2.反转整个字符串 * 3.反转各个单词 */ public String reverseWords(String s) { // System.out.println("ReverseWords.reverseWords2() called with: s = [" + s + "]"); // 1.去除首尾以及中间多余空格 StringBuilder sb = removeSpace(s); // 2.反转整个字符串 reverseString(sb, 0, sb.length() - 1); // 3.反转各个单词 reverseEachWord(sb); return sb.toString(); } private StringBuilder removeSpace(String s) { // System.out.println("ReverseWords.removeSpace() called with: s = [" + s + "]"); int start = 0; int end = s.length() - 1; while (s.charAt(start) == ' ') start++; while (s.charAt(end) == ' ') end--; StringBuilder sb = new StringBuilder(); while (start <= end) { char c = s.charAt(start); if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') { sb.append(c); } start++; } // System.out.println("ReverseWords.removeSpace returned: sb = [" + sb + "]"); return sb; } /** * 反转字符串指定区间[start, end]的字符 */ public void reverseString(StringBuilder sb, int start, int end) { // System.out.println("ReverseWords.reverseString() called with: sb = [" + sb + "], start = [" + start + "], end = [" + end + "]"); while (start < end) { char temp = sb.charAt(start); sb.setCharAt(start, sb.charAt(end)); sb.setCharAt(end, temp); start++; end--; } // System.out.println("ReverseWords.reverseString returned: sb = [" + sb + "]"); } private void reverseEachWord(StringBuilder sb) { int start = 0; int end = 1; int n = sb.length(); while (start < n) { while (end < n && sb.charAt(end) != ' ') { end++; } reverseString(sb, start, end - 1); start = end + 1; end = start + 1; } } } ``` **方法三:api** ### [93. 复原 IP 地址](https://leetcode-cn.com/problems/restore-ip-addresses/) 难度中等829 **有效 IP 地址** 正好由四个整数(每个整数位于 `0` 到 `255` 之间组成,且不能含有前导 `0`),整数之间用 `'.'` 分隔。 - 例如:`"0.1.2.201"` 和` "192.168.1.1"` 是 **有效** IP 地址,但是 `"0.011.255.245"`、`"192.168.1.312"` 和 `"192.168@1.1"` 是 **无效** IP 地址。 给定一个只包含数字的字符串 `s` ,用以表示一个 IP 地址,返回所有可能的**有效 IP 地址**,这些地址可以通过在 `s` 中插入 `'.'` 来形成。你 **不能** 重新排序或删除 `s` 中的任何数字。你可以按 **任何** 顺序返回答案。 **示例 1:** ``` 输入:s = "25525511135" 输出:["255.255.11.135","255.255.111.35"] ``` **示例 2:** ``` 输入:s = "0000" 输出:["0.0.0.0"] ``` **示例 3:** ``` 输入:s = "101023" 输出:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"] ``` **提示:** - `1 <= s.length <= 20` - `s` 仅由数字组成 ### [105. 从前序与中序遍历序列构造二叉树](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/) 难度中等1490 给定两个整数数组 `preorder` 和 `inorder` ,其中 `preorder` 是二叉树的**先序遍历**, `inorder` 是同一棵树的**中序遍历**,请构造二叉树并返回其根节点。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2021/02/19/tree.jpg) ``` 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7] ``` **示例 2:** ``` 输入: preorder = [-1], inorder = [-1] 输出: [-1] ``` **提示:** - `1 <= preorder.length <= 3000` - `inorder.length == preorder.length` - `-3000 <= preorder[i], inorder[i] <= 3000` - `preorder` 和 `inorder` 均 **无重复** 元素 - `inorder` 均出现在 `preorder` - `preorder` **保证** 为二叉树的前序遍历序列 - `inorder` **保证** 为二叉树的中序遍历序列 ### [31. 下一个排列](https://leetcode-cn.com/problems/next-permutation/) 难度中等1595 整数数组的一个 **排列** 就是将其所有成员以序列或线性顺序排列。 - 例如,`arr = [1,2,3]` ,以下这些都可以视作 `arr` 的排列:`[1,2,3]`、`[1,3,2]`、`[3,1,2]`、`[2,3,1]` 。 整数数组的 **下一个排列** 是指其整数的下一个字典序更大的排列。更正式地,如果数组的所有排列根据其字典顺序从小到大排列在一个容器中,那么数组的 **下一个排列** 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列,那么这个数组必须重排为字典序最小的排列(即,其元素按升序排列)。 - 例如,`arr = [1,2,3]` 的下一个排列是 `[1,3,2]` 。 - 类似地,`arr = [2,3,1]` 的下一个排列是 `[3,1,2]` 。 - 而 `arr = [3,2,1]` 的下一个排列是 `[1,2,3]` ,因为 `[3,2,1]` 不存在一个字典序更大的排列。 给你一个整数数组 `nums` ,找出 `nums` 的下一个排列。 必须**[ 原地 ](https://baike.baidu.com/item/原地算法)**修改,只允许使用额外常数空间。 **示例 1:** ``` 输入:nums = [1,2,3] 输出:[1,3,2] ``` **示例 2:** ``` 输入:nums = [3,2,1] 输出:[1,2,3] ``` **示例 3:** ``` 输入:nums = [1,1,5] 输出:[1,5,1] ``` **提示:** - `1 <= nums.length <= 100` - `0 <= nums[i] <= 100` ### [1143. 最长公共子序列](https://leetcode-cn.com/problems/longest-common-subsequence/) 难度中等891 给定两个字符串 `text1` 和 `text2`,返回这两个字符串的最长 **公共子序列** 的长度。如果不存在 **公共子序列** ,返回 `0` 。 一个字符串的 **子序列** 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。 - 例如,`"ace"` 是 `"abcde"` 的子序列,但 `"aec"` 不是 `"abcde"` 的子序列。 两个字符串的 **公共子序列** 是这两个字符串所共同拥有的子序列。 **示例 1:** ``` 输入:text1 = "abcde", text2 = "ace" 输出:3 解释:最长公共子序列是 "ace" ,它的长度为 3 。 ``` **示例 2:** ``` 输入:text1 = "abc", text2 = "abc" 输出:3 解释:最长公共子序列是 "abc" ,它的长度为 3 。 ``` **示例 3:** ``` 输入:text1 = "abc", text2 = "def" 输出:0 解释:两个字符串没有公共子序列,返回 0 。 ``` **提示:** - `1 <= text1.length, text2.length <= 1000` - `text1` 和 `text2` 仅由小写英文字符组成。 ### [41. 缺失的第一个正数](https://leetcode-cn.com/problems/first-missing-positive/) 难度困难1397 给你一个未排序的整数数组 `nums` ,请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 `O(n)` 并且只使用常数级别额外空间的解决方案。 **示例 1:** ``` 输入:nums = [1,2,0] 输出:3 ``` **示例 2:** ``` 输入:nums = [3,4,-1,1] 输出:2 ``` **示例 3:** ``` 输入:nums = [7,8,9,11,12] 输出:1 ``` **提示:** - `1 <= nums.length <= 5 * 105` - `-231 <= nums[i] <= 231 - 1` ### [239. 滑动窗口最大值](https://leetcode-cn.com/problems/sliding-window-maximum/) 难度困难1475 给你一个整数数组 `nums`,有一个大小为 `k` 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 `k` 个数字。滑动窗口每次只向右移动一位。 返回 *滑动窗口中的最大值* 。 **示例 1:** ``` 输入:nums = [1,3,-1,-3,5,3,6,7], k = 3 输出:[3,3,5,5,6,7] 解释: 滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 ``` **示例 2:** ``` 输入:nums = [1], k = 1 输出:[1] ``` **提示:** - `1 <= nums.length <= 105` - `-104 <= nums[i] <= 104` - `1 <= k <= nums.length` ### [22. 括号生成](https://leetcode-cn.com/problems/generate-parentheses/) 难度中等2464 数字 `n` 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 **有效的** 括号组合。 **示例 1:** ``` 输入:n = 3 输出:["((()))","(()())","(())()","()(())","()()()"] ``` **示例 2:** ``` 输入:n = 1 输出:["()"] ``` **提示:** - `1 <= n <= 8` 通过次数454,220 提交次数587,110 **方法一:DFS(回溯)** ```java ``` **方法二:BFS** ```java ``` ### [76. 最小覆盖子串](https://leetcode-cn.com/problems/minimum-window-substring/) 难度困难1723 给你一个字符串 `s` 、一个字符串 `t` 。返回 `s` 中涵盖 `t` 所有字符的最小子串。如果 `s` 中不存在涵盖 `t` 所有字符的子串,则返回空字符串 `""` 。 **注意:** - 对于 `t` 中重复字符,我们寻找的子字符串中该字符数量必须不少于 `t` 中该字符数量。 - 如果 `s` 中存在这样的子串,我们保证它是唯一的答案。 **示例 1:** ``` 输入:s = "ADOBECODEBANC", t = "ABC" 输出:"BANC" ``` **示例 2:** ``` 输入:s = "a", t = "a" 输出:"a" ``` **示例 3:** ``` 输入: s = "a", t = "aa" 输出: "" 解释: t 中两个字符 'a' 均应包含在 s 的子串中, 因此没有符合条件的子字符串,返回空字符串。 ``` **提示:** - `1 <= s.length, t.length <= 105` - `s` 和 `t` 由英文字母组成 **进阶:**你能设计一个在 `o(n)` 时间内解决此问题的算法吗? **方法一:滑动窗口** ```java class Solution { public String minWindow(String s, String t) { if (s == null || s == "" || t == null || t == "" || s.length() < t.length()) { return ""; } //维护两个数组,记录已有字符串指定字符的出现次数,和目标字符串指定字符的出现次数 //ASCII表总长128 int[] need = new int[128]; int[] have = new int[128]; //将目标字符串指定字符的出现次数记录 for (int i = 0; i < t.length(); i++) { need[t.charAt(i)]++; } //分别为左指针,右指针,最小长度(初始值为一定不可达到的长度) //已有字符串中目标字符串指定字符的出现总频次以及最小覆盖子串在原字符串中的起始位置 int left = 0, right = 0, min = s.length() + 1, count = 0, start = 0; while (right < s.length()) { char r = s.charAt(right); //说明该字符不被目标字符串需要,此时有两种情况 // 1.循环刚开始,那么直接移动右指针即可,不需要做多余判断 // 2.循环已经开始一段时间,此处又有两种情况 // 2.1 上一次条件不满足,已有字符串指定字符出现次数不满足目标字符串指定字符出现次数,那么此时 // 如果该字符还不被目标字符串需要,就不需要进行多余判断,右指针移动即可 // 2.2 左指针已经移动完毕,那么此时就相当于循环刚开始,同理直接移动右指针 if (need[r] == 0) { right++; continue; } //当且仅当已有字符串目标字符出现的次数小于目标字符串字符的出现次数时,count才会+1 //是为了后续能直接判断已有字符串是否已经包含了目标字符串的所有字符,不需要挨个比对字符出现的次数 if (have[r] < need[r]) { count++; } //已有字符串中目标字符出现的次数+1 have[r]++; //移动右指针 right++; //当且仅当已有字符串已经包含了所有目标字符串的字符,且出现频次一定大于或等于指定频次 while (count == t.length()) { //挡窗口的长度比已有的最短值小时,更改最小值,并记录起始位置 if (right - left < min) { min = right - left; start = left; } char l = s.charAt(left); //如果左边即将要去掉的字符不被目标字符串需要,那么不需要多余判断,直接可以移动左指针 if (need[l] == 0) { left++; continue; } //如果左边即将要去掉的字符被目标字符串需要,且出现的频次正好等于指定频次,那么如果去掉了这个字符, //就不满足覆盖子串的条件,此时要破坏循环条件跳出循环,即控制目标字符串指定字符的出现总频次(count)-1 if (have[l] == need[l]) { count--; } //已有字符串中目标字符出现的次数-1 have[l]--; //移动左指针 left++; } } //如果最小长度还为初始值,说明没有符合条件的子串 if (min == s.length() + 1) { return ""; } //返回的为以记录的起始位置为起点,记录的最短长度为距离的指定字符串中截取的子串 return s.substring(start, start + min); } } ``` ### [129. 求根节点到叶节点数字之和](https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/) 难度中等497 给你一个二叉树的根节点 `root` ,树中每个节点都存放有一个 `0` 到 `9` 之间的数字。 每条从根节点到叶节点的路径都代表一个数字: - 例如,从根节点到叶节点的路径 `1 -> 2 -> 3` 表示数字 `123` 。 计算从根节点到叶节点生成的 **所有数字之和** 。 **叶节点** 是指没有子节点的节点。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2021/02/19/num1tree.jpg) ``` 输入:root = [1,2,3] 输出:25 解释: 从根到叶子节点路径 1->2 代表数字 12 从根到叶子节点路径 1->3 代表数字 13 因此,数字总和 = 12 + 13 = 25 ``` **示例 2:** ![img](https://assets.leetcode.com/uploads/2021/02/19/num2tree.jpg) ``` 输入:root = [4,9,0,5,1] 输出:1026 解释: 从根到叶子节点路径 4->9->5 代表数字 495 从根到叶子节点路径 4->9->1 代表数字 491 从根到叶子节点路径 4->0 代表数字 40 因此,数字总和 = 495 + 491 + 40 = 1026 ``` **提示:** - 树中节点的数目在范围 `[1, 1000]` 内 - `0 <= Node.val <= 9` - 树的深度不超过 `10` 这道题中,二叉树的每条从根节点到叶子节点的路径都代表一个数字。其实,每个节点都对应一个数字,等于其父节点对应的数字乘以 1010 再加上该节点的值(这里假设根节点的父节点对应的数字是 00)。只要计算出每个叶子节点对应的数字,然后计算所有叶子节点对应的数字之和,即可得到结果。可以通过深度优先搜索和广度优先搜索实现。 方法一:DFS 深度优先搜索是很直观的做法。从根节点开始,遍历每个节点,如果遇到叶子节点,则将叶子节点对应的数字加到数字之和。如果当前节点不是叶子节点,则计算其子节点对应的数字,然后对子节点递归遍历。 ```java class Solution { int ans = 0; public int sumNumbers(TreeNode root) { dfs(root, 0); return ans; } public void dfs(TreeNode root, int preSum){ //递归终止条件:当越过叶子节点直接返回 if (root == null) return; //root递归主体 preSum = preSum * 10 + root.val; //如果遇到叶子节点,将结果添加到ans中 if (root.left == null && root.right == null){ ans += preSum; } //前序遍历框架 dfs(root.left, preSum); dfs(root.right, preSum); } } public int sumNumbers(TreeNode root) { return helper(root, 0); } //辅助函数 public int helper(TreeNode root, int i){ if (root == null) return 0; int temp = i * 10 + root.val; if (root.left == null && root.right == null) return temp; return helper(root.left, temp) + helper(root.right, temp); } ``` **方法二:BFS** **思路与算法** 使用广度优先搜索,需要维护两个队列,分别存储节点和节点对应的数字。 初始时,将根节点和根节点的值分别加入两个队列。每次从两个队列分别取出一个节点和一个数字,进行如下操作: 如果当前节点是叶子节点,则将该节点对应的数字加到数字之和; 如果当前节点不是叶子节点,则获得当前节点的非空子节点,并根据当前节点对应的数字和子节点的值计算子节点对应的数字,然后将子节点和子节点对应的数字分别加入两个队列。 搜索结束后,即可得到所有叶子节点对应的数字之和。 ```java class Solution { public int sumNumbers(TreeNode root) { if (root == null) { return 0; } int sum = 0; Queue nodeQueue = new LinkedList(); Queue numQueue = new LinkedList(); nodeQueue.offer(root); numQueue.offer(root.val); while (!nodeQueue.isEmpty()) { TreeNode node = nodeQueue.poll(); int num = numQueue.poll(); TreeNode left = node.left, right = node.right; if (left == null && right == null) { sum += num; } else { if (left != null) { nodeQueue.offer(left); numQueue.offer(num * 10 + left.val); } if (right != null) { nodeQueue.offer(right); numQueue.offer(num * 10 + right.val); } } } return sum; } } ``` ### [104. 二叉树的最大深度](https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/) 难度简单1153 给定一个二叉树,找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 **说明:** 叶子节点是指没有子节点的节点。 **示例:** 给定二叉树 `[3,9,20,null,null,15,7]`, ``` 3 / \ 9 20 / \ 15 7 ``` 返回它的最大深度 3 。 **方法一:后序遍历(自底向上求高度)** ```java class Solution { public int maxDepth(TreeNode root) { //base case if (root == null) return 0; //后续遍历框架 int L = maxDepth(root.left); int R = maxDepth(root.right); //root int max = Math.max(L, R) + 1; //返回值 return max; } } ``` **方法二:前序遍历(自顶向下求深度)** ```java class Solution { int maxDepth = 0; public int maxDepth(TreeNode root) { dfs(root, 0); return maxDepth; } public void dfs(TreeNode root, int depth){ //递归终止条件 if (root == null) return; //root递归主体 depth++; maxDepth = Math.max(maxDepth, depth); //maxDepth用来维护最大深度 //前序遍历框架 dfs(root.left, depth); dfs(root.right, depth); } } ``` **方法三:层序遍历(自左向右)** ```java class Solution { public int maxDepth(TreeNode root) { // 空树,高度为 0 if(root == null){ return 0; } // 初始化队列和层次 Queue queue = new LinkedList<>(); queue.offer(root); int depth = 0;//通过一层一层来记录二叉树的最大深度 // 当队列不为空 while(!queue.isEmpty()){ // 当前层的节点数 int n = queue.size(); // 弹出当前层的所有节点,并将所有子节点入队列 for(int i = 0; i < n; i++){ TreeNode node = queue.poll(); if(node.left != null){ queue.offer(node.left); } if(node.right != null){ queue.offer(node.right); } } depth++; } // 二叉树最大层次即为二叉树最深深度 return depth; } } ``` ### [110. 平衡二叉树](https://leetcode-cn.com/problems/balanced-binary-tree/) 难度简单930 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: > 一个二叉树*每个节点* 的左右两个子树的高度差的绝对值不超过 1 。 **示例 1:** ![img](https://assets.leetcode.com/uploads/2020/10/06/balance_1.jpg) ``` 输入:root = [3,9,20,null,null,15,7] 输出:true ``` **示例 2:** ![img](https://assets.leetcode.com/uploads/2020/10/06/balance_2.jpg) ``` 输入:root = [1,2,2,3,3,null,null,4,4] 输出:false ``` **示例 3:** ``` 输入:root = [] 输出:true ``` **提示:** - 树中的节点数在范围 `[0, 5000]` 内 - `-104 <= Node.val <= 104` https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/solution/acm-xuan-shou-tu-jie-leetcode-er-cha-shu-ckf4/ **方法一:前序遍历** **自顶向下的递归:类似于二叉树的前序遍历,即对于当前遍历的节点,首先计算左右子树的高度,如果左右子树的高度小于等于1,再分别递归遍历左右子节点,并判断左子树和右子树是否平衡,这是一个自顶向下的递归过程** ![image-20220325212115597](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220325212115597.png) ```java class Solution { //自上而下依次判断每个节点是否为平衡节点 public boolean isBalanced(TreeNode root) { //1、递归终止条件 if(root == null) return true; //2、root boolean flag = Math.abs(height(root.left) - height(root.right)) <= 1; //3、前序遍历框架,返回值 return flag && isBalanced(root.left) && isBalanced(root.right); } public int height(TreeNode root) { //1、递归终止条件:当 root 为空,即越过叶子节点,则返回高度 0 ; if (root == null) return 0; //2、后序遍历框架 int L = height(root.left); int R = height(root.right); //3、root int max = Math.max(L, R) + 1; //4、return:返回左 / 右子树的最大高度加 11 。 return max; } } ``` ![image-20220325212038980](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220325212038980.png) **方法二:后序遍历** **方法一由于是自顶向下递归,因此对于同一个节点,函数height 会被重复调用,导致时间复杂度较高。如果使用自底向上的做法,则对于每个节点,函数height 只会被调用一次。** **自底向上递归的做法类似于后序遍历,对于当前遍历到的节点,先递归地判断其左右子树是否平衡,再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的,则返回其高度(高度一定是非负整数),否则返回 −1。如果存在一棵子树不平衡,则整个二叉树一定不平衡。** ```java class Solution { public boolean isBalanced(TreeNode root) { return height(root) >= 0; } public int height(TreeNode root){ if (root == null) return 0; int L = height(root.left); int R = height(root.right); if (L == -1 || R == - 1 || Math.abs(L - R) > 1){ return -1; } else { return Math.max(L, R) + 1; } } } ``` ### [155. 最小栈](https://leetcode-cn.com/problems/min-stack/) 难度简单1227 设计一个支持 `push` ,`pop` ,`top` 操作,并能在常数时间内检索到最小元素的栈。 实现 `MinStack` 类: - `MinStack()` 初始化堆栈对象。 - `void push(int val)` 将元素val推入堆栈。 - `void pop()` 删除堆栈顶部的元素。 - `int top()` 获取堆栈顶部的元素。 - `int getMin()` 获取堆栈中的最小元素。 **示例 1:** ``` 输入: ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] 输出: [null,null,null,null,-3,null,0,-2] 解释: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2. ``` **提示:** - `-231 <= val <= 231 - 1` - `pop`、`top` 和 `getMin` 操作总是在 **非空栈** 上调用 - `push`, `pop`, `top`, and `getMin`最多被调用 `3 * 104` 次 **方法一:辅助栈** ![image-20220325081208361](C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20220325081208361.png) ```java class MinStack { private Stack stack; private Stack min_stack; public MinStack() { stack = new LinkedList<>(); min_stack = new LinkedList<>(); } public void push(int x) { stack.push(x); if(min_stack.isEmpty() || x <= min_stack.peek()) //注意<= min_stack.push(x); } public void pop() { if(stack.pop().equals(min_stack.peek())) //Integer对象判断是否相同只能用equals()方法 min_stack.pop(); } public int top() { return stack.peek(); } public int getMin() { return min_stack.peek(); } } ``` # 第三部分:二叉树专题 image.png ## 剑指Offer3.28~4.3 # 第六部分:回溯专题 #### [46. 全排列](https://leetcode-cn.com/problems/permutations/) 难度中等1698 给定一个不含重复数字的数组 `nums` ,返回其 **所有可能的全排列** 。你可以 **按任意顺序** 返回答案。 **示例 1:** ``` 输入:nums = [1,2,3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] ``` **示例 2:** ``` 输入:nums = [0,1] 输出:[[0,1],[1,0]] ``` **示例 3:** ``` 输入:nums = [1] 输出:[[1]] ``` **提示:** - `1 <= nums.length <= 6` - `-10 <= nums[i] <= 10` - `nums` 中的所有整数 **互不相同** **方法一:DFS+回溯(liweiwei1419题解)** ![image.png](https://pic.leetcode-cn.com/0bf18f9b86a2542d1f6aa8db6cc45475fce5aa329a07ca02a9357c2ead81eec1-image.png) **理解回溯** 从 [1, 2, 3] 到 [1, 3, 2] ,深度优先遍历是这样做的,从 [1, 2, 3] 回到 [1, 2] 的时候,需要撤销刚刚已经选择的数 3,因为在这一层只有一个数 3 我们已经尝试过了,因此程序回到上一层,需要撤销对 2 的选择,好让后面的程序知道,选择 3 了以后还能够选择 2。 用`res.add(new linkedList(path))`而不是`res.add(path)`。因为`path`是个引用,所指向的对象在不断地增加和删除元素,最后会变成空。得到的结果会变成`[[][][][][]]`所以要用`new linkedList(path)`拷贝一个对象加入`res` ```java class Solution { List> res = new LinkedList<>();//所有排列集合,也可以是new ArrayList<>() LinkedList path = new LinkedList<>();//单个排列集合,需要方法removeLast(); public List> permute(int[] nums) { if (nums == null || nums.length == 0) return res; boolean[] visited = new boolean[nums.length];//默认全为false dfs(nums, visited); return res; } void dfs(int[] nums, boolean[] visited){ //path集合容量和数组长度相同时,添加到res集合中,并返回至上一层 if (path.size() == nums.length){ res.add(new LinkedList<>(path)); return; } for (int i = 0; i < nums.length; i++){ if (!visited[i]){ // 没有访问过才可以访问 visited[i] = true; //将当前节点标记为已访问 path.add(nums[i]); dfs(nums, visited); path.removeLast(); //回溯,删除path最后一个节点, 也可以是pollLast() visited[i] = false; // 将当前删除的节点再重新标记为未访问过 } } } } class Solution { List> res = new LinkedList<>();//所有排列集合,也可以是new ArrayList<>() LinkedList path = new LinkedList<>();//单个排列集合,需要方法removeLast(); public List> permute(int[] nums) { if (nums == null || nums.length == 0) return res; boolean[] visited = new boolean[nums.length];//默认全为false dfs(nums, visited, 0); return res; } void dfs(int[] nums, boolean[] visited, int depth){ //path集合容量和数组长度相同时,添加到res集合中,并返回至上一层 if (depth == nums.length){ res.add(new LinkedList<>(path)); return; } for (int i = 0; i < nums.length; i++){ if (!visited[i]){ // 没有访问过才可以访问 visited[i] = true; //将当前节点标记为已访问 path.add(nums[i]); dfs(nums, visited, depth + 1); path.removeLast(); //回溯,删除path最后一个节点 visited[i] = false; // 将当前删除的节点再重新标记为未访问过 } } } } ``` ```java import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Deque; import java.util.List; public class Solution { public List> permute(int[] nums) { int len = nums.length; // 使用一个动态数组保存所有可能的全排列 List> res = new ArrayList<>(); if (len == 0) { return res; } boolean[] used = new boolean[len]; Deque path = new ArrayDeque<>(len); dfs(nums, len, 0, path, used, res); return res; } private void dfs(int[] nums, int len, int depth, Deque path, boolean[] used, List> res) { if (depth == len) { res.add(new ArrayList<>(path)); return; } for (int i = 0; i < len; i++) { if (!used[i]) { path.addLast(nums[i]); used[i] = true; System.out.println(" 递归之前 => " + path); dfs(nums, len, depth + 1, path, used, res); used[i] = false; path.removeLast(); System.out.println("递归之后 => " + path); } } } public static void main(String[] args) { int[] nums = {1, 2, 3}; Solution solution = new Solution(); List> lists = solution.permute(nums); System.out.println(lists); } } 控制台输出: 递归之前 => [1] 递归之前 => [1, 2] 递归之前 => [1, 2, 3] 递归之后 => [1, 2] 递归之后 => [1] 递归之前 => [1, 3] 递归之前 => [1, 3, 2] 递归之后 => [1, 3] 递归之后 => [1] 递归之后 => [] 递归之前 => [2] 递归之前 => [2, 1] 递归之前 => [2, 1, 3] 递归之后 => [2, 1] 递归之后 => [2] 递归之前 => [2, 3] 递归之前 => [2, 3, 1] 递归之后 => [2, 3] 递归之后 => [2] 递归之后 => [] 递归之前 => [3] 递归之前 => [3, 1] 递归之前 => [3, 1, 2] 递归之后 => [3, 1] 递归之后 => [3] 递归之前 => [3, 2] 递归之前 => [3, 2, 1] 递归之后 => [3, 2] 递归之后 => [3] 递归之后 => [] 输出 => [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] ``` **复杂度分析** - 时间复杂度:*O*(*N*×*N*!)。 - 空间复杂度:*O*(*N*×*N*!) - 递归树深度 log*N*; - 全排列个数 N!,每个全排列占空间 N。取较大者。 #### [47. 全排列 II](https://leetcode-cn.com/problems/permutations-ii/) 难度中等894 给定一个可包含重复数字的序列 `nums` ,**按任意顺序** 返回所有不重复的全排列。 **示例 1:** ``` 输入:nums = [1,1,2] 输出: [[1,1,2], [1,2,1], [2,1,1]] ``` **示例 2:** ``` 输入:nums = [1,2,3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] ``` **提示:** - `1 <= nums.length <= 8` - `-10 <= nums[i] <= 10` **方法一:DFS + 回溯 + 剪枝这一题** **在「力扣」第 46 题: 全排列 的基础上增加了 序列中的元素可重复 这一条件,但要求:返回的结果又不能有重复元素。** 思路是:在遍历的过程中,一边遍历一遍检测,在一定会产生重复结果集的地方剪枝。 一个比较容易想到的办法是在结果集中去重。但是问题来了,这些结果集的元素是一个又一个列表,对列表去重不像用哈希表对基本元素去重那样容易。 如果要比较两个列表是否一样,一个容易想到的办法是对列表分别排序,然后逐个比对。既然要排序,我们就可以 在搜索之前就对候选数组排序,一旦发现某个分支搜索下去可能搜索到重复的元素就停止搜索,这样结果集中不会包含重复列表。 画出树形结构如下:重点想象深度优先遍历在这棵树上执行的过程,哪些地方遍历下去一定会产生重复,这些地方的状态的特点是什么? 对比图中标注 ① 和 ② 的地方。相同点是:这一次搜索的起点和上一次搜索的起点一样。不同点是: - 标注 ① 的地方上一次搜索的相同的数刚刚被撤销; - 标注 ② 的地方上一次搜索的相同的数刚刚被使用。 ![image.png](https://pic.leetcode-cn.com/1600386643-uhkGmW-image.png) 产生重复结点的地方,正是图中标注了「剪刀」,且被绿色框框住的地方。 大家也可以把第 2 个 1 加上 ' ,即 [1, 1', 2] 去想象这个搜索的过程。只要遇到起点一样,就有可能产生重复。这里还有一个很细节的地方: - 在图中 ② 处,搜索的数也和上一次一样,但是上一次的 1 还在使用中; - 在图中 ① 处,搜索的数也和上一次一样,但是上一次的 1 刚刚被撤销,正是因为刚被撤销,下面的搜索中还会使用到,因此会产生重复,剪掉的就应该是这样的分支。 ```java class Solution { List> res = new ArrayList<>(); List path = new ArrayList<>(); public List> permuteUnique(int[] nums) { if (nums == null || nums.length == 0){ return res; } // 排序(升序或者降序都可以),排序是剪枝的前提 Arrays.sort(nums); boolean[] visited = new boolean[nums.length]; dfs(nums, visited, 0); return res; } void dfs(int[] nums, boolean[] visited, int depth){ if (depth == nums.length){ res.add(new ArrayList<>(path)); return; } for(int i = 0; i < nums.length; i++){ if (!visited[i]){ // 剪枝条件:i > 0 是为了保证 nums[i - 1] 有意义 // 写 !visited[i - 1] 是因为 nums[i - 1] 在深度优先遍历的过程中刚刚被撤销选择 if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]){ continue; } visited[i] = true; path.add(nums[i]); dfs(nums, visited, depth + 1); // 回溯部分的代码,和 dfs 之前的代码是对称的 path.remove(path.size() - 1); visited[i] = false; } } } } ``` #### [39. 组合总和](https://leetcode-cn.com/problems/combination-sum/) 难度中等1673 给你一个 **无重复元素** 的整数数组 `candidates` 和一个目标整数 `target` ,找出 `candidates` 中可以使数字和为目标数 `target` 的 **所有不同组合** ,并以列表形式返回。你可以按 **任意顺序** 返回这些组合。 `candidates` 中的 **同一个** 数字可以 **无限制重复被选取** 。如果至少一个数字的被选数量不同,则两种组合是不同的。 对于给定的输入,保证和为 `target` 的不同组合数少于 `150` 个。 **示例 1:** ``` 输入:candidates = [2,3,6,7], target = 7 输出:[[2,2,3],[7]] 解释: 2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选, 7 = 7 。 仅有这两种组合。 ``` **示例 2:** ``` 输入: candidates = [2,3,5], target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]] ``` **示例 3:** ``` 输入: candidates = [2], target = 1 输出: [] ``` **示例 4:** ``` 输入: candidates = [1], target = 1 输出: [[1]] ``` **示例 5:** ``` 输入: candidates = [1], target = 2 输出: [[1,1]] ``` **提示:** - `1 <= candidates.length <= 30` - `1 <= candidates[i] <= 200` - `candidate` 中的每个元素都 **互不相同** - `1 <= target <= 500` 思路**分析:**根据示例 1:输入: candidates = [2, 3, 6, 7],target = 7。 - 候选数组里有 2,如果找到了组合总和为 7 - 2 = 5 的所有组合,再在之前加上 2 ,就是 7 的所有组合; - 同理考虑 3,如果找到了组合总和为 7 - 3 = 4 的所有组合,再在之前加上 3 ,就是 7 的所有组合,依次这找下去。 基于以上的想法,可以画出如下的树形图。建议大家自己在纸上画出这棵树,**这一类问题都需要先画出树形图,然后编码实现**。 以输入:`candidates = [2, 3, 6, 7]`, `target = 7` 为例: ![](https://pic.leetcode-cn.com/1598091943-hZjibJ-file_1598091940241) 说明: - 以 target = 7 为 根结点 ,创建一个分支的时 做减法 ; - 每一个箭头表示:从父亲结点的数值减去边上的数值,得到孩子结点的数值。边的值就是题目中给出的 candidate 数组的每个元素的值; - 减到 0 或者负数的时候停止,即:结点 0 和负数结点成为叶子结点; - 所有从根结点到结点 0的路径(只能从上往下,没有回路)就是题目要找的一个结果。 这棵树有 4 个叶子结点的值 0,对应的路径列表是 [[2, 2, 3], [2, 3, 2], [3, 2, 2], [7]],而示例中给出的输出只有 [[7], [2, 2, 3]]。即:题目中要求每一个符合要求的解是 不计算顺序 的。下面我们分析为什么会产生重复。 **针对具体例子分析重复路径产生的原因(难点)** 友情提示:这一部分我的描述是晦涩难懂的,建议大家先自己观察出现重复的原因,进而思考如何解决。 **产生重复的原因是:在每一个结点,做减法,展开分支的时候,由于题目中说 每一个元素可以重复使用,我们考虑了 所有的 候选数,因此出现了重复的列表。** 一种简单的去重方案是借助哈希表的天然去重的功能,但实际操作一下,就会发现并没有那么容易。 可不可以在搜索的时候就去重呢?答案是可以的。遇到这一类相同元素不计算顺序的问题,我们在搜索的时候就需要 **按某种顺序搜索**。具体的做法是:每一次搜索的时候设置 **下一轮搜索的起点 begin**,请看下图。 ![img](https://pic.leetcode-cn.com/1598091943-GPoHAJ-file_1598091940246) **什么时候使用 used 数组,什么时候使用 begin 变量** 有些朋友可能会疑惑什么时候使用 visited数组,什么时候使用 begin 变量。这里为大家简单总结一下: - 排列问题,讲究顺序(即 [2, 2, 3] 与 [2, 3, 2] 视为不同列表时),需要记录哪些数字已经使用过,此时用 visited数组; - 组合问题,不讲究顺序(即 [2, 2, 3] 与 [2, 3, 2] 视为相同列表时),需要按照某种顺序搜索,此时使用 begin 变量。 **方法一:DFS + 回溯** ```java import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Deque; import java.util.List; public class Solution { public List> combinationSum(int[] candidates, int target) { int len = candidates.length; List> res = new ArrayList<>(); if (len == 0) { return res; } // 排序是剪枝的前提 Arrays.sort(candidates); Deque path = new ArrayDeque<>(); dfs(candidates, 0, len, target, path, res); return res; } private void dfs(int[] candidates, int begin, int len, int target, Deque path, List> res) { // 由于进入更深层的时候,小于 0 的部分被剪枝,因此递归终止条件值只判断等于 0 的情况 if (target == 0) { res.add(new ArrayList<>(path)); return; } // 重点理解这里从 begin 开始搜索的语意 for (int i = begin; i < len; i++) { // 重点理解这里剪枝,前提是候选数组已经有序, if (target - candidates[i] < 0) { break; } path.addLast(candidates[i]); // 注意:由于每一个元素可以重复使用,下一轮搜索的起点依然是 i,这里非常容易弄错 dfs(candidates, i, len, target - candidates[i], path, res); // 状态重置 path.removeLast(); } } } ``` **复杂度分析:** 这个问题的复杂度分析是在我的能力之外的,这里给出我的思考。 我的结论是:时间复杂度与 candidate 数组的值有关: 如果 candidate 数组的值都很大,target 的值很小,那么树上的结点就比较少; 如果 candidate 数组的值都很小,target 的值很大,那么树上的结点就比较多。 所以时间复杂度与空间复杂度不确定。 #### [40. 组合总和 II](https://leetcode-cn.com/problems/combination-sum-ii/) 难度中等773 给定一个数组 `candidates` 和一个目标数 `target` ,找出 `candidates` 中所有可以使数字和为 `target` 的组合。 `candidates` 中的每个数字在每个组合中只能使用一次。 **注意:**解集不能包含重复的组合。 **示例 1:** ``` 输入: candidates = [10,1,2,7,6,1,5], target = 8, 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ] ``` **示例 2:** ``` 输入: candidates = [2,5,2,1,2], target = 5, 输出: [ [1,2,2], [5] ] ``` **提示:** - `1 <= candidates.length <= 100` - `1 <= candidates[i] <= 50` - `1 <= target <= 30` **方法一:DFS + 回溯 + 剪枝** ```java class Solution { List> res = new LinkedList<>(); LinkedList path = new LinkedList<>(); public List> combinationSum2(int[] candidates, int target) { if (candidates == null || candidates.length == 0) return res; boolean[] visited = new boolean[candidates.length]; Arrays.sort(candidates); dfs(candidates, 0, visited, target); return res; } void dfs(int[] candidates, int begin, boolean[] visited, int target){ if (target < 0){ return; } if (target == 0){ res.add(new LinkedList<>(path)); return; } for (int i = begin; i < candidates.length; i++){ if (!visited[i]){ if (i > 0 && candidates[i] == candidates[i - 1] && !visited[i - 1]){ continue; } visited[i] = true; path.add(candidates[i]); dfs(candidates, i, visited, target - candidates[i]); path.removeLast(); visited[i] = false; } } } } ``` #### [77. 组合](https://leetcode-cn.com/problems/combinations/) 难度中等802 给定两个整数 `n` 和 `k`,返回范围 `[1, n]` 中所有可能的 `k` 个数的组合。 你可以按 **任何顺序** 返回答案。 **示例 1:** ``` 输入:n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] ``` **示例 2:** ``` 输入:n = 1, k = 1 输出:[[1]] ``` **提示:** - `1 <= n <= 20` - `1 <= k <= n` **方法一:DFS + 回溯** ```java class Solution { List> res = new ArrayList<>(); List path = new ArrayList<>(); public List> combine(int n, int k) { boolean[] visited = new boolean[n + 1]; dfs(1, n, k, visited); return res; } //因为是组合问题,和顺序无关,所以需要设置begin,从当前元素的下一个元素开始遍历 void dfs(int begin, int n, int k, boolean[] visited){ if (path.size() == k){ res.add(new ArrayList<>(path)); return; } for (int i = begin; i <= n; i++){ if (!visited[i]){ visited[i] = true; path.add(i); dfs(i, n, k, visited); path.remove(path.size() - 1); visited[i] = false; } } } } ``` #### [78. 子集](https://leetcode-cn.com/problems/subsets/) 难度中等1426 给你一个整数数组 `nums` ,数组中的元素 **互不相同** 。返回该数组所有可能的子集(幂集)。 解集 **不能** 包含重复的子集。你可以按 **任意顺序** 返回解集。 **示例 1:** ``` 输入:nums = [1,2,3] 输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] ``` **示例 2:** ``` 输入:nums = [0] 输出:[[],[0]] ``` **提示:** - `1 <= nums.length <= 10` - `-10 <= nums[i] <= 10` - `nums` 中的所有元素 **互不相同** **方法一:DFS + 回溯** ```java class Solution { List> res = new ArrayList<>(); List path = new ArrayList<>(); public List> subsets(int[] nums) { if (nums == null || nums.length == 0){ return res; } boolean[] visited = new boolean[nums.length]; dfs(0, nums, visited); return res; } //因为是组合问题,和顺序无关,所以需要设置begin,从当前元素的下一个元素开始遍历 void dfs(int begin, int[] nums, boolean[] visited){ res.add(new ArrayList<>(path)); for (int i = begin; i < nums.length; i++){ if (!visited[i]){ visited[i] = true; path.add(nums[i]); dfs(i, nums, visited); path.remove(path.size() - 1); visited[i] = false; } } } } ``` #### [90. 子集 II](https://leetcode-cn.com/problems/subsets-ii/) 难度中等709 给你一个整数数组 `nums` ,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。 解集 **不能** 包含重复的子集。返回的解集中,子集可以按 **任意顺序** 排列。 **示例 1:** ``` 输入:nums = [1,2,2] 输出:[[],[1],[1,2],[1,2,2],[2],[2,2]] ``` **示例 2:** ``` 输入:nums = [0] 输出:[[],[0]] ``` **提示:** - `1 <= nums.length <= 10` - `-10 <= nums[i] <= 10` **方法一:DFS + 回溯 + 剪枝** ```java class Solution { List> res = new ArrayList<>(); List path = new ArrayList<>(); public List> subsetsWithDup(int[] nums) { if (nums == null || nums.length == 0){ return res; } boolean[] visited = new boolean[nums.length]; //剪值的前提条件必须数组有序 Arrays.sort(nums); dfs(0, nums, visited); return res; } //因为是组合问题,和顺序无关,所以需要设置begin,从当前元素的下一个元素开始遍历 void dfs(int begin, int[] nums, boolean[] visited){ res.add(new ArrayList<>(path)); for (int i = begin; i < nums.length; i++){ if (!visited[i]){ //剪枝,因为数组中包含重复元素,需要先排序后再可以剪枝 if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]){ continue; } visited[i] = true; path.add(nums[i]); dfs(i + 1, nums, visited); path.remove(path.size() - 1); visited[i] = false; } } } } ``` #### [60. 排列序列](https://leetcode-cn.com/problems/permutation-sequence/) 难度困难608 给出集合 `[1,2,3,...,n]`,其所有元素共有 `n!` 种排列。 按大小顺序列出所有排列情况,并一一标记,当 `n = 3` 时, 所有排列如下: 1. `"123"` 2. `"132"` 3. `"213"` 4. `"231"` 5. `"312"` 6. `"321"` 给定 `n` 和 `k`,返回第 `k` 个排列。 **示例 1:** ``` 输入:n = 3, k = 3 输出:"213" ``` **示例 2:** ``` 输入:n = 4, k = 9 输出:"2314" ``` **示例 3:** ``` 输入:n = 3, k = 1 输出:"123" ``` **提示:** - `1 <= n <= 9` - `1 <= k <= n!` **方法一:DFS + 回溯 + 剪枝** ```java class Solution { List res = new ArrayList<>(); StringBuilder sb = new StringBuilder(); public String getPermutation(int n, int k) { boolean[] visited = new boolean[n + 1]; dfs(n, k, visited); return res.get(k - 1); } //因为是排列问题,和顺序有关,所以不需要设置begin void dfs(int n, int k, boolean[] visited){ if (sb.length() == n){ res.add(sb.toString()); return; } for (int i = 1; i <= n; i++){ if (!visited[i]){ //剪枝 if (res.size() > k){ return; } visited[i] = true; sb.append(i); dfs(n, k, visited); sb.deleteCharAt(sb.length() - 1); visited[i] = false; } } } } ``` #### [93. 复原 IP 地址(难题)](https://leetcode-cn.com/problems/restore-ip-addresses/) 难度中等754 **有效 IP 地址** 正好由四个整数(每个整数位于 `0` 到 `255` 之间组成,且不能含有前导 `0`),整数之间用 `'.'` 分隔。 - 例如:"0.1.2.201" 和 "192.168.1.1" 是 **有效** IP 地址,但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 **无效** IP 地址。 给定一个只包含数字的字符串 `s` ,用以表示一个 IP 地址,返回所有可能的**有效 IP 地址**,这些地址可以通过在 `s` 中插入 `'.'` 来形成。你不能重新排序或删除 `s` 中的任何数字。你可以按 **任何** 顺序返回答案。 **示例 1:** ``` 输入:s = "25525511135" 输出:["255.255.11.135","255.255.111.35"] ``` **示例 2:** ``` 输入:s = "0000" 输出:["0.0.0.0"] ``` **示例 3:** ``` 输入:s = "1111" 输出:["1.1.1.1"] ``` **示例 4:** ``` 输入:s = "010010" 输出:["0.10.0.10","0.100.1.0"] ``` **示例 5:** ``` 输入:s = "101023" 输出:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"] ``` **提示:** - `0 <= s.length <= 20` - `s` 仅由数字组成 **方法一:DFS + 回溯 + 剪枝** 回溯算法事实上就是在一个树形问题上做深度优先遍历,因此 首先需要把问题转换为树形问题。这里请大家一定要拿起纸和笔,模拟一下如何通过指定的字符串 s 生成 IP 地址的过程,把树形图画出来(这一点很重要)。 下面这张图我没有画完(如果画完,枝叶太多),请读者尽量不看我画的这张图,自己动手尝试一下这个问题的树形图应该怎么画。 在画树形图的过程中,你一定会发现有些枝叶是没有必要的,把没有必要的枝叶剪去的操作就是剪枝,在代码中一般通过 break 或者 contine 和 return (表示递归终止)实现。 ![「力扣」第 93 题:复原 IP 地址-1.png](https://pic.leetcode-cn.com/b581bdde1cef982f0af3182af17fc3c41960c76a7445af0dcfd445c89b4c2eaa-%E3%80%8C%E5%8A%9B%E6%89%A3%E3%80%8D%E7%AC%AC%2093%20%E9%A2%98%EF%BC%9A%E5%A4%8D%E5%8E%9F%20IP%20%E5%9C%B0%E5%9D%80-1.png) ```java class Solution { List res = new ArrayList<>(); Deque path = new ArrayDeque<>(4); public List restoreIpAddresses(String s) { int len = s.length(); if (len > 12 || len < 4) { return res; } dfs(s, len, 0, 4); return res; } // 需要一个变量记录剩余多少段还没被分割 private void dfs(String s, int len, int begin, int residue) { if (begin == len) { if (residue == 0) { res.add(String.join(".", path)); } return; } for (int i = begin; i < begin + 3; i++) { if (i >= len) { break; } if (residue * 3 < len - i) { continue; } if (judgeIpSegment(s, begin, i)) { String currentIpSegment = s.substring(begin, i + 1); path.addLast(currentIpSegment); dfs(s, len, i + 1, residue - 1); path.removeLast(); } } } private boolean judgeIpSegment(String s, int left, int right) { int len = right - left + 1; // 大于 1 位的时候,不能以 0 开头 if (len > 1 && s.charAt(left) == '0') { return false; } // 转成 int 类型 int res = 0; while (left <= right) { res = res * 10 + s.charAt(left) - '0'; left++; } return res >= 0 && res <= 255; } } ```