JZTXT

使用Python做笔试编程题的注意事项

发布时间 2023-08-14 12:54:16作者: izcat

上研究生这一两年一直在用Python，习惯了Python的库函数。由于Java语法严格又比较复杂，容易扰乱算法思路，并且太久没用以前擅长的C++，最近笔试一直首选Python。Python在笔试编程题中具有简洁易读、易于操作和大量的库支持的优点。然而，需要注意Python的执行效率，否则只要题目卡边界和时间就很难100%AC。根据笔试情况，总结了一些笔试注意事项。

优势

  • 基础类型丰富
    • int 天然支持大整数
    • string 类型支持 slice、反转等，语法灵活
    • dict 可作为哈希
  • 语法简洁，动态类型
    • 定义变量不用指定类型，更关注算法
    • map、zip、列表表达式等减少代码量
    • 支持多返回值
  • 特殊函数
    • eval 表达式求值
    • cache装饰器快速实现记忆化搜索 ，无序额外逻辑

劣势

  • 执行速度慢！！！

  • 不支持排序集合、排序map，其中 OrderedDict 是有序字典，类似于Java的LinkedHashMap

  • CPython解释器限制最大递归深度为1000

笔试遇到问题

  1. for循环超时

    去掉if判断：根据条件，改用max、min等函数

    合并多行语句：例如对于每次结果取模，直接在计算时取模，而不是额外判断或者先更新dp[i]再取模

  2. 使用PriorityQueue、heapq超时

    queue 库有线程同步操作，执行比较慢（参考我的博客第8条分析）。先考虑替换heapq（文远知行第三题通过92%），实在不行换语言吧。

    Java 优先队列，使用Lambda匿名函数，注意返回类型为 int

    PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2)->(o1[1]-o2[1]));

  3. RuntimeError: maximum recursion depth exceeded

    参考python递归次数过多，导致报错或者溢出

    import sys                    # 导入sys模块
sys.setrecursionlimit(10000)  # 将默认的递归深度修改为10000

  4. 搜索需要记忆化

    使用cache装饰器

    from functools import cache

// 加在需要记忆化的函数上，参数务必为可哈希类型
@cache
def dfs(u, flag=False, fa=-1):
    pass