Summary

[TOC]

学习思路

  • 对于一个算法和数据结构,只有把每一个详细的步骤都想清楚了,才能实现该算法,如果算法或者数据结构都不理解,那么谈何实现?举个例子,如果我们都不知道二叉堆的特性,不了解二叉堆的构建,插入,删除,那么谈何实现呢?

  • 有时候,我们会对一道题或者一类题的解法形成思维定势,例如,表达式求值的方法,就应该用栈,但是,你知道为什么用栈吗?栈的先进后出的特性,到底在表达式求值中起到了什么作用?

解题思路

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

  1. 审题

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

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

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

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

    3. 在草稿纸上演算寻找规律,寻找直觉这一过程非常重要

  2. 编码

    1. 返回值是什么?

    2. 输入输出是什么?

    3. 考虑边界

    4. ……

    5. 能不能用 Python 调包直接解决问题,不行的话,再考虑优化

ArrayList

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

  • 头插法逆置单链表

  • 快慢指针

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

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