[系统运维]数据结构篇

本篇博客主要记录力扣中考察数据结构的题目的刷题记录、思路和一些要点。

一、数组

1.理论：

①数组是一种基础的数据结构，在内存空间上为一段固定连续长度的地址，定义时需要指定大小。

②下标从0开始。

③注意区别vector，vector底层实现是数组，但vector是容器。

2.题目：

①二分查找：

????????本质上，二分查找就是在一定限制条件下，通过调整边界，快速缩小搜索范围。

? ? ? ? 在数组中，需要三个整型变量分别代表左右边界和中值，循环终止条件为左边界大于右边界。

注意：取中值时选择 ：中 = 左 + （右 - 左）/2；而不是：中 =（右 + 左）/2，因为后者可能内存溢出。

②移除元素：

? ? ? ? 由于数组是连续的内存，移除元素就需要把后面的所有元素挪动，最容易想到的方法是：遍历数组，每查找到一个元素就将该元素剔除并移动后续的元素，这样需要两层循环；想通过降低循环层数来降低复杂度，首先的思路应该是用一次循环里的多个变量来替代多个循环，所以该题用双指针比较好。