摸鱼学大师

分类

未归档(8) 题解(541)

/ 注册

TA的专栏 547篇文章 2人订阅

孤帆远影碧空尽

547篇文章 10911人学习

全部文章（共88篇）

题解 | #MagicString# 来自专栏

思路：题目的主要信息：循环同构串：遍历字符串，每到一个字符的时候，将其及后面的字符接到最前面，公式为要在S1的所有循环同构串中找到出现S2次数最多的一个，若相同次数则返回字典序最小两个字符串只由小写字母构成方法一：暴力法具体做法：遍历S1的每一个位置使用substr函数进行同构操作，每...

循环同构串字符串哈希二分前缀数组

2021-08-04

0 572

题解 | #单双难全# 来自专栏

思路：题目的主要信息：字符串t与字符串s的前缀（从头开始，取前t.length个），若是二者所有的奇数位字符串都相等则称之为单匹配，若是二者所有偶数位字符串都相等，则称之为双匹配奇数偶数下标从1开始，注意与字符串下标之间的关系需要求m个t字符串，各自在n个s字符串中有多少属于单匹配但不属于...

字典树单匹配双匹配字符串前缀匹配

2021-08-03

0 602

题解 | #字符串距离计算# 来自专栏

思路：题目的主要信息：两个长度相等的字符串距离定义为相同位置不同字符的数目现有两个字符串S1与S2，从S1中任选一个字符X1，将其全部替换成另一个字符串X2后再与S2比较距离，求这个距离可能的最小值两个字符串长度一定相等，全是小写字母，无特殊情况方法一：暴力法具体做法：既然全是小写字母...

字符串距离字符串矩阵数组

2021-07-31

0 523

题解 | #最长回文子序列# 来自专栏

思路：题目的主要信息：找到给定串中的最长回文子序列的长度子序列不同于字串，不要求字符全部相邻回文序列是指这个序列无论从左读还是从右读都是一样的方法一：递归（超时）性质：一个字符串的最长回文子序列等于该字符串与其逆序的最长公共子序列。具体做法：我们可以利用上述性质，构造字符串s的逆序字符...

动态规划子序列字符串递归回文序列

2021-07-28

0 610

题解 | #将字符串转化为整数# 来自专栏

思路：题目的主要信息：写一个atoi函数，将字符串转变成int型数字，输入没有任何限制，需要注意以下几点：前导0与前导空格要全部去掉第一个符号是正负号的情况输入了非数字要直接跳出输入达到了int型表示边界空串返回0 方法一：遍历法具体做法：用一个index全程记录字符串下标。按照上面...

字符串状态机

2021-07-28

0 498

题解 | #最小覆盖子串# 来自专栏

思路：题目的主要信息：在S字符串中找到包含T字符串所有字符的最小字串要求时间复杂度如果S中没有包含T中所有字符的子串，返回空字符串""，若有有则存在唯一最短方法一：滑动窗口+哈希表+双指针具体做法：维护一个哈希表，里面是字符串T的字符为key值，初始时当字符在T...

滑动窗口哈希表字符串字串双指针

2021-07-28

0 624

题解 | #括号生成# 来自专栏

思路：题目的主要信息：求n对括号的全部合法组合，左右括号之间任意组合，只要合法就行需要输出所有的结果方法一：暴力构造+栈验证具体做法：首先构造一个"(((((((......))))))"形式的字符串，然后调用STL的next_permutation函数遍历其每一个排...

括号栈递归回溯枝剪字符串

2021-07-27

0 527

题解 | #kmp算法# 来自专栏

思路：题目的主要信息：在文本串T中找到模板串S出现的次数 S不为空要求时间空间最多为方法一：暴力法（不会超时，但不符合要求）具体做法：遍历文本串，每次截取下标后m个与文本串比较，如果相同则答案加一。需要注意后面要留出m位防止访问越界。 class Solution { public: ...

KPM 字符串匹配

2021-07-27

1 477

题解 | #最长重复子串# 来自专栏

思路：题目的主要信息：重复字符串是由两个相同的字符串首尾拼接而成，不存在覆盖返回的是字串长度，为重复部分的2倍，必为偶数若不存在任何重复字符子串，则返回0 方法一：暴力解法（超时）具体做法：n记录最长的重复字串的重复长度，从字符串长度一半开始，然后依次比较后面的n个字符及再后面的n个字符...

二分法重复子串字符串

2021-07-25

1 1857

题解 | #判断回文# 来自专栏

思路：题目的主要信息：判断字符串是否是回文字符回文字符即首尾相互往中靠，字符都是相同的方法一：首尾依次比较法具体做法：两个指针，一个在字符串首，一个在字符串尾，在首的指针往后走，在尾的指针往前走，依次比较路过的两个字符是否相等，直到两指针在中间相遇。（我们这里用下标代替指针） clas...

回文字符字符串反转双指针

2021-07-25

0 417