HOT100与剑指Offer

---

前言

一个本硕双非的小菜鸡，备战24年秋招，计划刷完hot100和剑指Offer的刷题计划，加油！
根据要求，每一道题都要写出两种以上的解题技巧。

一、56. 合并区间（HOT100）

156. 合并区间
Note：贪心解题
先排序，让所有的相邻区间尽可能的重叠在一起
如果前一个右边界大于后一个左边界，证明是重叠，需要合并区间
用合并区间后左边界和右边界，作为一个新的区间，加入到result数组里就可以了。如果没有合并就把原区间加入到result数组

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> res;if (intervals.size() == 0) return res;sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});res.push_back(intervals[0]);for (int i = 1; i < intervals.size(); i++) {if (res.back()[1] >= intervals[i][0])res.back()[1] = max(res.back()[1], intervals[i][1]);elseres.push_back(intervals[i]);}return res;}
};

Note：双指针解题

1. 对 vector<vector> 排序，需要按照先比较区间开始，如果相同再比较区间结束，使用默认的排序规则即可
2. 使用双指针，左边指针指向当前区间的开始
3. 使用一个变量来记录连续的范围 t
4. 右指针开始往后寻找，如果后续的区间的开始值比 t 还小，说明重复了，可以归并到一起
5. 此时更新更大的结束值到 t
6. 直到区间断开，将 t 作为区间结束，存储到答案里
7. 然后移动左指针，跳过中间已经合并的区间

    vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end());vector<vector<int>> ans;for (int i = 0; i < intervals.size();) {int t = intervals[i][1];int j = i + 1;while (j < intervals.size() && intervals[j][0] <= t) {t = max(t, intervals[j][1]);j++;}ans.push_back({ intervals[i][0], t });i = j;}return ans;}

二、23. 链表中环的入口结点（剑指Offer）

链表中环的入口结点

Note：经典解法，
可以使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。
然后从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *entryNodeOfLoop(ListNode *head) {ListNode* fast = head;ListNode* slow = head;while (fast != NULL && fast->next != NULL) {slow = slow->next;fast = fast->next->next;if (slow == fast) {slow = head;while (fast != slow) {fast = fast->next;slow = slow->next;}return slow;}}return NULL;}
};

Note：哈希表解答
声明了一个大小为1010的整型数组 N 并初始化所有元素为0，这个数组用于存储访问过的节点的值，用来判断节点是否已经被访问过。
开始循环，存储。
如果当前节点的值已经在数组 N 中，说明已经访问过这个节点，因此这个节点是环的入口节点。函数返回当前节点的指针

class Solution {
public:ListNode *entryNodeOfLoop(ListNode *head) {int N[1010] = {0};while(head){if(!N[head->val]) N[head->val] = 1;else return head;head = head->next;}return NULL;}
};

总结

祝大家都能学有所成，找到一份好工作！