LeetCode双周赛73（Cpp+Golang）

题意：

给定一个数组，要求找出所有在key之后出现的数字当中，频数最高的那个数

思路：

用一个map保存出现次数，遍历一遍之后返回结果

代码（Cpp）：

class Solution {
public:
    int mostFrequent(vector<int>& nums, int key) {
        map<int,int>mp;
        int id=0,maxx=0;
        for(int i=1;i<nums.size();i++){
            if (nums[i-1]==key){
                mp[nums[i]]++;
                if(mp[nums[i]]>maxx){
                    maxx=mp[nums[i]];
                    id=nums[i];
                        
                }
                
            }
        }
        return id;
    }
};

题意：

给定一个数组和一个映射规则，要求将数组中的数字转换为映射之后的数字，进行排序，根据映射值的大小排序原数组的值，要求是一个稳定的排序，即相同映射值的数据相对位置不变。

思路：

直接模拟，转换成字符串，根据映射替换，求出映射值，然后排序，用一个结构体保存原数据、映射值、原位置。

代码（Cpp）：

struct node{
    int val,id,org;
    bool operator<(node b){
        if (val==b.val)return id<b.id;
        return val<b.val;
    }
};

class Solution {
public:
    vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {
        vector<node>p(nums.size());
        int n=nums.size();
        for(int i=0;i<n;i++){
            stringstream ss;
            string s;
            ss<<nums[i];
            ss>>s;
            int r=0;
            for(int i=0;i<s.size();i++){
                r=r*10+mapping[s[i]-0];
            }
            p[i].val=r,p[i].id=i,p[i].org=nums[i];
        }
        
        sort(p.begin(),p.end());
        for(int i=0;i<n;i++){
            nums[i]=p[i].org;
        }
        return nums;
    }
};

题意：

给定一个有向无环图，要求找出该节点的所有祖先。

思路：

利用 bitset 进行化简运算，对于条有向边，用a[i] |= a[k] 表示将 k 的所有父节点赋值到 i 结点上，最后根据操作结果将所有节点的祖先保存为二维数组并返回。

代码author：

代码（Cpp）：

class Solution {
public:
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& e) {
        bitset<1000> a[1000];
        for (int i = 0; i < e.size(); i++)
        {
            a[e[i][0]][e[i][1]] = 1;
        }
        for (int k = 0; k < n; k++)
        {
            for (int i = 0; i < n; i++)
            {
                if (a[i][k])
                {
                    a[i] |= a[k];
                }
            }
        }
        vector<vector<int> > z;
        for (int i = 0; i < n; i++)
        {
            vector<int> b;
            for (int j = 0; j < n; j++)
            {
                if (a[j][i])
                {
                    b.push_back(j);
                }
            }
            z.push_back(b);
        }
        return z;
    }
};

题意：

给定一个字符串，每次操作是交换相邻的两个字符，要求用最少的次数使得该字符串变成回文串。

思路一：

贪心。没做出来，根据

每次将第一个字符固定，从末端寻找相同字符，移到当前状态的末端。下一次从前端第二个字符开始，重复该算法。以此将问题分割成一系列子问题。如果找不到，就要将当前首字符移动到字符串的中间位置。

代码一（Golang）：

func minMovesToMakePalindrome(s string) int {
    n,ans:=len(s),0
    sb:=make([]byte,n)
    for i:=range s{
        sb[i]=s[i]
    }
    for i,j:=0,n-1;i<j;i++{
        for k:=j;i!=k;k--{
            if sb[i]==sb[k]{
                for ;k<j;k++{
                    sb[k],sb[k+1]=sb[k+1],sb[k]
                    ans++
                }
            }
        }
        ans+=n-i+1
        
    }
}

思路二：

根据。将问题转换为一个逆序对问题，用树状数组求解。