字节跳动（今日头条）算法岗笔试 03.16 AK题解
第一题，大水题，直接上代码：
n, answer = 1024-int(input()), 0 for coin in [64, 16, 4, 1]: answer += n // coin n = n % coin print(answer)第二题，比较简单，题目的中的两个判断条件，都只跟前2-3位字符有关。
思路：逐个判断字符，根据两个条件判断是否可以加到结果字符串中
代码：
第三题，Python挂掉，C++通过（不知道为什么字体变色了- -）def solve(s): n = len(s) r = list(s[:min(len(s), 2)]) for i in range(2, n): if s[i] == r[-1] == r[-2]: continue if s[i] == r[-1] and len(r) > 2 and r[-2] == r[-3]: continue r.append(s[i]) return ''.join(r) for test_case in range(int(input())): print(solve(input()))
思路：从未分配奖品的人中选取分数最小的人，然后判断她两边的人是否分配了奖品
情况1. 如果两边都已经分配奖品，当前位置的分数肯定比两边大（结合情况2,即可简单证明），此时取两边奖品最大值+1即可。
情况2. 如果有未分配奖品的方向：当前位置分配奖品数1，沿着未分配的方向，依次分配，直到当前结点大于后继结点。
比如：分数 为 1 -> 2 -> 2 -> 5 -> 3
那么：奖品 为 1 -> 2 -> 1 -> 不分配 （遇到相同可以重置为1）
多说一句，如果一个方向分配，另一个方向未分配，则分配过奖品方向的那个位置的分数，肯定比当前位置大，可简单证明。
依次取分数最小的位置，不断遍历即可，复杂度（排序 NlogN， 遍历O(n)），故NlogN
情况1. 如果两边都已经分配奖品，当前位置的分数肯定比两边大（结合情况2,即可简单证明），此时取两边奖品最大值+1即可。
情况2. 如果有未分配奖品的方向：当前位置分配奖品数1，沿着未分配的方向，依次分配，直到当前结点大于后继结点。
比如：分数 为 1 -> 2 -> 2 -> 5 -> 3
那么：奖品 为 1 -> 2 -> 1 -> 不分配 （遇到相同可以重置为1）
多说一句，如果一个方向分配，另一个方向未分配，则分配过奖品方向的那个位置的分数，肯定比当前位置大，可简单证明。
依次取分数最小的位置，不断遍历即可，复杂度（排序 NlogN， 遍历O(n)），故NlogN
代码，python 只过了11%数据，只好用C++重写了一遍：
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int t, n, x;
vector< pair<int, int> > a;
vector<int> b,v;
inline int left(int index){
if(index == n - 1)
return 0;
return index + 1;
}
inline int right(int index){
if(index == 0)
return n - 1;
return index - 1;
}
inline int get_next(int index, int dir){
if (dir == 1)
return left(index);
return right(index);
}
inline void fill(int start, int dir){
int index = start, count = 1;
int next = get_next(index, dir);
v[start] = 0;
while(b[index] <= b[next] && v[index] == 0){
v[index] = count;
if(b[index] < b[next])
count += 1;
else
count = 1;
index = next;
next = get_next(index, dir);
}
v[start] = 1;
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d", &n);
v.clear();a.clear(); b.clear();
for(int i = 0; i < n; ++i){
scanf("%d", &x);
v.push_back(0);
b.push_back(x);
a.push_back(make_pair(x, i));
}
sort(a.begin(), a.end());
for(int i = 0; i < n; ++i){
int index = a[i].second;
if (v[index] != 0)
continue;
if (v[left(index)] != 0 && v[right(index)] != 0)
v[index] = max(v[left(index)], v[right(index)]) + 1;
if (v[left(index)] == 0)
fill(index, 1);
if (v[right(index)] == 0)
fill(index, -1);
}
long long answer = 0;
for(int i = 0; i < n; ++i){
answer += v[i];
}
printf("%lld\n", answer);
}
return 0;
}
第四题，被数据量吓到了，但是这个数据量，肯定要二分长度，简单算下N*log(L)应该是可以过，所以二分最大长度，朴素的check是否满足就可以了
思路：能否等分出m个长度为L的绳子，在l ∈ [0, L] 上是个不减问题，即如果某个满足此条件的最大位置为l，则大于l的无法等分，小于l的可以等分
因此，二分满足题意的L，找到最大位置判断即可，复杂度已经算过是OK的，注意停止条件和输出位数有关；以及边界问题（r减 l不增，因为k是满足的）
代码，怕python不过，直接c++了：
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
int n, m, x;
vector<double> a;
inline bool check(double l){
int count = 0;
for(int i = n - 1; i >= 0 && a[i] >= l; --i){
count += floor(a[i] / l);
}
return count >= m;
}
inline double solve(int m){
double l = 0.f, r = a[n-1] + 1.f;
while( r - l > 1e-3){
double k = (l + r) / 2;
if (check(k))
l = k;
else
r = k - 0.001;
}
return l;
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 0; i < n; ++i){
scanf("%d", &x);
a.push_back((double)x);
}
sort(a.begin(), a.end());
printf("%.2lf", solve(m));
return 0;
}
第三题卡了被Python好久，总以为复杂度算错了T_T
以上。祝大家都能拿到满意offer，许愿~
微软公司福利 56人发布
查看45道真题和解析