编程题

编程题1

方法一 对x进行排序

刚开始是这么写的，其实写麻烦了，没有注意到这句话
所有点的横坐标和纵坐标都不重复, 坐标轴范围在[0, 1e9) 内)
不存在x坐标相同的多个点

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define max(a, b) (a) > (b) ? (a) : (b)
int n;
pair<int,int> A[500005];
void solve() {
    sort(A, A+n, [](const pair<int,int>&a, const pair<int,int>&b ) {
        return a.first == b.first ? a.second < b.second : a.first < b.first; 
    });
    int max_y = 0;
    int cnt = 0;
    for(int i = n - 1; i >= 0; --i) {
        int tmp_max = A[i].second;
        while(i > 0 && A[i].first == A[i-1].first ) {
            if(A[i].second >= max_y) {
                ++cnt;
                A[n - cnt].first = A[i].first;
                A[n - cnt].second = A[i].second;
            }
            --i;
        }
        if(A[i].second >= max_y) {
            ++cnt;
            A[n - cnt].first = A[i].first;
            A[n - cnt].second = A[i].second;
        } 
        max_y = max(max_y, tmp_max);
    }
    for(int i = n - cnt; i < n; ++i)
        printf("%d %d\n", A[i].first, A[i].second);
}
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d%d",&A[i].first,&A[i].second);
    solve();
}

改为

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define max(a, b) (a) > (b) ? (a) : (b)
int n;
pair<int,int> A[500005];
void solve() {
    sort(A, A+n, [](const pair<int,int>&a, const pair<int,int>&b ) {
        return a.first < b.first; 
    });
    int max_y = 0;
    int cnt = 0;
    for(int i = n - 1; i >= 0; --i) {
        if(max_y <= A[i].second) {
            max_y = A[i].second;
            ++cnt;
            A[n - cnt].first = A[i].first;
            A[n - cnt].second = A[i].second;
        }
    }
    for(int i = n - cnt; i < n; ++i)
        printf("%d %d\n", A[i].first, A[i].second);
}
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d%d",&A[i].first,&A[i].second);
    solve();
}

方法二 对y进行排序

#include <iostream>
#include <algorithm>
using namespace std;
int n;
pair<int, int> A[500005];
void solve() {
    sort(A, A+n, [](const pair<int,int>&a, const pair<int,int>&b){
        return a.second > b.second;
    });
    int max_x = -1;
    for(int i = 0; i < n; ++i) {
        if(max_x <= A[i].first) {
            max_x = A[i].first;
            cout << A[i].first << " " << A[i].second << endl;
        }
    }  
}
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        scanf("%d%d", &A[i].first, &A[i].second);
    }
    solve();
}

编程题2

方面一 枚举区间最小数,找到对应的最大值。

利用之前计算的一些信息来减少区间查找的范围。

#include <iostream>
using namespace std;
int n;
int A[500005], P[500005];
void solve() {
    // cal P
    P[0] = 0;
    for(int i = 1; i < n; ++i) {
        P[i] = P[i-1] + A[i-1];
    }
    int left = -1, right = 1;
    while(right < n && A[right] >= A[0]) ++right;
    // (left ..i. right)
    // i * (P[right] - P[left + 1])
    // right : 1 .. n
    // left  : 0 ... 
    int ans = A[0] * (P[right] - P[left + 1]);
    for(int i = 1; i < n; ++i) {
        if(A[i] == A[i-1]) continue;
        if(A[i] > A[i-1]) {
            left = i - 1;
            right = i + 1;
            while(right < n && A[right] >= A[i]) ++right;
        }else {
            while(left >= 0 && A[left] >= A[i]) --left;
            while(right < n && A[right] >= A[i]) ++right;
        }
        int t = A[i] * (P[right] - P[left + 1]);
        if(t > ans) ans = t;
    }
    cout << ans << endl;
}
int main() {
    cin >> n;
    for(int i = 0; i < n; ++i)
        scanf("%d", &A[i]);
    solve();
}

方法二 优化，只需要枚举[1,100]就可以了

注意读题
区间内的所有数字都在[0, 100]的范围内;

#include <iostream>
using namespace std;
int n;
int A[500005], P[500005];
void solve() {
    // cal P
    P[0] = 0;
    for(int i = 1; i < n; ++i) {
        P[i] = P[i-1] + A[i-1];
    }
    int ans = 0;
    for (int i = 1; i <= 100; ++i) {
        int flag = 0, start = -1, cnt = 0;
        for(int j = 0; j < n; ++j) {
            if(A[j] >= i) {
                ++cnt;
                if(start == -1) start = j;
                if(A[j] == i) flag = 1;
            }else {
                if(flag == 1) 
                    ans = max( ans, i * (P[start + cnt] - P[start]));
                flag = 0;
                start = -1;
                cnt = 0;
            }
         }
         if(flag == 1) ans = max(ans, i * P[start + cnt] - P[start]); 
    }
    cout << ans << endl;
}
int main() {
    cin >> n;
    for(int i = 0; i < n; ++i)
        scanf("%d", &A[i]);
    solve();
}

总结

认真读题，漏掉题目中的某些信息会把题做麻烦，而且时间复杂度空间复杂度也可能会变大。

问答题

1 给定一棵树的根节点, 在已知该树最大深度的情况下, 求节点数

给定一棵树的根节点, 在已知该树最大深度的情况下, 求节点数最多的那一层并返回具体的层数。 如果最后答案有多层, 输出最浅的那一层，树的深度不会超过100000。实现代码如下，请指出代码中的多处错误：

struct Node {

    vector<Node*> sons;

};

 

void dfsFind(Node *node, int dep, int counter[]) {
													// error 1: root 可能为NULL if(root == NULL) return;
    counter[dep]++;

 

    for(int i = 0; i < node.sons.size(); i++) {

        dfsFind(node.sons[i], dep, counter);  // error 2: dep -> dep + 1,  node.sones[i] -> node->sons[i], node.sons.size()-> node->sons.size()

    }

}

 

int find(Node *root, int maxDep) {

    int depCounter[100000];   

    dfsFind(root, 0, depCounter);

 

    int max, maxDep;                   // error 3: max 没有初始化 int max = 0;
    								 // error 4: maxDep 重名了 改为 maxDep_, 初始化为 -1 

    for (int i = 1; i <= maxDep; i++) {  // error 5: i 应该从0开始

        if (depCounter[i] > max) {

            max = depCounter[i];

            maxDep = i;				// error 4: maxDep -> maxDep_ 

        }

    }

    return maxDep;					// error 4: maxDep -> maxDep_ 

}

2 某一个RPC服务A，对外提供接口MatchAds(AdTar

某一个RPC服务A，对外提供接口MatchAds(AdTargetRequest req),发送请求，返回可展示的广告。如何测试这个服务接口的性能。

3 如果一个头条的客户端程序，冷启动时间为4秒，怎么判断开启速度

如果一个头条的客户端程序，冷启动时间为4秒，怎么判断开启速度是合理的还是不合理的？如果不合理，该如何找到问题，提供思路。