leetcode73双周赛

竞赛链接

T1: 6024. 数组中紧跟 key 之后出现最频繁的数字

---

思路

暴力

Code

class Solution {
public:
    unordered_map<int,int>mp;
    int mostFrequent(vector<int>& nums, int key) {
        for(int i=0;i<nums.size()-1;++i){
            if(nums[i]==key)
                mp[nums[i+1]]++;
        }
        int ans=0,shu=0;
        for(auto& i:mp){
            if(i.second>shu){
                shu=i.second;
                ans=i.first;
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度：O((N))
空间复杂度：O((N))

T2: 5217. 将杂乱无章的数字排序

---

思路

模拟，先将数字进行转换并保存，再用sort直接排序即可

Code

class Solution {
public:
    unordered_map<int,int>mp;
    unordered_map<int,int>mp2;
    vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {
        for(int i=0;i<mapping.size();++i){
            mp[i]=mapping[i];
        }
        for(auto& i:nums){
            string ii=to_string(i);
            for(auto& i:ii){
                i=mp[i-'0']+'0';
            }
            int i1=stoi(ii);
            mp2[i]=i1;
        }
        sort(nums.begin(),nums.end(),[&](int a,int b){

            int a1=mp2[a];
            int b1=mp2[b];


            return a1<b1;

        });
        return nums;
    }
};

复杂度分析

• 时间复杂度O((NlogNlogC))。
• 空间复杂度O((N))。

T3: 5300. 有向无环图中一个节点的所有祖先

---

思路

从每个节点开始，往下搜即可，途中将祖宗节点存入之后的结点数组中

Code

class Solution {
public:
    unordered_map<int,vector<int>>f;
    bool flag[1005];
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
        for(auto& i:edges){
            f[i[0]].emplace_back(i[1]);
        }
        vector<vector<int>>ha(n,vector<int>(0));

        auto dfs=[&](auto dfs,int fa,int val)->void{

            for(auto& i:f[val]){
                if(!flag[i]){
                    flag[i]=true;
                    if(i!=fa)
                        ha[i].emplace_back(fa);
                    dfs(dfs,fa,i);
                }
            }
        };
        for(int i=0;i<n;++i){
            memset(flag,false,sizeof(flag));
            dfs(dfs,i,i);
        }
        for(auto& i:ha){
            sort(i.begin(),i.end());
        }

        return ha;
    }
};

复杂度分析

• 时间复杂度：O((N^2+NM/W))
• 空间复杂度：O((N^2))

T4: 5237. 得到回文串的最少操作次数

---

思路

贪心+模拟

Code

class Solution {
public:
    int minMovesToMakePalindrome(string s) {
    int ans=0,n=s.size();
    for(int i=0;i<n/2;i++)
    {
        int cnt=0;
        for(int j=n-i-1;j>i;j--)
        {
            if(s[i]==s[j])
            {
                ans+=cnt;
                while(cnt)//小模拟
                {
                    swap(s[n-i-1-cnt],s[n-i-1-cnt+1]);
                    cnt--;
                }        
                break;
            }
            cnt++;
        }
    }

    return ans;
    }
};

复杂度分析

• 时间复杂度：O((N^2))
• 空间复杂度：O((N))

个人总结

---

本次双周赛，终于AC了！！！
t1看完直接暴力; t2本以为也可以直接暴力，结果tle了，于是优化了一下，然后ac了; t3看了下数据比较小，直接从每个节点开始dfs图+剪枝; t4是模拟+贪心,从两端开始模拟交换即可。