Leetcode第73场双周赛解题报告

史高，撞大运，可能是题太简单了

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

知识点：模拟
使用map记录符合目标条件的数字，然后找到最大即可

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

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

知识点：模拟

根据题意，将原数组按规则进行替换，并且保留原有的index。
将替换完的数组进行排序，然后得到排序完的index，从原数组中取出index，然后拼接为答案。

/**
 * @param {number[]} mapping
 * @param {number[]} nums
 * @return {number[]}
 */
var sortJumbled = function(mapping, nums) {
    let arr = []
    for(let i = 0;i < nums.length;i++) arr.push([nums[i].toString(),i])
    const getN =(old)=> {
        let res = "";
        for(let i = 0;i < old.length;i++) {
            const n = old.charCodeAt(i)-"0".charCodeAt(0)
            const x = mapping[n]
            res += x
        }
        return res
    }
    arr.forEach(x=>x[0]=parseInt(getN(x[0])))
    arr.sort((x,y)=>x[0]-y[0])
    console.log(arr)
    const ans = []
    arr.forEach(x=>ans.push(nums[x[1]]))
    return ans
};

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

知识点：搜索
效率：$O(n)$

目的是输出所有当前节点的父节点的集合，保证没有重复
可以使用拓扑排序，然而不是求序列，是求所有父节点，直接搜索就可以
注意搜索有个优化，可以记录访问次数，等待所有父亲都访问完以后再向下搜索，可以合并路径

class Solution {
public:
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
        vector<int> in(n,0);
        vector<int> out(n,0);
        vector<int> nowin(n,0);
        vector<vector<int>> p(n);
        vector<set<int>> ans(n);
        for(auto i :edges) {
            out[i[0]]++;
            in[i[1]]++;
            p[i[0]].push_back(i[1]);
        }
        std::function<void(set<int>&,int)> search = [&ans,&nowin,&in,&p,&search](set<int> &f,int now){
            nowin[now]++;
            //cout << now << ":" << nowin[now] << "?" << in[now]<<endl;
            for(auto i:f) ans[now].insert(i);
            if(nowin[now]>=in[now]) {
                auto x = ans[now];
                x.insert(now);
                for(auto i : p[now]) search(x,i);
            }
        };
        for(int i = 0;i < n;i++){
            //cout << "in" << i << " " << in[i] << endl;
            if(in[i]==0) {
                set<int> n;
                search(n,i);
            }
        }
        
        vector<vector<int>> aa(n);
        for(int i = 0;i < n;i++) {
            for(auto j : ans[i]) aa[i].push_back(j);
        }
        return aa;
    }
};

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

知识点：贪心
效率：$O(n)$
从两边向中间遍历即可

class Solution {
public:
    int minMovesToMakePalindrome(string s) {
        int n = s.size();
        int last;
        int before = n - 1;
        int now = 0;
        for (int i = 0; i < before; i++) {
            last = before;
            while (s[i] != s[last]) last--;
            char tmp;
            if (i == last) {
                now += n / 2 - i;
                continue;
            }
            if (s[i] == s[last]) {
                now += before - last;
                tmp = s[last];
                int l = last;
                for (; l < before; l++)  s[l] = s[l + 1];
                s[l] = tmp;
                before--;
            }
        }
        return now;
    }
};