头像

acwing_78697




在线 


最近来访(1)
用户头像
2580000


acwing_78697
3分钟前
class Solution {
public:
    int busyStudent(vector<int>& startTime, vector<int>& endTime, int queryTime) {
        int ret[1010] = {0};
        for(int i = 0;i < startTime.size();i++){
            ret[startTime[i]]++;
            ret[endTime[i] + 1]--;
        }
        for(int i = 1;i < 1010;i++){
            ret[i] += ret[i - 1];
        }
        return ret[queryTime];
    }
};



acwing_78697
21小时前
class Solution {
public:
    int hash[100010] = {0};
    int ret = 1;

    int maxEqualFreq(vector<int>& nums) {
        map<int,int>m; // 前一个是频率,后一个是次数
        set<int> s;
        for(int j = 0;j < nums.size();j++)
            s.insert(nums[j]);
        if (s.size() == 1)  return nums.size();
        else if(s.size() == nums.size())    return nums.size();
        int i = 0;
        for(i = 0;i < nums.size();i++){
            int x = ++hash[nums[i]];
            if(m.count(x - 1)){
                if(m[x - 1] == 1)   m.erase(x - 1);
                else    m[x - 1] --;
            }
            m[x] ++;
            auto pv = -- m.end();
            if(m.size() == 2 && ((m.begin()->first == 1 && m.begin()->second == 1) || (pv->first == m.begin()->first + 1 && pv->second == 1)))   ret = i;
        }
        return ret + 1;
    }
};



class Solution {
public:
    vector<int> f;

    void dfs(TreeNode* T,int depth){
        if(!T)  return;
        if(!T->left && !T->right){
            f[depth] += T->val;
            return;
        }
        if(T->left) dfs(T->left,depth + 1);
        if(T->right)    dfs(T->right,depth + 1);
    }

    int deepestLeavesSum(TreeNode* root) {
        this->f = vector<int>(10010,0);
        dfs(root,1);
        for(int i = f.size() - 1;i >= 0;i--)
            if(f[i])    return f[i];
        return 0;
    }
};


活动打卡代码 LeetCode 1656. 设计有序流

class OrderedStream {
private:
        int ptr;
        vector<string> s;
public:
    OrderedStream(int n) {
        ptr = 1;
        s.resize(n + 1);
    }

    vector<string> insert(int idKey, string value) {
        s[idKey] = value;
        vector<string> ret;
        if(idKey == ptr){
            while(ptr < s.size() && s[ptr] != ""){
                ret.push_back(s[ptr]);
                this->ptr ++;
            }
        }
        return ret;
    }
};




class MyCircularDeque {
private:
    vector<int> a;
    int capacity;
    int front,rear;
    int size;

public:
    MyCircularDeque(int k) {
        capacity = k + 1;
        front = 0;
        rear = 0;
        size = 0;
        a = vector<int>(k + 1);
    }

    bool insertFront(int value) {
        if(!isFull()){
            if(front != rear)   front = (front - 1 + capacity) % capacity;
            a[front] = value;
            if(rear == front)   rear++;
            size++;
            return true;
        }
        return false;
    }

    bool insertLast(int value) {
        if(!isFull()){
            a[rear] = value;
            rear = (rear + 1) % capacity;
            size ++;
            return true;
        }
        return false;
    }

    bool deleteFront() {
        if(size > 0){
            front = (front + 1) % capacity;
            size--;
            return true;
        }
        return false;
    }

    bool deleteLast() {
        if(size > 0){
            rear = (rear - 1 + capacity) % capacity;
            size--;
            return true;
        }
        return false;

    }

    int getFront() {
        if(!isEmpty())
            return a[front];
        return -1;
    }

    int getRear() {
        if(!isEmpty())
            return a[(rear - 1 + capacity) % capacity];
        return -1;
    }

    bool isEmpty() {
        return size == 0;
    }

    bool isFull() {
        return size == capacity - 1;
    }
};




活动打卡代码 AcWing 4507. 子数组异或和

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;
const int N = 300010;
int ret;
int a[N];

int main(){
    int n;
    cin >> n;
    unordered_map<int,int> hash[2];
    int sum = 0;
    hash[0][0]++;
    long long res = 0;
    for(int i = 1; i <= n;i++){
        cin >> a[i];
        sum ^= a[i];
        res += hash[i & 1][sum];
        hash[i & 1][sum]++;
    }

    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 4508. 移动的点

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 300010, Base = 111;
const LL Zero = 1e9;

int n, a, b;

int main()
{
    scanf("%d%d%d", &n, &a, &b);
    unordered_map<LL, int> hash1, hash2;

    while (n -- )
    {
        int vx, vy;
        scanf("%*d%d%d", &vx, &vy);
        hash1[vy - (LL)a * vx] ++ ;
        hash2[(vx + Zero) * Base + vy + Zero] ++ ;
    }

    LL res = 0;
    for (auto& [k, v]: hash1) res += v * (v - 1ll);
    for (auto& [k, v]: hash2) res -= v * (v - 1ll);

    printf("%lld\n", res);
    return 0;
}



活动打卡代码 AcWing 4405. 统计子矩阵

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 510;
int f[N][N];
int n,m,k;

int main(){
    cin >> n >> m >> k;
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++){
            int x;
            cin >> x;
            f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + x;
            //cout << f[i][j] << endl;
        }

    long res = 0;
    for(int i = 1;i <= n;i++){
        for(int j = i;j <= n;j++){
            for(int l = 1,r = 1;r <= m;r++){
                while(l <= r && f[j][r] - f[i - 1][r] - f[j][l - 1] + f[i - 1][l - 1] > k)  l++;
                if(l <= r)  res += r - l + 1;
            }
        }
    }
    cout << res << endl;
    return 0;
}



class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        stack<int> st;
        st.push(arr[0]);
        for(int i = 1;i < arr.size();i++){
            if(arr[i] >= st.top()){
               st.push(arr[i]);
            }
            else{
                int mx = st.top();
                st.pop();
                while(!st.empty() && arr[i] < st.top()){
                    st.pop();
                }
                st.push(mx);
            }
        }
        return st.size();
    }
};


活动打卡代码 LeetCode 1282. 用户分组

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        multimap<int,int>m;
        for(int i = 0;i < groupSizes.size();i++)
            m.emplace(groupSizes[i],i);
        vector<vector<int>> ret;
        vector<int>tmp;
        auto pv = m.begin();
        while(pv != m.end()){
            tmp.clear();   
            auto temp = pv;
            for(int i = 0;i < temp->first;i++){
                tmp.push_back(pv->second);
                pv++;
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};