2019面试算法题「字符串处理+动态规划」汇总，有哪些？

Attention 秋招接近尾声，我总结了 牛客、WanAndroid 上，有关笔试面经的帖子中出现的算法题，结合往年考题写了这一系列文章，所有文章均与 LeetCode 进行核对、测试。欢迎食用 本文将覆盖 「字符串处理」 + 「动态规划」 方面的面试算法题，文中我将给出： 面试中的题目 解题的思路 特定问题的技巧和注意事项 考察的知识点及其概念 详细的代码和解析 开始之前，我们先看下会有哪些重点案例： 为了方便大家跟进学习，我在 GitHub 建立了一个仓库 仓库地址：超级干货！精心归纳视频、归类、总结，各位路过的老铁支持一下！给个 Star ！ 现在就让我们开始吧！ 字符串处理 字符串广泛应用 在 Java 编程中，在 Java 中字符串属于对象，Java 提供了 String 类来创建和操作字符串。面试中的字符串处理问题，主要是对于字符串各种方法的灵活应用。下面结合实例，讲讲常见的考点： 括号生成 给定 n，表示有 n 对括号, 请写一个函数以将其生成所有的括号组合，并返回组合结果。 例如 给出 n = 3，生成结果为： [ "((()))", "(()())", "(())()", "()(())", "()()()" ] 解题思路 使用 回溯法 只有在我们知道序列仍然保持有效时才添加 '(' or ')'，而不是像 方法一 那样每次添加。我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点， 如果我们还剩一个位置，我们可以开始放一个左括号。 如果它不超过左括号的数量，我们可以放一个右括号。 视频 视频讲解和源码-生成括号 public List<String> generateParenthesis(int n) { List<String> res = new ArrayList<>(); helper(n, n, "", res); return res; } // DFS private void helper(int nL, int nR, String parenthesis, List<String> res) { // nL 和 nR 分别代表左右括号剩余的数量 if (nL < 0 || nR < 0) { return; } if (nL == 0 && nR == 0) { res.add(parenthesis); return; } helper(nL - 1, nR, parenthesis + "(", res); if (nL >= nR) { return; } helper(nL, nR - 1, parenthesis + ")", res); } 复杂度 Excel表列标题 给定一个正整数，返回相应的列标题，如Excel表中所示。如: 1 -> A， 2 -> B ... 26 -> Z， 27 -> AA 示例 : 输入: 28 输出: "AB" 解题思路 网上看了 n 多人的方法，感觉很多都做麻烦了。大多数人都困在这个 ‘A’ 或者说 n = 0 上 举个例子，如果输入 26，我们一般会直接把它 %26 这样得到的就是一个 0 然而很多人得到字符的方式都是 %26 + 64，也就是 0 + ‘A’ = 'A' ,正确答案当然是 ‘Z’，于是加了一堆判断 其实不用那么麻烦，一个 n-- 就能搞定. public String convertToTitle (int n) { StringBuilder str = new StringBuilder(); while (n > 0) { n--; str.append ( (char) ( (n % 26) + 'A')); n /= 26; } return str.reverse().toString(); } 翻转游戏 给定一个只包含两种字符的字符串：+和-，你和你的小伙伴轮流翻转"++"变成"--"。当一个人无法采取行动时游戏结束，另一个人将是赢家。编写一个函数，计算字符串在一次有效移动后的所有可能状态。