解答算法题的一个小技巧

简介: 解答算法题的一个小技巧

坦白说,这不是一篇怎么教你用具体的哪一门编程语言来编程的文章,而是想和大家分享一下如何用程序来解决一个具体问题。

最近面试的时候,会出一些简单的题,主要是想考察一下面试对象的逻辑能力。题目本身很简单,也算面试中的常见题了,然而还是有很多人做不出来。我认为主要还是解题思路的问题。

这里我们先给大家看看题目:

给你一个整数n. 从 1 到 n 按照下面的规则打印每个数:

  1. 如果这个数被3整除,打印fizz;
  2. 如果这个数被5整除,打印buzz;
  3. 如果这个数能同时被3和5整除,打印fizz buzz;
  4. 如果这个数既不能被3整除,也不能被5整除,打印它本身。

很多程序员,有些已经有很多年工作经验的程序员,一看到题目很快的就开始码代码了,最后改来改去,有些改成功了,大部分的并不能完全处理这三种情况,解题以失败告终。

这道题其实并不难,只有用合理的解题思路,一定可以轻松的写出来答案。

那么正确的解题思路是什么?对于任意复杂的算法题,大体都可以分这几步来完成:

  1. 分析题目,理解题目的要求;
  2. 用自然语言描述解题思路;
  3. 用伪代码来描述算法;
  4. 编程
  5. 重构

大体上一个算法题,都必须经历这几个过程,有些简单的题目,2,3这两步可以省略,但也增加了第4步的难度。有一个小窍门就是,1-3步最好在纸上完成。

从我个人经历来说,我们毕竟从小到大都是面对的纸质的课本、试卷,因此,我觉得在纸上写答案会更自然一些,思路也会更加清晰一些。当然,现在是数字时代了,可能大家的感受不太一样。

以这道题为例,第一步我们先分析一下这道题考的是什么?即所谓的考点。这个题主要考察的是同学对 if 这种选择结构的掌握,也考察了同学对各种条件逻辑推理能力。很多人的容易忽略的就是题目中第三个条件,只处理了题目中第一、二种可能。

分析完题目以后,可以尝试用我们自己的语言来重新组织一下这个题目:给一个整数n,然后打印从1到n的数字,如果是3的倍数的话打印fizz,如果是5的倍数的话打印成buzz,如果正好既是3的倍数也是5的倍数那么输出fizz buzz。

这么一说我们就很清楚了,要处理四种情况,一种这个数是3的倍数,一种是这个数是5的倍数,一种是这个数是3 * 5的倍数,一种是其他不满足以上条件的数。

接下来我们可以尝试把上面的这段话写成伪代码,为了便于理解,我们用中文来写这段伪代码:

n.times do  | i |
  假如 i 是3的倍数, 打印fizz
  假如 i 是5的倍数,打印buzz
  假如i 是3 * 5的倍数, 打印fizz buzz
  其他 打印 i
end

这里需要考虑的一点是,如果按照以上的伪代码,如果 i = 15, 那么打印出来的是fizzbuzzfizz buzz, 而我们要的是fizz buzz, 所以我们要调整一下我们的伪代码:

n.times do  | i |
  假如i 是3 * 5的倍数, 打印fizz buzz;next;
  假如 i 是3的倍数, 打印fizz
  假如 i 是5的倍数,打印buzz
  其他 打印 i
end

这时候,我们的思路已经很清晰了,我们可以开始对着编辑器来编程了:

def print_numbers( n)
    n.times do | i |
        if i % 15 == 0
           print "fizz buzz"
           next
        elsif i % 3 == 0
           print " fizz "
        elsif i % 5 == 0
           print " buzz "
         else
           print " #{i} "
         end
    end
end

这里写代码有两个技巧:1. 第一时间内闭合。比如说你写了 {, 那么要第一时间 写 } (当然现在很多都是编辑器帮我们完成了) 2. 我们能完成的,别让机器来完成。比如第一个条件,可以写成 i % 3 == 0 and i %5 == 0, 但是我们写成 i % 15 ==0 提高了程序运行的效率。

这时候我们可以尝试运行一下代码:

print_numbers(16)
=>  fizz buzz 1  2  fizz  4  buzz  fizz  7  8  fizz  buzz  11  fizz  13  14 fizz buzz=> 16

竟然多了一个fizz buzz, 少了一个16, 这和我们的想要的结果差一点。

究其原则是因为 n.times 是从 0 开始,所以我们可以fix 一下这个 bug:

def print_numbers( n)
    n.times do | i |
        if (i + 1) % 15 == 0
           print "fizz buzz"
           next
        elsif (i + 1) % 3 == 0
           print " fizz "
        elsif (i + 1) % 5 == 0
           print " buzz "
         else
           print " #{ i  + 1} "
         end
    end
