网易笔试，求最大奇约数和，O(n)复杂度超时
有跑出来的吗，我用python时间超了。
还是直接公式推出来的。
2016-09-12 21:10 成都信息工程大学 Java
关注
全部评论
LocksonJu
华南理工大学
long long findSum(int N)
{
if (N == 1)
return 1;
long long k = (N + 1) / 2;
return k*k + findSum(N / 2);
}
神公式
PatronSaint
华中师大 安全工程师
我也是用python，超内存
山野闲居
西安电子科大 C++
看了讨论区logn的答案，真是觉得生无可恋了
子「月」乐
西安邮电大学 Java
在交卷的一瞬间，我知道我超时的原因了，一直除以二就可以解决问题，再次GG
项煜东
中国科学技术大学 C++
每个奇数*2*2*2。。。
之乎者也
东南大学 C++
最后想起来的，妈的交卷了，坑爹啊
Riosngdfleiw1965
中央音乐学院 PHP
最大奇约数，奇数就是本身，偶数/2直到奇数为止，但还是不行，始终要循环
紫荆的传说
北京大学 测试工程师
C++超时……
luohan
北京林业大学 算法工程师
都100亿了，O(N)肯定超时啊。O(N)在1s内也就解1亿左右的数据了，常数还不能太大
94sd
北京科技大学 算法工程师
一直除以2超时，改成移位运算超时，我真不知道怎么做了，与网易无缘了，😭
冰月冷望 楼主
楼主 成都信息工程大学 Java
哎，O(logN)
Small_White
湖南工业大学 运维工程师
超时 ，好伤心。
董泽锋
西南交通大学 C++
unsigned long long cal(unsigned long long n){
unsigned long long sum = 0;
do
{
if (n % 2 == 0) {
sum += (long long)(n/2)*(n / 2);
n = n / 2;
} else {
sum += n;
n = n - 1;
}
} while (n != 1);
return sum + 1;
}
寒武纪三叶草
开始用python一直超时，换C++才AC了
牛客615963号
国际关系学院 C++
推公式推了半天, 只能O(1)的解决一半, 剩下的一半推死推不出来.
比如对于100的话能直接算出1-64的和 , 最后没办法只好遍历了. 没想到过了.
菜豆
上海大学 测试工程师
用移位操作做除2操作就可以不超时
牛客11111111
东南大学 C++
#include <iostream>
using namespace std;
int main()
{
long n;
cin>>n;
long long res=0;
long t=2;//用t表示2^k
int count=0;
while(count<n/2)
{
for(long i=1;t*i<=n;i=i+2)//找到2^k*i<=n的所有i
{
res=res+i;
count++;
}
t=t*2;
}
if(n%2==0) //当n为奇数时，序列中的奇数和
{
res=res+n*n/4;
}
else//当n为偶数时，序列中的奇数和
{
res=res+(n+1)*(n+1)/4;
}
cout<<res<<endl;
return 0;
}
牛客300474号
西南交通大学 运维工程师
位运算可以 res = n / (n & -n) 得到最大奇数
JUST&GO
四川大学 C++
怎么说呢。我觉得其实有规律的。
每4个看成一组。
不过最近一直没去解。。当时考试考到最后几分钟才反映过来。
糖糖不爱吃糖
哈尔滨工程大学 Java
考试后，和学弟们讨论得出了答案，logn的，也去网易的笔试题真题哪里测试了下，通过了，虽然笔试中没有做出来，不过后来没有看别人的现成的答案，而是我们集思广益想出来的，还是蛮开心的，这也是笔试的收获吧
相关推荐
查看17道真题和解析 点赞 评论 收藏
分享
10-24 11:10
山西大学 Java 
点赞 评论 收藏
分享
恒生电子公司氛围 50人发布