Python语言栈面经高频率问题总结（内附答案）

1. python装饰器和应用场景？

python装饰器用于在不改变原函数内部代码的前提下，为函数扩展功能，其形式为@装饰器，入门用法为记录原函数的执行时间，或者打印原函数执行日志，其基础功能实现代码如下：

import time
def logger(func):
    def wrapper(*args, **kw):
        print('我准备开始计算：{} 函数了:'.format(func.__name__))

        # 真正执行的是这行。
        func(*args, **kw)

        print('啊哈，我计算完啦。给自己加个鸡腿！！')

    return wrapper

def timmer(func):
    def timeCalculate(*args,**kwargs):
        print("函数开始执行，开始计时")
        starttime = time.time()

        func(*args,**kwargs)

        endtime = time.time()
        print("函数运行完毕，时间为",(endtime-starttime)*1000)
    return timeCalculate

@timmer
@logger
def add(x, y):
  print('{} + {} = {}'.format(x, y, x+y))

if __name__ == '__main__':
    add(1,2)

通过上述代码，可看出装饰器可以多个叠加，其叠加后效果为包含式，timmer，logger，func函数，执行结果为：

函数开始执行，开始计时
我准备开始计算：add 函数了:
1 + 2 = 3
啊哈，我计算完啦。给自己加个鸡腿！！
函数运行完毕，时间为 0.0

 装饰器作为一个函数而言，上述用法是没有参数的用法，进阶的做法为给装饰器传参，根据执行函数的不同，作出相应的功能。如下面代码所示

def say_hello(contry):
  def wrapper(func):
    def deco(*args, **kwargs):
      if contry == "china":
        print("你好!")
      elif contry == "america":
        print('hello.')
      else:
        return
 
      # 真正执行函数的地方
      func(*args, **kwargs)
    return deco
  return wrapper

结论：

带有参数的装饰器即为在无参数的装饰器的基础上外加一层带参数的函数，为上述的sayhello（country），内部的两层函数与前面类似。可以通过此种方式，传递参数，完成功能拓展。

2. 元组和数组的区别？是否都可以作为字典的键？

这是一个带坑的问题，python的语言基础里面，没有数组arrays，这里的数组不是list列表，实际上是讨论list，turple，arrays三者之间的区别。

2.1列表list

• 方括号[ ]，成员之间以，分割
• 可变的数据类型，可以进行增删改查，
• 成员类型不限

2.2元组tuple

• 小括号（），成员之间以，分割，索引为tup[2]
• 不可变数据类型，不可更改，可合并两个元组，不可删除元组的成员，

2.3数组arrays

准确来说Python中是没有数组类型的，只有列表(list)和元组（tuple), 数组是numpy库中所定义的，所以在使用数组之前必须下载安装numpy库。

• array中的类型全部相同，不同元素之间以空格分隔
• 可以是多维，获取其维度使用np.shape()

字典的key键：

作为字典的key键要求必须是可哈希的对象，列表和字典这样的可变类型，由于他们不可哈希，所以不能作为键，而所有不可变的类型都是可哈希的；

值相等的数字表示相同的键，即整型数字1和浮点数1.0的哈希值是相同的，它们是相同的键。

为什么键必须是可哈希的？

        解释器调用哈希函数，根据字典中键的值来计算存储你的数据的位置。如果键是可变对象，它的值可改变。如果键发生变化，哈希函数会映射到不同的地址来存储数据。如果这样的情况发生，哈希函数就不可能可靠地存储或获取相关的数据。选择可哈希的键的原因就是因为它们的值不能改变。
        数字和字符串可以被用做字典的键，元组是不可变的但也可能不是一成不变的，因此用元组做有效的键必须要加限制：若元组中只包括像数字和字符串这样的不可变参数，才可以作为字典中有效的键。

 以下代码中的元组中包含列表，即为可以改动。

tuple = (1, 2, 3, [1, 4, 7])
print(tuple)
tuple[3][2] = 100
print(tuple)

