头像

微糖




离线:13小时前


最近来访(3)
用户头像
一切皆有解
用户头像
小马哒哒
用户头像
heydayue


微糖
22小时前
class Solution {
public:
    int maxEqualFreq(vector<int>& nums) {
        //count统计每个数字出现的次数(频率),freq统计次数相同的个数(有多少个频率相同的个数)
        unordered_map<int, int> count, freq;

        int maxFreq = 0, res = 0;

        for(int i = 0; i < nums.size(); i ++ ){
            //统计次数曾经出现过,说明是旧数,频率即将+1,所以要更新freq
            if(count[nums[i]] > 0){
                freq[count[nums[i]]] --;
            }
            //频率+1
            count[nums[i]] ++;
            //更新最大频率
            maxFreq = max(maxFreq, count[nums[i]]);
            //频率的个数+1
            freq[count[nums[i]]] ++;
            //判断是否符合结果
            bool ok = maxFreq == 1 || freq[maxFreq] * maxFreq + freq[maxFreq - 1] * (maxFreq - 1) == i + 1 && freq[maxFreq] == 1 || freq[maxFreq] * maxFreq + 1 == i + 1 && freq[1] == 1;
            if(ok) {
                res = max(res, i + 1);
            }
        }
        return res; 
    }
};



微糖
1天前
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    int maxL = -1, sum = 0;
public:
    int deepestLeavesSum(TreeNode* root) {
        dfs(root, 0);
        return sum;
    }

    void dfs(TreeNode* node, int level){
        if(node == nullptr) return ;

        if(level > maxL){
            maxL = level;
            sum = node -> val;
        }
        else if(level == maxL) sum += node -> val;

    dfs(node -> left, level + 1);
    dfs(node -> right, level + 1);
    }
};


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

微糖
2天前
class OrderedStream {
private:
    vector<string> os;
    int ptr;
public:
    OrderedStream(int n) {
        os = vector<string> (n + 1);
        ptr = 1;
    }

    vector<string> insert(int idKey, string value) {
        os[idKey] = value;
        vector<string> res;
        while(ptr < os.size() && ! os[ptr].empty()){
            res.push_back(os[ptr]);
            ptr ++;
        }
        return res;
    }
};

/**
 * Your OrderedStream object will be instantiated and called as such:
 * OrderedStream* obj = new OrderedStream(n);
 * vector<string> param_1 = obj->insert(idKey,value);
 */



微糖
3天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;
int h[N], e[N], ne[N], idx;
int q[N], d[N];
int n, m;

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

bool topsort(){
    int hh = 0, tt = -1;

    //所有入度为0的点入队
    for(int i = 1; i <= n; i ++ ){
        if(! d[i]){
            q[++ tt] = i;
        }
    }

    while(hh <= tt){
        int t = q[hh ++];

        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            d[j] --;
            if(! d[j]) q[++ tt ] = j;
        }
    }
    //队列长度为n(等于所有点的个数),则说明存在拓扑序列
    return tt == n - 1;
}

int main(){
    cin >> n >> m;

    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i ++ ){
        int a, b;
        cin >> a >> b;
        add(a, b);
        d[b] ++;
    }

    if(topsort()){
        for(int i = 0; i < n; i ++ ) cout << q[i] << " ";
        puts("");
    }
    else
        cout << -1 << endl;

    return 0;
}


活动打卡代码 AcWing 847. 图中点的层次

微糖
3天前
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;
const int N = 100010;
int h[N], e[N], ne[N], d[N], idx;
int n, m;

//h[a]表示a指向的第一条邻边的地址
void insert(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int bfs(){
    queue<int> q;
    q.push(1);
    memset(d, -1, sizeof d);
    d[1] = 0;

    while(! q.empty()){
        int t = q.front();
        q.pop();

        //遍历t的所有邻边
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            //如果j没有被遍历过
            if(d[j] == -1){
                d[j] = d[t] + 1;
                q.push(j);
            }
        }
    }
    return d[n];
}

int main(){
    cin >> n >> m;

    memset(h, - 1, sizeof h);

    //记录邻接表
    for(int i = 0; i < m; i ++ ){
        int a, b;
        cin >> a >> b;
        insert(a, b);
    }

    cout << bfs() << endl;

    return 0;
}



微糖
3天前
class MyCircularDeque {
public:
    vector<int> q;
    int front, rear;
    int capacity;
public:
    MyCircularDeque(int k) {
        q = vector<int> (k + 1);
        front = 0;
        rear = 0;
        capacity = k + 1;
    }

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

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

    bool deleteFront() {
        if(isEmpty()) return false;
        front = (front + 1) % capacity;
        return true;
    }

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

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

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

    bool isEmpty() {
        return (rear - front + capacity) % capacity == 0;
    }

