考试时如何写代码

重要的是让老师理解思路，不需要能执行——不需要完全用机试的思落做

不能省略.调用库函数的地方

超出1/4的代码不能省略

可以偷懒的地方（完善中…）

* 最大最小值Max_int，Min_int
* 比大小函数max(a,b)，min(a,b)
* 输入输出函数Cin,Cout
* A[i++],A[++i]
* 交换函数swap(a,b)

复杂度问题

题目的描述

* 时间上尽可能高效——不用管空间
* 时间和空间两方面尽可能高效——先时间后空间
* 尽可能高效——先时间后空间
* 空间复杂度为O(1)且时间上尽可能高效的算法——只管时间，空间O(1)
* 什么都没说——只要能做出来就行

本质

* 空间复杂度：使用额外
* 多项式的最高项（不考虑常数部分）

时间复杂度

* 定义——指令执行次数的总量级
* 计算：
循环
递归次数

空间复杂度

* 定义——额外空间数量级
* 计算：
数组，链表
递归层次

符合加法原则

只考虑最坏复杂度

顺序表

先想出暴力算法

* 枚举所有情况——代码简洁
* 对无序数组快速排序——需要默写快排

思路优化

* 有没有条件没用到——摆烂人
* 有没有超额完成任务——卷王
* 有没有别的思路——顶针

潜在优化算法，根据条件选择优化

* 折半查找——条件:一个，数组，有序
* 数组指针后移
条件：多个，线性表，有序
原理：归并算法
* 以空间换时间——空间保存状态
* 贪心思想——每次选最有力
* 快排

分析复杂度

常见的时间复杂度：O(logn),O(n),O(nlogn),O(n^2),O(n^3)

书写

* 先考虑清楚整个做法再做题
* 第一问：主要介绍逻辑，告诉老师你用了什么，比如快排
* 第二问：
注释详实，用来介绍这部分变量，过程作用
对于快速排序和折半查找(注意是否查找成功)，可以直接默写，过程不需要变动，注意参数
* 直接写复杂度，不要过程，要检测是否符合代码

_ 单链表_

特点

是线性表——多指针后移，动态规划
* 无法随机访问——用不了快排/折半(利用链表操作)
* 只能向后查找，无法回头(利用链表操作)

需要注意题目要求

* 空间复杂度要求是O(1)
* 不可修改链表结构
* 注意是否有头节点

考察结构

记忆模板，根据题目要求修改

先想出暴力解法

* 枚举——容易思考
* 先用数组保存链表元素——！使用条件：题目要求不是链表，而是值

优化方向

* 利用链表的操作
1. 前后指针——前后指针的距离是一样的——查找倒数K个
2. 快慢指针——如果有环，快指针早晚追上慢指针
3. 头插法——逆置
* 类似数组指针后移
条件：多个，线性表，有序
原理：归并算法
* 以时间换空间

树

考察结构——记忆模板，根据题目要求修改

* 二叉树
    左右孩子表示法
    双亲表示法——并查集
* 树和森林
    孩子兄弟表示法

重点考察遍历

* 二叉树(如无特别强调，一定写递归)
    先序
    中序
    后序
    层序

* 树和森林(不是重点)
    先根
    后根
    层序

* 树转二叉树（理解即可）

二叉排序树

* 平衡二叉树
* 红黑树
(判断是否是一棵xx树)