百科问答小站 logo
百科问答小站 font logo



如何评价《职人介绍所》第 21 期节目,以及嘉宾 赵劼 和 winter 的表现? 第1页

  

user avatar   jianchichen 网友的相关建议: 
      

Javascript的那个3重循环,明显很久没做算法题了,就先不说了;

伪代码那个是错的啊,有这么几个地方:

1. if (r < j) continue; //这句是错的,应该是 if (r <= j),否则我给你一个[-2, 1, 2] 你会给我输出一个 [-2, 1, 1]。

2. 查重仍然不够。即使把(1)的错误改掉,仍然会有错,比如有 [-2, 1, 1, 1],这个伪代码会把 [-2, 1, 1]输出两次,而题目要求是 unique triplet。

另外,用hashtable显然比binarysearch时间复杂度低,伪代码的复杂度是O(n^2 log(n)),如果用hash就是O(n^2)。

当然复杂度的问题并不太大,你如果额外说只能用O(1)的空间那我也接受。但是 edge case 不考虑好,就是不及格啊,尤其是上来就声称“这题我见过,知道怎么做”的情况下,写成这样真是挺糟糕的。


user avatar   chenghan 网友的相关建议: 
      

首先,题目:

3Sum | LeetCode OJ

节目中答应了大家要放出

@winter

@赵劼

写的代码。

下面两张是二位分析 winter 代码的分析过程,实在看不懂了……


限于节目的时长,我们没有把整个的创作过程、review 过程及评价过程放出来。要是感兴趣的人多,我们找机会再把这个部分的完整版视频放出来?

更新:完整版来了,请戳→

《职人介绍所》第 21 期:你们要的 winter 赵劼徒手写码到分析代码完整版

user avatar   Ivony 网友的相关建议: 
      

真可怜,被要求手写代码,还不能掀桌子。

============================================

正经答题好了。

先讲这个算法题好了。


其实从题目来讲,这个题目太难了,而且过分侧重于底层的算法而不是高层的结构。

leetcode的题很多时候其实是一种基本功的训练,简单说这个题目就像是请两个数学教授来解一个大型的不定积分,并不能体现出超乎常人的能力出来。

这种题目要面试的时候手写真的是要掀桌子的。而且从答案来看,老赵确实占便宜了。像这种算法题,最麻烦的是你要知道坑在哪里,而你没做过的话就很难搞清楚。

老赵上来直接排序然后两重循环+BinarySearch,就是因为他知道这条简单直接的路是没有坑的,winter没见过吃亏了。至于排重的问题, HashSet的时间复杂度是O(n)(创建O(n),查询O(1),总体O(n)),也就是不会增加时间复杂度,除非你其他部分的时间复杂度做到了O(n)这个程度了(当然复杂度不代表最终的时间)。

那个Hash很明显是指HashSet应该可以代替BinarySearch提升性能嘛。



最后讲点别的。

很多时候最佳方案不是最好的方案,如果面试遇到这种问题,在没有限定复杂度的情况下,三重循环+结果排重是最稳妥的实现,稍微优化一下就可以得到老赵的代码。先做出来再去优化,比做不出来要好很多。


写了个风骚的版本,也通过leetcode了。。。。。

       public class Solution {   public IList<IList<int>> ThreeSum( int[] nums )   {     var all = new HashSet<int>( nums );     var left = new HashSet<int>();     var right = new HashSet<int>();     var doubles = new HashSet<int>();     var zeros = 0;      if ( nums.Length < 3 )       return new int[][] { };      foreach ( var i in nums )     {       if ( i < 0 )       {         if ( left.Add( i ) == false )           doubles.Add( i );       }       else       {         if ( right.Add( i ) == false )           doubles.Add( i );          if ( i == 0 )           zeros++;       }      }      var result = from i in left                  from j in right                  let k = -(i + j)                  where all.Contains( k ) && (k != i || doubles.Contains( i )) && (k != j || doubles.Contains( j ))//这里是避免只出现一次的数字被两次添加到结果                  select k > j ? new { i, j, k } : k > i ? new { i, j = k, k = j } : new { i = k, j = i, k = j };//这里是排序,为后面的排重做准备      var _result = result.Distinct().Select( item => new[] { item.i, item.j, item.k } ).ToList();     if ( zeros >= 3 )       _result.Add( new[] { 0, 0, 0 } );//这里是000补丁     return _result.ToArray();   }  }      

其实我主要是想测试一下leetcode对LINQ Expression的支持程度。


算法很简单,就是把正负数配对,然后看他们的和的取反是不是存在,存在就说明这是一个合法的结果。

其实相当暴力,但关键在于正负数配对,导致性能可以很大提升。

因为三个数之和要等于零,必然是++-、--+和000(我们把0归到+或-之一)这三种情况中的一种。


顺便说一句这个纯属卖弄风骚的代码版本,竟然是C#里面跑最快的?突然很奇怪其他人都写了些啥?!(╯°Д°)╯ ┻━┻


user avatar   xiao-jing-mo 网友的相关建议: 
      

想了想,如果是我的话,我会有三个反应。

1,事先告知不要问我狗屎题

2,如果非要问狗屎题,那么必须提前一个月告诉我,不然我不好准备

3,如果观众喜欢狗屎,那么就准备一坨更大的狗屎,让观众满意



请了老赵和 winter,结果拖住别人做这种狗屎题……

难道不应该问一点编程的心法,设计的思想,人生的经验吗

还是说知乎的这个节目只想面向知乎的核心用户群……




  

相关话题

  如何评价 4 月 19 日腾讯官宣再次启动战略升级,设立「可持续社会价值事业部」? 
  同事一点都不在乎程序性能,该怎么沟通? 
  面试时 HR 问你怎么看待阿里月饼事件,作为程序员要怎么回答? 
  如何看待 10 月 30 日国内发布的华为 Mate40 系列,有哪些惊喜与遗憾? 
  中国的软件为什么没有国外的发达? 
  世界上正在发生着哪些国内少有人关注的重要变革? 
  程序员为了期权加入创业公司,值得吗? 
  为什么高达要用剑等冷兵器? 
  雷军会是下一个马斯克吗? 
  Windows 95 的发布当时在消费者群体中造成的反响有多大? 

前一个讨论
当年取得庚子赔款的留学生究竟有多优秀?
下一个讨论
有哪些东西是你读大学以后才懂的?





© 2024-05-17 - tinynew.org. All Rights Reserved.
© 2024-05-17 - tinynew.org. 保留所有权利