头像

陌上青花_4




在线 


最近来访(13)
用户头像
种花家的兔兔
用户头像
软萌嘤嘤嘤
用户头像
妮可_
用户头像
vclip
用户头像
小猪快跑ya
用户头像
nickxiao
用户头像
ambie
用户头像
倾心_4
用户头像
coolcoder
用户头像
听我说谢谢你
用户头像
可爱抱抱呀
用户头像
csdoge
用户头像
acwing_7793


PS:吃完饭忘了写题解了

细节有点多

我们可以用两个map来操作,map1是存这个数出现了几次,map2是存出现这么多少次的数一共有几种
题目说只能变换一次,所以map2中最多只能有两种不同的种类,这个可以证明:
假如map2中有三类数,例如1出现1次,2出现2次,3出现3次,那么我们不管怎么变换,都做不到只修改一次就能使剩下不同的数出现的次数是一样的,所以map2中最多只能有两类数,我们来讨论一下:

第一种情况:当map2中后面的次数刚好为前面的次数+1,并且后面的种类只有一种,我们举例,例如2出现2次,3出现3次,这时只需要删除3一次即可使他们次数相同,所以这是一种情况

第二种情况:当map2中前一次出现次数为1并且种类为1时,我们举例:1出现1次,2出现2次,删除1一次,1没有了,剩下的就是两种出现次数为2的数了,符合题意

当然,我们上面是在讨论当map2的大小为2时的情况,那么map2大小为1时,即里面不同的数出现次数一样是,有没有情况也满足题意呢,答案是有的,这很容易忽略:

第一种情况:这map2里唯一的出现的次数是1,我们举例,1出现1次,2出现1次,3出现1次,那么我们不管删除那个,都不影响其他数的次数,都还是1次,符合题意

第二种情况:这map2里出现这个次数的数就一种,我们举例,5出现5次,那么我们不管删除那次,都还剩它自己,他自己肯定等于他自己,所以符合题意

所以情况就是这些了,其他的都不满足题意了,所以我们模拟一变即可

下见代码

class Solution {
public:
    int res=1,q,h,num1,num2;
    map<int,int> mp1,mp2;  //mp1存这个数出现了几次,mp2存出现了这么多次的数有几种
    int maxEqualFreq(vector<int>& nums) {
    for(int i=0;i<nums.size();i++)
    {
         if(mp1.count(nums[i]))   //如果以前这个数出现过,我们就要把他加入到新的出现次数中,旧的出现次数-1,例如2以前出现过2次,现在在出现就是3次了,所以mp2[3]++,mp2[2]--;
         {
            mp1[nums[i]]++;
            mp2[mp1[nums[i]]]++;
            mp2[mp1[nums[i]]-1]--;
            if(mp2[mp1[nums[i]]-1]==0)
            mp2.erase(mp1[nums[i]]-1);     //如果某个次数里的种类经此操作变成0了,就删除他
         }
         else  //没出现过直接加即可
         {
            mp1[nums[i]]++;
            mp2[mp1[nums[i]]]++;
         }
         if(mp2.size()==2)      //先讨论mp2大小为2的情况
         {
             q=-1,h=-1,num1=0,num2=0;
               for(auto it=mp2.begin();it!=mp2.end();it++)
               {
                   if(it==mp2.begin())
                   {
                       q=it->first;
                       num1=it->second;
                   }
                   else
                   {
                       h=it->first;
                       num2=it->second;
                   }
               }
               if(h==q+1&&num2==1||q==1&&num1==1)
               res=max(res,i+1);
         }
         if(mp2.size()==1)     //讨论mp2大小为1的情况
         {
             if(mp2.begin()->first==1||mp2.begin()->second==1)
             res=max(res,i+1);
         }
    }
    return res;
    }
};



class Solution {
public:
    int res=1,q,h,num1,num2;
    map<int,int> mp1,mp2;
    int maxEqualFreq(vector<int>& nums) {
    for(int i=0;i<nums.size();i++)
    {
         if(mp1.count(nums[i]))
         {
            mp1[nums[i]]++;
            mp2[mp1[nums[i]]]++;
            mp2[mp1[nums[i]]-1]--;
            if(mp2[mp1[nums[i]]-1]==0)
            mp2.erase(mp1[nums[i]]-1);
         }
         else
         {
            mp1[nums[i]]++;
            mp2[mp1[nums[i]]]++;
         }
         if(mp2.size()==2)
         {
             q=-1,h=-1,num1=0,num2=0;
               for(auto it=mp2.begin();it!=mp2.end();it++)
               {
                   if(it==mp2.begin())
                   {
                       q=it->first;
                       num1=it->second;
                   }
                   else
                   {
                       h=it->first;
                       num2=it->second;
                   }
               }
               if(h==q+1&&num2==1||q==1&&num1==1)
               res=max(res,i+1);
         }
         if(mp2.size()==1)
         {
             if(mp2.begin()->first==1||mp2.begin()->second==1)
             res=max(res,i+1);
         }
    }
    return res;
    }
};



class Solution {
public:
    int deep=0,ans=0;
    TreeNode* root_next;
    int deepestLeavesSum(TreeNode* root) {
    root_next=root;
    dfs1(root_next,0);
    dfs2(root,0);
    return ans;
    }
    void dfs1(TreeNode* root, int pos)
    {
        deep=max(deep,pos);
        if(root->left!=nullptr)
        dfs1(root->left,pos+1);
        if(root->right!=nullptr)
        dfs1(root->right,pos+1);
        return;
    }
    void dfs2(TreeNode* root, int pos)
    {
        if(pos==deep)
        {
            ans+=root->val;
            return;
        }
        if(root->left!=nullptr)
        dfs2(root->left,pos+1);
        if(root->right!=nullptr)
        dfs2(root->right,pos+1);
        return;
    }
};



