基础

Python有哪些特点和优点

  • 可解释
  • 具有动态特性
  • 面向对象
  • 简明简单
  • 开源
  • 具有强大的社区支持

python2和python3区别

  • Python3 使用 print
  • python2 range(1,10)返回列表，python3中返回迭代器，节约内存
  • python2中使用ascii编码，python中使用utf-8编码
  • python2中unicode表示字符串序列，str表示字节序列,python3中str表示字符串序列，byte表示字节序列
  • python2中为正常显示中文，引入coding声明，python3中不需要
  • python2中是raw_input()函数，python3中是input()函数

数据类型

基本数据类型 : 整型,浮点型,字符串,布尔型
容器类型 : 列表,元组,集合,字典

Python中有多少种运算符

7种运算符：算术运算符、关系运算符、赋值运算符、逻辑运算符、位运算符、成员运算符、身份运算符。

身份运算符:通过身份运算符‘is’和‘is not’，我们可以确认两个值是否相同。

Python中的标识符长度能有多长？

标识符可以是任意长度。此外，我们在命名标识符时还必须遵守以下规则：

  1. 只能以下划线或者 A-Z/a-z 中的字母开头
  2. 其余部分可以使用 A-Z/a-z/0-9
  3. 区分大小写
  4. 关键字不能作为标识符

在Python中如何使用多进制数字？

  • 二进制数字由0和1组成，我们使用 0b 或 0B 前缀表示二进制数。
  • 八进制数由数字 0-7 组成，用前缀 0o 或 0O 表示 8 进制数。
  • 十六进数由数字 0-15 组成，用前缀 0x 或者 0X 表示 16 进制数。
1
2
3
x = int(0b1010)
x = int(0o1010)
x = int(0x1010)

列出5个标准库

os
re
math
readom
asyncio
datetime
collections
functools
copy
urllib
pickle
itertools

什么是封装

封装可以分成两种:

  1. 对同一类方法封装到类中

    比如将数据库的增删改查封装成class DB类

  2. 将数据封装到对象中

    比如将age,name属性封装到Person对象中

什么是GIL

全局解释器锁

  • 同一进程中有多个线程运行，一个线程在运行python程序的时候会霸占python解释器（加了一把锁即GIL），使该进程内的其他线程无法运行，等该线程运行完后其他线程才能运行。

  • 如果线程运行过程中遇到耗时操作，则解释器锁解开，使其他线程运行。所以在多线程中，线程的运行仍是有先后顺序的，并不是同时进行。

  • 多进程中因为每个进程都能被系统分配资源，相当于每个进程有了一个python解释器，所以多进程可以实现多个进程的同时运行，缺点是进程系统资源开销大

什么是闭包

嵌套函数在其外部区域引用了一个值时，该嵌套函数就是一个闭包。其意义就是会记录这个值。

什么是__dict__

  • 类的静态函数、类函数、普通函数、全局变量以及一些内置的属性都是放在类__dict__里的。对象的__dict__中存储了一些self.xxx的一些东西

  • 一个实例的__dict__属性仅仅是那个实例的实例属性的集合，并不包含该实例的所有有效属性。

  • dir()函数会自动寻找一个对象的所有属性，包括__dict__中的属性。

    __dict__是dir()的子集，dir()包含__dict__中的属性。

什么是装饰器

  1. 装饰器本质上是一个callable object ，它可以让其他函数在不需要做任何代码变动的前提下增加额外功能，装饰器的返回值也是一个函数对象。
  2. 装饰器本质上是⼀个python函数，这个函数的特点是可以接受其它的函数当作它的参数，并将其替换成一个新的函数,它可以在让其他函数在不需要做任何代码的变动的前提下增加额外的功能；
  3. 装饰器的返回值也是⼀个函数的对象
  4. 用于插入日志、性能测试、事务处理、缓存、权限校验等场景。有了装饰器，就可以抽离出大量与函数功能本身无关的雷同代码并继续重用。

什么样的语言能够用装饰器

函数可以作为参数传递的语言，可以使用装饰器

什么是协程

协程：是一种用户态的轻量级线程，协程的调度完全由用户控制

协程主要解决的还是并发的问题，以及python GIL带来的并行处理能力。

什么是哈希函数

散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。创建一个叫做散列值的指纹

什么是猴子补丁

在运行期间动态修改一个类或模块。

什么是内存溢出,内存泄漏

  • 内存泄漏memory leak :
    是指程序在申请内存后，无法释放已申请的内存空间，一次内存泄漏似乎不会有大的影响，但内存泄漏堆积后的后果就是内存溢出。

    • 有__del__()函数的对象间的循环引用是导致内存泄露的主凶。
    • 不使用一个对象时使用 del object 来删除一个对象的引用计数就可以有效防止内存泄露问题。

  • 内存溢出 out of memory :
    指程序申请内存时，没有足够的内存供申请者使用，或者说，给了你一块存储int类型数据的存储空间，但是你却存储long类型的数据，那么结果就是内存不够用，此时就会报错,即所谓的内存溢出。

  • 内存溢出就是你要的内存空间超过了系统实际分配给你的空间，此时系统相当于没法满足你的需求，就会报内存溢出的错误。
  • 内存泄漏是指你向系统申请分配内存进行使用(new)，可是使用完了以后却不归还(delete)，结果你申请到的那块内存你自己也不能再访问，而系统也不能再次将它分配给需要的程序。

什么是多线程竞争

  • 线程是非独立的，同一个进程里线程是数据共享的，当各个线程访问数据资源时会出现竞争状态,即：数据几乎同步会被多个线程占用，造成数据混乱，即所谓的线程不安全
  • 怎么解决多线程竞争问题？ 锁
  • 锁的好处： 确保了某段关键代码（共享数据资源）只能由一个线程从头到尾完整地执行能解决多线程资源竞争下的原子操作问题。
  • 锁的坏处： 阻止了多线程并发执行，包含锁的某段代码实际上只能以单线程模式执行，效率就大大地下降了
  • 锁的致命问题: 死锁

