头像

Bug-Free

$ {\color {orange} {\Large{\mathit {AcWing\ University} }} }$




离线:58分钟前


最近来访(1063)
用户头像
A我的pig皮皮
用户头像
我要冷静思考
用户头像
L_52
用户头像
麻酱涮肉
用户头像
从头学习
用户头像
6402
用户头像
钻石镐
用户头像
lirq
用户头像
V-Bronze
用户头像
随便_80
用户头像
随便_80
用户头像
鑫霜
用户头像
1836796ad
用户头像
JaLin
用户头像
贺呵呵
用户头像
CaiJ
用户头像
Yuhan-W
用户头像
南木楠
用户头像
._4
用户头像
muse123

活动打卡代码 AcWing 2154. 梦幻布丁

Bug-Free
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 1000010;

int n, m;
int h[M], e[N], ne[N], idx;
int color[N], sz[M], p[M];
int ans;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
    sz[a] ++ ;
}

void merge(int& x, int& y)
{
    if (x == y) return;
    if (sz[x] > sz[y]) swap(x, y);
    for (int i = h[x]; ~i; i = ne[i])
    {
        int j = e[i];
        ans -= (color[j - 1] == y) + (color[j + 1] == y);
    }
    for (int i = h[x]; ~i; i = ne[i])
    {
        int j = e[i];
        color[j] = y;
        if (ne[i] == -1)
        {
            ne[i] = h[y], h[y] = h[x];
            break;
        }
    }
    h[x] = -1;
    sz[y] += sz[x], sz[x] = 0;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &color[i]);
        if (color[i] != color[i - 1]) ans ++ ;
        add(color[i], i);
    }

    for (int i = 0; i < M; i ++ ) p[i] = i;

    while (m -- )
    {
        int op;
        scanf("%d", &op);
        if (op == 2) printf("%d\n", ans);
        else
        {
            int x, y;
            scanf("%d%d", &x, &y);
            merge(p[x], p[y]);
        }
    }

    return 0;
}



Bug-Free
2个月前
class Solution {
public:
    int lengthOfLastWord(string s) {
        int n = s.size();
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == ' ') continue;
            int j = i - 1;
            while (j >= 0 && s[j] != ' ') j--;
            return i - j;
        }
        return 0;
    }
}



Bug-Free
3个月前
class MyStack {
public:
    queue<int> q1;
    queue<int> q2;
    /** Initialize your data structure here. */
    MyStack() {

    }

    /** Push element x onto stack. */
    void push(int x) {
        q1.push(x);
    }

    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        while(q1.size() > 1 ) {
            q2.push(q1.front());
            q1.pop();
        }
        int ans = q1.front();
        q1.pop();
        while (q2.size()) {
            q1.push(q2.front());
            q2.pop();
        }
        return ans;
    }

    /** Get the top element. */
    int top() {
        while(q1.size() > 1 ) {
            q2.push(q1.front());
            q1.pop();
        }
        int ans = q1.front();
        q1.pop();
        while (q2.size()) {
            q1.push(q2.front());
            q2.pop();
        }
        q1.push(ans);
        return ans;
    }

    /** Returns whether the stack is empty. */
    bool empty() {
        return q1.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */



Bug-Free
3个月前
class MyStack {
public:
    queue<int> q1;
    queue<int> q2;
    /** Initialize your data structure here. */
    MyStack() {

    }

    /** Push element x onto stack. */
    void push(int x) {
        q1.push(x);
    }

    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        while(q1.size() > 1 ) {
            q2.push(q1.front());
            q1.pop();
        }
        int ans = q1.front();
        q1.pop();
        while (q2.size()) {
            q1.push(q2.front());
            q2.pop();
        }
        return ans;
    }

    /** Get the top element. */
    int top() {
        while(q1.size() > 1 ) {
            q2.push(q1.front());
            q1.pop();
        }
        int ans = q1.front();
        q1.pop();
        while (q2.size()) {
            q1.push(q2.front());
            q2.pop();
        }
        q1.push(ans);
        return ans;
    }

    /** Returns whether the stack is empty. */
    bool empty() {
        return q1.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */


活动打卡代码 LeetCode 160. 相交链表

Bug-Free
3个月前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *p = headA, *q = headB;
        while (p != q) {
            if (p) {
                p = p->next;
            } else {
                p = headB;
            }
            if (q) {
                q = q->next;
            } else {
                q = headA;
            }
        }
        return p;
    }
};



Bug-Free
3个月前
/**
 * 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* deleteDuplicates(ListNode* head) {
        ListNode *dummy = new ListNode(-101);
        dummy->next = head;
        ListNode *cur = dummy;
        while (cur && cur->next) {
            while (cur && cur->next &&cur->val == cur->next->val) {
                cur->next = cur->next->next;
            } 
            cur = cur->next;
        }
        return dummy->next;
    }
};



Bug-Free
3个月前
/**
 * 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* deleteDuplicates(ListNode* head) {
        ListNode *dummy = new ListNode(-101);
        dummy->next = head;
        ListNode *cur = dummy;
        while (cur && cur->next) {
            ListNode *last;
            while (cur && cur->next &&cur->val == cur->next->val) {
                cur->next = cur->next->next;
            } 
            cur = cur->next;
        }
        return dummy->next;
    }
};



Bug-Free
3个月前
/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        ListNode v_head(0, head), *fast = head, *slow = &(v_head);
        while (n--) {
            fast = fast->next;
        }
        while (fast) {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return v_head.next;
    }
};



Bug-Free
3个月前
/**
 * 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* swapPairs(ListNode* head) {
        ListNode dummy(0, head);
        ListNode *a = &dummy;
        ListNode *b;
        while (a->next && b->next->next) {
            b = a->next;
            a->next = b->next;
            b->next = b->next->next;
            a->next->next = b;
            a = b;
        }
        return dummy.next;
    }
};



Bug-Free
4个月前

sort

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        for (int i = 0; i < nums2.size(); i++) {
            nums1.push_back(nums2[i]);
        }
        sort(nums1.begin(), nums1.end());
        double t = nums1[nums1.size() / 2];
        if (nums1.size() & 1) {
            return t;
        }
        t = nums1[nums1.size()/2 - 1] + nums1[nums1.size() / 2];
        return t / 2;
    }
};

递归

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        // 如何找到两个有序数组合成一个, 从小大大排列, 第k个数是多少?
        // 解决了这个问题, 就可以找到中位数(当 k = (n+m)/2 的时候)了.
        int total = nums1.size() + nums2.size();
        if (total % 2 == 0)
        {
            int left = findKthNumber(nums1, 0, nums2, 0, total / 2);
            int right = findKthNumber(nums1, 0, nums2, 0, total / 2 + 1);
            return (left + right) / 2.0;
        }
        else
        {
            return findKthNumber(nums1, 0, nums2, 0, total / 2 + 1);
        }
    }

    int findKthNumber(vector<int> &nums1, int i, vector<int> &nums2, int j, int k) {
        if (nums1.size() - i > nums2.size() - j) {
            return findKthNumber(nums2, j, nums1, i, k); 
        }
        if (nums1.size() == i) return nums2[j + k - 1];
        if (k == 1) return min(nums1[i], nums2[j]);
        int si = min(i + k / 2, int(nums1.size())), sj = j + k / 2;
        if (nums1[si - 1] > nums2[sj - 1])
        {
            return findKthNumber(nums1, i, nums2, j + k / 2, k - k / 2);
        }
        else
        {
            return findKthNumber(nums1, si, nums2, j, k - (si - i));
        }
    }
};