字节的只有18年以前的题了 看笔试来说还是很亲民的~ 而且分了大数据小数据给大家 可以先骗点分
不过系统设计会考到的 这个是很值得复习的一部分
P为给定的二维平面整数点集。定义 P 中某点x，如果x满足 P 中任意点都不在 x 的右上方区域内（横纵坐标都大于x），则称其为“最大的”。求出所有“最大的”点的集合。（所有点的横坐标和纵坐标都不重复, 坐标轴范围在[0, 1e9) 内） 如下图：实心点为满足条件的点的集合。请实现代码找到集合 P 中的所有 ”最大“ 点的集合并输出。
输入描述:
第一行输入点集的个数 N， 接下来 N 行，每行两个数字代表点的 X 轴和 Y 轴。 对于 50%的数据, 1 <= N <= 10000; 对于 100%的数据, 1 <= N <= 500000;
输出描述:
输出“最大的” 点集合， 按照 X 轴从小到大的方式输出，每行两个数字分别代表点的 X 轴和 Y轴。
输入例子1:
5
1 2
5 3
4 6
7 5
9 0
输出例子1:
4 6
7 5
9 0
题里实际上给了暗示 输出要按x从小到大输出
首先就是按x排列 这样当遍历到当前节点时候，其右边的所有点都满足x更大，那么我们可以通过记录右边所有点最大的y是否比当前点的大 来判断 这里记录右边所有点最大的y就预处理 从右向左遍历一次就好了
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
using PII = pair<int, int>;
const int N = 500010;
int n;
PII p[N];
int maxy[N];
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
int x, y;
scanf("%d%d", &x, &y);
p[i] = {x, y};
}
// 按照x排序
sort(p, p + n);
maxy[n] = -1;
for(int i = n - 1; i >= 0; i--)
maxy[i] = max(maxy[i + 1], p[i].second);
for(int i = 0; i < n; i++)
{
if(p[i].second > maxy[i + 1])
printf("%d %d\n", p[i].first, p[i].second);
}
return 0;
}给定一个数组序列, 需要求选出一个区间, 使得该区间是所有区间中经过如下计算的值最大的一个： 区间中的最小数 * 区间所有数的和最后程序输出经过计算后的最大值即可，不需要输出具体的区间。如给定序列 [6 2 1]则根据上述公式, 可得到所有可以选定各个区间的计算值:
[6] = 6 * 6 = 36;
[2] = 2 * 2 = 4;
[1] = 1 * 1 = 1;
[6,2] = 2 * 8 = 16;
[2,1] = 1 * 3 = 3;
[6, 2, 1] = 1 * 9 = 9;
从上述计算可见选定区间 [6] ，计算值为 36， 则程序输出为 36。 区间内的所有数字都在[0, 100]的范围内;
输入描述:
第一行输入数组序列长度n，第二行输入数组序列。 对于 50%的数据, 1 <= n <= 10000; 对于 100%的数据, 1 <= n <= 500000;
输出描述:
输出数组经过计算后的最大值。
输入例子1:
3
6 2 1
输出例子1:
36
这题开始一看到区间问题就想到线段树了 后来发现不对
这里有一个隐藏的贪心性质，我们可以通过枚举每个点作为最小值的情况 这样就包含了所有可能性 而每个点作为最小值时最大的区间和 肯定是向左向右扩展，保证最长的区间，这样我们需要知道左边和右边第一个比他小的数的位置 这样最长的区间就可以确定 实际上就是leetcode接雨水/最大矩形面积的变形
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
const int N = 500010;
int n;
int nums[N];
int r[N];
int s[N];
int get(int l, int r)
{
return s[r] - s[l - 1];
}
int main()
{
scanf("%d", &n);
stack<int> stk;
for(int i = 1; i <= n; i++)
{
scanf("%d", nums + i);
s[i] = s[i - 1] + nums[i];
}
for(int i = n; i > 0; i--)
{
while(stk.size() && nums[stk.top()] >= nums[i])
stk.pop();
// 此时栈顶是右边比他小的第一个元素
if(stk.size()) r[i] = stk.top(); // 如果stk不为空
else r[i] = n + 1;
stk.push(i);
}
stk = stack<int>();
int res = 0, l = 0;
for(int i = 1; i <= n; i++)
{
while(stk.size() && nums[stk.top()] >= nums[i])
stk.pop();
if(stk.size())
l = stk.top();
else l = 0;
res = max(res, nums[i] * get(l + 1, r[i] - 1));
stk.push(i);
}
printf("%d\n", res);
return 0;
}产品经理(PM)有很多好的idea，而这些idea需要程序员实现。现在有N个PM，在某个时间会想出一个 idea，每个 idea 有提出时间、所需时间和优先等级。对于一个PM来说，最想实现的idea首先考虑优先等级高的，相同的情况下优先所需时间最小的，还相同的情况下选择最早想出的，没有 PM 会在同一时刻提出两个 idea。 同时有M个程序员，每个程序员空闲的时候就会查看每个PM尚未执行并且最想完成的一个idea,然后从中挑选出所需时间最小的一个idea独立实现，如果所需时间相同则选择PM序号最小的。直到完成了idea才会重复上述操作。如果有多个同时处于空闲状态的程序员，那么他们会依次进行查看idea的操作。 求每个idea实现的时间。 输入第一行三个数N、M、P，分别表示有N个PM，M个程序员，P个idea。随后有P行，每行有4个数字，分别是PM序号、提出时间、优先等级和所需时间。输出P行，分别表示每个idea实现的时间点。
输入描述:
输入第一行三个数N、M、P，分别表示有N个PM，M个程序员，P个idea。随后有P行，每行有4个数字，分别是PM序号、提出时间、优先等级和所需时间。全部数据范围 [1, 3000]。
输出描述:
输出P行，分别表示每个idea实现的时间点。
输入例子1:
2 2 5
1 1 1 2
1 2 1 1
1 3 2 2
2 1 1 2
2 3 5 5
输出例子1:
3
4
5
3
9
说真的 考模拟题的我还是第一次见... 这和算法没啥太大关系了
不过考试的时候能够搞明白这些乱七八糟的逻辑关系还是挺难的把（是我搞不出来的了）
#include <bits/stdc++.h>
#pragma warning(disable:4996)
using namespace std;
typedef struct node
{
int id;
int time;
int rank;
int cost;
int global_id;
int finish_time = 0;
bool operator < (const struct node&b)const
{
if (rank != b.rank)
return rank < b.rank;
if (cost != b.cost)
return cost > b.cost;
if (time != b.time)
return time > b.time;
return false;
}
} idea;
bool cmp2(idea a, idea b)
{
return a.global_id < b.global_id;
}
bool cmp3(idea a, idea b)
{
if(a.time!=b.time)
return a.time < b.time;
return false;
}
int main()
{
int n, m, p;
cin >> n >> m >> p;
vector<idea> v;
idea in;
for (int i = 0; i < p; i++)
{
cin >> in.id>>in.time>>in.rank>>in.cost;
in.global_id = i;
v.push_back(in);
}
sort(v.begin(), v.end(), cmp3); // 先按提出时间排序
vector<priority_queue<idea>> PM(n); // 每位pm用一个优先队列去枚举优先级最高的idea
priority_queue<int, vector<int>, greater<int>> pq; // 程序员的空闲时间
vector<idea> finished_idea; // 完成的idea
for (int i = 0; i < m; i++)
pq.push(1);
int time = 1; // 当前时间
int i = 0;
while (finished_idea.size()!=p)
{
// 找到已经提出的idea 加入优先队列
for (; i < v.size()&&v[i].time<=time; i++)
{
PM[v[i].id - 1].push(v[i]);
}
// 如果有程序员都空闲
while (pq.top()<=time)
{
// 找到优先级最高的 这里暗示了一个优先级 找到cost最小的来完成
int first = 0, minn = 9999;
bool haveidea = false;
for (int j = 0; j < n; j++)
{
if (PM[j].empty())
continue;
if (minn > PM[j].top().cost)
{
minn = PM[j].top().cost;
first = j;
haveidea = true;
}
}
if (haveidea)
{
int coder = pq.top(); pq.pop();
idea cur = PM[first].top(); PM[first].pop();
cur.finish_time = time + cur.cost;
coder = cur.finish_time;
pq.push(coder);
finished_idea.push_back(cur);
}
else
break;
}
if (time >= pq.top())
time++;
else
time = pq.top();
}
sort(finished_idea.begin(), finished_idea.end(), cmp2);
for (int j = 0; j < p; j++)
{
cout << finished_idea[j].finish_time << endl;
}
return 0;
}
给定一棵树的根节点, 在已知该树最大深度的情况下, 求节点数最多的那一层并返回具体的层数。 如果最后答案有多层, 输出最浅的那一层，树的深度不会超过100000。实现代码如下，请指出代码中的多处错误：
struct Node {
vector<Node*> sons;
};
void dfsFind(Node *node, int dep, int counter[]) {
counter[dep]++;
for(int i = 0; i < node.sons.size(); i++) {
dfsFind(node.sons[i], dep, counter);
}
}
int find(Node *root, int maxDep) {
int depCounter[100000]; // 不会超过这里是不是要开大一点
dfsFind(root, 0, depCounter);
int max, maxDep;
for (int i = 1; i <= maxDep; i++) {
if (depCounter[i] > max) {
max = depCounter[i];
maxDep = i;
}
}
return maxDep;
}原代码 求一层中节点数最多的一层 其实应该用bfs来实现的 但这题用dfs也不是不行 找找他代码里面的问题吧
dfsFind函数
- node是指针，所以得是
node->sons[i] - 往下搜索 要
dep + 1 - DFS 要有出口 如果是node为空，要直接返回
find函数
- 参数和内部定义的变量名字不能重复
- max 和 maxDep 都没赋初值
- root为空没有考虑
struct Node {
vector<Node*> sons;
};
void dfsFind(Node *node, int dep, int counter[]) {
if(node == nullptr) return;
counter[dep]++;
for(int i = 0; i < node.sons.size(); i++) {
dfsFind(node->sons[i], dep + 1, counter); // dep + 1;
}
}
int find(Node *root, int maxdepth) { //改革民治
if(root == nullptr) return 0;
int depCounter[100000];
dfsFind(root, 0, depCounter);
int max = 0, maxDep = 0; // 没赋初值
for (int i = 1; i <= maxdepth; i++) {
if (depCounter[i] > max) {
max = depCounter[i];
maxDep = i;
}
}
return maxDep;
}题目描述
早期短链接广泛应用于图片上传网站，通过缩短网址URL链接字数，达到减少代码字符串的目的。常见于网店图片分类的使用，因有字符个数限制，采用短链接可以达到外链图片的目的。自微博盛行以来，在微博字数有限的特色下，短链接也盛行于微博网站，以节省字数给博主发布更多文字的空间。 **问题描述：**设计一个短链生成和查询系统，需要提供以下两个功能： 1、提供长链转换短链的接口 2、点击短链能跳转到对应的长链 题目要求： 1、同一个长链生成同一个短链接，不要有多个短链指向同一个长链。 2、同一个短链只能指向某一个长链，短链生成后要固定不变，不能再指向其它长链。 3、给出系统架构，需要考虑高并发解决方案。 4、考虑存储和缓存方案 数据量预估： 1、预计长链接总量500亿 2、长链换短链请求量：10W qps 3、短链跳转请求量：100W qps
系统设计等学到了再写吧~