分享｜2021秋招算法总结6-字符串篇
鲂
27315
2020.12.29
2021.08.09
发布于 未知归属地
字符串数据结构与算法面经我要上推荐技术交流

置顶科普

年份是毕业年份，2021是指2021年毕业，不是2021年面试

鲂的2021秋招算法总结目录（已完结）

1. 分享｜2021秋招算法总结1-DFS篇
2. 分享｜2021秋招算法总结2-BFS篇
3. 分享｜2021秋招算法总结3-链表篇
4. 分享｜2021秋招算法总结4-二叉树篇
5. 分享｜2021秋招算法总结5-排序算法篇
6. 分享｜2021秋招算法总结6-字符串篇

  1. 分享｜2021秋招算法总结7-双指针篇
  2. 分享｜2021秋招算法总结8-哈希篇
  3. 分享｜2021秋招算法总结9-位运算
  4. 分享｜2021秋招算法总结10-数组篇
  5. 分享｜2021秋招算法总结11-动规篇
  6. 分享｜2021秋招算法总结12-栈篇

鲂的2021秋招经验总结（不定时更新）

1. 分享｜2021届毕业生秋招经验总结1-岗位类别介绍
2. 分享｜2021届毕业生秋招经验总结2-如何选择offer

鲂的面经整理目录（已完结）

1. 美团金融｜安卓客户端｜面经｜offer｜2021届秋招｜
2. 拼多多｜客户端开发｜面经｜offer｜2021届秋招｜
3. 网易云音乐｜安卓客户端｜面经｜offer｜2021届秋招｜
4. 阿里巴巴｜客户端开发｜面经｜2021届秋招｜
5. 花旗银行｜软件工程师｜面经｜offer｜2021届秋招｜
6. 字节跳动｜客户端开发｜面经｜2021届秋招｜
7. 叠纸游戏｜客户端开发｜面经｜2021届秋招｜
8. 腾讯｜客户端开发｜面经｜2021届秋招｜
9. 360｜安卓客户端｜面经｜offer｜2021届秋招｜
10. 作业帮｜IOS客户端｜面经｜2021届秋招｜
11. 滴滴｜安卓客户端｜面经｜2021届秋招｜
12. 百度｜IOS客户端｜面经｜2021届秋招｜
13. 快手｜客户端开发｜面经｜2021届秋招｜
14. 顺丰科技｜安卓客户端｜面经｜offer｜2021届秋招｜

鲂的内推

1. 内推+校招秋招｜美团金融服务平台｜多项岗位｜北京+上海

本篇概要

首先，要学会如何处理输入输出！
在这发表一下个人看法，刷算法平台的目的是为了让你更了解某个算法，所以在平台上刷算法会直接给定函数的输入输出。听说曾经也是白板编程（白板是一种黑话，就是啥都不给），弄的怨声载道以后变成了现在这种专注算法本身的模式，我觉得挺好的。但是，在面试中，面试官考察的方面可能存在差异，有些面试官跟平台一样注重算法本身的实现，有些面试官要求面试者一定要在白板环境下运行出来。后者需要面试者自己写主函数和功能函数（与大多数笔试类似）。
其次，学习一些处理字符串的常见方法（内库or快速写一个类似功能）。比如：java的String类、StringBuffer类和StringBuilder类中常见的函数
最后，在力扣中进行字符串算法本身的训练。

字符串排序

  1. 【笔试前必备基础】将按空格、逗号或者分号隔开的字符串按字典序的顺序或者按逆字典序的顺序进行排列后输出。注意已知行数和未知行数的区别。此处分享一个用java编程可能会遇到的问题：
    如果输入的数据有三行，第一行是整数，第二行和第三行都是字符串，java中的Scanner类在nextInt()后输入的nextLine()无效。我相信很多人听不懂，举个代码给大家解释下。
  • 会有bug的代码。
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
String s1 = sc.nextLine();
String s2 = sc.nextLine();
s1 = s1.replaceAll(" ", "");
s2 = s2.replaceAll(" ", "");

具体bug长什么样，我建议大家自己运行下，别老是靠别人讲解而忽略了自己应该把代码跑起来这个事实。包括为什么会有这个现象，感兴趣的自己去搜索，自己理解的才是自己的呀。

  • 解决方法1：朴实无华的加上一个换行
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
sc.nextLine(); //换行
String s1 = sc.nextLine();
String s2 = sc.nextLine();
s1 = s1.replaceAll(" ", "");
s2 = s2.replaceAll(" ", "");
  • 解决方法2：不用nextLine()
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
String s1 = "";
for (int i =0; i < N; i++){
    s1 += sc.next().charAt(0);
}
String s2 = "";
for (int i =0; i < N; i++){
    s2 += sc.next().charAt(0);
}
  • 解决方法3：不用nextInt()
