编程题

用户喜好

方法一 暴力遍历 （居然过了,耗时1049ms）

#include <iostream>
using namespace std;
int n, p;
int T[300005];
void solve(int l, int r, int k) {
    int cnt = 0;
    for(int i = l; i <= r; ++i) {
        if(T[i] == k) ++cnt;
    } 
    printf("%d\n", cnt);
    
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &T[i]);
    scanf("%d",&p);
    for(int  i = 0; i < p; ++i) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        solve(l, r, k);
    }
}

方法二 二分（这个居然不如上面的快，耗时2110ms）

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <map>
using namespace std;
int n, q;
int T[300005];
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        scanf("%d", &T[i]);
    }
    map<int, vector<int>> t;
    scanf("%d", &q);
    for(int i = 0; i < q; ++i) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        if(t.find(k) == t.end()) {
            t[k] = vector<int>();
            for(int i = 0; i < n; ++i)
                if(T[i] == k)  {
                    t[k].push_back(i+1);
            //        cout << "insert " << i << endl;
                }
        }
        auto low = lower_bound(t[k].begin(), t[k].end(), l);
        auto up  = upper_bound(t[k].begin(), t[k].end(), r);
        printf("%d\n", up - low);
        
    }
    return 0;
}

手串

方法一 滑动窗口

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
using namespace std;
int n, m, c;
int color[20005][51];
void solve() {
    unordered_map<int,int> H;
    unordered_set<int> ans;
    for(int i = 0; i < m; ++i) {
        int idx = i % n;
        int j = 0;
        while(color[idx][j] != -1) {
            if(++H[color[idx][j]] >= 2) {
                ans.insert(color[idx][j]);
            }
            ++j;
        }
    }
    for(int i = 0; i < n - 1; ++i) {
        int j = 0;
        while(color[i][j] != -1) {
            --H[color[i][j]];
            ++j;
        }
        int idx = (i + m) % n;
        j = 0;
        while(color[idx][j] != -1) {
            if(++H[color[idx][j]] >= 2) {
                ans.insert(color[idx][j]);
            }
            ++j;
        }
    }
    printf("%d\n", ans.size());
    
}
int main() {
    scanf("%d%d%d",&n, &m, &c);
    for(int i = 0; i < n; ++i) {
        int k, a;
        scanf("%d", &k);
        for(int j = 0; j < k; ++j) 
            scanf("%d", &color[i][j]);
        color[i][k] = -1;
    }
    if(m > n) 
        printf("%d\n", c);
    else if(m == 1) 
    	printf("0\n");
    else 
    	solve();
}

方法二 颜色的个数比较小，直接枚举颜色判断

#include <iostream>
#include <algorithm>
#include <map>
#include <unordered_set>
#include <vector>
using namespace std;
int n, m, c;
map<int, vector<int>> A;
void solve() {
    int ans = 0;
    for(int i = 1; i <= c; ++i) {
        int sz = A[i].size();
        bool flag = false;
        for(int j = 0; j < sz; ++j) {
            int cur = A[i][j], limit = (cur + m - 1) % n;
            int next = A[i][(j+1)%n];
            if(cur < limit  && next <= limit && next > cur) flag = true;
            else if(cur > limit && (next > cur || next <= limit)) flag = true;
            if(flag) break;
        }
        if(flag) ++ans;    
    } 
    printf("%d\n", ans);
}
int main() {
    scanf("%d%d%d",&n, &m, &c);
    for(int i = 0; i < n; ++i) {
        int k, a;
        scanf("%d", &k);
        for(int j = 0; j < k; ++j) {
            int color;
            scanf("%d", &color);
            A[color].push_back(i);
        }
    }
    if(m > n)
        printf("%d\n", c);
    else if(m == 1) 
        printf("0\n");
    else 
        solve();
}

解答题

1 以下函数使用二分查找搜索一个增序的数组，当有多个元素值与目标

以下函数使用二分查找搜索一个增序的数组，当有多个元素值与目标元素相等时，返回最后一个元素的下标，目标元素不存在时返回-1。请指出程序代码中错误或不符最佳实践的地方（问题不止一处，请尽量找出所有你认为有问题的地方）

int BinarySearchMax(const std::vector<int>& data, int target)

{

   int left = 0;

   int right = data.size();

   while (left < right) {

       int mid = (left + right) / 2;

       if (data[mid] <= target)

           left = mid + 1;

       else

           right = mid - 1;

   }

   if (data[right] == target)

       return right;

   return -1;

}
  1. int right = data.size() - 1;
  2. while(left <= right)
  3. if(right >= 0 && data[right] == target)

2 如何测试一个消息系统，这个消息系统包含了：今日头条的评论消息

如何测试一个消息系统，这个消息系统包含了：今日头条的评论消息、点赞消息、关注提醒、头条号提醒、问答邀请和系统消息（比如头条活动）

3 某城市部分移动用户反馈无法刷新今日头条的信息流， 并且总是提

某城市部分移动用户反馈无法刷新今日头条的信息流， 并且总是提示网络错误。 可能是什么原因导致的？