其内存地址表示为：

 

 上图来源：https://blog.csdn.net/machi1/article/details/86601119https://blog.csdn.net/machi1/article/details/86601119

 结论：

列表list不能作为字典的键，其可变，而作为字典的键必须可哈希，即为通过键所指向的位置找到其映射的数据出的内存地址。

元组可以成为字典的键，但是必须加限制，元组中的元素必须是数字和字符串这样的不可变参数。

3. 数组遍历的循环遍历方法

1. for  in方法

colours = ["red","green","blue"]
for colour in colours:
    print colour
 
# red
# green
# blue

2. 序号：

colours = ["red","green","blue"]
for i in range(0, len(colours)):
    print i, colour[i]
 
# 0 red
# 1 green
# 2 blue

4. python内变量存储方式：

python中一切变量都是对象，存储的不是变量本身，而是其内存地址

4.1存储类型

引用语义：在python中，变量保存的是对象(值)的引用，我们称为引用语义。采用这种方式，变量所需的存储空间大小一致，因为变量只是保存了一个引用。也被称为对象语义和指针语义。

值语义：有些语言采用的不是这种方式，它们把变量的值直接保存在变量的存储区里，这种方式被我们称为值语义，例如C语言，采用这种存储方式，每一个变量在内存中所占的空间就要根据变量实际的大小而定，无法固定下来。

4.2 python与C++的区别

• 各自支持的内建数据类型不同，此处可以在各自语言的入门课程中轻松查到，不一一列举了。
• Python是动态类型的语言，而C, C++是静态类型。静态类型的变量需要在编译运行之前就显式声明其类型，而动态类型则不用。
• 变量与内存地址的关系不同：在C语言中，当编译器为变量分配一个空间时，当变量改变值时，改变的是这块空间中保存的值，在程序运行中，变量的地址就不能再发生改变了；
• Python不同，它的变量与C语言中的指针相似，当变量赋值时，编译器为数值开辟一块空间，而变量则指向这块空间，当变量改变值时，改变的并不是这块空间中保存的值，而是改变了变量指向的空间，使变量指向另一空间。

5. python的垃圾回收机制 

引用计数法：在Python中每一个对象的核心就是一个结构体PyObject，它的内部有一个引用计数器（ob_refcnt）。程序在运行的过程中会实时的更新ob_refcnt的值，来反映引用当前对象的名称数量。当某对象的引用计数值为0,那么它的内存就会被立即释放掉。

引用计数法有其明显的优点，如高效、实现逻辑简单、具备实时性，一旦一个对象的引用计数归零，内存就直接释放了。将垃圾回收随机分配到运行的阶段，处理回收内存的时间分摊到了平时，正常程序的运行比较平稳。但是，引用计数也存在着一些缺点，通常的缺点有：

• 逻辑简单，但实现有些麻烦。每个对象需要分配单独的空间来统计引用计数，这无形中加大的空间的负担，并且需要对引用计数进行维护，在维护的时候很容易会出错。
• 在一些场景下，速度慢。正常来说垃圾回收会比较平稳运行，但是当需要释放一个大的对象时，比如字典，需要对引用的所有对象循环嵌套调用，从而可能会花费比较长的时间。
• 循环引用。这将是引用计数的致命伤，引用计数对此是无解的，因此必须要使用其它的垃圾回收算法对其进行补充。

 6. python导入模块的方式

主要有以下两种：

1. import 模块名1 [as 别名1], 模块名2 [as 别名2]，…：使用这种语法格式的 import 语句，会导入指定模块中的所有成员（包括变量、函数、类等）。不仅如此，当需要使用模块中的成员时，需用该模块名（或别名）作为前缀，否则 Python 解释器会报错。
2. from 模块名 import 成员名1 [as 别名1]，成员名2 [as 别名2]，…： 使用这种语法格式的 import 语句，只会导入模块中指定的成员，而不是全部成员。同时，当程序中使用该成员时，无需附加任何前缀，直接使用成员名（或别名）即可。

