Kwai 20200412 recruitment

There are four questions in total , Made the first three questions . Record the next two questions , The first picture is the third question 、 The second picture is question 4 .

The code of the third question is as follows , I will simplify the third question to a sorting problem ：

vector<int> WaitInLine(vector<int>& a, vector<int>& b) {
    // write code here
    vector<int>c; c.clear();
    vector<int>out; out.clear();
    for (int i = 0; i < a.size(); i++)
    {
        c.push_back(a[i] - b[i]);
        out.push_back(i + 1);
    }
    // From big to small //
    int num = c.size();
    for(int i=0;i<num-1;i++)
        for (int j = 0; j < num - 1 - i; j++)
        {
            if (c[j] < c[j + 1])
            {
                int temp = c[j + 1];
                c[j + 1] = c[j];
                c[j] = temp;

                int temp2 = out[j + 1];
                out[j + 1] = out[j];
                out[j] = temp2;

            }
        }
    return out;
}

The fourth question didn't work out , But I saw the idea on Niuke ,“ Select the least points around each time for statistics , And change the surrounding points to '*' ”, Some people also say using state compression , But I'm Xiaobai , I haven't heard of .

int GetMaxStaffs(vector<vector<char> >& pos) {
    // write code here
    // Traverse //
    int rows = pos.size();
    int cols = pos[0].size();
    // The number of surrounding minimum points //
    
    int row = 0; int col = 0;
    do
    {
        bool isupdate = false;
        int num = 4;
        for (int i = 0; i < rows; i++)
            for (int j = 1; j < cols; j++)
            {
                int tempNum = 0;
                if (pos[i][j] == '.') {
                    if (i - 1 >= 0 && pos[i - 1][j] == '.')
                    {
                        tempNum++;
                    }
                    if (i + 1 < rows&&pos[i + 1][j] == '.')
                    {
                        tempNum++;
                    }
                    if (j - 1 >= 0 && pos[i][j - 1] == '.')
                    {
                        tempNum++;
                    }
                    if (j + 1 < cols&&pos[i][j + 1] == '.')
                    {
                        tempNum++;
                    }
                }
                if (tempNum>0&&tempNum < num)
                {
                    num = tempNum;
                    row = i;
                    col = j;
                    isupdate = true;
                }
            }
        if (row - 1 >= 0 && pos[row - 1][col] == '.')
        {
            pos[row - 1][col]='*';
        }
        if (row + 1 < rows&&pos[row + 1][col] == '.')
        {
            pos[row + 1][col] = '*';
        }
        if (col - 1 >= 0 && pos[row][col - 1] == '.')
        {
            pos[row][col - 1] = '*';
        }
        if (col + 1 < cols&&pos[row][col + 1] == '.')
        {
            pos[row][col + 1] = '*';
        }
        if (!isupdate)
        {
            break;
        }
    } while (true);

    int out = 0;
    for (int i = 0; i < rows; i++)
        for (int j = 0; j < cols; j++)
        {
            if (pos[i][j] == '.')
            {
                out++;
            }
        }
    return out;

}

If there is a better way , Welcome to leave a message .