第九周 字符串处理、高级搜索

题目数：30+

本周作业

基础问题

• 转换成小写字母 （Easy）半年内出题频次：

• 最后一个单词的长度 （Easy）半年内出题频次：

• 宝石与石头 （Easy）半年内出题频次：

• 字符串中的第一个唯一字符 （Easy）半年内出题频次：

• 最长公共前缀 （Easy）半年内出题频次：

字符串操作

• 反转字符串 （Easy）半年内出题频次：

• 翻转字符串里的单词 （Medium）半年内出题频次：

• 仅仅反转字母 （Easy）半年内出题频次：

同构 / 异位词系列问题

• 同构字符串 （Easy）半年内出题频次：

• 有效的字母异位词 （Easy）半年内出题频次：

• 字母异位词分组 （Medium）半年内出题频次：

• 找到字符串中所有字母异位词 （Medium）半年内出题频次：

字符串 + 动态规划

• 通配符匹配 （Hard）半年内出题频次：

• 二进制矩阵中的最短路径 （Medium）半年内出题频次：

自己选择合适的算法解答 （普通 BFS？双向 BFS？A*？）

实战例题

以下为课上实战例题

第 17 课 字符串处理

字符串基础知识

• 字符串转换整数 (atoi) （Medium）半年内出题频次：

Rabin-Karp 字符串哈希算法

• 实现 strStr() （Easy）半年内出题频次：

• 重复叠加字符串匹配 （Medium）半年内出题频次：

回文串系列问题

• 验证回文串 （Easy）半年内出题频次：

• 验证回文字符串 Ⅱ （Easy）（贪心 + 验证）半年内出题频次：

• 最长回文子串 （Medium）

中间向两边扩张 O(n2) 加入二分 + Rabin-Karp 优化，O(nlogn)

半年内出题频次：

字符串 + 动态规划

• 正则表达式匹配 （Hard）半年内出题频次：

• 不同的子序列 （Hard）半年内出题频次：

第 18 课 高级搜索

搜索剪枝

• 括号生成 （Medium）半年内出题频次：

• N 皇后 （Hard）半年内出题频次：

数独系列

• 有效的数独 （Medium）半年内出题频次：

• 解数独 （Hard）半年内出题频次：

迭代加深、折半搜索与双向搜索

• 单词接龙 （Hard）半年内出题频次：

启发式搜索：A* 算法

• 滑动谜题 （Hard）半年内出题频次：

• 八数码 （Medium）（AcWing）
• 八数码（打印方案） （Medium）（AcWing）