7. 多态，重载，重写之间的区别 继承：子类继承父类的相关方法，可以重写父类的方法

重写：在子类继承中，子类可以重写父类的方法。

重载：方法重载是在一个类中，定义了多个方法名相同，但是其参数数量不同或者数量相同类型和次序不同的方法。

多态：方法重载是一个类的多态性的体现，方法重写是子类与父类的另一种多态性体现

8.python2与python3的特性与区别

1. python2支持unicode和str字符，python3支持的unicode的字符
2. python2采用相对路径import，更容易出错，python3采用绝对路径import
3. python2允许tab式缩进与space式缩进共存，而python3不允许
4. 部分函数废弃类
   1. xrange
   2. print
   3. long整型
   4. file函数->open
   5. <>->!=

9. 排序算法

冒泡排序：每两个数之间对比，将a

选择排序：找出最小的一个元素，和第一个元素交换，

插入排序：类似于打牌，每轮将一个元素置于已经有序的序列中的合适位置。遍历原数组与有序数组两个，因此为O（n2）

O（nlogn）

快速排序：取出一个作为基数，左右指针分别移动，将比基数大的放右边，比基数小的放在左边。

归并排序：递归拆分为两个有序数列，然后通过对比的方式将分支有序数列重新组合为整体的有序数列。

时间复杂度O(n2) 冒泡排序

代码模板（JAVA）

public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 如果左边的数大于右边的数，则交换，保证右边的数字最大
                arr[j + 1] = arr[j + 1] + arr[j];
                arr[j] = arr[j + 1] - arr[j];
                arr[j + 1] = arr[j + 1] - arr[j];
            }
        }
    }
}

选择排序

代码模板（JAVA）

public static void selectionSort(int[] arr) {
    int minIndex;
    for (int i = 0; i < arr.length - 1; i++) {
        minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[minIndex] > arr[j]) {
                // 记录最小值的下标
                minIndex = j;
            }
        }
        // 将最小元素交换至首位
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

插入排序

• 类似打牌

代码模板（JAVA）

public static void insertSort(int[] arr) {
    // 从第二个数开始，往前插入数字
    for (int i = 1; i < arr.length; i++) {
        int currentNumber = arr[i];
        int j = i - 1;
        // 寻找插入位置的过程中，不断地将比 currentNumber 大的数字向后挪
        while (j >= 0 && currentNumber < arr[j]) {
            arr[j J+ 1] = arr[j];
            j--;
        }
        // 两种情况会跳出循环：1. 遇到一个小于或等于 currentNumber 的数字，跳出循环，currentNumber 就坐到它后面。
        // 2. 已经走到数列头部，仍然没有遇到小于或等于 currentNumber 的数字，也会跳出循环，此时 j 等于 -1，currentNumber 就坐到数列头部。
        arr[j + 1] = currentNumber;
    }
}

时间复杂度O(nlogn) 快速排序

1. 从数组中取出一个数，称之为基数（pivot）

2. 左右双指针分别向中间缩进，将比基数大的数字放到它的右边，比基数小的数字放到它的左边，不符合的时候指针变量交替，同时切换运行指针，直到两指针指向同一位置。遍历完成后，数组被分成了左右两个区域

3. 将左右两个区域视为两个数组，重复前两个步骤，直到排序完成

代码模板（C++）

void QuickSort(int array[], int start, int last)
{
    int i = start;
    int j = last;
    int temp = array[i];
    if (i < j)
    {
        while (i < j)
        {
            while (i < j &&  array[j]>=temp ) j--;
            if (i < j)
            {
                array[i] = array[j];
                i++;
            }
            while (i < j && temp > array[i]) i++;
            if (i < j)
            {
                array[j] = array[i];
                j--;
            }
        }
        //把基准数放到i位置
        array[i] = temp;
        //递归方法
        QuickSort(array, start, i - 1);
        QuickSort(array, i + 1, last);
    }
}

堆排序

