Neo's Blog

//单链表 —— 模板题 AcWing 826. 单链表
// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}

// 将头结点删除，需要保证头结点存在
void remove()
{
    head = ne[head];
}

//双链表 —— 模板题 AcWing 827. 双链表
// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;

// 初始化
void init()
{
    //0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// 在节点a的右边插入一个数x
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}

// 删除节点a
void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}

一般哈希 —— 模板题 AcWing 840. 模拟散列表
(1) 拉链法
    int h[N], e[N], ne[N], idx;

    // 向哈希表中插入一个数
    void insert(int x)
    {
        int k = (x % N + N) % N;
        e[idx] = x;
        ne[idx] = h[k];
        h[k] = idx ++ ;
    }

    // 在哈希表中查询某个数是否存在
    bool find(int x)
    {
        int k = (x % N + N) % N;
        for (int i = h[k]; i != -1; i = ne[i])
            if (e[i] == x)
                return true;

        return false;
    }

(2) 开放寻址法
    int h[N];

    // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
    int find(int x)
    {
        int t = (x % N + N) % N;
        while (h[t] != null && h[t] != x)
        {
            t ++ ;
            if (t == N) t = 0;
        }
        return t;
    }

class Solution {
public:
    /*
    int lowbit(int n) {
        return n & (~n);
    }
    */
    vector<int> countBits(int num) {
        vector<int> dp(num + 1);
        for (int i = 1; i <= num; ++i) {
            dp[i] = dp[i & i - 1] + 1; //每次n&n-1会抹掉最后一个1
        }

        return dp;
    }
};

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        //1~N
        //一定可以为i找到一个合适的坑；
       for (int i = 1; i <= n; ++i) {
           int x = nums[i - 1];
            while (x >= 1 && x <= n && x != nums[x - 1]) {
                swap(nums[x - 1], nums[i - 1]);
                x = nums[i - 1];
            }
       }

       for (int i = 1; i <= n; ++i) {
           if (nums[i - 1] != i) {
               return i;
           }
       }

       return n + 1;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* successor;

    //非递归实现
    ListNode* reverseN(ListNode* head, int n) {
        ListNode* pre = NULL;
        auto cur = head;
        while (cur && n > 0) {
            auto next = cur->next; //记录下一个cur
            cur->next = pre; //核心步骤---操作cur的next指针，让其指向pre；
            pre = cur;  //记录前一个
            cur = next; //给下一个cur赋值
            n--;
        }

        head->next = cur;
        return pre;
    }

    ListNode* reverseN(ListNode* head, int n) {
        if (!head) return head;
        //base 
        if (n == 1) {
            successor = head->next; //这一步特别关键，记录当前元素的后继节点，则外面会使用。
            return head;
        }

        //子问题-下一个节点
        auto x = reverseN(head->next, n - 1);
        //head->next 是递归之前的头，也就是递归之后的尾巴
        (head->next)->next = head;
        head->next = successor;
        return x;
    }

    ListNode* reverseBetween(ListNode* head, int m, int n) {
        //base
        if (m == 1) {
            return reverseN(head, n);
        }

        auto x = reverseBetween(head->next, m - 1, n - 1);
        head->next = x;
        return head; //返回的是头
    }
};

/**
 * 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* reverse(ListNode* head, ListNode* tail) {
        if (head == tail) return head;

        auto x = reverse(head->next, tail);
        head->next->next = head;
        head->next = NULL;
        return tail;
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        if (!head) return head;

        auto p = head;
        ListNode* pre = NULL;
        for (int i = 0; i < k; ++i) { 
            //base 不足k个
            if (!p) return head;
            pre = p;
            p = p->next;
        }

        //反转
        reverse(head, pre);

        auto x = reverseKGroup(p, k);
        head->next = x;
        return pre;
    }
};