初级算法-链表

知识

链表是一种线性数据结构。

查找O(n)，删除O(1)，插入O(1)，随机读取O(n)。

技巧

节点关系：

对于链表来说，我们通常没有办法知晓链表的全貌，只能了解从已知的当前节点开始的表的内容。所以，在对链表问题做处理时，考虑节点之间的关系（主要是当前节点相关的函数关系）是解决链表问题的主要手段。

所以，在进行链表题时，预先将整个链表的处理流程书写完毕再写代码有事半功倍的效果。

表头设置（浅拷贝）：

由于链表通常需要使用对象的next方法来获取下一节点，所以为了在处理完整个链表后，可以对初始节点进行返回，对表头节点进行浅拷贝是非常有用的。

在这里需要注意，对next节点的继承需要在当前节点处理之前，不然会因为浅拷贝而改变next节点的状态。

此外需要注意，随着对head的迭代或者递归，直接指定表头节点的next为head是无效的手段。

迭代或递归：

双指针法：

重点看反转链表一题。

初级算法-字符串

知识

数组是一种线性数据结构，其常见复杂度如下：

查找O(n)，删除O(n)，插入O(n)，随机读取O(1)

若初始化一个定长数组，可以降低复杂度，但将会失去可变数组带来的简便添加元素和删除元素的方法。

大部分情况下，字符串可以视作数组（或是列表）来考虑。

技巧

转换列表

使用list()函数，将字符串转为列表，再用for循环将结果重新添加回字符串，这是没有更好解决办法时可以使用的技巧。

初级算法-数组

知识

数组是一种线性数据结构，其常见复杂度如下：

查找O(n)，删除O(n)，插入O(n)，随机读取O(1)

若初始化一个定长数组，可以降低复杂度，但将会失去可变数组带来的简便添加元素和删除元素的方法。

技巧

双指针法（多指针法）

其核心思想是，构建单个（多个）数组中需要交互操作，同时操作，同一操作的两个（多个）位置之间的函数关系，赋予指针变量。这样，即可通过遍历一次由单位向量构成的自变量，达成同时对相应的全部位置进行操作。

运算符

运算符还包括了逻辑运算符，在写代码时不应只留意函数关系的加减乘除。