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

上研究生这一两年一直在用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