【字节跳动校招笔试】编程1-3题O(n)思路及代码

得分： 80 | 100 | 100 | 0 (来不及了...）

一些吐槽，大家有什么好的想法也可以分享一下哈：

1. 第一题被卡应该是因为没有考虑从家到学校的时间为0分钟的情况，以及所有闹钟都会迟到的情况（这也太过分了，说好的一定不会迟到？）

2. 其实第3题我是考完试才把一个bug改完，实际没有拿100满分，不过我确信改完的方法可以ac，而且第三题被我做复杂了，评论区有更简单的办法，还是太菜🤣

1. 上学闹钟O(nlogn)

小明定了n个闹钟，他只能在闹钟响起时出发去学校，每个闹钟时间分别为hi点mi分，小明家到学校要x分钟，学校上课时间a点b分（0-24小时，0-59分钟），求他最晚几点起

输入：

3 //定了几个闹钟
5 0 //第1个闹钟的小时数和分钟数
6 0 //第2个闹钟的小时数和分钟数
7 0 //第3个闹钟的小时数和分钟数
59 //到学校要多少分钟
6 59 //上课的小时数和分钟数

输出：

6 0 //最晚的起床时间

思路（80/100分）：

纯智障思路，自定义结构体存储闹钟时间，全部输入后对闹钟时间从晚到早排序，接下来从前往后遍历闹钟时间，计算从当前时刻出发到学校的时间，输出第一个能够到达学校的，由于算法很粗劣，很明显被卡边界了，没时间管了直接看下一题。

代码：

struct Time
{
    int h;
    int m;
    friend bool operator < (Time a, TIme b){
        if(a.h == b.h){
            return a.m > b.m;
        }
        return a.h > b.h;
    }
}
int main()
{
	int n, x, a, b, rest;
	cin >> n;
	Time* time = (Time*)malloc(n * sizeof(Time));
	for (int i = 0; i < n; i++)
	{
		cin >> time[i].h >> time[i].m;
	}
	sort(time, time + n);
	cin >> x;
	cin >> a >> b;
	for (int i = 0; i < n; i++)
	{
		rest = 0;
		if (time[i].h < a || time[i].h == a && time[i].m < b)
		{
			rest = (a - time[i].h) * 60 + b - time[i].m;
			if (rest >= x)
			{
				cout << time[i].h << ' ' << time[i].m << endl;
				break;
			}
		}
	}
	return 0;
}

2. 加密通信 O(n)

小明和小红采用密码加密通信，每次通信有固定的明文长度n和加密次数k。

比如：密码二进制明文是1001010，加密次数是4，则每次将密文右移1位与明文做异或操作，总共位移3次（k=4, 所以k - 1 = 3）

输入：

7 4 // n k
1110100110 //密文

输出：
1001010 //明文

解释：

1001010---
-1001010--
--1001010-
---1001010
加密次数为4，故对于明文右移4-1=3轮，每轮与当前密文进行一次异或，故1001010对应密文为1110100110

思路（100/100分）：一道标准的异或数学题，不知道该怎么归类，有一点考数学的感觉，看几眼就能看出规律了直接上代码

简单讲一下思路：

首先密文和明文第1位是一样的，看一下上方样例里的解释就懂了。

然后考虑第2到k-1位，可以发现这一段的每一位都是由前一位密文的异或结果再与当前位明文异或得到的。

接下来考虑第k到n-1位，观察规律可以发现这一段的每一位都是由前一位密文与第i-k位明文异或得到的结果再与当前位明文异或得到的。

如何消除异或影响大家应该都能理解，因此只要把参与异或的部分再与密文异或一下即可得到明文。

int main() {
	int n, k, tmp;
	string s,ans="";
	cin >> n >> k;
	cin >> s;
	ans += s[0];
	for (int i = 1; i < k; i++)
	{
		tmp = (int)(s[i] - '0') ^ (int)(s[i - 1] - '0');
		ans += tmp + '0';
	}
	for (int i = k; i < n; i++)
	{
		ans += (int)(s[i] - '0') ^ (int)(s[i - 1] - '0') ^ (int)(ans[i - k] - '0') + '0';
	}
	cout << ans;
	return 0;
}

3.发工资O(n)

王大锤要给员工发工资，员工从左到右坐成一排，每个员工知道彼此的资历，每个员工只知道自己左右员工的工资，如果某员工比左边或右边的人资历老，那他一定比这个人工资高100元，每个人最低工资100元，求王大锤最低给多少工资。

样例

输入：

4 //几个员工
3 9 2 7 //员工顺序以及对应的资历

输出：
600 //100元，200元，100元，200元

6
1 2 3 4 5 6
2100 //100，200，300，400，500，600

5
1 1 1 1 1

500 //100，100，100，100，100

8
1 2 3 4 3 2 3 4

1800 //100 200 300 400 200 100 200 300
8
3 4 3 4 3 4 3 4

1200 //100 200 100 200 100 200 100 200
5
1 2 3 4 1

1100 //100 200 300 400 500

思路（100/100分）：

广度优先搜索，可以把员工序列看作一棵多根树，每个工资最低的员工就是根节点，一个员工的工资其实就是他在多根树里的深度，

首先在输入的时候找到比左右资历都年轻的员工入队，每次从队列pop一个员工，然后判断该员工的最小工资，然后判断左右员工是否可以入队，直到所有员工出队

int main() {
	int n, now;
	long long ans = 0;
	cin >> n;
	if (n == 0)
	{
		cout << 0 << endl;
		return 0;
	}
	vector<int> epy(n, 0), depth(n, 0);
	queue<int> sal;
	for (int i = 0; i < n; i++)
	{
		cin >> epy[i];
		if (i > 1 && epy[i - 1] <= epy[i - 2] && epy[i - 1] <= epy[i])
		{
			depth[i - 1] = 1;
			sal.push(i - 1);
		}
	}
	if (epy[0] <= epy[1])
	{
		depth[0] = 1;
		sal.push(0);
	}
	if (epy[n - 1] <= epy[n - 2])
	{
		depth[n - 1] = 1;
		sal.push(n - 1);
	}
	while (!sal.empty())
	{
		now = sal.front();
		int left = (now > 0 && epy[now-1] < epy[now]) ? depth[now - 1] : 0;
		int right = (now < n - 1 && epy[now + 1] < epy[now]) ? depth[now + 1] : 0;
		sal.pop();
		if (depth[now] == 0)
		{
			depth[now] = max(left, right) + 1;
		}
		//left
		if (now > 0 && depth[now - 1] == 0 && (now == 1 || epy[now - 2] > epy[now - 1] || depth[now - 2] > 0))
		{
			sal.push(now - 1);
		}
		//right
		if (now < n - 1 && (depth[now + 1] == 0) && (now == n - 2 || epy[now + 2] > epy[now + 1] || depth[now + 2] > 0))
		{
			sal.push(now + 1);
		}
	}
	for (auto salary : depth) {
		ans += salary;
	}
	cout << ans * 100 << endl;
}

#字节跳动##笔试题目#