Scanner sc = new Scanner(System.in);
int N = Integer.valueOf(sc.nextLine()); //不能用sc.nextInt()，否则后面的 nextLine()无效
String s1 = sc.nextLine();
String s2 = sc.nextLine();
sc.close();
s1 = s1.replaceAll(" ", "");
s2 = s2.replaceAll(" ", "");
  1. 567. 字符串的排列：给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
  2. 791. 自定义字符串排序：字符串S和 T 只包含小写字符。在S中，所有字符只会出现一次。S已经根据某种规则进行了排序。我们要根据S中的字符顺序对T进行排序。更具体地说，如果S中x在y之前出现，那么返回的字符串中x也应出现在y之前。返回任意一种符合条件的字符串T。
  3. 953. 验证外星语词典：某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。
  4. 451. 根据字符出现频率排序：给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
  5. 937. 重新排列日志文件：按一定规则返回日志的最终顺序。

字符串匹配

  1. 28. 实现 strStr()：给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回-1。
  2. 10. 正则表达式匹配和剑指 Offer 19. 正则表达式匹配：请实现一个函数用来匹配包含'. '和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但与"aa.a"和"ab*a"均不匹配。
  3. 290. 单词规律：给定一种规律 pattern 和一个字符串str，判断str 是否遵循相同的规律。还有个291. 单词规律2是会员的困难题，学有余力的会员可以试试看。
  4. 面试题 17.17. 多次搜索：给定一个较长字符串big和一个包含较短字符串的数组smalls，设计一个方法，根据smalls中的每一个较短字符串，对big进行搜索。输出smalls中的字符串在big里出现的所有位置positions，其中positions[i]为smalls[i]出现的所有位置。
  5. 面试题 16.18. 模式匹配：你有两个字符串，即pattern和value。 pattern字符串由字母"a"和"b"组成，用于描述字符串中的模式。例如，字符串"catcatgocatgo"匹配模式"aabab"（其中"cat"是"a"，"go"是"b"），该字符串也匹配像"a"、"ab"和"b"这样的模式。但需注意"a"和"b"不能同时表示相同的字符串。编写一个方法判断value字符串是否匹配pattern字符串。
  6. 686. 重复叠加字符串匹配：给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。

异位词

  1. 242. 有效的字母异位词和面试题 01.02. 判定是否互为字符重排：给定两个字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。
  2. 49. 字母异位词分组和面试题 10.02. 变位词组：对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串。
  3. 438. 找到字符串中所有字母异位词：给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串压缩和解码

  1. 面试题 01.06. 字符串压缩：字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。
  2. 443. 压缩字符串：给定一组字符，使用原地算法将其压缩。压缩后的长度必须始终小于或等于原数组长度。数组的每个元素应该是长度为1 的字符（不是 int 整数类型）。在完成原地修改输入数组后，返回数组的新长度。
  3. 394. 字符串解码：给定一个经过编码的字符串，返回它解码后的字符串。编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

字符串反转、翻转和旋转

  1. 344. 反转字符串：其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
  2. 541. 反转字符串 II：给定一个字符串 s 和一个整数 k，你需要对从字符串开头算起的每隔2k个字符的前k个字符进行反转。
  3. 剑指 Offer 58 - II. 左旋转字符串：字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
  4. 796. 旋转字符串和面试题 01.09. 字符串轮转：给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成。
  5. 151. 翻转字符串里的单词和剑指 Offer 58 - I. 翻转单词顺序：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。
    提升1：试试让结尾依旧是"."，且结尾的"."与前一个单词之间无空格。比如：输入一个英文句子, 词之间有1个或者若干个空格，句子以英文标点"."结尾。要求颠倒该句子中的词语顺序，并且词之间有且只有一个空格，结尾仍然是"."，结尾的"."与前一个单词之间无空格。
    提升2：如果输入是字符数组，如何在不分配额外空间的情况下，得到和上述一样的效果。
  6. 557. 反转字符串中的单词 III：给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

单词

可以直接按关键词【单词】搜索，以下仅列举一些比较常见的。

  1. 720. 词典中最长的单词：给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词，该单词是由words词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案，则返回答案中字典序最小的单词。
  2. 819. 最常见的单词：给定一个段落 (paragraph) 和一个禁用单词列表 (banned)。返回出现次数最多，同时不在禁用列表中的单词。
  3. 面试题 17.15. 最长单词：给定一组单词words，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。若有多个长度相同的结果，返回其中字典序最小的一项，若没有符合要求的单词则返回空字符串。
  4. 面试题 17.22. 单词转换：给定字典中的两个词，长度相等。写一个方法，把一个词转换成另一个词， 但是一次只能改变一个字符。每一步得到的新词都必须能在字典中找到。编写一个程序，返回一个可能的转换序列。如有多个可能的转换序列，你可以返回任何一个。
  5. 面试题 17.11. 单词距离和会员题245.最短单词距离3：有个内含单词的超大文本文件，给定任意两个单词，找出在这个文件中这两个单词的最短距离(相隔单词数)。