    bool isFull() {
        return (rear + 1) % capacity == front;
    }
};

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque* obj = new MyCircularDeque(k);
 * bool param_1 = obj->insertFront(value);
 * bool param_2 = obj->insertLast(value);
 * bool param_3 = obj->deleteFront();
 * bool param_4 = obj->deleteLast();
 * int param_5 = obj->getFront();
 * int param_6 = obj->getRear();
 * bool param_7 = obj->isEmpty();
 * bool param_8 = obj->isFull();
 */


活动打卡代码 AcWing 4276. 擅长C

微糖
4天前
#include <iostream>
#include <cstring>
#include <vector>
#include <unordered_map>

using namespace std;

//最大单词个数
const int N = 310;
//存储所有单词
string a[N];
//记录字母到字母图形的映射
unordered_map<char, vector<string>> mp;
//字母图形的每一行
string s;

int main(){
    //用于得到每个单词字符串
    string x = "";
    int res = 0;

    //读入字母图形
    for(int i = 0; i < 26; i ++ ){
        char c = char('A' + i);
        for(int j = 0; j < 7; j ++ ){
            cin >> s;
            mp[c].push_back(s);
        }
    }

    //吞掉空格
    getchar();
    getline(cin, s);

    //划分所有单词
    for(int i = 0; i < s.size(); i ++ ){
        if(s[i] >= 'A' && s[i] <= 'Z') x += string(1, s[i]);
        else{
            if(x != "") a[res ++ ] = x;
            x = "";
        }
    }

    if(x != "") a[res ++] = x;

    //遍历每个单词
    for(int i = 0; i < res; i ++ ){
        //得到每个单词的长度
        int len = a[i].size();
        //按行输入单词中每个字母的第j行
        for(int j = 0; j < 7; j ++ ){
            //遍历每个字母
            for(int k = 0; k < len; k ++ ){
                cout << mp[a[i][k]][j];
                if(k != len - 1) cout << " ";
            }
            if(j != 6) cout << endl;
        }
        if(i != res - 1) cout << endl << endl;
    }
    return 0;
}


活动打卡代码 AcWing 846. 树的重心

微糖
5天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
//N代表点数,M代表边数
const int N = 100020, M = 2 * N;
//h存储以u为根结点的第一条邻边的地址
int h[N], e[M], ne[M], idx;
//状态数组,点是否被遍历过
int st[N];
int n;
int ans = N;

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

//返回以u为根结点的子树大小
int dfs(int u){
    //记录u已经被遍历过
    st[u] = true;

    //sum初始表示自己本身就算一个点 res记录当前最大连通块个数
    int sum = 1, res = 0;
    //遍历u的邻边,并不断深搜dfs
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(! st[j]){
            //返回子树大小
            int t = dfs(j);
            res = max(res, t);
            sum += t;
        }
    }
    res = max(res, n - sum);
    ans = min(ans, res);

    return sum;
}

int main(){
    scanf("%d", &n);

    memset(h, -1, sizeof h);

    for(int i = 0; i < n - 1; i ++ ){
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    //1最保险
    dfs(1);

    printf("%d\n", ans);

    return 0;
}



微糖
5天前
//4507.子数组异或和 运用前缀和

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;

const int N = 300010;
int a, s[N], odd[N], even[N], oddcnt, evencnt;
int n;
ll res;

int main(){
    scanf("%d", &n);

    //处理前缀和
    for(int i = 1; i <= n; i ++ ){
        scanf("%d", &a);
        s[i] = s[i - 1] ^ a;
    }

    // !!! i从0开始,表示可以有从开头开始的数组符合条件
    for(int i = 0; i <= n; i ++ ){
        if(i & 1) odd[oddcnt ++ ] = s[i];
        else even[evencnt ++ ] = s[i];
    }

    //排序方便处理
    sort(odd, odd + oddcnt);
    sort(even, even + evencnt);

    // !!! 防止快指针j跑到odd[oddcnt] 使得odd[j]=odd[i]
    for(ll i = 0, j = 0; i < oddcnt; i = j){
        while(odd[i] == odd[j]) j ++;
        res += (j - i ) * (j - i - 1ll) >> 1;
    }

    for(ll i = 0, j = 0; i < evencnt; i = j){
        while(even[i] == even[j]) j ++;
        res += (j - i) * (j - 1ll - i) >> 1;
    }

    printf("%lld\n", res);

    return 0;
}




微糖
5天前
class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int len = arr.size();
        long long s1[len + 1], s2[len + 1];
        s1[0] = arr[0];
        for(int i = 1; i < len; i ++) s1[i] = s1[i - 1] + arr[i];
        sort(arr.begin(), arr.end());
        s2[0] = arr[0];
        for(int i = 1; i < len; i ++ ) s2[i] = s2[i - 1] + arr[i];

        int res = 0;
        for(int i = 0; i < len; i ++ ){
            if(s1[i] == s2[i]) res++;
        } 
        return res;
    }
};