什么是锁，有哪几种锁

  • 锁(Lock)是python提供的对线程控制的对象。
  • 互斥锁，可重入锁，死锁。

什么是死锁

  • 若干子线程在系统资源竞争时，都在等待对方对某部分资源解除占用状态，结果是谁也不愿先解锁，互相干等着，程序无法执行下去，这就是死锁。

  • GIL锁 全局解释器锁
    作用： 限制多线程同时执行，保证同一时间只有一个线程执行，所以cython里的多线程其实是伪多线程！

  • 所以python里常常使用协程技术来代替多线程，协程是一种更轻量级的线程。
    进程和线程的切换时由系统决定，而协程由我们程序员自己决定，而模块gevent下切换是遇到了耗时操作时才会切换。
    三者的关系：进程里有线程，线程里有协程。

什么是同步，异步，阻塞，非阻塞

  • 同步： 多个任务之间有先后顺序执行，一个执行完下个才能执行。
  • 异步： 多个任务之间没有先后顺序，可以同时执行，有时候一个任务可能要在必要的时候获取另一个同时执行的任务的结果，这个就叫回调！
  • 阻塞： 如果卡住了调用者，调用者不能继续往下执行，就是说调用者阻塞了。
  • 非阻塞： 如果不会卡住，可以继续执行，就是说非阻塞的。

同步异步相对于多任务而言，阻塞非阻塞相对于代码执行而言。

什么是僵尸进程和孤儿进程？怎么避免僵尸进程

  • 孤儿进程： 父进程退出，子进程还在运行的这些子进程都是孤儿进程，孤儿进程将被init 进程（进程号为1）所收养，并由init 进程对他们完成状态收集工作。

  • 僵尸进程： 进程使用 fork 创建子进程，如果子进程退出，而父进程并没有调用wait 获取waitpid 获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中的这些进程是僵尸进程。

    • 启动一个程序，开始我们的任务，然后等任务结束了，我们就停止这个进程。 进程停止后， 该进程就会从进程表中移除。但是，有时候有些程序即使执行完了也依然留在进程表中。那么，这些完成了生命周期但却依然留在进程表中的进程，我们称之为 “僵尸进程”。

    • 当你运行一个程序时，它会产生一个父进程以及很多子进程。 所有这些子进程都会消耗内核分配给它们的内存和 CPU 资源。

      这些子进程完成执行后会发送一个 Exit 信号然后死掉。这个 Exit 信号需要被父进程所读取。父进程需要随后调用 wait 命令来读取子进程的退出状态，并将子进程从进程表中移除。

      若父进程正确第读取了子进程的 Exit 信号，则子进程会从进程表中删掉。

      但若父进程未能读取到子进程的 Exit 信号，则这个子进程虽然完成执行处于死亡的状态，但也不会从进程表中删掉。

  • 避免僵尸进程的方法：

    1. fork 两次用孙子进程去完成子进程的任务
    2. 用wait()函数使父进程阻塞
    3. 使用信号量，在signal handler 中调用waitpid,这样父进程不用阻塞

python中进程与线程的使用场景

多进程适合在CPU密集操作（cpu操作指令比较多，如位多的的浮点运算）。

多线程适合在IO密性型操作（读写数据操作比多的的，比如爬虫）

回调函数是如何通信的

回调函数是把函数的指针(地址)作为参数传递给另一个函数，将整个函数当作一个对象，赋值给调用的函数。

Python什么时候会造成内存溢出

  1. 一次性加载过大的文件
  2. 滥用__del__方法
  3. 关闭了垃圾回收或者将垃圾回收的阈值调得太高

Python是如何管理内存的

Python有一个私有堆空间来保存所有的对象和数据结构。

  • 计数引用
  • 垃圾回收
  • 内存池机制

Python的调优手段

  1. 手动垃圾回收

  2. 调高垃圾回收阈值

  3. 避免循环引用

Python中变量的作用域

LEGB顺序

  • L： local 函数内部作用域
  • E： enclosing 函数内部与内嵌函数之间
  • G： global 全局作用域
  • B： build-in 内置作用

可变对象和不可变对象的区别

  • 可变对象：对象存放在地址中的值不会被改变
    （所谓的改变是创建了一块新的地址并把新的对象的值放在新地址中原来的对象并没有发生变化）
  • 不可变对象：对象存放在地址中的值会原地改变

is和==区别

  • is：比较的是两个对象的id值是否相等，也就是比较俩对象是否为同一个实例对象。是否指向同一个内存地址
  • == ： 比较的两个对象的内容/值是否相等，默认会调用对象的eq()方法。

import M和from A import B区别

  • 在底层执行机制都会执行三步走,并没有没有谁比谁更节省内存之说

    • 在自己的命名空间执行被导入模块中的所有代码；
    • 以模块名为名称创建一个模块对象，并将模块中所有的顶级变量（包括变量和函数）以属性的形式绑定在该模块对象上；
    • 在import位置引入该对象名称到当前命名空间。

  • 区别在于 : 拿被导入模块中的哪些部分到当前命名空间中进行使用

__new__和__init__区别

1
2
3
4
__init__ 方法为初始化方法, __new__方法才是真正的构造函数。
__new__至少要有一个参数cls，代表当前类，此参数在实例化时由Python解释器自动识别,返回实例化出来的实例
如果__new__创建的是当前类的实例，会自动调用__init__函数
__init__有一个参数self，就是这个__new__返回的实例

copy和deepcopy区别

  1. copy.copy 浅拷贝 只拷贝父对象，不会拷贝对象的内部的子对象。
  2. copy.deepcopy 深拷贝 拷贝对象及其子对象

新式类和经典类的区别

  • 经典类在加载的时候采用的是深度优先算法，新式类采用的是广度优先算法
  • 新式类增加了__slots__内置属性, 可以把实例属性的种类锁定到__slots__规定的范围之中。
  • 新式类增加了__getattribute__方法
  • 新式类内置有__new__方法而经典类没有__new__方法而只有__init__方法
  • Python 2中默认都是经典类，只有显式继承了object才是新式类

