「LeetCode」第73场双周赛 题解

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

Code

class Solution {
    
public:
    int mostFrequent(vector<int>& nums, int key) {
    
        int n = nums.size();
        int ans = 0;
        unordered_map<int, int> mp;
        for (int i = 0; i <= n - 2; i++) {
    
            /* 统计key之后元素的个数, 更新最大元素的个数 */
            if (nums[i] == key && ++mp[nums[i + 1]] > mp[ans]) {
    
                ans = nums[i + 1];
            }
        }
        return ans;
    }
};

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

Code

class Solution {
    
public:
    int cal(vector<int>& mapping, int num) {
    
        string str = to_string(num);
        int ans = 0;
        for (int i = 0; i < str.length(); i++)
            ans = ans * 10 + mapping[str[i] - '0'];  // 这样做顺便去除了前导0
        return ans;
    }
    
    vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {
    
        pair<int, int> p[nums.size()];
        for (int i = 0; i < nums.size(); i++) {
    
            int val = cal(mapping, nums[i]);
            p[i] = {
    val, i};
        }
        
        sort(p, p + nums.size());
        vector<int> res;
        for (auto x : p) res.push_back(nums[x.second]);
        
        return res;
    }
};

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

题目描述

Code

class Solution {
    
private:
    vector<vector<int>> g, res;
    int n;
    
public:
    void bfs(int i) {
    
        vector<bool> vis(n);
        queue<int> q;
        q.push(i);
        vis[i] = true;
        
        while (q.size()) {
    
            int t = q.front();
            q.pop();
            
            for (auto v : g[t])   
                if (!vis[v]) {
    
                    vis[v] = true;
                    res[v].push_back(i);  // 对于i能到达的所有点的集合中加入i
                    q.push(v);
                }
        }
    }
    
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
    
        this->n = n;
        g = vector<vector<int>>(n);
        res= vector<vector<int>>(n);
        
        for (auto &edge : edges)    g[edge[0]].push_back(edge[1]);
        for (int i = 0; i < n; i++) bfs(i);
        
        for (int i = 0; i < n; i++) sort(res[i].begin(), res[i].end());  // 对每个点进行排序
            
        return res;
    }
};

5237. 得到回文串的最少操作次数(贪心 + 双指针)

题目描述

解题思路

因为输入数据确保了字符串一定能变成一个回文串，当字符串的长度为奇数时必然存在一个字符的出现次数是奇数，即最后当左指针指向只剩最后一个没成组的该字符时，左右指针会相遇，该字符应当放在字符串的中间。当字符串的长度为偶数时，双指针不可能相遇，安心模拟就好了
贪心，固定左指针所指向的字符，若右指针指向的字符和左指针相同无需额外操作，将左右指针都同时移动，判断下一组。
否则让右指针寻找与左指针所指相同的字符，
若右指针没有与左指针相遇，找到左指针所指的字符，将其逐步交换到原先右指针的位置，交换完成后，将左右指针都同时移动，判断下一组。
否则右指针与左指针相遇，说明该字符的出现次数是奇数且是最后一个没成组的，先直接记录将其交换到中间的位置的步数，并将左指针移动，判断下一组。
这个逐步交换操作实际上是将字符串的其他出现次数为偶数的字符处理完毕之后再进行的，这样可以保证是最少的操作次数，因为题目没有要求返回最后的回文串，只简单要求统计最少操作次数，所以先直接记录步数到答案中，最后将这个字符逐步交换到中间可以不做。
时间复杂度：O(n²)
TIPS: 对于贪心的证明参考此处

Code

class Solution {
    
public:
    int minMovesToMakePalindrome(string s) {
    
        int left = 0, right = s.length() - 1;
        int res = 0;
        
        while (left < right) {
    
            char c = s[left];  // 固定左指针所指向的字符
            int t = right;  // 代替右指针进行寻找的变量
            while (s[t] != c)   t--;
            if (t > left) {
     // 若右指针没有与左指针相遇
                res += right - t;
                while (t < right) {
    
                    swap(s[t], s[t + 1]);
                    t++;
                }
                left++, right--;
            }else {
    // 双指针相遇将出现次数为奇数的字符逐步交换至中间的操作实际上要到最后将其他出现次数为偶数的字符交换好再进行
                res += (s.length() >> 1) - t;
                left++;
            }
        }
        return res;
    }
};