前几天看到一个网友爆料，说他在鹅厂外包，喜欢上了一个正式员工的小姐姐，想约她吃饭，结果被人家婉拒了，话里话外的意思就是：“你去找份正经工作吧，不想浪费时间”。
说实话，外包和正式员工的差别其实挺明显的。外包的同学一般来说没有那么多的资源和福利，工作内容也是按项目来定的，没个稳定的职位感。
而正式员工有的是固定薪水、完整的晋升通道、各种福利，还有更高的工作安全感。
可能那个小姐姐就是看中这些，觉得在外包上不太能看到未来。谁让咱们外包的工资、福利、年终奖啥的都比不上正式员工呢？
不过，我觉得评论里说的也有道理：“实力是最好的吸引力”。
如果你在外包工作上做得特别出色，积累了非常丰富的经验或者有更高的技术水平，小姐姐也许会更看得上你。
算法题：贴纸拼词
今天我们来聊聊一道很有意思的算法题：贴纸拼词。
这道题的核心是，给定一些贴纸，每个贴纸上都有一定数量的字母，你的任务是使用这些贴纸来拼出一个目标词。贴纸是有限的，每个贴纸上的字母可以无限制使用，但你不能任意拿贴纸，必须利用已有的贴纸拼凑目标字符串。任务的挑战性在于如何高效地判断是否能拼出目标词，以及如何找到最少的贴纸数量。
我觉得这种题目，背后其实是动态规划（Dynamic Programming，DP）思想的典型应用。
假设我们有以下的几个贴纸：
String[] stickers = {"with", "example", "science"};
String target = "thehat";
目标是从这些贴纸中拼出 "thehat"。显然，我们可以从“with”贴纸中拿到“t”和“h”，“example”中拿到“e”，而从“science”中拿到“a”和“t”……等。所以，如何组织这些贴纸的字母就变成了问题的关键。
方法一：暴力法
要是你让我一开始就手动拼，可能会“哇，这好像挺简单的”。但是作为程序员，你得想想，如果贴纸和目标词非常大，这样的暴力拼法就很容易超时了。直接遍历所有组合，显然是不可行的。
动态规划解决方案
我们的目标是找到最少的贴纸数量来拼出目标词。问题的核心在于状态转移。假设 dp[i] 表示拼出目标词前 i 个字符所需要的最少贴纸数。我们可以通过动态规划来逐步更新每个状态，直到我们拼出目标词。
首先，初始化一个 dp 数组，表示拼出不同字符数量的最小贴纸数。然后，我们逐步尝试使用每一个贴纸来更新这些状态。
下面是用 Java 实现这个算法的代码示例：
import java.util.HashMap;
import java.util.Map;
public class StickerToWord {
public int minStickers(String[] stickers, String target) {
int n = target.length();
// dp[mask] 表示目标字母的状态，mask 是 target 中字符出现次数的二进制表示
Map<String, Integer> memo = new HashMap<>();
memo.put("", 0); // 拼出空字符串所需的贴纸数是 0
return helper(stickers, target, memo);
}
private int helper(String[] stickers, String target, Map<String, Integer> memo) {
if (memo.containsKey(target)) {
return memo.get(target);
}
int res = Integer.MAX_VALUE;
// 统计 target 中字符的频率
int[] targetCount = new int[26];
for (char c : target.toCharArray()) {
targetCount[c - 'a']++;
}
// 尝试使用每一个贴纸
for (String sticker : stickers) {
// 如果贴纸没有帮助，就跳过
if (sticker.indexOf(target.charAt(0)) == -1) continue;
// 构造新目标字符串
int[] stickerCount = new int[26];
for (char c : sticker.toCharArray()) {
stickerCount[c - 'a']++;
}
StringBuilder newTarget = new StringBuilder();
// 减少目标字母的数量
for (int i = 0; i < 26; i++) {
if (targetCount[i] > 0) {
int remaining = targetCount[i] - stickerCount[i];
if (remaining > 0) {
newTarget.append(String.valueOf((char) (i + 'a')).repeat(remaining));
}
}
}
// 如果剩余目标是空，说明已经拼完了
if (newTarget.length() > 0) {
res = Math.min(res, helper(stickers, newTarget.toString(), memo) + 1);
}
}
// 记录最小结果并返回
memo.put(target, res == Integer.MAX_VALUE ? -1 : res);
return res;
}
public static void main(String[] args) {
StickerToWord solver = new StickerToWord();
String[] stickers = {"with", "example", "science"};
String target = "thehat";
int result = solver.minStickers(stickers, target);
System.out.println(result); // 输出拼出 "thehat" 所需的最少贴纸数
}
}
代码解析
目标频率统计：首先，我们统计目标词中每个字符出现的次数。这是因为我们需要一个依据来判断如何通过贴纸来减少目标词中字符的数量。
使用每个贴纸：我们逐一尝试使用每个贴纸，计算拼出目标词所需的最少贴纸数。如果一个贴纸有助于减少目标词中的字符数量，我们就递归地更新目标状态，并尝试下一个贴纸。
记忆化递归：为了避免重复计算相同的子问题，我们使用了记忆化（
memo）来缓存已经计算过的结果。最小值更新：对于每一次递归，我们更新最小的贴纸数量。如果无法拼出目标词，则返回 -1。
复杂度分析
时间复杂度上，由于我们使用了递归和记忆化，所以对于每个目标字母的状态转移最多会处理一次。每次递归都需要遍历所有的贴纸，因此总体时间复杂度是 O(n * 2^m)，其中 n 是目标词的长度，m 是贴纸的数量。
总的来说，这道题的解决方案其实是通过动态规划和记忆化搜索来减少不必要的重复计算。虽然看起来有点复杂，但一旦掌握了这种递归加记忆化的技巧，就能有效地解决类似的问题。🧠
-END-
以上，就是今天的分享了，看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言。
