大厂程序员爆料：原来30k，被裁后找了个外包25k，活少不加班， 感觉日子有点安逸了，还要不要继续找工作？
虎哥约 5 分钟我最近看到一个有趣的爆料，说的是某位大厂程序员在被裁后，找了个外包工作，工资从原来的30K降到了25K，虽然工资低了点，但工作压力反而轻松了很多。
基本上每天7点就能下班，生活也变得相对安逸。嗯…听起来，好像是很多程序员都梦寐以求的那种工作状态吧？😌
大家知道，大厂的工作节奏有多快，项目总是堆积如山，加班更是家常便饭。
那种压迫感真的很让人疲惫。不过，转到外包之后，尽管薪水缩水了一点，但工作强度减轻了，整个人都轻松了不少。
不过，很多人可能会问：“你会不会觉得自己降低了标准？会不会觉得自己没啥追求了？” 其实我觉得，“安逸”并不是一件坏事。
毕竟，工作也只是生活的一部分，能有时间去追求自己喜欢的事，何乐而不为呢？
所以，关于要不要继续找工作，怎么说呢？如果你已经觉得现在的日子挺好，那就不必急着去追求更高的薪水或更大压力的职位。
生活是自己的，做自己喜欢的事，才是最重要的。
算法题：贴纸拼词
嗨，大家好。今天咱们聊一个有点意思的算法题：贴纸拼词。
题目大致是这样：给定一个字符串 target 和一些“贴纸”，每个贴纸也是一个字符串。你需要通过使用这些贴纸的字母来拼出 target 字符串，并且每个贴纸的字母只能用一次。你要返回拼出 target 的最少贴纸数，如果无法拼出，则返回 -1。
让我们来逐步分析这个问题。
首先，看到这个题目，你可能会想，这不就像是典型的背包问题吗？但它和一般的背包问题有些不同，因为我们不是背包容量有限，而是“字母的数量有限”，也就是说我们只能使用每个字母一次。简单来说，这是一道“有字母限制的拼接问题”。但别着急，我们先不急着判断复杂度，先来理清楚怎么做。
思路一：字母计数
我们首先要做的是，把每个贴纸中的字母出现频率统计一下。你会发现，其实问题的核心就在于如何高效地利用这些贴纸中的字母。比如说，给你三个贴纸 "aab", "bc", "d" 和目标字符串 "abc", 那么显然我们需要从这些贴纸里找到能拼出 "abc" 的最少字母组合。通过统计频率，我们能够清楚地知道：a 和 b 需要被至少两次使用，而 c 需要被至少一次使用。
思路二：递归 + 剪枝
要解决这个问题，直接暴力穷举所有的贴纸组合是不可取的，因为贴纸数目可能非常大，目标字符串也可能很长。那么，怎么办呢？我们可以用递归和剪枝来优化。
递归的思路就是，每次从 target 中挑选一个字母，看看能不能用已有的贴纸来拼出这个字母，如果拼得出，就减去这个字母，继续拼接剩下的部分，直到全部字母拼出为止。如果拼不出来，就返回 -1。
但是递归带来的问题是重复计算，所以我们引入记忆化搜索（memoization）来缓存计算过的状态，避免重复计算。
具体实现时，我们可以用一个字典来记录当前 target 的字母数量，每次递归调用时，将 target 转换为一个字符串形式作为键，存储最少的贴纸数作为值。
代码实现
下面是我写的一个实现方法，使用了递归和剪枝的技巧。
from collections import Counterdef minStickers(stickers, target):
# 将目标字符串转为字母计数
target_count = Counter(target)
# 将所有贴纸转为字母计数的列表
sticker_counts = []
for sticker in stickers:
sticker_counts.append(Counter(sticker))
# 使用记忆化搜索来记录已计算过的目标字母情况
memo = {}
def dfs(target_count):
# 如果目标为空，说明已经拼完，返回0
if not target_count:
return 0
# 如果已计算过这个目标字母组合，直接返回结果
target_tuple = tuple(sorted(target_count.items()))
if target_tuple in memo:
return memo[target_tuple]
# 初始化最小贴纸数为一个非常大的数
res = float('inf')
# 遍历每个贴纸
for sticker_count in sticker_counts:
# 如果当前贴纸不能帮助解决问题，跳过
if target_count.most_common(1)[0][0] not in sticker_count:
continue
# 减去当前贴纸能覆盖的字母
new_target_count = target_count.copy()
for letter in sticker_count:
if letter in new_target_count:
new_target_count[letter] -= sticker_count[letter]
if new_target_count[letter] <= 0:
del new_target_count[letter]
# 递归求解剩下的目标字符串
result = dfs(new_target_count)
if result != -1:
res = min(res, 1 + result) # 使用1个贴纸 + 递归结果
# 记录结果
memo[target_tuple] = res if res != float('inf') else -1
return memo[target_tuple]
return dfs(target_count)
# 测试用例
stickers = ["with", "example", "science"]
target = "thehat"
print(minStickers(stickers, target)) # 输出: 3
解释
target_count用来存储目标字符串中各个字母的数量。sticker_counts存储了所有贴纸的字母计数。我们使用递归 dfs来尝试拼接target字符串，每次递归尝试减少目标字母的数量，直到完全拼出目标。通过 memo字典缓存已经计算过的状态，避免重复计算。
复杂度分析
时间复杂度：O(N * 2^M)，其中 N是目标字符串target的长度，M是贴纸的数量。由于递归的深度受target中不同字母数的限制，实际表现比理论复杂度要好。空间复杂度：O(N)，主要由字母计数和递归栈深度占用。
总结
这个题目看似简单，实际上考验了我们如何通过有效的计数和递归来减少计算量。记忆化搜索和剪枝的结合使用，极大地提高了算法的效率，避免了暴力递归的重复计算。对于程序员来说，这种技巧是非常实用的，尤其在处理组合问题时。
对编程、职场感兴趣的同学，大家可以联系我微信：golang404，拉你进入“程序员交流群”。
虎哥作为一名老码农，整理了全网最全《python高级架构师资料合集》。