1.1.1 如何实现一个高效的单向链表逆序输出?
出题人:阿里巴巴出题专家:昀龙/阿里云弹性人工智能负责人
参考答案:下面是其中一种写法,也可以有不同的写法,比如递归等。供参考。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
| typedef struct node{ int data; struct node* next; node(int d):data(d), next(NULL){} }node;
void reverse(node* head) { if(NULL == head || NULL == head->next){ return; } node* prev=NULL; node* pcur=head->next; node* next; while(pcur!=NULL){ if(pcur->next==NULL){ pcur->next=prev; break; } next=pcur->next; pcur->next=prev; prev=pcur; pcur=next; } head->next=pcur; node*tmp=head->next; while(tmp!=NULL){ cout<<tmp->data<<"\t"; tmp=tmp->next; } }
|
1.1.2 题目:已知 sqrt (2)约等于 1.414,要求不用数学库,求 sqrt (2)精确到小数点后 10 位。
出题人:——阿里巴巴出题专家:文景/阿里云 CDN 资深技术专家
考察点
- 基础算法的灵活应用能力(二分法学过数据结构的同学都知道,但不一定往这个方向考虑;如果学过数值计算的同学,应该还要能想到牛顿迭代法并解释清楚)
- 退出条件设计
解决办法
已知 sqrt(2)约等于 1.414,那么就可以在(1.4, 1.5)区间做二分
查找,如:
a) high=>1.5
b) low=>1.4
c) mid => (high+low)/2=1.45
d) 1.45*1.45>2 ? high=>1.45 : low => 1.45
e) 循环到 c)
退出条件
a) 前后两次的差值的绝对值<=0.0000000001, 则可退出
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| const double EPSINON = 0.0000000001;
double sqrt2( ){ double low = 1.4, high = 1.5; double mid = (low + high) / 2; while (high - low > EPSINON){ if (mid*mid > 2){ high = mid; } else{ low = mid; } mid = (high + low) / 2; } return mid; }
|