算法复习记录
可能会有些乱

1. 数组处理

过滤器模板
26. 删除有序数组中的重复项 - 力扣（LeetCode）

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int idx = 0;
        for (int i = 0; i < nums.size(); i++) 
            if (i == 0 || nums[i] != nums[i - 1])
                nums[idx++] = nums[i];
        return idx;
    }
};

283. 移动零 - 力扣（LeetCode）

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = 0;
        for (int i = 0; i < nums.size(); i++) 
            if (nums[i] != 0)
                nums[n++] = nums[i];
        while (n < nums.size())
            nums[n++] = 0;
    }
};

88. 合并两个有序数组 - 力扣（LeetCode）

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1, j = n - 1;
        for (int k = m + n - 1; k >= 0; k--) 
            if (j < 0 || i >= 0 && nums1[i] >= nums2[j])
                nums1[k] = nums1[i--];
            else
                nums1[k] = nums2[j--];
    }
};

2. 链表处理

206. 反转链表 - 力扣（LeetCode）

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur != nullptr) {
            ListNode* nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
};

25. K 个一组翻转链表 - 力扣（LeetCode）

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* protect = new ListNode(0, head);
        ListNode* last = protect;
        // 分组遍历
        while (head != nullptr) {
            // 1. 分组
            ListNode* end = getKth(head, k);
            if (end == nullptr) break; // 此分组不够k即为最后一组直接退出
            ListNode* nextHead = end->next;
            // 2. 内部反转
            reverse(head, nextHead);
            // 3. 组间重连
            head->next = nextHead;
            last->next = end;
            // 指针后移
            last = head;
            head = nextHead;
        }
        return protect->next;
    }

private:
    ListNode* getKth(ListNode* node, int k) {
        while (node != nullptr) {
            k--;
            if (k == 0) return node;
            node = node->next;
        }
        return nullptr;
    }
    void reverse(ListNode* begin, ListNode* end) {
        ListNode* last = begin;
        begin = begin->next;
        while (begin != end) {
            ListNode* next = begin->next;
            begin->next = last;
            last = begin;
            begin = next;
        }
    }
};

136. 邻值查找 - AcWing题库

#include<bits/stdc++.h>
using namespace std;
struct Node {
    int val, idx;
    Node* pre, * next;
};
const int SIZE = 100005;
int a[SIZE], ans[SIZE], rk[SIZE];
Node* pos[SIZE];
int n;
Node* AddNode(Node* node, int idx) {
    Node* newNode = new Node();
    newNode->idx = idx;
    newNode->val = a[idx];
    newNode->next = node->next; node->next->pre = newNode;
    node->next = newNode; newNode->pre = node;
    return newNode;
}
Node* DeleteNode(Node* node) {
    node->pre->next = node->next;
    node->next->pre = node->pre;
    delete node;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)  {
        cin >> a[i];
        rk[i] = i;
    }
    sort(rk + 1, rk + n, [&](int rki, int rkj) { return a[rki] < a[rkj]; }); // 此处要排序rk，其中rk从下标1到n，所以sort参数应该为rk+1到rk+n+1才对。但报错，改为rk+n就AC了。。纳闷~
    Node head, tail;
    head.next = &tail, tail.pre = &head;
    head.val = a[rk[1]] - 1e9;
    tail.val = a[rk[n]] + 1e9;
    for (int i = 1; i <= n; i++) 
        pos[rk[i]] = AddNode(tail.pre, rk[i]);
    for (int i = n; i > 1; i--) {
        Node* cur = pos[i];
        if (cur->val - cur->pre->val <= cur->next->val - cur->val)
            ans[i] = cur->pre->idx;
        else
            ans[i] = cur->next->idx;
        DeleteNode(cur);
    }
    for (int i = 2; i <= n; i++)
        cout << abs(a[ans[i]] - a[i]) << ' ' << ans[i] << endl;
}