生成器，迭代器的区别

  • 迭代器是遵循迭代协议的对象。需要对象实现__iter__和__next__方法,我们可以使用iter函数将序列改造成一个迭代器。当没有元素时，迭代器引发 StopIteration 。
  • 生成器只是在需要返回数据的时候使用yield语句。被next()调用时,生成器就会挂起。
  • 区别： 生成器能做到迭代器能做的所有事，而且因为自动创建iter()和next()方法，生成器显得特别简洁，而且生成器也是高效的，使用生成器表达式取代列表解析可以同时节省内存。除了创建和保存程序状态的自动方法，当发生器终结时，还会自动抛出StopIteration异常。

抽象类和接口类的区别和联系

  1. 抽象类：

    • 规定了一系列的方法，并规定了必须由继承类实现的方法。
    • 由于有抽象方法的存在，所以抽象类不能实例化。
    • 可以将抽象类理解为毛坯房，门窗，墙面的样式由你自己来定，所以抽象类与作为基类的普通类的区别在于约束性更强

  2. 接口类：

    • 与抽象类很相似，表现在接口中定义的方法，必须由引用类实现，但他与抽象类的根本区别在于用途：与不同个体间沟通的规则，
    • 你要进宿舍需要有钥匙，这个钥匙就是你与宿舍的接口，你的舍友也有这个接口，所以他也能进入宿舍，你用手机通话，那么手机就是你与他人交流的接口

  3. 区别和关联：

    • 接口是抽象类的变体，接口中所有的方法都是抽象的，而抽象类中可以有非抽象方法，抽象类是声明方法的存在而不去实现它的类
    • 接口可以继承，抽象类不行
    • 接口定义方法，没有实现的代码，而抽象类可以实现部分方法
    • 接口中基本数据类型为static而抽象类不是

IO密集型和CPU密集型区别

IO密集型： 系统运行，大部分的状况是CPU在等 I/O（硬盘/内存）的读/写

CPU密集型： 大部分时间用来做计算，逻辑判断等CPU动作的程序称之CPU密集型。

并行(parallel)和并发（concurrency)的区别

  • 并行： 同一时刻多个任务同时在运行
    并发： 不会在同一时刻同时运行，存在交替执行的情况。
  • 实现并行的库有： multiprocessing
    实现并发的库有: threading
  • 程序需要执行较多的读写、请求和回复任务的需要大量的IO操作，IO密集型操作使用并发更好。
  • CPU运算量大的程序，使用并行会更好

简述继承

当一个类继承自另一个类，它就被称为一个子类/派生类，继承自父类/基类/超类。它会继承/获取所有类成员（属性和方法）。

简述dir() 函数

  • 不带参数时，返回当前范围内的变量、方法和定义的类型列表；
  • 带参数时，返回参数的属性、方法的列表。

简单来说 : 返回内建方法

简述使用*args和**kwargs的含义

  • 当我们不知道向函数传递多少参数时，比如我们向传递一个列表或元组，我们就使用*args。
  • 在我们不知道该传递多少关键字参数时，使用**kwargs来收集关键字参数。

简述函数重载机制

函数重载主要是为了解决两个问题。

  1. 可变参数类型。
  2. 可变参数个数。

一个基本的设计原则是，

  • 仅仅当两个函数功能是完全相同的，此时才使用函数重载，如果两个函数的功能其实不同，那么不应当使用重载，而应当使用一个名字不同的函数。
  • 如果函数功能相同，但是参数类型不同。python本身就是动态语言,变量并没有数据类型,可以接受任何类型的参数
  • 如果函数功能相同，但参数个数不同。python可以使用缺省参数
  • 如果真的要显式的使用重载,可以使用functools里面的singledispatch函数

简述多线程、多进程

进程：

  1. 操作系统进行资源分配和调度的基本单位，多个进程之间相互独立
  2. 稳定性好，如果一个进程崩溃，不影响其他进程，但是进程消耗资源大，开启的进程数量有限制

线程：

  1. CPU进行资源分配和调度的基本单位，线程是进程的一部分
  2. 如果IO操作密集，则可以多线程运行效率高，缺点是如果一个线程崩溃，都会造成进程的崩溃

简述Python的线程同步

  1. setDaemon(False)
    主线程执行完自己的任务以后，就退出了，此时子线程会继续执行自己的任务，直到自己的任务结束。
  2. setDaemon(True)
    主线程一旦执行结束，则全部子线程被强制终止。
  3. join(线程同步)
    join 所完成的工作就是线程同步，即主线程任务结束以后，进入堵塞状态，一直等待所有的子线程结束以后，主线程再终止。

简述垃圾回收机制(引用计数机制)

  • 以引用计数为主，标记-清除和分代清除为辅
  • 标记-清除和分代回收主要是为了处理循环引用的难题。

简述设计模式

  • 设计模式是经过总结，优化的，对我们经常会碰到的一些编程问题的可重用解决方案。
  • 一个设计模式并不像一个类或一个库那样能够直接作用于我们的代码，反之，设计模式更为高级，它是一种必须在特定情形下实现的一种方法模板。
  • 常见的是工厂模式和单例模式

单例模式的应用场景

  • 资源共享的情况下，==避免由于资源操作时导致的性能或损耗==等，如日志文件，应用配置。
  • 控制资源的情况下，==方便资源之间的互相通信==。如线程池等，
    1. 网站的计数器
    2. 应用配置
    3. 多线程池
    4. 数据库配置 数据库连接池
    5. 应用程序的日志应用
    6. …

简述Python如何管理内存

  • Python有一个私有堆空间来保存所有的对象和数据结构。
  • 作为开发者，我们无法访问它，是解释器在管理它。但是有了核心API后，我们可以访问一些工具。Python内存管理器控制内存分配。
  • 另外，内置垃圾回收器会回收使用所有的未使用内存，所以使其适用于堆空间。

