Day9|数组、链表、哈希表、字符串

一、数组

1.基础：

对于数组，我们要知道数组的下标都是从0开始的，并且数组的内存地址都是连续的，所以我们在删除或者添加某个元素时，就会牵连到其它元素，要记住的是数组的元素是无法删除的，只能覆盖。

而且大家如果使用C 的话，要注意vector 和 array的区别，vector的底层实现是array，严格来讲vector是容器，不是数组。

c 里，二维数组地址空间上是连续的。

2.习题：

1）704.二分查找                      题目链接：704. 二分查找 - 力扣（LeetCode）

2）27.移除元素                        题目链接：27. 移除元素 - 力扣（LeetCode）

3）977.有序数组的平方           题目链接：977. 有序数组的平方 - 力扣（LeetCode）

4）209.长度最小的子窗口       题目链接：209. 长度最小的子数组 - 力扣（LeetCode）

5）59.螺旋矩阵||                     题目链接：59. 螺旋矩阵 II - 力扣（LeetCode）

3.总结：

对于二分法来说，最主要就是把边界条件整明白，把区间定义弄清楚，要根据区间的定义来做边界处理，坚持循环不变量的原则。

其实刚接触数组的时候，让我最眼前一新的就是在写第二道题（移除元素）时，双指针解法的出现，现在我还记得当时那简单粗暴的想法，用两层for循环来解题，想想还挺有意思的😂。双指针法它的使用范围不止停留在数组，在很多解题的时候都会用到它，是非常常见的。双指针法可以通过一个快指针和一个慢指针在一个for循环下完成两个for循环的工作，但是前提是你要弄清楚每个指针的含义，只有明确含义，思路才能更加清楚，理解起来才会容易。而且双指针法也有很多花样的哦，要多多刷题才能体会得到。

滑动窗口也是数组中一个重要的方法，没做过这种题型的人，可能很难会想到这种方法。所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。

二、链表

1.基础：

链表是一种通过指针串联在一起的线性结构，每个节点都由数据域和指针域组成，最后一个节点的指针域指向null（空指针），链表的入口节点称为head（头结点）。链表包括单链表、双链表（有两个指针域，可以前后查询）、循环链表keyijiejueyussefuhuandewenti（链表首尾相连，可以解决约瑟夫环的问题）。

链表和数组在内存中储存方式的区别：数组在内存中是连续分布的。    链表在内存中不是连续分布的，链表是通过指针域的指针链接在内存中各个节点，是散乱的。

链表和数组在应用场景上的区别：数组在定义的时候长度是固定的，所以它适合频繁查询、增删较少的情况。   链表的长度不是固定的，所以它适合频繁增删，查询较少的情况。

2.习题：

1）203.移除链表元素                    题目链接：203. 移除链表元素 - 力扣（LeetCode）

2）707.设计链表                           题目链接：707. 设计链表 - 力扣（LeetCode）

3）206.反转链表                           题目链接：206. 反转链表 - 力扣（LeetCode）

4）24.两两交换链表中的节点       题目链接：24. 两两交换链表中的节点 - 力扣（LeetCode）

5）19.删除链表的倒数第N个节点 题目链接：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

6）142.环形链表||                         题目链接：142. 环形链表 II - 力扣（LeetCode）

3.总结：

对于链表的增删，可以用原来的链表直接进行操作，但是使用这种方法需要单独写一段代码来处理头节点，所以有一种更好的方法就是--虚拟头节点法，这样的话原链表就可以按照统一的方式进行增删改写的操作了。707.设计链表就是练习链表操作非常好的一道题目，大家可以尝试一下。而206.反转链表就用到了双指针，不用定义新链表就能做，仅仅改变指针方向便可以了，大家可以试一下哦，19题也是个双指针经典应用的题。

链表中像是要交换结点的题，并不单纯的只是交换值，要实际的交换节点。

写链表的题一般来说最好要画图，不然的话特别容易混乱！！！就像142.环形链表||这道题，它不仅考察了链表，同时里面也需要数学运算，不画图的话不是很容易想明白其中关系，尤其是在判断完链表有环之后，去找环入口的时候，也是用双指针，挺有意思的一道题。

考察链表的操作其实就是考察指针的操作，是面试中的常见类型。

三、哈希表（当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。）

1.基础：（需要了解哈希表的内部实现原理，哈希函数，哈希碰撞，以及常见哈希表的区别，数组，set 和map。）

哈希表是根据关键码的值而直接进行访问的数据结构，直白来说，其实数组就是一张哈希表，而关键码就是索引下标，一般哈希表都是用来快速判断一个元素是否出现集合里。

常见的三种哈希结构：数组、set（集合）、map（映射）

 

2.习题：

1）242.有效的字母异位词    题目链接：242. 有效的字母异位词 - 力扣（LeetCode）

2）349.两个数组的交集       题目链接：349. 两个数组的交集 - 力扣（LeetCode）

3）1.两数之和                      题目链接：1. 两数之和 - 力扣（LeetCode）

4）454.四数相加||                题目链接：454. 四数相加 II - 力扣（LeetCode）

5）15.三数之和                    题目链接：15. 三数之和 - 力扣（LeetCode）

6）18.四数之和                    题目链接：18. 四数之和 - 力扣（LeetCode）

3.总结：

三种哈希结构每种数据结构的底层实现和用途都有所不同，必须要十分熟悉才可以灵活运用。要明白哈希函数和哈希碰撞在哈希表上的作用，处理碰撞的普遍方式是拉链法和线性探测法。

如果哈希值比较少、特别分散、跨度非常大，就不要使用数组了，因为使用数组就会造成空间的极大浪费！哈希法是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。

直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。使用map的时候，我们需要明确map是用来存什么的，map中key和value分别表示什么，这点很重要。

去重和剪枝的操作要想明白，有点绕。

四、字符串

1.基础：

字符串也是一种数组，所以元素在内存中是连续分布。

2.习题：

1）344.反转字符串                  题目链接：344. 反转字符串 - 力扣（LeetCode）

2）541.反转字符串||                题目链接：541. 反转字符串 II - 力扣（LeetCode）

3）151.反转字符串里的单词   题目链接：151. 反转字符串中的单词 - 力扣（LeetCode）

4）28. 实现 strStr() （本题可以跳过）

5）459.重复的子字符串  （本题可以跳过）

kmp算法很难，一刷可以放过，或者适当了解一下，二刷的时候再硬啃

3.总结：

如果题目关键的部分直接用库函数就可以解决，建议不要使用库函数。如果库函数仅仅是 解题过程中的一小部分，并且你已经很清楚这个库函数的内部实现原理的话，可以考虑使用库函数。

当需要固定规律一段一段去处理字符串的时候，要想想在在for循环的表达式上做做文章。

这篇好文章是转载于：学新通技术网