笔试面试相关记录（10）

（1）马走棋盘，只能走‘日’字形，起点在（0,0），给定一个点[x,y](-300<=x,y<=300)，问最少多少步可以到达？

输入：2,1

输出：1

 这个题目通过了91.76%

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最小移动步数
     * @param x int整型 x坐标
     * @param y int整型 y坐标
     * @return int整型
     */
    vectorint>> directions = {{2,1},{1,2},{-2,1},{-1,2},{-2,-1},{-1,-2},{1,-2},{2,-1}};
    
    int getMinStep(int x, int y) {
        // 先建立一个最大的棋盘
        vectorint>> grid(601, vector<int>(601, -1));
        // 此时300,300是原来原点的位置，最小步数是0
        grid[300][300] = 0;
        //从300,300出发，将其他八个方向设置为1，表示一步到达，并保存坐标
        queueint>> q;
        for (int i = 0; i < 8; i++) {
            int x_ = 300+directions[i][0];
            int y_ = 300+directions[i][1];
            grid[x_][y_] = 1;
            q.push({x_, y_});
        }
        //如果目标点就是这八个点中的，直接返回1
        if (grid[300+x][300+y] != -1) return 1;
        int step = 1;
        while (q.size()) {
            //每一层对应的步数都会变大
            step++;
            //类似于层次遍历，将这一层全部都走到
            int size = q.size();
            for (int i = 0; i < size; i++) {
                vector<int> t = q.front();
                q.pop();
                for (int j = 0; j < 8; j++) {
                    int new_x = t[0] + directions[j][0];
                    int new_y = t[1] + directions[j][1];
                    if (new_x >= 0 && new_x < 601 && new_y >= 0 && new_y < 601 && grid[new_x][new_y] == -1) {
                        //如果走到了目标点了，直接返回此时的step
                        if (new_x-300 == x && new_y-300 == y) return step;
                        grid[new_x][new_y] = step;
                        q.push({new_x, new_y});
                    }
                }
            }
        }
        return step;
    }
    int minHorseSteps(int x, int y) {
        // write code here
        return getMinStep(x, y);
    }
};

（2）给定一个数组表示强盗，strength[i] = x，表示强盗i有力量x，小明起初时的力量是0，每天都会增加力量y，如果小明的力量大于等于强盗的力量，则表示小明可以战胜强盗，当小明战胜强盗后，小明的力量变成0，并且y++,如果小明没有战胜强盗，则等待下一天，小明每天会先增加y的力量，问最少多少天可以战胜全部的强盗。（下面这个通过了90%）

#include 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 救出公主最少的天数
     * @param strength int整型vector 强盗的力量值数组
     * @return int整型
     */
    int minDays(vector<int>& strength) {
        // write code here
        int minDays = 0;
        int y = 1;
        int startStrength = 0;
        int n = strength.size();
        int deathCount = 0;
        vector<int> death(n, 0);
        while (deathCount < n) {
            startStrength += y;
            minDays++;
            int diff = INT_MAX, index = 0;
            bool hasVic = false;
            //寻找一个可以战胜且力量值最接近的强盗
            for (int i = 0; i < n; i++) {
                if (death[i] == 0 && startStrength >= strength[i] && (startStrength-strength[i]) < diff) {
                    diff = startStrength - strength[i];
                    hasVic = true;
                    index = i;
                }
            }
            if (hasVic) {
                death[index] = 1;
                startStrength = 0;
                y++;
                deathCount++;
            }
        }
        return minDays;
    }
};

（3）数组interviews表示各个面试者开始和结束时间，例如interviews[i] = [start, end]表示第i个面试者的开始时间为start，结束时间为end，并且每两个面试官为固定一组（这里我的理解是2个面试官一起对面试者进行面试），并且每个面试不可以中途被打断，问至少需要多少个面试官？其实就是如果对数据按照start排序之后，求同一时刻需要面试的的面试者的最大数，然后乘于2返回。

输入：[ [0,20], [10,15], [25,40] ]

输出：4

（下面的方法通过率100%）