谈谈你对多进程，多线程，以及协程的理解，项目是否用

  • 进程：一个运行的程序（代码）就是一个进程，没有运行的代码叫程序，进程是系统资源分配的最小单位，进程拥有自己独立的内存空间，所有进程间数据不共享，开销大。
  • 线程: cpu调度执行的最小单位，也叫执行路径，不能独立存在，依赖进程存在，一个进程至少有一个线程，叫主线程，而多个线程共享内存（数据共享，共享全局变量),从而极大地提高了程序的运行效率。
  • 协程: 是一种用户态的轻量级线程，协程的调度完全由用户控制。协程拥有自己的寄存器上下文和栈。协程调度时，将寄存器上下文和栈保存到其他地方，在切回来的时候，恢复先前保存的寄存器上下文和栈，直接操中栈则基本没有内核切换的开销，可以不加锁的访问全局变量，所以上下文的切换非常快。

当退出Python时，是否释放全部内存

  • No。循环引用其它对象或引用自全局命名空间的对象的模块，在Python退出时并非完全释放。
  • 另外，也不会释放C库保留的内存部分

如何让数字闭环

  • 输入0到11正常显示
  • 输入12,返回0.输入13返回1,实现数字的闭环

使用求余:

1
num % 12

谈谈你对面向对象的理解

面向对象有三大特性：封装、继承、多态。

面向对象是相当于面向过程而言的，面向过程语言是一种基于功能分析的，以算法为中心的程序设计方法，而面向对象是一种基于结构分析的，以数据为中心的程序设计思想。在面向对象语言中有一个很重要的东西，叫做类。

多态 :

  • 对于一个变量，我们只需要知道它是Animal类型，无需确切地知道它的子类型，就可以放心地调用run()方法，而具体调用的run()方法是作用在Animal、Dog、Cat还是Tortoise对象上，由运行时该对象的确切类型决定，
  • 这就是多态真正的威力：调用方只管调用，不管细节，而当我们新增一种Animal的子类时，只要确保run()方法编写正确，不用管原来的代码是如何调用的。这就是著名的“开闭”原则：

对扩展开放：允许新增Animal子类；

对修改封闭：不需要修改依赖Animal类型的run_twice()等函数。

面向对象中怎么实现只读属性

  • 添加单个或两个下划线,将对象私有化
  • 使用特性,或者使用描述符

函数调用参数的传递方式是值传递还是引用传递

  • 不可变参数用值传递：像整数和字符串这样的不可变对象，是通过拷贝进行传递的，因为你无论如何都不可能在原处改变不可变对象。
  • 可变参数是引用传递：比如像列表，字典这样的对象是通过引用传递。

多线程交互访问数据，如果访问到了就不访问了？

怎么避免重读？

创建一个已访问数据列表，用于存储已经访问过的数据，并加上互斥锁，在多线程访问数据的时候先查看数据是否在已访问的列表中，若已存在就直接跳过。

解决哈希冲突

  • 开放寻址
  • 拉链法

尾递归

尾递归，比线性递归多一个参数，这个参数是上一次调用函数得到的结果；
所以，关键点在于，尾递归每次调用都在收集结果，避免了线性递归不收集结果只能依次展开消耗内存的坏处。

python闭包的延迟绑定

1
2
3
def multipliers():
    return [lambda x: i *x for i in range(4)]
print([m(2) for m in multipliers()])  # [6, 6, 6, 6]

内部函数被调用时，参数的值在闭包内进行查找。因此，当任何由multipliers()返回的函数被调用时,i的值将在附近的范围进行查找。那时，不管返回的函数是否被调用，for循环已经完成，i被赋予了最终的值3.

解决方式:
使用生成器,每次返回一个新的lambda表达式:

1
2
3
4
5
def multipliers():
    for i in range(4):
        yield lambda x: i *x

print([m(2) for m in multipliers()])   # [0, 2, 4, 6]

python asyncio的原理

  • 使用python的yield这个可以打断保存当前函数的上下文的机制，
  • 封装好了 selector 摆脱掉了复杂的回调关系

排序

选择排序

在遍历时寻找最大的值，并在完成遍历后，将其放置在正确的位置。

遍历，每次取最高项

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def selection_sort(arr):
    # 注意这里range需要倒置
    for idx1 in range(len(arr)-1,0,-1):
        max_idx = 0
        # 注意这里从1开始到idx1(含)
        for idx2 in range(1,idx1+1):
            if arr[max_idx] < arr[idx2]:
                max_idx = idx2
        arr[max_idx],arr[idx2] = arr[idx2],arr[max_idx]
    return arr


if __name__ == '__main__':
    testlist = [17, 23, 20, 14, 12, 25, 1, 20, 81, 14, 11, 12]
    print(selection_sort(testlist))

选择排序不稳定

快速排序

快速排序选择一个值来拆分列表，该值称为枢轴值。

注意：枢轴值属于最终排序列表（通常称为拆分点）的实际位置。

1
2
3
4
5
6
7
8
9
10
11
def quick_sort(array):
	if len(array) < 2:
		return array
	else:
		pivot = array[0]
		less    = [i for i in array[1:] if i <= pivot]
		greater = [i for i in array[1:] if i > pivot]

		return quick_sort(less) + [pivot] + quick_sort(greater)

print(quick_sort([10,5,2,3,8,6]))

注意这里的len(array)可能等于0,可能等于1

或者:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def quick_sort(alist):
    if len(alist) < 2:
        return alist
    else:
        pivot = alist[0]

        left = 0
        right = len(alist) - 1

        while left < right:
            while left < right and alist[right] > pivot:
                right -= 1
            alist[left] = alist[right]

            while left < right and alist[left] <= pivot:
                left += 1
            alist[right] = alist[left]

        return quick_sort(alist[:left]) + [pivot] + quick_sort(alist[left+1:])


