# Game 73 biweekly

## subject

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

### General idea of the topic

Give you an integer array nums with subscript starting from 0, and give you an integer key, which has appeared in nums.

Count the occurrence times of different integer targets that appear immediately after the key in the num array. In other words, the number of occurrences of target is the number of i that meet the following conditions:

• 0 <= i <= n - 2
• Num [i] = = key and
• nums[i + 1] == target .

Please return the target that appears the most times. The test data ensures that the target with the most occurrences is unique.

### thinking

I haven't done questions and played games for too long. The first question was WA twice.

Wrong reading at the beginning: accident as long as t a r g e t target target in k e y key After the key, I didn't realize that the two must be next to each other.

Consider using map < int, int > MP to record the number of all elements, then traverse num to ensure num [i] = = key, and then take num [i + 1] with the largest number, which is the required target.

### code

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

## subject

5217. Sort messy numbers

### General idea of the topic

Give you an integer array mapping with subscript starting from 0, which represents the mapping rule of a decimal number. mapping[i] = j means that digit I is mapped to digit j under this rule.

The mapped value of an integer is to map each digit I (0 < = I < = 9) of the original number to mapping[i].

In addition, we give you an integer array nums. Please sort each number in the array nums according to their mapped corresponding number in non decreasing order and return it.

be careful:

• If two numbers have the same size after mapping, they are sorted according to the relative order in the input.
• The elements in num only need to be compared according to the mapped value when sorting, and the returned value should be the input element itself.

### thinking

This question is WA again: the reason is that it is not considered when decomposing numbers 0 0 0.

A structure Node is defined to record the original value p, the index position id and the mapped value w.

Define sorting order: sort each number in the array nums according to the non decreasing order of the corresponding number after mapping. If the corresponding number after mapping is the same size, sort them according to the relative order in the input.

Then decompose and map the numbers in nums, store them in the Node array, sort them, and then directly return the sorted results.

### code

```struct Node{
int w,id,p;
};
bool cmp(Node x,Node y){
if(x.w==y.w)return x.id<y.id;
return x.w<y.w;
}
class Solution {
public:
Node a[30000+50];
vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {
int cnt=0;
for(auto it:nums){
vector<int>b;
int x=it,y=0;
if(it==0){
cnt++;
a[cnt].id=cnt;a[cnt].w=mapping[0];a[cnt].p=it;
continue;
}
while(x){
int q=x%10;
x/=10;
b.push_back(q);
}
for(int i=b.size()-1;i>=0;i--){
int q=mapping[b[i]];
y=y*10+q;
}
cnt++;
a[cnt].id=cnt;a[cnt].w=y;a[cnt].p=it;
}
sort(a+1,a+1+cnt,cmp);
vector<int>ans;
for(int i=1;i<=cnt;i++)ans.push_back(a[i].p);
return ans;
}
};
```

## subject

5300. All ancestors of a node in a directed acyclic graph

### General idea of the topic

Give you a positive integer n, which represents the number of nodes in a directed acyclic graph. The node numbers are 0 to n - 1 (including both).

Give you a two-dimensional integer array edges, where edges[i] = [fromi, toi] represents a one-way edge from fromi to toi in the figure.

Please return an array answer, where answer[i] is all the ancestors of the ith node, and these ancestor nodes are sorted in ascending order.

If u can reach V through a series of edges, then we call node u the ancestor of node v.

### thinking

The extreme case is 1000 1000 1000 points, no more than 2000 2000 2000 edges, directly considering each point i i i what points can be reached from the start.

How to consider it?

For example, the condition gives a directed edge a − > b a->b a − > b, then it means a a a yes b b b's ancestors, then we can consider building edges in reverse b − > a b->a b − > A, from point b b b departure, arrival point a a a.

Then, for all edges, reverse the edge as above, and then start from any point i i i start, then all the points it can traverse are points i i The ancestor of i (and the data ensures that there is no self ring), and then add the points to the vector array to ensure the order from small to large.

### code

```class Solution {
public:
vector<int>e[1000+50];
int vis[1000+50];
void dfs(int x,int f){
vis[x]=1;
for(int i=0;i<e[x].size();i++){
if(!vis[e[x][i]]){
dfs(e[x][i],x);
}
}
}
vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
for(int i=0;i<edges.size();i++){
for(int j=0;j<edges[i].size();j++){
int x=edges[i][0],y=edges[i][1];
e[y].push_back(x);
}
}
vector<vector<int> >ans;
for(int i=0;i<n;i++){
memset(vis,0,sizeof(vis));
dfs(i,i);
vector<int>a;
for(int j=0;j<n;j++){
if(i==j||!vis[j])continue;
a.push_back(j);
}
ans.push_back(a);
}
return ans;
}
};
```

## subject

5237. Get the minimum number of operations of the palindrome string

### General idea of the topic

Give you a string s that contains only lowercase letters.

For each operation, you can select two adjacent characters in s and exchange them.

Please return the minimum number of operations to turn s into a palindrome string.

Note that the input data will ensure that s will become a palindrome string.

### thinking

Judge whether the string can become a palindrome string

• The corresponding character cannot be found from the right:
• The string length is even and cannot have a quantity of 1 1 Characters of 1
• The length of the string is odd, and only one quantity can be 1 1 Characters of 1
• The corresponding characters can be found from the right:
• At this time, move the character to the right position where the left character is symmetrical, and the front and rear characters move backward and forward respectively

The problem turns to: complete the string every time (...) Convert to X (...) x. Then convert to XY (...) YX until it becomes symmetrical.

code:

### code

```class Solution {
public:
int minMovesToMakePalindrome(string s) {
int n=s.length();
int k=n-1,flag,ans;
ans=flag=0;
for(int i=0;i<k;i++){
for(int j=k;j>=i;j--){
if(j==i){
flag=1;
ans=ans+n/2-i;
}
else if(s[i]==s[j]){
for(int o=j;o<k;o++){
swap(s[o],s[o+1]);
ans++;
}
k--;
break;
}
}
}
return ans;
}
};
```

Keywords: leetcode

Added by metalblend on Sun, 06 Mar 2022 11:47:09 +0200