6024. The number that appears most frequently immediately after the key in the array

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++) {
            /* Count the number of elements after the key and update the maximum number of elements */
            if (nums[i] == key && ++mp[nums[i + 1]] > mp[ans]) {
                ans = nums[i + 1];
            }
        }
        return ans;
    }
};

5217. Sort messy numbers

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'];  // This removes the leading 0 by the way
        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. All ancestors of a node in a directed acyclic graph(BFS)

Title Description

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);  // Add i to the set of all points i can reach
                    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());  // Sort each point
            
        return res;
    }
};

5237. Get the minimum number of operations of the palindrome string (greedy + double pointer)

Title Description

Problem solving ideas

Because the input data ensures that the string can become a palindrome string. When the length of the string is odd, there must be an odd number of occurrences of a character, that is, when the left pointer points to the last character that is not grouped, the left and right pointers will meet, and the character should be placed in the middle of the string. When the length of the string is even, the double pointers cannot meet. It's good to simulate at ease
Greedy, fix the character pointed by the left pointer. If the character pointed by the right pointer is the same as the left pointer, no additional operation is required. Move the left and right pointers at the same time to judge the next group.
Otherwise, let the right pointer look for the same character as the left pointer,
If the right pointer does not meet the left pointer, find the character indicated by the left pointer and gradually exchange it to the original position of the right pointer. After the exchange is completed, move the left and right pointers at the same time to judge the next group.
Otherwise, if the right pointer meets the left pointer, it means that the number of occurrences of the character is odd and the last one is not grouped. First, directly record the steps to exchange it to the middle position, and move the left pointer to judge the next group.
This step-by-step exchange operation is actually carried out after other characters with an even number of occurrences of the string are processed, which can ensure the minimum number of operations. Because the title does not require the return of the last palindrome string, it simply requires the statistics of the minimum number of operations, so first record the steps directly into the answer, Finally, this character is gradually exchanged to the middle, which can be omitted.
Time complexity: O(n) ²)
TIPS: proof reference for greed here

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];  // Fixed the character pointed to by the left pointer
            int t = right;  // Variable to find instead of the right pointer
            while (s[t] != c)   t--;
            if (t > left) { // If the right pointer does not meet the left pointer
                res += right - t;
                while (t < right) {
                    swap(s[t], s[t + 1]);
                    t++;
                }
                left++, right--;
            }else {// When the double pointer meets, the operation of gradually exchanging the characters with odd occurrences to the middle actually needs to be carried out until the other characters with even occurrences are exchanged at the end
                res += (s.length() >> 1) - t;
                left++;
            }
        }
        return res;
    }
};