草庐IT

Python面试常见算法题集锦（递归部分）

noproblems 2023-03-28 原文

0x1 前言

开始学习python基础的时候，有以下几种算法是面试中常见的，也是前期学习python的时候可以连带学习了解的，不卡门槛哟

0x2 实现算法的方式很多种，而算法的实现也是分程序语言的，此处用python

1.用python写一个简单的递归函数

分析：

递归函数 : 自己调用自己的函数是递归函数
递:去
归:回

触发回的过程有2个条件: 回到上一层函数调用的位置
(1) 当前这层空间函数全部执行结束的时候,触底反弹,触发回的过程
(2) 遇到return 返回值, 直接返回到上一层空间
(3) 递归: 去的过程:就是不停的开辟空间,在回的时候,不停的释放空间,递归函数就是不停的开辟和释放空间的过程
回过程:最后一层空间所有代码执行完毕,会触发回的过程,或者遇到return返回值,也会触发回的过程,回到上一层函数调用的位置

注意事项:
1.递归每一层空间都是独立的个体,独立的副本,资源不共享,可以通过参数或者返回值形成共享
2.递归务必给予跳出的条件,如果递归的层数过深,不推荐使用.容易内存溢出或者蓝屏;

代码：

def digui(n):
    """
    打印1111,2222 是为了使读者看的更清楚 去 回  的两个过程区分
    """
    if n > 0:
        print(n, "1111111")
        digui(n - 1)
    print(n, "2222222")
digui(5)

代码解析：

5 1111111
4 1111111
3 1111111 去
2 1111111
1 1111111

0 2222222

1 2222222
2 2222222
3 2222222 回
4 2222222
5 2222222

2.求任意数n的阶乘 5! 5x4x3x2x1=?

def jiecheng(n):
    if n <= 1:
        return 1
    return n * jiecheng(n - 1)


res = jiecheng(5)
print(res)

代码解析：

去的过程
n = 5 return n*jiecheng(n-1) => 5*jiecheng(4)
n = 4 return n*jiecheng(n-1) => 4*jiecheng(3)
n = 3 return n*jiecheng(n-1) => 3*jiecheng(2)
n = 2 return n*jiecheng(n-1) => 2*jiecheng(1)
n = 1 return 1

回的过程
n = 2 return n*jiecheng(n-1) => 2*1
n = 3 return n*jiecheng(n-1) => 3*2*1
n = 4 return n*jiecheng(n-1) => 4*3*2*1
n = 5 return n*jiecheng(n-1) => 5*4

 

3.斐波那契数列: 1,1,2,3,5,8,13,21,34,55 ,… 第n个数字是几?

代码：

def fbnq(n):
    if n == 1 or n == 2:
        return 1
    return fbnq(n - 1) + fbnq(n - 2)


res = fbnq(5)
print(res)

代码解析：

可以转化为斐波那契数列的方式进行求解，假设要跳N阶台阶，那么第一步有两种跳法：
（1）跳一步，后面还有n-1个台阶需要跳；
（2）跳两步，后面还有n-2个台阶需要跳。
可以看到跳n阶台阶的跳法数等于跳n-1和n-2阶台阶数的和，即F(n) = F(n-1) + F(n-2)

 

4.青蛙跳台阶: 一只青蛙要跳上n层高的台阶,一次能跳一级,也可以跳两级,请问这只青蛙有多少种跳上这个n层高台阶的方法?

代码：

def frog_jumpSteps_steps(n):
    if n in (1, 2):
        return 1
    return frog_jumpSteps_steps(n - 1) + frog_jumpSteps_steps(n - 2)


res = frog_jumpSteps_steps(5)
print(res)

代码解析：

可以转化为斐波那契数列的方式进行求解，假设要跳N阶台阶，那么第一步有两种跳法：
（1）跳一步，后面还有n-1个台阶需要跳；
（2）跳两步，后面还有n-2个台阶需要跳。
可以看到跳n阶台阶的跳法数等于跳n-1和n-2阶台阶数的和，即F(n) = F(n-1) + F(n-2)

 

Python面试spanstylefont算法与数据结构

