一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1852|回复: 9
收起左侧

[编程题] 论python狗的优越感

[复制链接] |试试Instant~ |关注本帖
Linzertorte 发表于 2015-9-12 14:03:19 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
楼主不是python狗,但是感觉有些面试题,你用python来写,面试官会比较无语,但是他有什么办法呢。。。感觉python简直是推土机,见到一些题目就辗压过去。

就说面经里重复出现的一个题。

http://www.1point3acres.com/bbs/ ... p;page=1#pid1982933
http://www.1point3acres.com/bbs/thread-139727-1-1.html


write a fuction to add operator(+-*/) to a string so it equals to a target value
for example
123,6 -> 1+2+3. Waral 鍗氬鏈夋洿澶氭枃绔�,
12345, 27-> 1+2*3+4*5

这个题目啊,刷过几个题的人,但是刷得不是特别多的人,可能会觉得挺简单啊,回溯一下就好了。两个数字间有五种情况,不加操作符或者加四个操作符之一。
但是细看,这题的坑还是很多。我们假设这个输入的数字不是特别多(n个) 5^n是枚举的复杂度.
C++ int型也就2x10^9左右吧,由于n不会特别多,就姑且认为不会溢出吧。(但是你还是要估计一下才放心)
再一个坑就是/的情况,这是算浮点数的除法,还是整数除法(即3/2=1这种不要小数部分的除法).除数为零的时候直接算,就异常了啊。

再一个大坑,可以说比上面和复杂度都高的一个部分就是表达式的求值,大家都会波兰后缀表达式的求值,但这种中缀表达式可能就没接触过。
那我们可以用把中缀转为后缀再求值,恩,这个算法是经典算法,叫做dijkstra双栈扫描法,这个算法也不是那么直观,也容易忘。
但是本题的表达式没有括号,这就好办了,divide-conquer来,就很容易了。
  1. #include<iostream>
  2. #include<string.h>
  3. using namespace std;
  4. int eval_sub(const char *s,const char *t){
  5.     const char *p;
  6.     int lhs,rhs;
  7.     for(p=t-1;p>=s;p--) if(*p=='+'||*p=='-') break;
  8.     if(p>=s) {
  9.         lhs = eval_sub(s,p), rhs = eval_sub(p+1,t);
  10.         if(*p=='+') return lhs+rhs;
  11.         if(*p=='-') return lhs-rhs;
  12.     }
  13.     for(p=t-1;p>=s;p--) if(*p=='*'||*p=='/') break;
  14.     if(p>=s) {
  15.         lhs = eval_sub(s,p), rhs = eval_sub(p+1,t);
  16.         if(*p=='*') return lhs*rhs;
  17.         if(*p=='/') return lhs/rhs;
  18.     }
  19.     int x = 0;
  20.     for(p=s;p<t;p++) x = x*10 + (*p-'0');
  21.     return x;
  22. }
  23. int eval(const char *expr){
  24.     int n = strlen(expr);
  25.     return eval_sub(expr,expr+n);
  26. }
  27. int main(){
  28.     cout<<eval("3*4*56+2+3*7+490")<<endl;
  29.     cout<<eval("12*3+1+23*123*4")<<endl;
  30.     cout<<eval("1*2/2+3-2*3")<<endl;
  31. }
复制代码
上面这段代码非常好写。唯一的缺点是没有考虑除数为0的情况,这个时候,你可以判断一下除数,如果为0,抛出一个异常。或者说在求值之前就扫描一下表达式,看看/字符是不是0.

还有一个坑, 比如说1203->15,  可以可以输出12+03,这样数前面有无意义的0,这个可以与面试官沟通。 这里假设可以


但是说了这么多。推土机一来,什么都不需要了。
  1. def get_next(xs):
  2.   if xs=='':
  3.     yield ''
  4.     return
  5.   for x in get_next(xs[1:]):
  6.     for h in ['','+','-','*','/']:
  7.       yield h+xs[:1]+x

  8. def f(xs,val):
  9.   for x in get_next(xs[1:]):
  10.     try:
  11.       if eval(xs[:1]+x)==val:
  12.          return xs[:1]+x
  13.     except:
  14.       pass
  15.   return "no solution"

  16. print '123->6,',f('123',6)
  17. print '12345->27, ', f('12345',27)
复制代码
不要问我yield是什么,反正写yield显人高端就是了。

评分

4

查看全部评分

luzhuzeng 发表于 2015-9-12 14:41:03 | 显示全部楼层
python果然神器。但是如果让你分析时间空间复杂度怎么办?像Python这种高级语言如果不清楚每个函数背后的实现逻辑的话,很难说清楚空间时间复杂度啊
回复 支持 反对

使用道具 举报

 楼主| Linzertorte 发表于 2015-9-12 14:53:35 | 显示全部楼层
luzhuzeng 发表于 2015-9-12 14:41
python果然神器。但是如果让你分析时间空间复杂度怎么办?像Python这种高级语言如果不清楚每个函数背后的实 ...

5^n字数字数
回复 支持 反对

使用道具 举报

sudo_0 发表于 2015-9-13 22:59:42 | 显示全部楼层
楼主写得很好~ 我也是学Python出身的,深感python的易用性,用Java,C++就有点不习惯,懒惯了。。
不过感觉这个面试问题用脚本语言写起来应该都比较轻松,有很多现成的工具可以直接用。
回复 支持 反对

使用道具 举报

nyhenry 发表于 2015-9-14 05:21:00 | 显示全部楼层
原来你经常来这里啊。这里比mitbbs 面经什么的多
回复 支持 反对

使用道具 举报

adamzjw 发表于 2015-9-15 03:35:12 | 显示全部楼层
“推土机”这个比喻让我真的笑出声了。。
回复 支持 反对

使用道具 举报

cffls 发表于 2015-9-15 04:21:06 | 显示全部楼层
如果可以用matlab,那战斗机就飞过来了。
回复 支持 反对

使用道具 举报

小柯西 发表于 2015-10-22 04:03:16 | 显示全部楼层
python狗过来说两句。。python的确是有些magic function可以打打简化写代码的过程。但是我个人面试的时候是不用的。。就和其他语言一样,该写的逻辑还是得写。当然,python确实可以让你少考虑很多情况,比如说overflow啊啥的,不过我觉得要是自己aware,并且主动和考官提起,或者再不然,也把控制overflow的逻辑给他写出来,就好了,不碍事
回复 支持 反对

使用道具 举报

头像被屏蔽
我叫习明泽 发表于 2015-10-27 15:26:06 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 18:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表