字节Tiktok后端二面凉经 面试时长40分钟，就问了几个简单的问题就匆忙结束了，最后是说跟业务要求不匹配。 我感觉可能没hc了？ 项目介绍 八股 忘了。 B+树比B树的优势 输入url到看到页面的整个过程 问了不超过5个问题吧。 算法 k个一组翻转链表。 典中典。写的递归的O(1)的写法。 总结 被刷kpi了。

字节Tiktok后端一面 0.前言 上来先简单自我介绍，然后简单交流了一波qwq，然后发现面试官不懂算法竞赛。 1.八股 流量控制 mysql的insert的过程实现 Redis(说了解一点，准备问，但是没问) 虚拟内存 子进程与父进程的内存关系 消息队列MQ C++的线程池 synchronized 信号量的实现 ...

#2020我的牛客回忆# 2021，祝你事业有成，万事顺心！ @王清楚

A.生成树 思路：贪心。 一开始用写了个假算法，发现数据太弱了。以第一棵树为基准，我们用记录每条边，规定，这样方便去重。 然后我们只需在第二课树找到第一棵树中不存在的边即可，因为第二棵树少的边和多的边数肯定相等的，不然边数和不可能为，所以根据贪心我们只需统计少的边即可，这样用就很方便了，此时的大小是：，是相重的个数， 我们需要的答案是，所以答案是：。 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7...

完全平方数的尾巴 思路：暴力枚举。 考虑。 所以当时又回到，即周期为。 所以我们只需要暴力枚举特判。 时间复杂度： typedef long long ll; class Solution { public: /** * * @param x int整型 * @return bool布尔型 */ bool solve(int x) { for(int i=0;i<1000;i++) if(i*i%1000==x) return true; return false; } }...

B.Basic Gcd Problem(质因数分解） 思路：考虑的贡献次数，我们最后的答案肯定是：形式，所以我们只需求出。 。 显然。 。 。 所以。 看了上面这个样例你可能已经发现了跟因数有关系。 因为我们要让尽可能大，所以我们需要尽可能多的进行相乘转换。 我们换个方式考虑：。 。 这样是不是很显然了。 再来：。 。 显然按照质因数分解后的个数依次相乘是最大的。 即答案就是质因数个数之和。 接下来就很简单了，可以考虑直接暴力一边分解一边计算贡献，或者预处理一波每个数的对应素数。 总复杂度：或 #include<bits/stdc++.h> using namespace st...

Codeforces Round #479 (Div. 3)（A-F)题解 传送门 A. Wrong Subtraction 思路：签到题，根据题意模拟即可。 时间复杂度： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7; #define mst(a) memset(a,0,sizeof a) #define lx x<<1 #define rx x<<1|1 #defin...

P1168 中位数 传送门 思路： 1.对顶堆，大根堆(从大到小)存较小的数，小根堆(从小到大)存较大的数。 如果当前数大于大根堆顶，就放入小根堆，否则放入大根堆。 然后维护使两堆容量大小之差小于等于1，然后容量较大的那个堆顶元素即是答案。 因为题目保证是求奇数个数的中位数，显然比中位数小的个数=比中位数大的个数，所以取多了那一个的堆顶即可。 时间复杂度：。 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5,M=1e6+5,inf=0x3f3f3f3f,mod=1...

LC.32. 最长有效括号 传送门 挺好的一个题，这里主要再分析一下官方的解法。 思路: 1.。 令以下标结尾的字符串的最大长度为，显然，. 当，需要讨论两种情况。 ，这样显然有. ，因为我们已知，我们可以找到的开始匹配的前面 一个位置即，显然如果，是不能更新的，因为一定是未被匹配的，不然会包含掉它，所以显然，才能与进行匹配，然后再加上的长度就可以了。 即 时间复杂度： class Solution { public: int longestValidParentheses(string s) { int n=s.length(),ans=0; v...

A.最小生成树 思路：贪心。 显然对于一个个结点的无向完全图，要想使其成为一棵树，我们只需选取条边，总贡献是 我们所有结点至少被加一次，所以剩下个结点是要重复加的，显然用点权最小的结点重复即可。所以排个序就解决了。 时间复杂度： 代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7; #define mst(a) memset(a,0,sizeof a) #define lx x<<...

F. Cyclic Shifts Sorting（模拟&排序) 传送门思路： 模拟冒泡排序，只不过两个数交换，变成了三个数进行位置转换。 显然三个数可以顺时针走，也可以逆时针走。 我们可以第轮将当前最小的数移动到位置， 因为每操作一次，第三个数可以移动到第一个数的位置。 如果当前最小的数与位置的距离不是2的倍数，我们需要让位置操作一次，使其变为，然后再不断进行操作 就可以了。 这里需要注意特判一下，如果当前最小的数在最后一个，直接操作位置， 这样可以在距离不是的倍数时，向前移动一个位置。 这样我们就可以排好。 接下来特判一下如果 不用再操作了。 否则我们需要将交换一下位置。 如果我们...

AtCoder Beginner Contest 172.F - Unfair Nim 传送门 思路：异或的性质+构造。 显然题目背景是游戏，我们目的是让后手胜，显然堆石子异或为时，后手必胜。接下我们需要构造来使堆石子异或和为。 因为题目要求我们只能将移动第一堆石子给第二堆石子。 我们记第一堆和第二堆石子个数分别为。 所以我们可以预处理第堆到第堆石子的异或和，我们记为。 设需要移动的石子数为个。 即我们要使： 首先我们需要知道几个结论： 1： 即个数异或和不能大于其求和。显然取等当这个个数两两的所在位不同。 2.异或和与求和奇偶性相同。 3.要构造长度为2的数组。 最开始满足的条件是 当且仅...

E - NEQ(容斥原理&组合数学) 传送门 思路：容斥原理+组合数学。 显然要求且数组中元素互异。 所以对于数组，我们要从个数选个数来全排列。 即个数为. 接下来我们考虑每个对于的方案，对于有多少个。 显然这是个一个容斥原理的应用，我们考虑用总方案减去所有不合法的方案数， 枚举不合法的位置个数分别为个对应的方案数， 当不合法的位置有个时，不合法的方案数为： 从个位置中选出个不合法的位置，然后用剩下个数，选出个数进行全排列。 然后用 #include<bits/stdc++.h> using namespace std; typedef long long ll; co...

P1637 三元上升子序列(DP+离散化权值树状数组) 传送门 思路：方法1：离散化转权值树状数组。 显然可以设为长度为以结尾的子序列的个数。 有转移方程： 显然暴力时间复杂度 ： 因为,但考虑离散化，然后转权值线段树储存。 先初始化一元上升子序列，然后从前往后遍历， 有转移方程： 再更新。 时间复杂度：,是几元上升子序列。 #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; typedef long lo...