end

这时候输出的结果是:

pry(main)> print_numbers 16
1  2  fizz  4  buzz  fizz  7  8  fizz  buzz  11  fizz  13  14 fizz buzz 16 => 16

和我们想要的是一样的。

这里面我们看到有四个 ( i + 1), 对于同样的数字,程序要计算四次,所以我们可以简单重构一下:

def print_numbers( n)
    n.times do | i |
        m = i + 1
        if m % 15 == 0
           print "fizz buzz"
           next
        elsif m % 3 == 0
           print " fizz "
        elsif m % 5 == 0
           print " buzz "
         else
           print " #{ i  + 1} "
         end
    end
end

至此, 我们的编程工作貌似基本完成了。为什么说貌似完成了呢?因为在实际生产中假如我们需要实现一个这样的功能的话,可能我们还需要做好应对修改的准备。

而且,在以上写代码的过程中,我们第一次实现的代码竟然引入了一个bug。

如何能避免出现这样的问题呢?我们可以求助于测试驱动开发,即TDD, 当然这又是另外一个话题了。

相关文章
|
9月前
|
存储 算法 容器
算法刷题小技巧【持续补充~】
算法刷题小技巧【持续补充~】
37 2
|
算法
超实用的算法小技巧
本篇文章我们将介绍一些超级实用的算法小技巧,灵活使用这些算法小技巧可以帮助我们更好的解决遇到的问题,让我们的时间复杂度,空间复杂度大大降低,有效的提高我们的编程能力。
163 0
|
存储 算法 Java
【算法攻坚】整数翻转的小技巧
【算法攻坚】整数翻转的小技巧
166 0
|
Web App开发 JSON JavaScript
|
1天前
|
算法 数据安全/隐私保护 计算机视觉
基于FPGA的图像双线性插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
本项目展示了256×256图像通过双线性插值放大至512×512的效果,无水印展示。使用Matlab 2022a和Vivado 2019.2开发,提供完整代码及详细中文注释、操作视频。核心程序实现图像缩放,并在Matlab中验证效果。双线性插值算法通过FPGA高效实现图像缩放,确保质量。
|
1月前
|
算法 数据安全/隐私保护 计算机视觉
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。
|
1月前
|
算法 数据可视化 安全
基于DWA优化算法的机器人路径规划matlab仿真
本项目基于DWA优化算法实现机器人路径规划的MATLAB仿真,适用于动态环境下的自主导航。使用MATLAB2022A版本运行,展示路径规划和预测结果。核心代码通过散点图和轨迹图可视化路径点及预测路径。DWA算法通过定义速度空间、采样候选动作并评估其优劣(目标方向性、障碍物距离、速度一致性),实时调整机器人运动参数,确保安全避障并接近目标。
146 68
|
1月前
|
算法 数据安全/隐私保护
室内障碍物射线追踪算法matlab模拟仿真
### 简介 本项目展示了室内障碍物射线追踪算法在无线通信中的应用。通过Matlab 2022a实现,包含完整程序运行效果(无水印),支持增加发射点和室内墙壁设置。核心代码配有详细中文注释及操作视频。该算法基于几何光学原理,模拟信号在复杂室内环境中的传播路径与强度,涵盖场景建模、射线发射、传播及接收点场强计算等步骤,为无线网络规划提供重要依据。
|
2天前
|
传感器 算法 物联网
基于粒子群算法的网络最优节点部署优化matlab仿真
本项目基于粒子群优化(PSO)算法,实现WSN网络节点的最优部署,以最大化节点覆盖范围。使用MATLAB2022A进行开发与测试,展示了优化后的节点分布及其覆盖范围。核心代码通过定义目标函数和约束条件,利用PSO算法迭代搜索最佳节点位置,并绘制优化结果图。PSO算法灵感源于鸟群觅食行为,适用于连续和离散空间的优化问题,在通信网络、物联网等领域有广泛应用。该算法通过模拟粒子群体智慧,高效逼近最优解,提升网络性能。
|
2天前
|
机器学习/深度学习 数据采集 算法
基于GWO灰狼优化的CNN-GRU-SAM网络时间序列回归预测算法matlab仿真
本项目基于MATLAB2022a,展示了时间序列预测算法的运行效果(无水印)。核心程序包含详细中文注释和操作视频。算法采用CNN-GRU-SAM网络,结合灰狼优化(GWO),通过卷积层提取局部特征、GRU处理长期依赖、自注意力机制捕捉全局特征,最终实现复杂非线性时间序列的高效预测。

热门文章

最新文章