有关Python面试常见算法题集锦（递归部分）的更多相关文章

  1. python - 如何使用 Ruby 或 Python 创建一系列高音调和低音调的蜂鸣声？ - 2

    关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。

  2. Python 相当于 Perl/Ruby ||= - 2

    这个问题在这里已经有了答案:关闭10年前。PossibleDuplicate:Pythonconditionalassignmentoperator对于这样一个简单的问题表示歉意，但是谷歌搜索||=并不是很有帮助；)Python中是否有与Ruby和Perl中的||=语句等效的语句？例如:foo="hey"foo||="what"#assignfooifit'sundefined#fooisstill"hey"bar||="yeah"#baris"yeah"另外，类似这样的东西的通用术语是什么？条件分配是我的第一个猜测，但Wikipediapage跟我想的不太一样。

  3. java - 什么相当于 ruby​​ 的 rack 或 python 的 Java wsgi？ - 2

    什么是ruby​​的rack或python的Java的wsgi？还有一个路由库。 最佳答案 来自Python标准PEP333:Bycontrast,althoughJavahasjustasmanywebapplicationframeworksavailable,Java's"servlet"APImakesitpossibleforapplicationswrittenwithanyJavawebapplicationframeworktoruninanywebserverthatsupportstheservletAPI.ht

  4. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  5. 华为OD机试用Python实现 -【明明的随机数】 2023Q1A - 2

    华为OD机试题本篇题目：明明的随机数题目输入描述输出描述：示例1输入输出说明代码编写思路最近更新的博客华为od2023|什么是华为od，od薪资待遇，od机试题清单华为OD机试真题大全，用Python解华为机试题|机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为o

  6. 【Java 面试合集】HashMap中为什么引入红黑树，而不是AVL树呢 - 2

    HashMap中为什么引入红黑树，而不是AVL树呢1.概述开始学习这个知识点之前我们需要知道，在JDK1.8以及之前，针对HashMap有什么不同。JDK1.7的时候，HashMap的底层实现是数组+链表JDK1.8的时候，HashMap的底层实现是数组+链表+红黑树我们要思考一个问题，为什么要从链表转为红黑树呢。首先先让我们了解下链表有什么不好？？？2.链表上述的截图其实就是链表的结构，我们来看下链表的增删改查的时间复杂度增：因为链表不是线性结构，所以每次添加的时候，只需要移动一个节点，所以可以理解为复杂度是N(1)删：算法时间复杂度跟增保持一致查：既然是非线性结构，所以查询某一个节点的时候

  7. python - 如何读取 MIDI 文件、更改其乐器并将其写回？ - 2

    我想解析一个已经存在的.mid文件，改变它的乐器，例如从“acousticgrandpiano”到“violin”，然后将它保存回去或作为另一个.mid文件。根据我在文档中看到的内容，该乐器通过program_change或patch_change指令进行了更改，但我找不到任何在已经存在的MIDI文件中执行此操作的库.他们似乎都只支持从头开始创建的MIDI文件。 最佳答案 MIDIpackage会为您完成此操作，但具体方法取决于midi文件的原始内容。一个MIDI文件由一个或多个音轨组成，每个音轨是十六个channel中任何一个上的

  8. 「Python｜Selenium｜场景案例」如何定位iframe中的元素？ - 2

    本文主要介绍在使用Selenium进行自动化测试或者任务时，对于使用了iframe的页面，如何定位iframe中的元素文章目录场景描述解决方案具体代码场景描述当我们在使用Selenium进行自动化测试的时候，可能会遇到一些界面或者窗体是使用HTML的iframe标签进行承载的。对于iframe中的标签，如果直接查找是无法找到的，会抛出没有找到元素的异常。比如近在咫尺的例子就是，CSDN的登录窗体就是使用的iframe，大家可以尝试通过F12开发者模式查看到的tag_name,class_name,id或者xpath来定位中的页面元素，会抛出NoSuchElementException异常。解决

  9. git使用常见问题（提交代码，合并冲突） - 2

    文章目录git常用命令（简介，详细参数往下看）Git提交代码步骤gitpullgitstatusgitaddgitcommitgitpushgit代码冲突合并问题方法一：放弃本地代码方法二：合并代码常用命令以及详细参数gitadd将文件添加到仓库：gitdiff比较文件异同gitlog查看历史记录gitreset代码回滚版本库相关操作远程仓库相关操作分支相关操作创建分支查看分支：gitbranch合并分支：gitmerge删除分支：gitbranch-ddev查看分支合并图：gitlog–graph–pretty=oneline–abbrev-commit撤消某次提交git用户名密码相关配置g

  10. python ffmpeg 使用 pyav 转换 一组图像 到 视频 - 2

    2022/8/4更新支持加入水印水印必须包含透明图像，并且水印图像大小要等于原图像的大小pythonconvert_image_to_video.py-f30-mwatermark.pngim_dirout.mkv2022/6/21更新让命令行参数更加易用新的命令行使用方法pythonconvert_image_to_video.py-f30im_dirout.mkvFFMPEG命令行转换一组JPG图像到视频时，是将这组图像视为MJPG流。我需要转换一组PNG图像到视频，FFMPEG就不认了。pyav内置了ffmpeg库，不需要系统带有ffmpeg工具因此我使用ffmpeg的python包装p

随机推荐