替换字符串

  1. 剑指 Offer 05. 替换空格：请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
  2. 面试题 01.03. URL化：URL化。编写一种方法，将字符串中的空格全部替换为%20。假定该字符串尾部有足够的空间存放新增字符，并且知道字符串的“真实”长度。（注：用Java实现的话，请使用字符数组实现，以便直接在数组上操作。）
  3. 424. 替换后的最长重复字符：给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。

子串

可以直接按关键词【子串】搜索，以下仅列举一些比较常见的。

  1. 696. 计数二进制子串：给定一个字符串 s，计算具有相同数量0和1的非空(连续)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。
  2. 459. 重复的子字符串：给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
  3. 3. 无重复字符的最长子串和剑指 Offer 48. 最长不含重复字符的子字符串：给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
  4. 395. 至少有K个重复字符的最长子串：找到给定字符串（由小写字符组成）中的最长子串 T ， 要求 T 中的每一字符出现次数都不少于k。输出T的长度。
  5. 1044. 最长重复子串：给出一个字符串 S，考虑其所有重复子串（S 的连续子串，出现两次或多次，可能会有重叠）。返回任何具有最长可能长度的重复子串。（如果 S 不含重复子串，那么答案为 ""。）PS：本题较难，量力而行。

唯一字符

  1. 剑指 Offer 50. 第一个只出现一次的字符：在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
  2. 387. 字符串中的第一个唯一字符：给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
  3. 面试题 01.01. 判定字符是否唯一：确定一个字符串 s 的所有字符是否全都不同。

字符串运算

  1. 415. 字符串相加：给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。
  2. 43. 字符串相乘：给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
  3. 227. 基本计算器 II和面试题 16.26. 计算器：给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外)，计算其结果。
    提升：按关键词【计算器】搜索，查看其他计算器相关的困难题。

字符串转换

  1. 剑指 Offer 46. 把数字翻译成字符串：给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
  2. 剑指 Offer 67. 把字符串转换成整数：写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
  3. 12. 整数转罗马数字：给定一个整数，将其转为罗马数字。
  4. 13. 罗马数字转整数：给定一个罗马数字，将其转换成整数。
  5. 273. 整数转换英文表示和面试题 16.08. 整数的英语表示：将非负整数num转换为其对应的英文表示。PS：高频困难题，量力而行。
  6. 面试题 05.02. 二进制数转字符串：二进制数转字符串。给定一个介于0和1之间的实数（如0.72），类型为double，打印它的二进制表达式。如果该数字无法精确地用32位以内的二进制表示，则打印“ERROR”。

字符串游戏

  1. 657. 机器人能否返回原点：在二维平面上，有一个机器人从原点 (0, 0) 开始。给出它的移动顺序，判断这个机器人在完成移动后是否在 (0, 0) 处结束。
  2. 面试题 16.04. 井字游戏：设计一个算法，判断玩家是否赢了井字游戏。输入是一个 N x N 的数组棋盘，由字符" "，"X"和"O"组成，其中字符" "代表一个空位。
  3. 面试题 16.22. 兰顿蚂蚁：编写程序来模拟蚂蚁执行的前 K 个动作，并返回最终的网格。
  4. 6. Z 字形变换：将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

括号

可以直接按关键词【括号】搜索，以下仅列举一些比较常见的。

  1. 面试题 08.09. 括号和22. 括号生成：数字n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
  2. 20. 有效的括号：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
  3. 856. 括号的分数：给定一个平衡括号字符串 S，按一定规则计算该字符串的分数。
  4. 32. 最长有效括号：给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。PS：困难题量力而行。
  5. 1249. 移除无效的括号：给你一个由 '('、')' 和小写字母组成的字符串 s。你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。
  6. 301. 删除无效的括号：删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。

回文

可以直接按关键词【回文】搜索，以下仅列举一些比较常见的。

  1. 409. 最长回文串：给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
  2. 125. 验证回文串：给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
  3. 680. 验证回文字符串 Ⅱ：给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
  4. 面试题 01.04. 回文排列：给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。
  5. 5. 最长回文子串：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
  6. 647. 回文子串：给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
  7. 516. 最长回文子序列：给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。
  8. 214. 最短回文串：给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。PS：困难题量力而行。

结束语

字符串的题目非常多，是笔试面试的高频考题。本人建议初学者先按上面的列表刷题，其中连题解都看不懂的题目可以先忽略，后面有机会再看的话，可能会了解的更透彻。有些题目不要过分追求最优解，特别是可以用马拉车算法，不要只背最优解的答案，而是去理解更深层的原理，理解不了的话干脆不要用这个解法，因为真正面试时候被发现只会背代码的话，印象分会更差。

评论 (16)