1. 数组和字符串

文章目录数组简介集合、列表和数组数组的操作二维数组简介定义内存存储应用字符串定义字符串匹配算法KMP双指针数组是数据结构中的基本模块之一。因为字符串是由字符数组形成的所以二者是相似的。数组简介集合、列表和数组我们先来了解一下集合、列表和数组的概念之间的差别。集合1定义由一个或多个确定的元素所构成的整体称为集合。2特点集合里的元素类型不一定相同。列表列表的概念是在集合的特征上形成的1定义列表又称线性列表的定义为是一种数据项构成的有限序列即按照一定的线性顺序排列而成的数据项的集合。2特点具有顺序且长度是可变列表里的元素类型不一定相同数组数组是列表的实现方式之一1定义不同的编程语言定义有所不同。在js中定义为数组是一种用于存储多个值的数据结构这些值可以是任意类型如数字、字符串、对象等并且它们按照特定的顺序排列。js中数组的数据类型可以不同。2特点数组会用一些名为索引的数字来标识每项数据在数组中的位置且在大多数编程语言中索引是从 0 算起的。我们可以根据数组中的索引快速访问数组中的元素。列表中没有索引这是数组与列表最大的不同点。数组中的元素在内存中是连续存储的。而列表中的元素在内存中可能彼此相邻也可能不相邻比如列表的另一种实现方式链表 内存就是不相邻的。在C中数组中元素的类型是一致的所以每个元素占用相同大小的内存但是在js中数组中的元素数据类型可以不一致所以不一定占用相同大小的内存。数组的操作读取元素1读取方式通过下标来读取元素。根据数组的存储空间是连续的这个特性读取数组的流程是这样的有数组[C, O, D, E, R]如果访问索引为 2 处的元素 “D” 时计算机会进行以下计算找到该数组的索引 0 的内存地址 2008将内存地址加上索引值作为目标元素的地址即 2008 2 2010对应的元素为 “D”这时便找到了目标元素。2时间复杂度计算内存地址这个过程是很快时间复杂度是常数级别为O(1)。查找元素1查找方式由于我们只保存了索引为 0 处的内存地址因此在查找元素时只需从数组开头逐步向后查找就可以了。如果数组中的某个元素为目标元素则停止查找否则继续搜索直到到达数组的末尾。2时间复杂度最坏情况是将整个数组都查找一般因此查找元素的时间复杂度为O(N)N为数组的长度。插入元素1插入方式 如果在数组的末尾插入直接插入即可只需要一步。但是如果在其他位置插入需要将在他后面的数据统一向后移动一个存储空间。2时间复杂度当数组的长度为 n 时最坏情况下我们在第一个位置插入元素共需要的步骤数为 1 n 步其中1 为插入操作n 为移动其余元素的步骤数。即时间复杂度为O(N1)N 为数组的长度。如果需要频繁地对数组元素进行插入操作会造成时间的浪费。删除元素1删除方式删除元素与插入元素的操作类似当我们删除掉数组中的某个元素后数组中会留下空缺的位置而数组中的元素在内存中是连续的这就使得后面的元素需对该位置进行填补操作统一向前移动一个存储空间。2时间复杂度当数组的长度为 n 时最坏情况下我们删除第一个元素共需要的步骤数为 1 (n - 1) n 步其中1 为删除操作n - 1 为移动其余元素的步骤数。删除操作具有线性时间复杂度即时间复杂度为O(N)N 为数组的长度。二维数组简介定义二维数组是一种结构较为特殊的数组只是将数组中的每个元素变成了一维数组。所以二维数组的本质上仍然是一个一维数组内部的一维数组仍然从索引 0 开始我们可以将它看作一个矩阵并处理矩阵的相关问题。内存存储类似一维数组对于一个二维数组A [[1, 2, 3, 4],[2, 4, 5, 6],[1, 4, 6, 8]]计算机同样会在内存中申请一段连续的空间并记录第一行数组的索引位置即A[0][0]的内存地址通过A[0][0]的地址和于元素在二维数组中的位置可以计算出元素的内存地址位置。存储位置示例图应用实际题目中往往使用二维数组处理矩阵类相关问题包括矩阵旋转、对角线遍历以及对子矩阵的操作等。字符串定义字符串是一个由字符构成的数组。字符串与数组有很多相似之处比如使用名称[下标]来得到一个字符。但是和数组又有不同之处字符串的基本操作对象通常是字符串整体或者其子串字符串操作比其他数据类型更复杂例如比较、连接操作字符串匹配算法KMPKnuth–Morris–PrattKMP算法是一种改进的字符串匹配算法它的核心是利用匹配失败后的信息尽量减少模式串与主串的匹配次数以达到快速匹配的目的。它的时间复杂度是O(mn)。详解https://leetcode.cn/leetbook/read/array-and-string/cpoo6/next数组记录子串和父串不匹配的时候子串重新开始对比的位置。如果子串和父串对比的时候在子串的i位置、父串的j位置不匹配那么next[i]0, 那么子串从next[i]位置开始, 父串从j位置开始对比next[i]0, 那么子串从i1位置开始父串从j1位置开始对比next数组构造next[i]的取值为P[0...i - 1]的最长公共前缀后缀的长度(P为子串)令next[0] -1。最长公共前缀后缀 就是某个字符串中所有的前缀和所有的后缀中共有的最长字符串的场长度。例如对于字符串 abcba前缀它的前缀包括a, ab, abc, abcb不包括本身后缀它的后缀包括bcba, cba, ba, a不包括本身最长公共前缀后缀abcba 的前缀和后缀中只有 a 是公共部分字符串 a 的长度为 1next数组构造方法/** * 构造next数组查找最长公共前后缀的过程 * p: 子串 */functionbuildNext(p){// 构造子串 p 的 next 表letnp.length,i0;// i: p串指针记录的是后缀最后一个字母的指针位置letnextnewArray(n);// next 表lettnext[0]-1;// t: 模式串指针记录的是前缀最后一个字母的指针位置所以前缀的长度是t1while(in-1)// p[i] p[t]说明前后缀字符串匹配,给next赋值就是前缀的长度即1后的t// t0表示是初始位置,给next赋值就是0if(t0||p[i]p[t]){// 匹配i;t;next[i]t;}else{// 没有匹配到就重置子串的坐标到next[t](t是前缀的下标找前缀也相当于在p中找子串所以不匹配就重置下标到next[t])tnext[t];}returnnext;}KMP算法/** * * param {*} p 子串 * param {*} s 父串 * returns */functionmatch(p,s){// KMP 算法letnextbuildNext(p);// 构造 next 表letms.length,i0;letnp.length,j0;while(jnim)// 自左向右逐个比对字符if(j0||s[i]p[j]){// 若匹配或 P 已移除最左侧i;j;}else{jnext[j];}returni-j;}案例给你两个字符串 haystack 和 needle 请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标下标从 0 开始。如果 needle 不是 haystack 的一部分则返回 -1 。/** * * param {*} p 子串 * param {*} s 父串 * returns */functionmatch(s,p){// KMP 算法letnextbuildNext(p);// 构造 next 表letms.length,i0;letnp.length,j0;while(jnim)if(j0){// 没有匹配到任何字符串的情况i;j;}elseif(s[i]p[j]){// 有字符串匹配到直接比较下一个字符串if(jn-1){returni-n1}i;j;}else{// 表示之前有字符串匹配到到该字符不匹配了jnext[j];}return-1}/** * 构造next数组查找最长公共前后缀的过程 * p: 子串 */functionbuildNext(p){// 构造子串 p 的 next 表letnp.length,i0;// i: p串指针记录的是后缀最后一个字母的指针位置letnextnewArray(n);// next 表lettnext[0]-1;// t: 模式串指针记录的是前缀最后一个字母的指针位置所以前缀的长度是t1while(in-1)// p[i] p[t]说明前后缀字符串匹配,给next赋值就是前缀的长度即1后的t; 匹配继续i1j1匹配下一个// t0表示是没有匹配到字符,给next赋值就是初始位置0即1后的t没有匹配到字符直接i1,j1if(t0||p[i]p[t]){// 匹配i;t;next[i]t;}else{// 没有匹配到就重置子串的坐标到next[t](t是前缀的下标找前缀也相当于在p中找子串所以不匹配就重置下标到next[t])tnext[t];}returnnext;}console.log(match(aaaasad,sad))双指针有时我们会使用两个指针进行数组的迭代使用双指针的典型场景之一是你想要从两端向中间迭代数组。实例反转数组反转数组中的元素。比如数组为[l, e, e, t, c, o, d, e]反转之后变为[e, d, o, c, t, e, e, l]。使用双指针技巧其思想是分别将两个指针分别指向数组的开头及末尾然后将其指向的元素进行交换再将指针向中间移动一步继续交换直到这两个指针相遇。有时我们可以使用两个不同步的指针来解决问题即快慢指针。与情景一不同的是两个指针的运动方向是相同的而非相反。