alist = [10,5,2,3,8,6]
print(quick_sort(alist))

快速排序不稳定

冒泡排序

冒泡排序的基本思想是，对相邻的元素进行两两比较，顺序相反则进行交换，这样，每一趟会将最小或最大的元素“浮”到顶端，最终达到完全有序

1
2
3
4
5
6
7
8
9
def bubble_sort(alist):
	for idx1 in range(len(alist)-1,0,-1):
		for idx2 in range(idx1):
			if alist[idx1] < alist[idx2]:
				alist[idx1],alist[idx2] = alist[idx2],alist[idx1]
	return alist

alist = [9,6,3,2,5,8,7,4,1]
print(bubble_sort(alist))

注意这里的两个for.第一个for是倒置的range

短冒泡排序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def short_bubble_sort(alist):
	idx1 = len(alist) -1
	exchange = True
	while idx1 != 0 and exchange:
		exchange = False
		for idx2 in range(idx1):
			if alist[idx2] > alist[idx2+1]:
				exchange = True
				alist[idx2],alist[idx2+1] = alist[idx2+1],alist[idx2]
		idx1 -= 1
	return alist
	
alist = [9,6,3,2,5,8,7,4,1]
print(short_bubble_sort(alist))

或者:

1
2
3
4
5
6
7
8
9
10
11
def short_bubble_sort(alist):
    for idx1 in range(len(alist)-1,0,-1):
        count = 0
        for idx2 in range(idx1):
            if alist[idx1] < alist[idx2]:
                alist[idx1],alist[idx2] = alist[idx2],alist[idx1]
                count += 1
        if count == 0:
            break
            
    return alist

如果alist是已经排序完成的话，就不会进行下一次遍历，可以直接退出了。

冒泡排序稳定

插入排序

1
2
3
4
5
6
7
8
9
def insertion_sort(alist):
    for idx in range(1,len(alist)):
        while alist[idx-1] > alist[idx] and idx != 0:
            alist[idx-1],alist[idx] = alist[idx],alist[idx-1]
            idx -= 1
    return alist

alist = [54,26,93,17,77,31,44,55,31,20]
print(insertion_sort(alist))

插入排序稳定

希尔排序

(递减递增排序)(分组插入排序)

先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def shell_sort(alist):
    def core(alist,gap):
        for idx in range(gap,len(alist),gap):
            while idx - gap >= 0 and alist[idx-gap] > alist[idx]:
                alist[idx-gap],alist[idx] = alist[idx],alist[idx-gap]
                idx -= gap

    leng = len(alist)
    while leng != 1:
        leng //= 2
        core(alist,leng)
    return alist


alist = [9,6,3,2,5,8,7,4,444,1,0]
print(shell_sort(alist))

希尔排序不稳定

归并排序

归并排序是一种递归算法，将数据进行两两分组，每组之间进行排序，每小组排序完成后，再见这些有序的小组之间进行合并排序，知道最后合并完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def merge_sort(alist):
	if len(alist) > 1:
		mid = len(alist) // 2

		left = alist[:mid]
		right = alist[mid:]

		merge_sort(left)
		merge_sort(right)

		i,j,k = 0,0,0

		while i < len(left) and j < len(right):
			if left[i] < right[j]:
				alist[k] = left[i]
				i += 1
			else:
				alist[k] = right[j]
				j += 1
			k += 1

		while i < len(left):
			alist[k] = left[i]
			i += 1
			k += 1

		while j < len(right):
			alist[k] = right[j]
			j += 1
			k += 1

	return alist


alist = [9,6,3,2,5,8,7,4,444,1,0]
print(merge_sort(alist))

上面代码有三个while，第一个while处理了90%的工作，但是把alist的最后一个元素弄丢了。所以需要后面两个while来处理。（两个while只会触发一个）

