始まりと終わりのプロローグ
-Turning Point-
数组 二分 704. 二分查找 35. 搜索插入位置
在数组中搜索元素的题通常都可以用二分。但要注意前提是该数组有序 。
关于二分的边界条件 ：
while(left <= right) 必须是 <= ，因为 left 和 right 是有可能相等的。同理left 更新时是 mid + 1 ， right 更新时是 mid - 1 。
704. 二分查找 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution {public : int search (vector<int >& nums, int target) int n = nums.size (); int l = 0 , r = n - 1 ; int mid = 0 ; while (l <= r) { mid = (l + r) / 2 ; if (nums[mid] > target) { r = mid - 1 ; } else if (nums[mid] < target) { l = mid + 1 ; } else return mid; } return -1 ; } };
双指针 27. 移除元素 977. 有序数组的平方
这类题往往用暴力需要两层 for 循环。如果在第一层循环时能够记录一些信息提供给第二层循环，则可以考虑使用双指针。
27. 移除元素 1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution {public : int removeElement (vector<int >& nums, int val) int l = 0 ; int n = nums.size (); for (int r = 0 ; r < n; r ++) { if (val != nums[r]) { nums[l++] = nums[r]; } } return r; } };
但双指针不一定要是都向同一个方向运动，也可以是从数组两端向中间走。
977. 有序数组的平方 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution {public : vector<int > sortedSquares (vector<int >& nums) { int n = nums.size (); int k = n - 1 ; vector<int > ans (n, 0 ) ; int l = 0 , r = n - 1 ; while (l != r) { int a = nums[l] * nums[l]; int b = nums[r] * nums[r]; if (a >= b) { ans[k --] = a; l ++; } else { ans[k --] = b; r --; } } ans[0 ] = nums[l] * nums[l]; return ans; } };
滑动窗口 209. 长度最小的子数组
本质也是双指针。适用于求解数组中的子数组 的情况。
209. 长度最小的子数组 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : int minSubArrayLen (int target, vector<int >& nums) int n = nums.size (); int l = 0 , r = 0 ; int sum = 0 , res = 0 ; int len = INT_MAX; for (r = 0 ; r < n; r ++) { sum += nums[r]; while (sum >= target) { len = min (len, r - l + 1 ); sum -= nums[l ++]; } } if (len == INT_MAX) return 0 ; return len; } };
链表 链表定义 1 2 3 4 5 6 7 struct ListNode { int val; ListNode* next; ListNode () : val (0 ), next (nullptr ) {} ListNode (int x) : val (x), next (nullptr ) {} ListNode (int x, ListNode *next) : val (x), next (next) {} };
删除元素 203. 移除链表元素
对链表进行删除时一定要注意判断链表是否为空，以及对头结点的特殊操作。虚拟头结点 ，这样就不用针对头结点特判，也是一个实用的技巧。
203. 移除链表元素 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : ListNode* removeElements (ListNode* head, int val) { ListNode* dummyHead = new ListNode (0 , head); ListNode* cur = dummyHead; while (cur->next != nullptr ) { ListNode* tmp = cur->next; if (tmp->val == val) { cur->next = tmp->next; delete tmp; } else { cur = cur->next; } } head = dummyHead->next; delete dummyHead; return head; } };
反转链表 206. 反转链表
原本想的是定义一个新链表，然后把旧链表元素依次插到新表头。但是显然复杂度比较高。next 指针的朝向。
206. 反转链表 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution {public : ListNode* reverseList (ListNode* head) { ListNode* pre = nullptr ; ListNode* cur = head; ListNode* tmp; while (cur) { tmp = cur->next; cur->next = pre; pre = cur; cur = tmp; } return pre; } };
交换结点 24. 两两交换链表中的节点
用到了前面提到的虚拟头结点。
24. 两两交换链表中的节点 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : ListNode* swapPairs (ListNode* head) { ListNode* dummyHead = new ListNode (0 , head); ListNode* cur = dummyHead; while (cur->next != nullptr && cur->next->next != nullptr ) { ListNode* t = cur->next; ListNode* t1 = cur->next->next->next; cur->next = cur->next->next; cur->next->next = t; cur->next->next->next = t1; cur = cur->next->next; } return dummyHead->next; } };
链表中的双指针 19.删除链表的倒数第 N 个结点
双指针的经典应用。fast 先移动 n 个位置，再让 slow 指针一起移动。
19. 删除链表的倒数第 N 个结点 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution {public : ListNode* removeNthFromEnd (ListNode* head, int n) { ListNode* dummyHead = new ListNode (0 , head); ListNode* fast = dummyHead; ListNode* slow = dummyHead; while (n-- && fast->next != nullptr ) { fast = fast->next; } while (fast->next != nullptr ) { fast = fast->next; slow = slow->next; } if (n == 1 ) { delete fast; return head; } ListNode* tmp = slow->next; slow->next = tmp->next; delete tmp; return dummyHead->next; } }
142. 环形链表 II
两种解法：详解看这里
142. 环形链表 II 解法一
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution {public : ListNode *detectCycle (ListNode *head) { ListNode* fast = head; ListNode* slow = head; while (fast != NULL && fast->next != NULL ) { fast = fast->next->next; slow = slow->next; if (slow == fast) { ListNode* p = head; ListNode* t = fast; while (p != t) { p = p->next; t = t->next; } return p; } } return NULL ; } };
解法二
1 2 3 4 5 6 7 8 9 10 11 12 class Solution {public : ListNode *detectCycle (ListNode *head) { unordered_set<ListNode*> visited; while (head != NULL ) { if (visited.count (head)) return head; visited.insert (head); head = head->next; } return NULL ; } };
设计链表 707. 设计链表
模拟，注意 index 从 0 开始。
class MyLinkedList {
public:
struct ListNode {
int val;
ListNode* next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
MyLinkedList() {
dummyHead = new ListNode(0);
size = 0;
}
int get(int index) {
if (index < 0 || index > size - 1) return -1;
ListNode* cur = dummyHead->next;
while (index --) cur = cur->next;
return cur->val;
}
void addAtHead(int val) {
ListNode* node = new ListNode(val, dummyHead->next);
dummyHead->next = node;
size ++;
}
void addAtTail(int val) {
ListNode* cur = dummyHead;
while (cur->next != nullptr) {
cur = cur->next;
}
ListNode* node = new ListNode(val);
cur->next = node;
size ++;
}
void addAtIndex(int index, int val) {
if (index > size) return;
ListNode* cur = dummyHead;
ListNode* node = new ListNode(val);
while (index --) cur = cur->next;
node->next = cur->next;
cur->next = node;
size ++;
}
void deleteAtIndex(int index) {
if (index < 0 || index > size - 1) return;
ListNode* cur = dummyHead;
while (index --) cur = cur->next;
ListNode* tmp = cur->next;
cur->next = tmp->next;
delete tmp;
size --;
}
private:
int size;
ListNode* dummyHead;
};
