企业官网建设流程全解析

在这一章节中，我通过学习后得出了以下关于数据结构的一些相关概念

1. 数据结构的概念
   数据结构是相互之间存在一种或多种特定关系的数据元素的集合。这些数据元素不是孤立存在的，而是有着某种关系，这种关系构成了某种结构。
   公式：数据结构 = 数据 + 结构，可以理解为带结构的数据元素的集合。
   课程视角：数据结构讨论数据元素之间的相邻关系。
   著名公式（Pascal 之父 尼古拉斯・沃斯）：程序 = 算法 + 数据结构

2. 数组的基本知识
   （1）数组概念数组是 (n(n>1))个相同类型数据元素(a_1、a_2、…、a_n)构成的有限序列，逻辑表示：(A=(a_1,a_2,…,a_n))。ps.其中，ai（1≤i≤n）表示数组A的第i个元素
   Python 中没有原生数组，使用列表 list模拟数组 / 线性表，列表元素可以不同类型；一维列表当作一维数组，嵌套列表当作二维数组。
   （2）随机访问
   在数组中,一旦a1的存储地址LOC(a1)确定,并假设每个数据元素占用k个存储单元,则
   任一数据元素ai的存储地址LOC(ai)就可由以下公式求出：
   LOC(ai)=LOC(a1)+(i-1)*k (0≤i≤n)
   上式说明,数组中任一数据元素的存储地址可直接计算得到,即数组中任一数据元素
   可直接存取,因此,数组是一种随机存储结构。
   数组可以直接计算地址存取元素，属于随机存储结构。
   （4）顺序查找（线性查找）
   思路：从表头依次遍历，逐个比对关键字；找到返回位置，遍历结束没找到代表查找失败。
   python运行def sq_search(R, n, k):
   i = 0
   while i < n and R[i] != k:
   i += 1
   if i >= n:
   return 0
   else:
   return i + 1

3. 二分查找法（LeetCode 704. 二分查找）前提条件有序顺序表（递增），只适用于已经排好序的数组。基本思路维护查找区间
   基本思路：设R[low…high]是当前的查找区间，首先
   确定该区间的中点位置mid=(low+high)/2；然后将待查
   的k值与R[mid].key比较：
   若R[mid].key=k，则查找成功并返回该元素的逻辑序号。
   若R[mid].key>k，则由表的有序性可知新的查找区间是
   左子表R[low…mid-1]。
   若R[mid].key<k，则新的查找区间是右子表
   R[mid+1…high]。
   

在新区间继续循环，直到找到或者区间耗尽。
左闭右闭区间([\text{left},\text{right}])标准代码（对应 LeetCode704）
区间含义：target 的候选下标包含 left 和 right 两个端点，循环条件while left <= right
python运行from typing import List
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] > target:
right = mid - 1
elif nums[mid] < target:
left = mid + 1
else:
return mid
return -1

左闭右开：
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) # 定义target在左闭右开的区间里，即：[left, right)
while left < right: # 因为left == right的时候，在[left, right)是无效的空间，所以
使用 <
middle = left + (right - left) / 2
if nums[middle] > target:
right = middle # target 在左区间，在[left, middle)中
elif nums[middle] < target:
left = middle + 1 # target 在右区间，在[middle + 1, right)中
else:
return middle # 数组中找到目标值，直接返回下标
return -1 # 未找到目标值

移除元素
4. 移除元素（LeetCode27）
PPT 数组删除逻辑对应本题：给数组 nums，移除所有值等于 val 的元素，原地修改数组，返回新数组有效长度。
PPT 基础删除逻辑回顾
删除数组某个下标 i 元素：后面元素全部向前移动覆盖 i 位置。
解法思路

双指针（快慢指针）最优解法
快指针：遍历整个数组，寻找不等于 val 的元素；
慢指针：记录新数组需要写入的位置；
快指针遇到不等于 val 的元素，赋值给慢指针位置，慢指针向后走；最后慢指针的值就是有效数组长度。
python
运行
from typing import List
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
slow = 0
for fast in range(len(nums)):
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
return slow

暴力解法：遍历数组，遇到等于 val 的元素，把后面全部元素向前移动一位覆盖；每删除一次数组长度减一。
def removeElement(self, nums: List[int], val: int) -> int:
i, l = 0, len(nums)
while i < l:
if nums[i] == val: # 找到等于目标值的节点
for j in range(i+1, l): # 移除该元素，并将后面元素向
前平移
nums[j - 1] = nums[j]
l -= 1
i -= 1
i += 1
return l