Catalogue of series articles

Force deduction hot question brushing record

preface

Make a little progress every day!!

1, Background

For a group of people, there are two information about them. The first is the height information, and the second is how many people are taller (> =) than them in front of them. According to these information, they are sorted to meet the requirements.

The data format is [height, number of people taller than themselves]

As shown below:

Title:

Source: force buckle
Link: https://leetcode-cn.com/problems/queue-reconstruction-by-height/

2, My thoughts

Sorry, I can't do it, but I wrote the code myself. The idea is to see the official prompt.

Describe the following ideas:
There are n empty positions in total. Sort the original data first, and sort each height from low to high. Each person's information shows that the height of the person in front of it does not affect where it stands. Therefore, if there is ki taller than him in front of it, leave ki space for those tall people and stand at the position of ki +1.

The code is as follows:

class Solution {
public:
    static bool cmp(vector<int>a,vector<int>b){
        if(a[0]!=b[0]) return a[0]<b[0];
        else return a[1] > b[1];//Put the one with large k value in front
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        //If the label is greedy, try it
        //Let's look at the solution and do it

        vector<vector<int> > my_vec(people.size(),vector<int>(people[0].size(),-1));
        sort(people.begin(),people.end(),cmp);
        //cout<<people[0][0]<<endl;
        for (int i=0;i<people.size();i++)
        {
            //Traverse the empty bits and find the current element ki. Before inserting, ensure that there are ki empty bits in front of you and put yourself in the ki +1 position
            for ( int count=0,j=0;j<people.size();j++)
            {
                if ( my_vec[j][1]==-1)
                {
                    count++;
                }
                if (count== people[i][1]+1){
                    //cout<<"count--"<<count<<endl;
                    my_vec[j][0]= people[i][0];
                    my_vec[j][1]= people[i][1] ;
                    break;
                }
            }           
        }        
        return my_vec;
    }
};

Here are two things to note:
First, cmp comparison function, according to the height from low to high, but the number of people higher than themselves is sorted from large to small. The reason is very simple. If the height is the same, the people in front will not affect their standing position. According to the number of people higher than themselves, those with large values will go to the standing position first (think carefully, if those with small values go to the team, then the current element will be affected by the people in front, because they are the same height).

Second, the cmp function is placed in the class as a non static member function pointer, while the sort function requires a static member function pointer, so you need to add a static. Otherwise, it will be placed outside the class. (the reason is that the class member function depends on a specific object)

3, Official thinking

1. Low to high ranking, station position

As I said above, the code is attached:

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), [](const vector<int>& u, const vector<int>& v) {
            return u[0] < v[0] || (u[0] == v[0] && u[1] > v[1]);
        });
        int n = people.size();
        vector<vector<int>> ans(n);
        for (const vector<int>& person: people) {
            int spaces = person[1] + 1;
            for (int i = 0; i < n; ++i) {
                if (ans[i].empty()) {
                    --spaces;
                    if (!spaces) {
                        ans[i] = person;
                        break;
                    }
                }
            }
        }
        return ans;
    }
};

Author: leetcode solution
Link: https://leetcode-cn.com/problems/queue-reconstruction-by-height/solution/gen-ju-shen-gao-zhong-jian-dui-lie-by-leetcode-sol/
Source: LeetCode

2. Ranking from high to low, station position

Ranking from high to low indicates that the people behind are affected by the people in front. That is, each person selected depends on the situation of the people in front (the rest do not affect the current element). This can be seen according to the subscript.

Since the remaining people do not affect the current elements, we only need to look at the existing standing in line and count the situation that the people standing in front are higher than themselves, so that we can directly stand behind them.

The code is as follows:

class Solution {
public:
    static bool cmp(vector<int>a,vector<int>b){
        if(a[0]!=b[0]) return a[0]>b[0];
        else return a[1] < b[1];//Put the small value of k in front
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        //Sort from high to low
        vector<vector<int> > my_vec;
        sort(people.begin(),people.end(),cmp);

        for (int i=0;i<people.size();i++)
        {
            //Traverse people who are taller than yourself and insert them behind them
            //Here j must be equal to, and it is guaranteed that the value can be inserted, otherwise it will jump out directly and will never be inserted
            for ( int count=0,j=0;j<=my_vec.size();j++)
            {
                if (count== people[i][1] )
                {
                    my_vec.insert(my_vec.begin()+j, people[i] );
                    break;
                }
                if ( my_vec[j][0] >= people[i][0] )
                    count++;                               
            }           
        }        
        return my_vec;
    }
};

Official change:
Thinking: the people behind will not affect, so this Ki is your final position

class Solution {
public:
    static bool cmp(vector<int>a,vector<int>b){
        if(a[0]!=b[0]) return a[0]>b[0];
        else return a[1] < b[1];//Put the small value of k in front
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        //Sort from high to low
        vector<vector<int> > my_vec;
        sort(people.begin(),people.end(),cmp);

        for (int i=0;i<people.size();i++)
        {
            //The people behind will not affect you, so this Ki is your final position
            my_vec.insert(my_vec.begin()+people[i][1], people[i] );
        }        
        return my_vec;
    }
};

I still didn't react!!

One is to occupy the position, the other is to insert directly. Cow!

summary

Thinking is very important. With thinking, writing code is easy!!

Like to order a praise!