头像

仅仅刷题




离线:5天前


活动打卡代码 AcWing 786. 第k个数

#include <iostream>

using namespace std;

int n,k;
const int N = 100010;
int q[N];

int quick_sort(int l,int r,int k)
{
    if(l == r) return q[l];

    int x = q[l],i = l - 1,j = r + 1;
    while (i < j)
    {
        do i++;while(q[i] < x);
        do j--;while(q[j] > x);

        if(i < j) swap(q[i],q[j]);
    }
    int sl = j - l + 1;
    if(k <= sl)return quick_sort(l,j,k);
    else return quick_sort(j + 1,r,k - sl);
}

int main()
{
    cin >> n >> k;
    for(int i = 0; i < n; i++ ) cin >> q[i];

    cout << quick_sort(0,n - 1,k)<<endl;

    return 0;
}


活动打卡代码 AcWing 785. 快速排序

#include <iostream>

using namespace std;

const int N = 1e6 + 10;
int n;
int q[N];

void quick_sort(int q[],int l,int r)
{
    if(l >= r) return;
    int x = q[(l + r + 1) / 2], i = l - 1, j = r + 1;
    while(i < j)
    {
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j) swap(q[i],q[j]);
    }

    quick_sort(q,l,i - 1);
    quick_sort(q,i,r);
}

int main()
{
    scanf("%d",&n);
    for(int i = 0; i < n; i ++) scanf("%d",&q[i]);

    quick_sort(q,0,n - 1);

    for(int i = 0; i < n; i++) printf("%d ",q[i]);

    return 0;
}



/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplication(ListNode* head) {
        auto dummy = new ListNode(-1);
        dummy->next = head;
        auto p = dummy;

        while (p->next)
        {
            auto q = p->next;
            while(q->next && p->next->val == q->next->val) q = q->next;

            if(q == p->next) p = q;
            else p->next = q->next;
        }

        return dummy->next;
    }
};



/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        auto 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;

    }
};


活动打卡代码 AcWing 35. 反转链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next) return head;

        auto p = head , q = p->next;
        while(q)
        {
            auto o = q->next;
            q->next = p;
            p = q, q = o;
        }
        head->next = NULL;
        return p;

    }
};



class Solution {
public:
    int strToInt(string str) {
        int k = 0;
        while (k < str.size() && str[k] == ' ') k++;
        long long number = 0;
        bool is_mins = false;
        if(str[k] == '+') k++;
        else if(str[k] == '-') k++, is_mins = true;
        while (k < str.size() && str[k] >= '0' && str[k] <= '9')
        {
            number = number*10 + str[k] - '0';
            k++;
        }
        if (is_mins) number *= -1;
        if(number > INT_MAX) number = INT_MAX;
        if(number < INT_MIN) number = INT_MIN;

        return (int)number;

    }
};


活动打卡代码 AcWing 78. 左旋转字符串

class Solution {
public:
    string leftRotateString(string str, int n) {
        return str.substr(n) + str.substr(0,n);

    }
};



/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        auto dummy = new ListNode(-1),tail = dummy;
        while (l1 && l2)
        if(l1->val < l2->val)
        {
            tail = tail->next = l1;
            l1 = l1 ->next;
        }
        else
        {
            tail = tail->next = l2;
            l2 = l2->next;
        }

        if(l1) l1->next = l1;
        if(l2) l2->next = l2;

        return dummy->next;
    }  
};




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

    }
};


活动打卡代码 AcWing 84. 求1+2+…+n

class Solution {
public:
    int getSum(int n) {
        int res = n;
        n > 0 && (res += getSum(n - 1));

        return res;

    }
};