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.
Sample
Data scale
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.
Sample
Data scale
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.
Sample
Data scale
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.
Sample
Data scale
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;
}
};