Leetcode_数据结构_数组与字符串 刷完了Leetcode_学习_数组与字符串，在这里记录一下重点，增强自己对知识点和题目的掌握。计划首先记录知识点，其次再补充一些题目。数组与字符串的主要内容如下：数组（一维数组）的基本概念、操作方式；二维数组的基本概念、操作方式；字符串的基本概念、数组与字符串之间的差异；双指针解题技巧；字符串匹配中的KMP算法。 1. 数组（一维数组）的基本概念、操作方式 1.1 数组的基本概念 
集合、列表、数组 集合==>列表（线性列表）==>数组，集合是最基础的，列表建立在集合的基础上，数组是列表的实现方式。 集合概念，由一个或者多个确定的素构成的整体； 集合特点（两点），集合中的素类型不一定相同；集合中的素没有顺序。 列表概念，是一种数据项构成的有限序列，按照一定的线性顺序，排列而成的数据项的集合； 列表特点（两点），具有一定的顺序；长度可变（存在添加、删除素的操作）； 列表实现方式，常用形式包括数组和链表，特殊形式包括栈和队列。 数组概念，是常用的列表的一种实现方式； 数组和列表的区别（两点），数组通过索引操作快速访问特定位置上的素；数组中素在内存中连续存储，列表中素在内存中不一定是连续存储的。 1.2 数组的操作方式 数组基本操作，读取素、查找素、插入素、删除素。 读取素，通过索引进行读取，数组将素存储于连续内存中，知道内存地址后就得到素，时间复杂度O(1)； 查找素，通过遍历在数组中查找特定素的地址，最坏情况查到数组末尾，时间复杂度O(N)； 插入素，在特定位置插入素，首先将其后素后移，其次将特定位置置为插入素；末尾插入很方便，中段插入和频繁插入很繁琐，链表更适合这种情况； 删除素，与插入素相似，首先删除特定位置的素，其次将其后素前移，时间复杂度O(N)； 2. 二维数组的基本概念 二维数组概念，一种特殊数组，数组中的每个素变成一维数组，常用于数组图像中，题目也与矩阵相关； 3. 字符串的基本概念、操作方式 3.1 字符串的基本概念 字符串概念，字符串是由若干个字符组成的有限序列，String = a1a2a3…an； 字符串和数组的概念和操作相似，可以通过索引处理字符串中的字符； 字符串的基本操作对象是字符串整体或者字符串子串；字符串操作比其他数据类型更加复杂； 3.2 字符串的操作方式 字符串基本操作，字符串比较操作、字符串连接操作； 比较操作，比较两个字符串是否相同，支持运算符重载的语言(Cpp/Python)可使用”==”进行判断，不支持运算符重载(Java)不支持使用”==”进行判断，”==”会比较两个字符串是否为同一个对象； 连接操作，连接若干个字符串，通过”+”完成字符串连接操作。但是对于不同语言，连接操作的时间复杂度不同，对于字符串可变的语言(Cpp)，连接操作没有性能影响；对于字符串不可变的语言(Python/Java)，字符串连接实际上新建了一个字符串对象。 4. 双指针解题技巧 4.1 首尾指针 双指针分别置于头部和尾部，以相同速度向中间迭代，直到双指针相遇时结束迭代；常用于数组排序； 4.2 快慢指针 快慢指针始于数组头部，按不同速度向后迭代，快指针在每轮迭代后都向后移动，慢指针在满足条件后向后迭代；快慢指针考虑内容，快指针迭代条件、慢指针迭代条件、快慢指针迭代之间的关系； 经典场景，删除某个数组中的所有特定数值的素，返回新数组的长度；
删除数组nums中数值为2的所有素 解决方法，首先在数组nums处放置快慢指针（实际上，快指针放置在nums头部，慢指针放置在result头部，用result直接在nums上进行操作，因此是原地处理），从头至尾迭代快指针，每次迭代中，快指针判断指向素是否为特定数值：如果不是特定数值，nums[慢指针]=nums[快指针]，慢指针向后迭代一位；如果是特定数值，慢指针不操作，保持原位；最后快指针迭代到末尾结束，返回慢指针即为新数组长度。 5. KMP字符串匹配算法 算法核心，利用匹配失败后的信息，减少子串与主串的匹配次数达成快速匹配，时间复杂度O(m+n)；
字符串匹配实例 应用实例，S为主串(长度n)，P为模式串(长度m)，判断主串S是否包含模式串P；常用方法是遍历，暴力遍历的时间复杂度是 O(mn) ((n-m+1)×m)；KMP利用匹配失败的信息将时间复杂度降低到 O(m+n)；
KMP字符串匹配算法说明 算法原理，经过第一轮迭代，匹配失败；迭代过程中发现，模式串P与主串S中的”T”和”Y”不匹配，所以S中的蓝色”AC”与P右侧的”AC”不匹配，但是可能与P左端的”AC”匹配；因此平移模式串P使得P左端的”AC”与S中蓝色”AC”匹配，进行下一次迭代。 算法流程，规定主串S的迭代下标是i，模式串P的迭代下标是j，假设主串和模式串分别迭代到i和j；如果 j == -1，则 i++, j++，开始匹配下一个字符；如果 S[i] == T[j]，则 i++, j++，继续匹配下一个字符；如果 j != -1 且 S[i] != T[j]，则i不变，j=next[j]，即字符串失配时，模式串T相对于主串S向右移动(j-next[j])； 字符串匹配失败时，需要更新模式串和主串的索引头，主串的索引头保持为(i)，模式串相对于主串向右移动(j-next[j])位；next是最长公共前后缀，前缀是除了最后一个字符外的所有字串，后缀是除了第一个字符外的所有字串，下图能说明字符串的前后缀；
模式串的前缀、后缀、公共前后缀最大长度 结合以上字符串前后缀表，可以得到字符串中字符与公共前后缀最长长度之间的关系，得到以下表格，
模式串字符与公共前后缀最大长度之间的关系 以上表格是当前字符作为最后一个字符时，当前字符串的公共前后缀的最长长度；由此可以引出next数组，由于模式串在特定位置出现不匹配，因此需要特定位置的上一个位置对应的公共前后缀的最长长度，得到next数组，
导出next数组 求解过程，按照KMP算法对上述主串和模式串进行字符串匹配；
主串与模式串的匹配求解过程 程序实现(Python3)，主要由两步组成，首先根据模式串得到next数组，其次匹配模式串和主串； next数组求解，包含两种方法，暴力方法求解最长公共前后缀；递推方法求解； 1. 暴力求解，直接对模式串的每个子串，求解最长公共前后缀； 2. 递推求解，对于next数组，假设next[0], …, next[x-1]，通过递推关系求解出next[x]，将next[x-1]设置为next[x-1]=temp，表示(x-1)位置的公共前后缀最大长度是temp，那么就在此基础上判断next[x-1]的数值，存在以下两种情况；
递推方法，第一种情形
递推方法，第二种情形 已知模式串A的next[x-1]=2，对应的前后缀是”AB”，设置next[x-1]=temp，表示(x-1)位置的公共前后缀的最大长度是temp；因此模式串A的next[x]，需要考虑新前缀中的A[temp]和新后缀中的A[x]； 第一种情况，A[temp]=A[x]，因此next[x]=next[x-1]+1； 第二种情况，A[temp]!=A[x]，需要缩小temp，将temp变为next[temp-1]，直到A[temp]=A[x]为止； 匹配模式串和主串，求解得到next数组后，在主串中查找模式串；
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/26363.html