较好理解版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def guibing(alist):
    lenght = len(alist) 
    if lenght > 1:
        left_list = guibing(alist[:lenght//2])
        right_list = guibing(alist[lenght//2:])

        idx, left_idx, right_idx = 0,0,0

        while left_idx < len(left_list) and right_idx < len(right_list):
            if left_list[left_idx] < right_list[right_idx]:
                alist[idx] = left_list[left_idx]
                left_idx += 1
            else:
                alist[idx] = right_list[right_idx]
                right_idx += 1
            idx += 1

        while left_idx < len(left_list):
            alist[idx] = left_list[left_idx]
            left_idx += 1
            idx += 1


        while right_idx < len(right_list):
            alist[idx] = right_list[right_idx]
            right_idx += 1
            idx += 1

        return alist
    else:
        return alist


alist = [9,6,3,2,5,8,7,4,1]
print(guibing(alist))

归并排序稳定

利用headqp模块实现堆排序

1
2
3
4
5
6
7
8
9
10
import heapq

def heap_sort(alist):
    h = []
    for val in alist:
        heapq.heappush(h,val)
    return [heapq.heappop(h) for _ in range(len(h))]

x = [1,2,3,45,6,7,8,9,9,9,9,9]
print(heap_sort(x))  # [1, 2, 3, 6, 7, 8, 9, 9, 9, 9, 9, 45]

冒泡排序的基本思想

对所有相邻记录的关键字值进行比效，如果是逆顺（a[j]>a[j+1]），则将其交换，最终达到有序化;

快速排序的基本思想

分治法

查找

顺序查找

顾名思义,就是按顺序的查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def squential_search(alist,item):
	idx = 0
	while idx < len(alist):
		if alist[idx] != item:
			idx += 1
		else:
			return idx
	return False


if __name__ == '__main__':
	alist = [1,2,3,4,5,6]
	item = 2
	print(squential_search(alist,item))

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def binary_search(alist,item):
    left = 0
    right = len(alist)

    while left < right:
        mid = left + (right - left) // 2

        if alist[mid] > item:
            right = mid
        elif alist[mid] < item:
            left = mid +1
        else:
            return mid

    return False


if __name__ == '__main__':
    alist = [1,2,3,4,5,6,7,8,9]
    item = 5
    print(binary_search(alist,item))

    alist = [1,2,3,4,5,6,7,8,9,10]
    item = 5
    print(binary_search(alist,item))
  1. 使用==high=mid,low=mid+1==,这样while low<high退出的时机一定是low=high.不要再使用high=mid-1,low=mid+1,这样很不好控制.
  2. ==使用左闭右开的区间==用于查找.这样的好处是，当while loop终止时(提前break出来的不算)，left、right、mid三个索引取值全相同
  3. 使用==mid = low + (high - low) // 2==,这样就保证了left、right一致.

递归版:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def binary_search(alist,item):
	if len(alist) == 0:
		return False

	mid = len(alist) // 2
	if alist[mid] == item:
		return mid
	elif alist[mid] > item:
		return binary_search(alist[:mid],item)
	else:
		return mid + 1 + binary_search(alist[mid + 1:],item)
    		

if __name__ == '__main__':
    alist = [1,2,3,4,5,6,7,8,9,10,11]
    item = 11
    print(binary_search(alist,item))

    alist = [1,2,3,4,5,6,7,8,9,10]
    item = 10
    print(binary_search(alist,item))

递归

  1. 使用递归的思路:

    1. 找出简单的基线条件
    2. 每次递归都必须缩小问题的规模，使其符合基线条件
    3. 假设递归可用

  2. 有1680*640的矩形，要将矩形均匀分成正方形，且正方形尽可能大，求分割方法。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    def func(a,b):
    	lenght = max(a,b)
    	width = min(a,b)

    	if lenght % width == 0:
    		return width
    	else:
    		lenght -= width
    		return func(lenght,width)

    a = 1680
    b = 640
    print(func(a,b))

  3. 碾平列表:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    def flat(alist):
    	x = []
    	for each in alist:
    		if not isinstance(each,list):
    			x.append(each)
    		else:
    			x.extend(flat(each))
    	return x

    a = [1,2,3,[4,5,[6,7,8,[9,10,[11]]]]]
    print(flat(a))

    注意,这使用list的做法可以总结出获取递归数据列表的方法

数据结构

  1. 散列表性能决定因素:

    1. 较低的填装因子
    2. 良好的散列函数

    所谓的填装因子，其实就是数据的密度

    在调整长度之后，所有的元素都要重新插入到新的散列表中

  2. 广度优先搜索回答两种问题：

    1. 从节点A出发，有前往节点B的路径吗？
    2. 从节点A出发，前往节点B的哪条路径最短？

图

模拟树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class BinaryTree:
    def __init__(self,rootval):
        self.root = rootval
        self.left == None
        self.right == None

    def insert_left(self,new_node):
        if not self.left:
            self.left = BinaryTree(new_node)
        else:
            tree = BinaryTree(new_node)
            tree.left = self.left
            self.left = tree


    def insert_right(self,new_node):
        if not self.right:
            self.right = BinaryTree(new_node)
        else:
            tree = BinaryTree(new_node)
            tree.right = self.right
            self.right = tree

    def get_right(self):
        return self.right

    def get_left(self):
        return self.left

    def set_root_val(self,rootval):
        self.root = rootval

    def get_root_val(self):
        return self.root

树的构建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
from string import digits
from operator import mul,add,isub,itruediv

from pythonds.basic.stack import Stack
from pythonds.trees.binaryTree import BinaryTree


def build_parse_tree(exp):
    exp_list = exp.split()
    stack = Stack()
    root_tree = BinaryTree('')

    stack.push(root_tree)
    current_tree = root_tree

    for char in exp_list:
        if char == '(':
            current_tree.insertLeft('')
            stack.push(current_tree)
            current_tree = current_tree.getLeftChild()
        elif char in ['+','-','/','*']:
            current_tree.setRootVal(char)
            current_tree.insertRight('')
            stack.push(current_tree)
            current_tree = current_tree.getRightChild()
        elif char in digits:
            current_tree.setRootVal(int(char))
            parent = stack.pop()
            current_tree = parent
        elif char == ')':
            current_tree = stack.pop()
        else:
            raise ValueError
    return root_tree


def parse2int(tree):
    def back(tree):
        if (not tree.getLeftChild()) and (not tree.getRightChild()):
            yield tree.getRootVal()
        else:
            yield from back(tree.getLeftChild())
            yield from back(tree.getRightChild())
            yield tree.getRootVal()

    mapping = {'+':add,'-':isub,'*':mul,'/':itruediv}
    stack = Stack()
    for char in back(tree):
        if str(char) in digits:
            stack.push(char)
        elif char in ['+','-','/','*']:
            num1 = stack.pop()
            num2 = stack.pop()
            stack.push(mapping[char](int(num2),int(num1)))
    return stack.pop()

root_tree = build_parse_tree('( 3 + ( 4 * 5 ) )')
print(root_tree)
# <pythonds.trees.binaryTree.BinaryTree object at 0x000002B90CE3AFD0>

print(parse2int(root_tree))
# 23

树的遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 前序遍历
def front(tree):
    if (not tree.getLeftChild()) and (not tree.getRightChild()):
        yield tree.getRootVal()
    else:
        yield tree.getRootVal()
        yield from front(tree.getLeftChild())
        yield from front(tree.getRightChild())


# 中序遍历
def middle(tree):
    if (not tree.getLeftChild()) and (not tree.getRightChild()):
        yield tree.getRootVal()
    else:
        yield from middle(tree.getLeftChild())
        yield tree.getRootVal()
        yield from middle(tree.getRightChild())


# 后续遍历
def back(tree):
    if (not tree.getLeftChild()) and (not tree.getRightChild()):
        yield tree.getRootVal()
    else:
        yield from back(tree.getLeftChild())
        yield from back(tree.getRightChild())
        yield tree.getRootVal()


for node in back(root_tree):
	print(node)

或者:

1
2
3
4
5
def front(tree):
	if tree:
		print(tree.getRootVal())
		front(tree.getLeftChild())
		front(tree.getRightChild())

完整二叉树

父节点的左子节点（在位置p处）(从1开始)是在列表中位置2p中找到的节点。
父节点的右子节点在列表中的位置2p+1.

所以 idx // 2 即为父节点的位置

最小二叉堆

利用性质 :

  • 父节点的左子节点（在位置p处）是在列表中位置2p中找到的节点。
  • 父节点的右子节点在列表中的位置2p+1。

在堆中，对于父p的每个节点x，p中的键小于或等于x中的键。

得出:

  • 二叉堆insert需要实现的逻辑 ：
    比较新添加的项与其父项，如果新添加的项小于其父项，则将项与其父项交换。
  • delMin弹出根节点 :
    1. 将列表中的最后一个项移动到根位置来恢复根项，保持我们的堆结构属性
    2. 我们通过将新的根节点沿着树向下推到其正确位置来恢复堆顺序属性。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class BinHeap:
    def __init__(self):
        # 使用列表来模拟二叉堆
        # 堆的运算从1开始.所以添加一个[0],方便以后使用整数除法
        self.heap_list = [0]
        self.current_size = 0

    def change_child2parent(self,idx):
        # idx表示当前待移动节点的索引
        while idx > 1
            # 如果子节点的值小于父节点的值
            if self.heap_list[idx] < self.heap_list[idx//2]:
                # 交换子节点和父节点的值
                self.heap_list[idx],self.heap_list[idx//2] = self.heap_list[idx//2],self.heap_list[idx]
            idx //= 2


    # 比较新添加的项和父项,如果新添加的项小于父项,则将该项和父项交换
    def insert(self,val):
        # 先在列表的最后添加
        self.heap_list.append(val)
        self.current_size += 1
        # 然后再移动位置
        self.change_child2parent(self.current_size)

    # 返回 min(节点的右孩子,左孩子)
    def get_min_idx(self,idx):
        # 堆是从左向右排序,左孩子一定有,右孩子不一定有
        # 外层的if用来保证内层的的self.heap_list[2*idx+1]不会出错
        if  self.current_size < 2 * idx + 1:
            min_idx = 2 * idx
        else:
            if self.heap_list[2*idx] > self.heap_list[2*idx+1]:
                min_idx = 2 * idx + 1
            else:
                min_idx = 2 * idx           


    def change_parent2child(self,idx):
        # idx代表了刚从最后一层提到第一层的元素
        # idx = min_idx不断获取子节点
        # while保证了self.heap_list[idx*2]不会出错
        while 2 * idx <= self.current_size:
            # 获取当前节点的最小的孩子
            min_idx = self.get_min_idx(idx)
            # 如果节点的值大于孩子的值
            if self.heap_list[idx] > self.heap_list[min_idx]:
                self.heap_list[idx],self.heap_list[min_idx] = self.heap_list[min_idx],self.heap_list[idx]
            idx = min_idx

    def pop(self):
        # 首先返回第一个元素
        return_val =  self.heap_list.pop(1)
        # 将最后一个元素移动到第一个位置
        self.heap_list[1] = self.heap_list.pop()
        self.current_size -= 1
        self.change_parent2child(1)
        return return_val

    def build_from_list(self,alist):
        self.current_size = len(alist)
        # 因为是使用列表来模拟二叉堆.直接插入即可
        self.heap_list = [0] + alist[:]
        # i为最后一个有孩子的节点
        i = len(alist) // 2
        while i > 0:
            self.change_parent2child(i)
            i -= 1

二叉树创建堆的复杂度：O(n)
二叉树堆排序的复杂度：O(logN)

二叉查找树

一种映射类型，能从键映射到值。二叉查找树也可以做到类似于map一样的映射功能。

二叉搜索树:左子树的键小于父节点的键，并且在右子树的键大于父节点的键。

_put根据以下算法搜索树：

  1. 从根节点开始，搜索二叉树，将新键与当前节点的键比较。若新键小于当前节点，则搜索左子树。若新键大于当前节点，则搜索右子树。
  2. 当没有左（或右）孩子时，我们在树中找到应该建立新节点的位置。
  3. 要向树中添加节点，请创建一个新的TreeNode对象，并将对象插入到上一步发现的节点。

get:
递归地搜索树，直到它到达不匹配的叶节点或找到匹配的键。

delete:
第一个任务使用_get方法搜索以找到需要删除的TreeNode。如果未找到键，del操作符将引发错误

  1. 待删除节点没有子节点 :
    直接删除即可
  2. 待删除节点只有一个子节点 :
    子取代父
  3. 待删除节点有两个子节点 :
    • 在树中搜索可用于替换被调度删除的节点的节点。这个节点称为后继节点（Successor）。是树中具有次最大键的节点。
      后继结点：在二叉树中中序遍历的序列中，某个节点紧随的那个节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
class TreeNode:
    def __init__(self,key,val,left=None,right=None,parent=None):
        self.key = key
        self.payload = val
        self.left_child = left
        self.right_child = right
        self.parent = parent

    def has_left_child(self):
        return self.left_child

    def has_right_child(self):
        return self.right_child

    def is_root(self):
        return not self.parent

    def is_leaf(self):
        return not (slef.left_child or self.right_child)

    def is_left_child(self):
        return self.parent and self.parent.left_child == self

    def is_right_child(self):
        return self.parent and self.parent.right_child == self

    def has_any_children(self):
        return self.right_child or self.left_child

    def has_both_children(self):
        return self.right_child and self.left_child

    def replace_node_data(self,key,val,left_child,right_child):
        self.key = key
        self.payload = val

        self.left_child = left_child
        self.right_child = right_child

        if self.has_left_child():
            self.left_child.parent = self
        if self.has_right_child():
            self.right_child.parent = self


class BinarySearchTree:
    def __init__(self):
        self.root = None
        self.size = 0

    def length(self):
        return self.size

    def __len__(self):
        return self.size

    def _put(self,key,val,current_node):
        if current_node.key > key:
            if current_node.has_left_child():
                self._put(key,val,current_node.left_child)
            else:
                current_node.left_child = TreeNode(key,val,parent=current_node)
        elif current_node.key == key:
            current_node.payload = val
        else:
            if current_node.has_right_child():
                self._put(key,val,current_node.right_child)
            else:
                current_node.right_child = TreeNode(key,val,parent=current_node)

    def put(self,key,val):
        if not self.root:
            self.root = TreeNode(key=key,val=val)
        else:
            self._put(key,val,self.root)
        self.size += 1

    def _get(self,key,current_node):
        if current_node.key > key:
            if current_node.has_left_child():
                return self._get(key,current_node.left_child)
            else:
                return False
        elif current_node.key < key:
            if current_node.has_right_child():
                return self._get(key,current_node.right_child)
            else:
                return False
        else:
            return current_node


    def get(self,key):
        if self.root:
            return self._get(key)
        else:
            return None

    # 使用中序遍历yeild出所有节点
    def minddle(self,current_node):
        if current_node:
            yield from self.minddle(current_node.left_child)
            yield current_node
            yield from self.minddle(current_node.right_child)

    # 找出后继
    def find_successor(self,current_node):
        gen = self.minddle(self.root)
        for node in gen:
            if node == current_node:
                return next(gen)

    def splice_out(self):
        if self.is_leaf():
            if self.is_left_child():
                self.parent.left_child = None
            else:
                self.parent.right_child = None

        elif self.has_any_children():
            if self.has_left_child():
                if self.is_left_child():
                    self.parent.left_child = self.left_child
                else:
                    self.parent.right_child = self.left_child
                    self.left_child.parent = self.parent
            else:
                if self.is_left_child():
                    self.parent.left_child = self.right_child
                else:
                    self.parent.right_child = self.right_child
                    self.right_child.parent = self.parent


    def delete(self,key):
        node = self.get(key)
        if not node:
            raise '404 not found'
        else:
            # 无子节点
            if node.is_leaf():
                if node.parent.left_child == node:
                    node.parent.left_child == None
                else:
                    node.parent.right_child == None
            # 拥有两个子节点
            elif node.has_both_children():
                seccessor = self.find_successor(node)
                self.splice_out(self)
            # 拥有一个子节点
            else:
                son = node.left_child or node.right_child
                son.parent = node.parent

                if node.parent.left_child == node:
                    node.parent.left_child = son
                elif node.parent.right_child == node:
                    node.parent.right_child = son
                # 根节点
                else:
                    node.replace_node_data(son.key,payload,self.left_child,self.right_child,son.parent)

        self.size -= 1


    def __setitem__(self,key,val):
        self.put(k,v)

    def __getitem__(self,key):
        return self.get(key)

    def __contains__(self,key):
        if self.get(key):
            return True
        else:
            return False

广度优先搜索

  • 广度优先搜索先从其他起始顶点开始添加它的所有子节点，然后再添加其子节点的子节点。
  • 广度优先搜索算法就像在建一棵树，一次建一层。
  1. 当图被构造时，所有顶点被初始化为白色。白色顶点是未发现的顶点。
  2. 当一个顶点最初被发现时它变成灰色的
    (下次别的点搜索到这个点时，发现是灰色就说明已经被发现了，就不会再进行搜索了)，
  3. 当BFS完全探索完一个顶点时，它被染成黑色。这意味着一旦顶点变黑色，就没有与它相邻的白色顶点。另一方面，如果一个顶点被标识为了灰色，这就意味着其附近可能还存在着未探索的顶点(白色顶点)等待被探索。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def search(name):
    search_queue = deque()
    search_queue += graph[name]
    searched = []

    while search_queue:
        person = search_queue.popleft()
        if person not in searched:
            if is_willing(person):
                print(person + 'is willing')
                return True
            else:
                search_queue += graph[person]
                searched.append(person)
    return False

search_queue对应灰色,searched对应黑色

BFS算法使用Vertex类的扩展版本。这个新的顶点类添加了三个新的实例变量：

  • distance（距离），
  • predecessor（前导）（父顶点）
  • color（颜色）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from pythonds.graphs import Graph,Vertex
from pythonds.basic import Queue

def bfs(start):
	q = Queue()
	start.setDistance(0)
	start.setPared(None)
	q.enqueue(start)

	while q.size() > 0:
		current_vert = q.dequeue()
		for nbr in current_vert.getConnections():
			if nbr.getColor() == 'white':
				nbr.setColor('gray')
				nbr.setDistance(current_vert.getDistance() +1 )
				nbr.setPared(current_vert)
				q.enqueue(nbr)

		current_vert.setColor('black')

什么是MD5加密，有什么特点？

对输入信息生成唯一的128位散列值（32个字符）

  1. md5加密不可逆，所以它的安全度比较高
  2. 不管多大的字符串，它都能生成32位字符串

什么是对称加密和非对称加密

  1. 加密和解密过程不同
    对称加密过程和解密过程使用的同一个密钥，加密过程相当于用原文+密钥可以传输出密文，同时解密过程用密文-密钥可以推导出原文。但非对称加密采用了两个密钥，一般使用公钥进行加密，使用私钥进行解密。

  2. 加密解密速度不同
    对称加密解密的速度比较快，适合数据比较长时的使用。非对称加密和解密花费的时间长、速度相对较慢，只适合对少量数据的使用。

  3. 传输的安全性不同对称加密的过程中无法确保密钥被安全传递，密文在传输过程中是可能被第三方截获的，如果密码本也被第三方截获，则传输的密码信息将被第三方破获，安全性相对较低。

    非对称加密算法中私钥是基于不同的算法生成不同的随机数，私钥通过一定的加密算法推导出公钥，但私钥到公钥的推导过程是单向的，也就是说公钥无法反推导出私钥。所以安全性较高。