剑指offer2 类型总结： 数组移动替换和排序搜索
数组移动替换型
常见题干
这类题目一般传递的目的都很明确，例如“替换空格”，“旋转数组”等，理解题意并不困难，不过需要认真读题争取把握所有信息（是否排序，要求复杂度等）
题目思路
- 首先要思考能否原地交换？如果可以，覆盖的情况需要考虑；如果不可以，借助列表or字符串进行拼接。
- 然后采取相应的算法（主要是考虑从后向前or从前向后，以及扫描情况判断）进行代码编写，比如字符串中的切片，数组中的交换，这里常常和排序搜索型有相通之处。
- 最后检查取余情况。
涉及题目
排序搜索型
常见题干
排序往往是为搜索做铺垫，有时候甚至可以不用排序就可以直接搜索（比如链表中倒数第K个结点）！这类题目的解决方法有很多种，一定要先沟通是空间or时间优先。其中较为典型的两个排序方法为：
- 二分法：碰到 “数组or串，有序，搜索，数字范围1~n（这个要格外注意，可以利用下标关系确定信息！）” 这些关键词常常有意想不到的效果！
- 快排：快排经常会以一种变体的形式存在，如双指针等，我们只需要抓到其精髓是 根据某种关系交换到自己应该在的位置
- 快慢指针：常常用于搜索一个快一个慢，二者维护一个固定距离的情况
题目思路
- 当你确定了使用二分法or快排，先要寻找的就是分割条件（二分法中称之为med，有可能是该下标或该下标对应的数字；快排中则称为哨兵，是左右指针相撞的地方，这二者本质上都是“要插入的位置”）
- 再寻找：题目要求和分割条件的关系以确定终止条件，具体而言就是 1. 和谁比较（可能是最后一个元素，也可能是某个位置的特定元素） 2. 比较结果影响什么（需要交换or缩小范围）
- 最后关注细节：相等的情况是否需要额外考虑，边界条件和等号是否需要（这两者常常综合判定，即相等的情况不退出循环，指针需要再变一次）
涉及题目
|