头像

番茄酱

NJUPT


访客:17915

离线:2小时前



class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {
        int n = A.size();
        for (int i = 0; i < n; i++) A.push_back(A[i]);
        vector<int> s(n * 2 + 1);
        for (int i = 1; i <= n * 2; i++) s[i] = s[i - 1] + A[i - 1];
        deque<int> q;
        int res = INT_MIN;
        q.push_back(0);
        for (int i = 1; i <= n * 2; i++) {
            if (q.size() && i - n > q.front()) q.pop_front();
            res = max(res, s[i] - s[q.front()]);
            while (q.size() && s[q.back()] >= s[i]) q.pop_back();
            q.push_back(i);
        }
        return res;
    }
};



class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> res;
        deque<int> q;
        for (int i = 0; i < n; i++) {
            if (q.size() && i - k + 1 > q.front()) q.pop_front();
            while (q.size() && nums[q.back()] <= nums[i]) q.pop_back();
            q.push_back(i);
            if (i >= k - 1) res.push_back(nums[q.front()]);
        }
        return res;
    }
};


活动打卡代码 LeetCode 155. Min Stack

class MinStack {
public:
    /** initialize your data structure here. */

    stack<int> stk, stk_min;

    MinStack() {

    }

    void push(int x) {
        stk.push(x);
        if (stk_min.size()) x = min(x, stk_min.top());
        stk_min.push(x);
    }

    void pop() {
        stk.pop();
        stk_min.pop();
    }

    int top() {
        return stk.top();
    }

    int getMin() {
        return stk_min.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */



class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        int i = 0, j = n - 1;
        while (i < j) {
            if (nums[i] + nums[j] < target) i++;
            else if (nums[i] + nums[j] > target) j--;
            else return {i + 1, j + 1};
        }
        return {};
    }
};



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


活动打卡代码 LeetCode 88. Merge Sorted Array

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> res;
        int i = 0, j = 0;
        while (i < m && j < n) {
            if (nums1[i] < nums2[j]) res.push_back(nums1[i++]);
            else res.push_back(nums2[j++]);
        }
        while (i < m) res.push_back(nums1[i++]);
        while (j < n) res.push_back(nums2[j++]);
        nums1 = res;
    }
};



class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        int i = 0, j = n - 1;
        while (i < j) {
            if (nums[i] + nums[j] < target) i++;
            else if (nums[i] + nums[j] > target) j--;
            else return {i + 1, j + 1};
        }
        return {};
    }
};


活动打卡代码 AcWing 263. 作诗

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>

using namespace std;

const int N = 100010, M = sqrt(N) + 10;

int n, c, m, B, sz;
int belong[N], L[M], R[M];
int a[N], s[M][N]; // s[i][j]表示前1~i块中j出现的次数
int f[M][M]; // f[i][j] 表示i~j块中出现次数为正偶数的不同的数的个数
int cnt[N]; // cnt[i]表示i出现的次数

void build() {
    B = sqrt(n), sz = (n - 1) / B + 1;
    for (int i = 1; i <= n; i++) belong[i] = (i - 1) / B + 1;
    for (int i = 1; i <= sz; i++) L[i] = (i - 1) * B + 1, R[i] = L[i] + B - 1;
    R[sz] = n;
}

// x在[l,r]块中出现的次数
int get(int l, int r, int x) {
    return s[r][x] - s[l - 1][x];
}

// [l,r]之间出现次数为正偶数次的不同的数的个数
int query(int l, int r) {
    int res = 0;
    if (belong[l] == belong[r]) {
        for (int i = l; i <= r; i++) {
            cnt[a[i]]++;
            if (cnt[a[i]] % 2 == 0) res++;
            else if (cnt[a[i]] > 1) res--;
        }
        for (int i = l; i <= r; i++) cnt[a[i]]--;
        return res;
    }
    res = f[belong[l] + 1][belong[r] - 1];
    for (int i = l; i <= R[belong[l]]; i++) {
        cnt[a[i]]++;
        int t = get(belong[l] + 1, belong[r] - 1, a[i]);
        int x = cnt[a[i]] + t;
        if (x % 2 == 0) res++;
        else if (x > 1) res--;
    }
    for (int i = L[belong[r]]; i <= r; i++) {
        cnt[a[i]]++;
        int t = get(belong[l] + 1, belong[r] - 1, a[i]);
        int x = cnt[a[i]] + t;
        if (x % 2 == 0) res++;
        else if (x > 1) res--;
    }
    for (int i = l; i <= R[belong[l]]; i++) cnt[a[i]]--;
    for (int i = L[belong[r]]; i <= r; i++) cnt[a[i]]--;
    return res;
}

int main() {
    cin >> n >> c >> m;
    build();
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= sz; i++) {
        for (int j = 1; j <= c; j++) s[i][j] = s[i - 1][j];
        for (int j = L[i]; j <= R[i]; j++) s[i][a[j]]++;
    }
    for (int i = 1; i <= sz; i++) {
        int ans = 0; // ans表示起始块为i时,到每一个结束块之间的答案
        for (int j = L[i]; j <= n; j++) {
            cnt[a[j]]++;
            if (cnt[a[j]] % 2 == 0) ans++;
            else if (cnt[a[j]] > 1) ans--;
            if (j == R[belong[j]]) f[i][belong[j]] = ans;
        }
        for (int j = L[i]; j <= n; j++) cnt[a[j]]--;
    }
    int last = 0;
    while (m--) {
        int l, r;
        scanf("%d%d", &l, &r);
        l = (l + last) % n + 1;
        r = (r + last) % n + 1;
        if (l > r) swap(l, r);
        printf("%d\n", last = query(l, r));
    }
    return 0;
}



class Solution {
public:
    bool canArrange(vector<int>& arr, int k) {
        unordered_map<int, int> mp;
        int n = arr.size();
        for (auto x : arr) mp[(x % k + k) % k]++;
        int cnt = 0;
        for (int i = 0; i <= k / 2; i++) {
            if (i == 0 || i == k - i) cnt += mp[i] / 2;
            else cnt += min(mp[i], mp[k - i]);
        }
        return cnt == n / 2;
    }
};


新鲜事 原文

一人血书进阶课y总提早开课