Liam W
封面

通俗算法01 - 开篇

作者
王亮·发表于 3 年前

大家好,我计划写一个通俗的算法系列教程,今天开台吧。

开篇语

为什么要写算法系列教程呢?因为最近刚看完《Algorithms, 4th Edition》这本经典算法书(电子书,中英版网上都有下载),有了些新收获,觉得那些零散的知识点和经验有必要也值得花时间好好整理一下。另外,我自己的算法知识应该还没有达到去学好“机器学习”这门学科的程度,在写教程的同时我也会不断学习,我想和大家一起用算法这把钥匙开启“机器学习”这扇大门,去探索算法是如何让机器“学习”的。

为什么要学习算法呢?我个人觉得最终目的还是为了提高自己的职场竞争力。算法的本质就是解决问题,所以学习算法本质上是在提高解决问题的能力,这是职场最重要的能力之一。另外,如果你想在面试中表现得更加出色,也要对算法有一定程度的掌握。

写教程是很耗费精力的,而且学习算法是很枯燥的,但如果大家都能参与进来一起交流讨论,那么整个过程就是不断进行头脑风暴、集思广益的过程,这会是我继续写作的动力,这也会使得枯燥的算法学习之路变得有趣,并让每个人收获满满。

为了更方便大家利用碎片化的时间学习,更好的利用空闲时间在手机上阅读,这个系列的每一篇文章我都会精心排版,而且每一篇文章阅读时间都不会太长,会尽量控制在 6 分种以内(不包括思考的时间)。

这个系列会包含三部分内容。第一部分是算法基础,由于算法和数据结构是密切相关的,所以也会讲到一些数据结构的知识,但不会讲太细。第二部分以常见的算法案例解析为主,包括解析一些算法面试题。第三部分是算法在机器学习中的应用,由于我自己也没有学习过机器学习,所以这部分是探索式和交流式的,我会把我学到的用我理解写出来,希望大家能参与进来一起交流。

这个系列的文章代码选择用 JavaScript 语言来编写,程序语言都是相通的,我相信你看了 JavaScript 写的算法实现可以很快用你熟悉的语言写出来。但第三部分的机器学习相关内容,可能选用 Python,现在还不确定。

希望这个算法系列教程能帮助大家在今后的编程道路上得心应手。

开篇算法题:FizzBuzz

好了,我们今天以一个算法问题 FizzBuzz 来开篇吧。FizzBuzz 是一个非常典型的用来面试的算法题。下面是 FizzBuzz 的自然语言描述:

编写一个程序,打印 1 到 100 中的数字,但能被 3 整除的变为“Fizz”,能被 5 整除的变为“Buzz”,既能被 3 整除又能被 5 整除的变为“FizzBuzz”。

一看是不是很简单?确实很简单。看完题,随手就能写出下面的代码:

for (var i = 1; i < 101; i++) {
  if (i % 3 == 0) console.log('Fizz')
  else if (i % 5 == 0) console.log('Buzz')
  else if (i % 3 == 0 && i % 5 == 0) console.log('FizzBuzz')
  else console.log(i)
}

和需求吻合,好像没什么问题。等等,仔细检查,这段代码问题大了,FizzBuzz永远没有输出的机会,例如遇到 i=15 还是会输出Fizz。这是初级程序员很容易犯的一个错误,拿到需求后直接就是一通写,对需求的理解比较生硬,不容易考虑到上下文的关联关系。纠正后的写法是将第 4 行的 if 条件放到最前面:

for (var i = 1; i < 101; i++) {
  if (i % 3 == 0 && i % 5 == 0) console.log('FizzBuzz')
  else if (i % 3 == 0) console.log('Fizz')
  else if (i % 5 == 0) console.log('Buzz')
  else console.log(i)
}

这样写是对的,但如果是面试,这个答案只能算是及格。如何能做到优秀呢?我总结写算法可以分为三个步骤:

第一步是实现,即按照需求把算法写对了,让程序能正确的运行;第二步是优化,即降低复杂度,让程序运算更高效。第三步是美化,即让代码看起来美观简洁,这一步很多时候会灵活运用到程序语言本身的语法糖,但简洁有时候会牺牲代码的易读性,这需要在实际场景中稍作权衡。

做到这三步,我觉得应对面试中的算法题就可以拿优秀了。

前面我们已经完成了写 FizzBuzz 算法的第一步,我们再来做第二步:优化。既能被 3 整除又能被 5 整除,我们很自然会想到 3 和 5 的最小公倍数:15,能被 15 整除的数一定也是既能被 3 整除又能被 5 整除的。也就是说上面的第二行代码可以只对 i 判断一次(而不是两次),下面是优化后的代码:

for (var i = 1; i < 101; i++) {
  if (i % 15 == 0) console.log('FizzBuzz')
  else if (i % 3 == 0) console.log('Fizz')
  else if (i % 5 == 0) console.log('Buzz')
  else console.log(i)
}

我们再来看第三步:美化。上面我们写这个算法用了 6 行代码(包括大括号),如果要减少代码量,能减少到多少行呢?这里给到 2 行的实现方案:

for (let i = 0; i < 100; )
  console.log((++i % 3 ? '' : 'Fizz') + (i % 5 ? '' : 'Buzz') || i)

这个实现来自 Reddit 。当然也可以写成一行,但写成两行阅读体验更好。这段代码很好理解,我就不解读了,有疑问可以在留言区留言提问。

最后,对于 FizzBuzz 算法问题,你有其它的实现方案吗?欢迎在留言区讨论。