string题目 | 彩潭有鲤的札记

type

status

date

slug

summary

无重复字符的最长子串

题目：给定一个字符串s ，请找出其中不含有重复字符的最长子串的长度

示例：

重复的子字符串

题目：给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成

示例：

如果一个长度为的字符串可以由它的一个长度为的子串重复多次构成，那么：

一定是的倍数

一定是的前缀

对于任意的，有

也就是说，中长度为的前缀就是，并且在这之后的每一个位置上的字符，都需要与它之前的第个字符相同

最长公共前缀

题目：查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。

示例：

反转字符串

题目：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组s的形式给出。

示例：

反转字符串中的单词

题目：

给一个字符串 s ，请反转字符串中单词的顺序。单词由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例：

反转字符串中的单词 III

题目：给定一个字符串 s ，需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例：

开辟一个新字符串。然后从头到尾遍历原字符串，直到找到空格为止，此时找到了一个单词，并能得到单词的起止位置。随后，根据单词的起止位置，可以将该单词逆序放到新字符串当中。如此循环多次，直到遍历完原字符串，就能得到翻转后的结果。

罗马数字转整数

题目：

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

例如，罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。

X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。

C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。

示例：

通常情况下，罗马数字中小的数字在大的数字的右边。若输入的字符串满足该情况，那么可以将每个字符视作一个单独的值，累加每个字符对应的数值即可。例如可视作

若存在小的数字在大的数字的左边的情况，根据规则需要减去小的数字。对于这种情况，我们也可以将每个字符视作一个单独的值，若一个数字右侧的数字比它大，则将该数字的符号取反。例如可视作

字符串相加

题目：给定两个字符串形式的非负整数num1和num2 ，计算它们的和并同样以字符串形式返回。不能使用任何內建的用于处理大整数的库（比如 BigInteger），也不能直接将输入的字符串转换为整数形式。

示例:

字符串相乘

题目：给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式

示例:

如果和之一是0，则直接将0作为结果返回即可。

如果和都不是0，则可以通过模拟「竖式乘法」的方法计算乘积。从右往左遍历乘数，将乘数的每一位与被乘数相乘得到对应的结果，再将每次得到的结果累加。这道题中，被乘数是，乘数是

注意：除了最低位以外，其余的每一位的运算结果都需要补0。

二进制求和

题目：给定两个二进制字符串，返回他们的和（用二进制表示）。输入为非空字符串且只包含数字 1 和 0

示例:

字符串中的单词数

题目：统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。可以假定字符串里不包括任何不可打印的字符。

示例:

重复叠加字符串匹配

题目：给定两个字符串a和b，寻找重复叠加字符串a的最小次数，使得字符串b成为叠加后的字符串a的子串，如果不存在则返回-1。字符串 "abc" 重复叠加 0 次是 ""，重复叠加 1 次是 "abc"，重复叠加 2 次是 "abcabc"。

示例:

a可能比b短，也可能比b长。但如果a能拼接成包含b的字符串，那么无限多个a拼接起来一定能包含b。但问题在于不可能无限拼接a。

但是，如果n个a拼接起来的字符串s可以包含b，那么b在s中出现的位置一定不会超过a的范围。所以只需要拼接到a的大小刚刚超过b的大小+1得到s，就可以保证b一定出现在s中。然后调用find函数，找到第一次的位置为found；显然 found+b.size() 就是整个字符串b匹配在s中结尾的位置。对他向上取整即可得到多少个a可以包含b。

最常见的单词

题目：给定一个段落 (paragraph) 和一个禁用单词列表 (banned)。返回出现次数最多，同时不在禁用列表中的单词。题目保证至少有一个词不在禁用列表中，而且答案唯一。禁用列表中的单词用小写字母表示，不含标点符号。段落中的单词不区分大小写。答案都是小写字母。

示例:

亲密字符串

题目：给两个字符串s和goal，只要可以通过交换s中的两个字母得到与goal相等的结果，就返回true ；否则返回false 。交换字母的定义是：取两个下标i和j（下标从0 开始）且满足i != j，接着交换s[i]和s[j]处的字符。

示例:

设两个字符串分别为和，如果满足交换和后两个字符串相等，那么需要满足以下几个条件：

字符串的长度与字符串的长度相等

存在且满足以及，实际在这四个自由变量中，只存在两种情况：

满足：则此时必然满足，字符串与相等，应当能够在s中找到两个不同的索引，且满足，如果能够找到两个索引不同但值相等的字符则满足与为亲密字符串；否则不为亲密字符串。
满足：满足的情况下，两个字符串与除了索引以外的字符都是匹配的

Z 字形变换

题目：将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

之后，输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

设numRows行字符串分别为，则容易发现：按顺序遍历字符串s时，每个字符c在Z字形中对应的行索引先从增大，再从减小至…… 如此反复：

算法流程：按顺序遍历字符串 s；

res[i] += c：把每个字符c填入对应行

i += flag：更新当前字符c对应的行索引

flag = - flag：在达到 Z字形转折点时，执行反向

字符串转换整数 (atoi)

题目：实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

读入字符串并丢弃无用的前导空格

检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。确定最终结果是负数还是正数。如果两者都不存在，则假定结果为正。

读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。

将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。

如果整数数超过 32 位有符号整数范围 [] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于的整数应该被固定为，大于的整数应该被固定为。

返回整数作为最终结果。

示例:

电话号码的字母组合

题目：给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

仅含 1 的子串数

题目：给一个二进制字符串s（仅由'0'和'1'组成的字符串）。返回所有字符都为1的子字符串的数目。由于答案可能很大，请你将它对取模后返回

示例：

如果一个所有字符都为 1 的字符串的长度为 k，则该字符串包含的所有字符都为 1 的子字符串（包括该字符串本身）的数量是 k * (k + 1) / 2。

首先寻找到所有的只包含字符1的最长子字符串。这里的「只包含字符1的最长子字符串」的意思是，假设该子字符串的下标范围是[i, j]（包含下标 i 和下标 j），其中 i <= j，该子字符串中的所有字符都是 1，且下标i满足i位于字符串s的最左侧或者下标i - 1位置的字符是0，以及下标 j 满足 j 位于字符串 s 的最右侧或者下标 j + 1 位置的字符是 0。

寻找到所有的只包含字符 1 的最长子字符串之后，就可以计算所有字符都为 1 的子字符串的数量。

比较版本号

题目：

给你两个版本号 version1 和 version2 ，请你比较它们。

版本号由一个或多个修订号组成，各修订号由一个 '.' 连接。每个修订号由 多位数字 组成，可能包含 前导零 。每个版本号至少包含一个字符。修订号从左到右编号，下标从 0 开始，最左边的修订号下标为 0 ，下一个修订号下标为 1 ，以此类推。例如，2.5.33 和 0.1 都是有效的版本号。

比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较 忽略任何前导零后的整数值 。也就是说，修订号 1 和修订号 001 相等。如果版本号没有指定某个下标处的修订号，则该修订号视为 0 。例如，版本 1.0 小于版本 1.1 ，因为它们下标为 0 的修订号相同，而下标为 1 的修订号分别为 0 和 1 ，0 < 1 。