题目要加和所以处在最深层的数字,然后返回
我们可以用两个dfs来解决
一个来找最深层是多少层并记录,另一个找哪些点处在最深层,并加和,最后返回ans

class Solution {
public:
    int deep=0,ans=0;  //deep深度,ans最后总和
    TreeNode* root_next;
    int deepestLeavesSum(TreeNode* root) {
    root_next=root;
    dfs1(root_next,0);   //用来找最大深度
    dfs2(root,0);        //用来加和
    return ans;
    }
    void dfs1(TreeNode* root, int pos)
    {
        deep=max(deep,pos);   //更新最大深度
        if(root->left!=nullptr)
        dfs1(root->left,pos+1);
        if(root->right!=nullptr)
        dfs1(root->right,pos+1);
        return;
    }
    void dfs2(TreeNode* root, int pos)
    {
        if(pos==deep)   //符合条件,加和
        {
            ans+=root->val;
            return;
        }
        if(root->left!=nullptr)
        dfs2(root->left,pos+1);
        if(root->right!=nullptr)
        dfs2(root->right,pos+1);
        return;
    }
};



题有点难读,但读懂后实现起来还是容易的,下见代码

class OrderedStream {
public:
    string u[1010];          //存储字符串的地方
    int ptr=1,xz,bj[1010]={0};  //xz----限制,防止下面我们遍历数组时越界,bj-----标记数组,看看这个数有没有被用过
    OrderedStream(int n) {
    xz=n;
    }

    vector<string> insert(int idKey, string value) {
    vector<string> vec;
    u[idKey]=value;
    bj[idKey]=1;
    while(ptr<=xz&&bj[ptr])  //即防越界又要保证这个数被用过
    {
        vec.push_back(u[ptr]);
        ptr++;
    }
    return vec;
    }
};


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

class OrderedStream {
public:
    string u[1010];
    int ptr=1,xz,bj[1010]={0};
    OrderedStream(int n) {
    xz=n;
    }

    vector<string> insert(int idKey, string value) {
    vector<string> vec;
    u[idKey]=value;
    bj[idKey]=1;
    if(idKey==ptr)
    {
    vec.push_back(value);
    ptr++;
    while(ptr<=xz&&bj[ptr])
    {
        vec.push_back(u[ptr]);
        ptr++;
    }
    return vec;
    }
    else
    return vec;
    }
};



ps:上午事太多了,来的有点晚
用vector模拟即可,要前插用insert,后插用push,前删用erase,后删用pop

class MyCircularDeque {
public:
    int l=0,r=0,xz;
    vector<int> vec;
    MyCircularDeque(int k) {
    xz=k;
    }

    bool insertFront(int value) {
    if(vec.size()<xz)
    {
    vec.insert(vec.begin(),value);
    return true;
    }
    else
    return false;
    }

    bool insertLast(int value) {
    if(vec.size()<xz)
    {
    vec.push_back(value);
    return true;
    }
    else
    return false;
    }

    bool deleteFront() {
    if(!vec.empty())
    {
    vec.erase(vec.begin());
    return true;
    }
    else
    return false;
    }

    bool deleteLast() {
    if(!vec.empty())
    {
    vec.pop_back();
    return true;
    }
    else
    return false;
    }

    int getFront() {
    if(!vec.empty())
    {
    return vec[0];
    }
    else
    return -1;
    }

    int getRear() {
    if(!vec.empty())
    {
    return vec[vec.size()-1];
    }
    else
    return -1;
    }

    bool isEmpty() {
    if(!vec.empty())
    {
    return false;
    }
    else
    return true;
    }

    bool isFull() {
    if(vec.size()==xz)
    {
    return true;
    }
    else
    return false;
    }
};



class MyCircularDeque {
public:
    int l=0,r=0,xz;
    vector<int> vec;
    MyCircularDeque(int k) {
    xz=k;
    }

    bool insertFront(int value) {
    if(vec.size()<xz)
    {
    vec.insert(vec.begin(),value);
    return true;
    }
    else
    return false;
    }

    bool insertLast(int value) {
    if(vec.size()<xz)
    {
    vec.push_back(value);
    return true;
    }
    else
    return false;
    }

    bool deleteFront() {
    if(!vec.empty())
    {
    vec.erase(vec.begin());
    return true;
    }
    else
    return false;
    }

    bool deleteLast() {
    if(!vec.empty())
    {
    vec.pop_back();
    return true;
    }
    else
    return false;
    }

    int getFront() {
    if(!vec.empty())
    {
    return vec[0];
    }
    else
    return -1;
    }

    int getRear() {
    if(!vec.empty())
    {
    return vec[vec.size()-1];
    }
    else
    return -1;
    }

    bool isEmpty() {
    if(!vec.empty())
    {
    return false;
    }
    else
    return true;
    }

    bool isFull() {
    if(vec.size()==xz)
    {
    return true;
    }
    else
    return false;
    }
};


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

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

using namespace std;

typedef long long LL;

const int N = 300010, Base = 2e9 + 1;
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 4581. 数列

#include <bits/stdc++.h>
using namespace std;
const int mod = 9e6;
int a,b,ax,by,m,k;
string n;
int main ()
{
    cin>>a>>b>>ax>>by>>m>>k>>n;
    int x=0;
    for(int i=0;i<n.size();i++)
    {
        x=x*10+n[i]-'0';
        x%=mod;
    }
    for(int i=1;i<=x;i++)
    {
        int c=ax*b+by*a;
        c%=m;
        a=b;
        b=c;
    }
    for(int i=1;i<=k;i++)
    {
        int c=ax*b+by*a;
        c%=m;
        a=b;
        b=c;
        cout<<a<<endl;
    }
    return 0;
}