#include 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最少需要面试官数量
     * @param interviews int整型vector> 面试时间安排数组
     * @return int整型
     */
    //按照开始时间升序排序
    static bool cmp(vector<int>& a, vector<int>& b) {
        return a[0] <= b[0];
    }
    int minInterviewersCount(vectorint> >& interviews) {
        // write code here
        sort(interviews.begin(), interviews.end(), cmp);
        // for (int i = 0; i < interviews.size(); i++) {
        //     cout << interviews[i][0] << " " << interviews[i][1] << endl;
        // }
        int n = interviews.size();
        int interviewCount = 1;
        //用一个小根堆记录此前面试者的结束时间，这个结束时间堆
        //在用来判断后面的面试者是否可以加入到之前已经面试完毕的组里面，而不用新开一个组
        priority_queue<int, vector<int>, greater<int>> q;
        q.push(interviews[0][1]);
        int end = q.top();
        //从第二个开始遍历
        for (int i = 1; i < n; i++) {
            //如果当前面试者和上一个有交集并且不能安排到别的组里面，此时新开一组
            if (interviews[i][0] < interviews[i-1][1] && interviews[i][0] < q.top()) {
                interviewCount++;
                q.push(interviews[i][1]);
            } else {
                //到这里表示不需要新开一组，则当前面试者加入到之前某个已经完成面试的组里面
                //也就是完成时间最靠前的，并且将其弹出
                q.pop();
                q.push(interviews[i][1]);
            }
        }
        return interviewCount*2;
    }
};

（4）给定一个循环字符串，从中找到相同字符最长的长度，例子如下：

输入：aabaa，输出4，表示字符串头尾相连可以得到的最长的相同字符字符串的长度

输入：aabcc，输出2，可以得到的最长的相同字符的长度为2

#include 
#include 
 
using namespace std;
 
int main() {
    string str;
    while (cin >> str) {
        int n = str.size();
        int max_len = 0, total_len = 2*n;
        string str1 = str + str;
        int i = 0;
        bool flag = false;
        while (i < n) {
            int j = i+1;
            int len = 1;
            while (j < total_len && str1[j] == str1[i]) {
                len++;
                j++;
            }
            //如果j跑到了最后，说明整个字符串都是同一个字符组成的，其他情况，
            //j都不可能跑到最后
            if (j == total_len) {
                flag = true;
            }
            max_len = max(max_len, len);
            i = j;
        }
        if (flag) {
            cout << max_len / 2 << endl;
        } else {
            cout << max_len << endl;
        }
    }
}

（5）描述：输入一个数字n，表示药的种类，接下来n行，每行两个数字，表示每种药的疼痛指数和功效值，再接下来输入一个数字q，表示查询次数，在接下来q行，每行一个数字表示输入的可以接受的疼痛指数，求出在不超过给定疼痛指数情况下可以获得的最大的功效，最后结果输出q行。

5
3 10
4 2
6 6
9 10
10 9
3
1
6
9

输出

-1
10
10

每个数字都很大，我的暴力解法超时了。 

#include 
#include 
#include 
#include 
using namespace std;
 
static bool cmp(vector<int>& a, vector<int>& b) {
    if (a[0] == b[0]) {
        return a[1] >= b[1];
    }
    return a[0] >= b[0];
}
 
int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        int a, b;
        vectorint>> vec;
        map<int, int> mp;
        for (int i = 0; i< n; i++) {
            cin >> a >> b;
            vec.push_back({a, b});
        }
        sort(vec.begin(), vec.end(), cmp);
        // 排序之后，将后面的最大值逐个向前更新
        for (int i = n-2; i >= 0; i--) {
            if (vec[i][1] < vec[i+1][1]) {
                vec[i][1] = vec[i+1][1];
            }
        }
        int q, t;
        cin >> q;
        vector<int> ans;
        for (int i = 0; i < q; i++) {
            cin >> t;
            bool find_ = false;
            int max_ = 0;
            for (int j = 0; j < n; j++) {
                if (vec[j][0] <= t) {
                    max_ = vec[j][1];
                    find_ = true;
                    break;
                }
            }
            if (!find_) {
                ans.push_back(-1);
            } else {
                ans.push_back(max_);
            }
        }
        for (int i = 0; i < q; i++) {
            cout << ans[i] << endl;
        }
    }
}
// 64 位输出请用 printf("%lld")