代码

基础数据类型

整形值

无额外空交换

• 异或

  a = a^b
  b = a^b
  a = a^b

• 加减

  a = a+b
  b = a-b
  a = a-b

• 当然，对某些语言可以同时交换，如：python

取整

• 向下取整：mid = (left + right) // 2
• 向上取整：mid = (left + right + 1) // 2

运算溢出

• 正数：边界值1、0x7FFF FFFF、0xFFFF FFFF
• 负数：边界值0x8000 0000、0xFFFF FFFF
• 忽略语言特性：如long类型常量不加LL

初值选取

0值未考虑

浮点值

• 浮点取整：尽量避免混用使用向上取整、向下取整，容易混淆

• 浮点型相等比较：不应使用==，应该使用相差<某常数

  a, b = 1.11111, 1.11111111
  if abs(a - b) < 0.00001:
  	print("equal")

数据结构

线性表

• 常用初值

  • 数值型：0、-1、sys.maxsize、float('inf')
  • 字符串型：""
  • 迭代过程中可能取值：输出列表首个元素

• 判断条件

  • 是否为初值
  • 是否越界

• 对比迭代技巧

  • 从左至右、从右至左分别遍历
  • 原始列表、排序后列表分别遍历

• 边界条件限制

  • 判断语句中：先列出边界条件，利用短路求值简化代码

双指针

• 迭代操作注意事项

  • 保证退出循环
  • 所有值均被检验
  • 数据处理、移动指针的顺序

• 相向双指针：两指针均向中间靠拢不断缩小搜索空间

  • 明确切片范围：是否包括端点，并尽量保持不变
  • 据此明确搜索空间范围，则搜索空间为空时结束循环

• 滑动窗口：两指针同时向一侧移动，检验窗口内切片

  • 分类
    • 固定间隔双指针
    • 不同条件移动双指针
  • 示例

• 快慢指针：两指针同时迭代、但运动速度不同

  • 示例
    • 判断单链表是否成环

端点利用

• 两端限位器：在数据端点添加标记数据，便于

  • 指示“指针”已经到达数据端点
  • 简化特殊情况代码
    • 将循环中的判断条件合并
    • 端点标记数据符合一般情况，无需特殊处理
  • 示例
    • 数组末尾添加查找键（查询问题）：在顺序查找中可以 将判断数组越界、查找键比较合并

• 末端点为空闲位置：存储有效值

  • 队列、栈插入元素：末端点处为空闲位置，可直接使用
  • 数组迭代比较：末端点处存储有效值，先比较再更新指针

• 末端点为非空闲位置

  • 队列、栈：可以直接使用其末尾元素作为上次添加的元素， 简化代码

链表特性

• 头指针/节点：添加链表头，保证特殊情况链表正常工作

  • 示例
    • 删除只包含一个元素的链表

• 自设外部指针

  • 使用时注意有时会改变内部节点值

    // 修改链表内节点值
    outer.next.val = 4

HashXXX

• hash数据结构查询是常数时间，非常合适缓冲记录结果

  • HashSet：常数时间判断元素存在性
  • HashDict：键元素、值元素出现次数，记录次数

• 特殊、常用键

  • 有重复元素：有序tuple、字符串
  • 无重复元素：frozen set

逻辑

运算符

• 注意运算符优先级

• =结合不等号

  • 同时使用<=、>=，容易造成死循环、遗漏等
  • 尽量只使用>=号，不再使用<=号

递归终止条件

递归终止条件主要有两种设计方案

• 最后元素：判断元素是否是最后元素，终止递归调用

• 空（无效）元素：判断元素是空（无效）元素，终止递归调用

  • 需要确保最终能够进入该分支，而不是停止在最后一步

预处理方法

排序

• 预排序是简化问题的好方法

分治

• 缩小搜索空间：按特征排序后，根据该特征是否满足条件 即可缩小搜索空间

组合

• 组合后剔除重复：可重复组合排序后唯一，方便剔除重复元素
• 组合前保证唯一：对组合候选集“预排序”，保证取用元素位序 不减（可重复）、单增（不可重复）
  • 相当于提前对结果排序，保证得到组合结果唯一
  • “预排序”指候选集中顺序有意义，无需真正排序

特殊测试用例

字符串

• 空字符串
• 长度1字符串、长度2字符串
• 字符相同字符串

普通列表

• 空列表

  • 若在循环外即已取值，应该提前判断列表是否空

• 长度1列表、长度2列表

• 元素相同列表

树、二叉树

• 空树、只有根元素

  node.val = value;
  	# 未考虑空树

• 只有左子树、右子树

文件边界条件

• 首个字符
• 最末字符、倒数第二个字符

代码优化考量

• 保持程序设计风格：把经常使用的工具性代码编辑成已验证
• 用规范的格式处理、保存数据
• 区分代码与数据：与代码无关的数据应该尽可能区分开来，尽量 把数据保存在常量数组中

代码执行速度

• 输入输出方式过慢：cin等高级输入、输出方式比较慢

程序结构优化

• 栈溢出：数组等大局部变量保存到栈，少量递归即会发生栈溢出

输入、输出

将输入、输出流重定向到文件中，避免频繁测试时频繁输入

• 输入放在in.txt文件中
• 输出到out.txt中
• 输出执行时间

C/C++

#ifdef SUBMIT
freopen("in.txt", "r", stdin);
	// input data
freopen("out.txt", "w", stdout);
	// output
long _begin_time = clock();
#endif

// put code here

#ifdef SUBMIT
long _end_time = clock();
printf("time = %ld ms\n", _end_time - begin_time);
#endif

Python

import sys
import time
sys.stdin = open("in.txt", "r")
sys.stdout = open("out.txt", "w")
__tstart = time.time()

 # code here

__trange = time.time() - __tstart
print("time used: %f" % __trange)