Summary

[TOC]

解题思路

拿到一个问题,我们的解题步骤可以归纳为:

  1. 审题

    1. 归纳出题目的特点,确定使用的数据结构

    2. 从该数据结构的特点出发,结合题目的特点,寻找算法思路

      例如将顺序表进行置的问题,审题后,关键词是 顺序表 和 逆。顺序表就要想到根据 index 在 $O(1)$ 时间内获取值和长度已知的特性;逆置就要想到栈的特性。

      还要考虑,是对时间复杂度要求高,还是空间复杂度要求高。

  2. 编码

    1. 返回值是什么?

    2. 输入输出是什么?

    3. 考虑边界

    4. ……

ArrayList

  • 位置互换,利用 index 进行逆置

  • 头插法逆置单链表

  • 快慢指针

  • 链表节点最有价值的是节点值,而不是整个节点,这是个可以变通的地方,在不依赖前驱节点删除链表节点的时候,就用到了这个思想

  • 链表真正可以有所作为的地方,在于链表的头部,链表头部的操作,复杂度最低