8.31顺丰秋招算法工程师笔试题求解

麻了,以前都是这么难得题吗,这尼玛。。。就只能得个十几分一共,有没有大佬能帮忙写个题解呢?选择题也是不当人。

1. 猜排列游戏
有一个1到n整数组成的排列,现在来猜这个排列是什么,每次可以猜某一位置的数字,得到的反馈是“大了”,“小了”或者“正确”。求最坏的情况下需要猜测几次,才能在所有位置得到“正确”?

输入一个整数n
输出最坏情况下的猜测次数

例:
输入:
5
输出:
11

2. 圣诞树
圣诞树由n个节点组成,每个节点上为一个整数(可为负数),节点从1到n编号。每次操作需选择一个包含1号节点的子图,并将子图中所有节点的值+1或者-1,请问至少需要操作多少次,才能让所有节点的值都是0?

输入包含三行
第一行是节点个数n
第二行是n-1个数据表示节点(i = 2, 3, 4 ...)的父亲节点
第三行是n个数据表示(i = 1, 2, 3, ...)节点的初始值

输出最少操作次数

例:
输入:
3
1 1
1 -1 1

输出:
3

#顺丰##笔试算法题##算法题##求助##算法题目求助#
全部评论
第一题应该是对枚举每个i,求log2。 因为最坏的情况应该是1/n这种最难被二分到的在首部,n/2这种容易被二分到的在尾部。 第二题直接摆了……图的完全不会直接进行一个re的turn
2 回复 分享
发布于 2022-08-31 20:55 湖北
第一题搜每位我用的二分,然后过了80多,超时了,这两题感觉都挺麻烦的
点赞 回复 分享
发布于 2022-08-31 20:51 江苏
第一题:类似折半查找顺序表中每个元素的成功查找次数总和,先找到节点数≤n的最大的满二叉树,高度为floor(log2(n)),然后最后一层的节点数为n-满二叉树的节点数。构造二分查找树,然后求每个节点查找成功的查找次数,相加。 #include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){   ll n, res = 0;   cin>>n;   ll height = floor(log2(n));   ll leaves = n - ll(pow(2, height) - 1);   for(int i = 1; i <= height; ++i){     res += ll(pow(2, i - 1)) * i;   }   res += leaves * (height + 1);   cout<<res<<endl;   return 0; } 第二题:B - Zero Tree原题。
1 回复 分享
发布于 2022-08-31 21:06 江苏
第1题我都没读懂。。。为什么是11次啊,都没有样例解释。而且第二道做的不一样
点赞 回复 分享
发布于 2022-08-31 20:53 北京
第一题a了,第二题不会。     public static long find(int n) {         long ans = 0, num = 1, i = 2;         while (i <= n) {             if (i * 2 <= n) {                 ans += (i * num++);                 i *= 2;             } else {                 ans += ((n - i + 1) * num);                 break;             }         }         return ans + n;     }
1 回复 分享
发布于 2022-08-31 20:58 重庆
第一题直接输出11能过38%
点赞 回复 分享
发布于 2022-08-31 21:02 安徽

相关推荐

3 9 评论
分享
牛客网
牛客企业服务