堆：符合以下两个条件之一的完全二叉树：

• 根节点的值 ≥ 子节点的值，这样的堆被称之为最大堆，或大顶堆；

• 根节点的值 ≤ 子节点的值，这样的堆被称之为最小堆，或小顶堆。

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

堆排序过程如下：

• 用数列构建出一个大顶堆，取出堆顶的数字；

• 调整剩余的数字，构建出新的大顶堆，再次取出堆顶的数字；

• 循环往复，完成整个排序。

构建大顶堆有两种方式：

• 方案一：从 0 开始，将每个数字依次插入堆中，一边插入，一边调整堆的结构，使其满足大顶堆的要求；

• 方案二(较常用)：将整个数列的初始状态视作一棵完全二叉树，自底向上调整树的结构，使其满足大顶堆的要求。

完全二叉树有如下性质：

• 对于完全二叉树中的第 i 个数，它的左子节点下标：left = 2i + 1

• 对于完全二叉树中的第 i 个数，它的右子节点下标：right = left + 1

• 对于有 n 个元素的完全二叉树（n >2），它的最后一个非叶子结点的下标：n/2 - 1

方案二堆排序思想：

调整数组结构使其所表示的完全二叉树为大顶堆，然后将最大值放在末尾（即交换数组头和数组末尾的元素），然后对剩余数组重复上述步骤，即可完成堆排序。

方案二动图演示如下

public static void heapSort(int[] arr) {
    // 构建初始大顶堆
    buildMaxHeap(arr);
    for (int i = arr.length - 1; i > 0; i--) {
        // 将最大值放到数组最后
        exchange(arr, 0, i);
        // 调整剩余数组，使其满足大顶堆
        maxHeapify(arr, 0, i);
    }
}

// 构建初始大顶堆
public static void buildMaxHeap(int[] arr) {
    // 从最后一个非叶子结点开始调整大顶堆，最后一个非叶子结点的下标就是 arr.length / 2-1
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
        maxHeapify(arr, i, arr.length);
    }
}

// 调整大顶堆，第三个参数表示剩余未排序的数字的数量，也就是剩余堆的大小
private static void maxHeapify(int[] arr, int i, int heapSize) {
    // 左子结点下标
    int l = 2 * i + 1;
    // 右子结点下标
    int r = l + 1;
    // 记录根结点、左子树结点、右子树结点三者中的最大值下标
    int largest = i;
    // 与左子树结点比较
    if (l < heapSize && arr[l] > arr[largest]) {
        largest = l;
    }
    // 与右子树结点比较
    if (r < heapSize && arr[r] > arr[largest]) {
        largest = r;
    }
    if (largest != i) {
        // 将最大值交换为根结点
        exchange(arr, i, largest);
        // 再次调整交换数字后的大顶堆
        maxHeapify(arr, largest, heapSize);
    }
}
// 交换元素
private static void exchange(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

归并排序

• 归并排序的思想就是递归地将两个有序序列进行合并

• 将数组按拆分成左右两部分，可以认为左右子序列均为有序序列，对两序列进行合并。

• 拆分时对子序列递归上述步骤，则子序列优先先完成归并排序成为有序。

代码模板（JAVA）

public static void mergeSort(int[] arr) {
    if (arr.length == 0) return;
    int[] result = mergeSort(arr, 0, arr.length - 1);
    // 将结果拷贝到 arr 数组中
    for (int i = 0; i < result.length; i++) {
        arr[i] = result[i];
    }
}

// 对 arr 的 [start, end] 区间归并排序
private static int[] mergeSort(int[] arr, int start, int end) {
    // 只剩下一个数字，停止拆分，返回单个数字组成的数组
    if (start == end) return new int[]{arr[start]};
    int middle = (start + end) / 2;
    // 拆分左边区域
    int[] left = mergeSort(arr, start, middle);
    // 拆分右边区域
    int[] right = mergeSort(arr, middle + 1, end);
    // 合并左右区域
    return merge(left, right);
}