最近看到一个有意思的爆料，不禁想和大家聊聊这个话题。一个华为员工突然接到领导的电话，问他愿不愿意去非洲上班，工资45000元，合同五年，外加双倍年终奖。
但这位同事也不傻，问了一句：“为什么选我？” 领导的回答更让人“惊呆”了：“你不是准备买房吗？五年赚够一套房，心动不？”
大家都知道，程序员虽然在国内有不小的工资，但买房的压力也大得很。要是换到非洲，换个环境，薪水翻倍，生活成本可能还低，那么这是不是个机会呢？
我觉得，在这种情况下，关键是看两个因素：薪水的吸引力和个人的生活需求。
如果合同靠谱，薪水按时到位，我觉得不妨去试试看，也许这是一个能改变人生轨迹的机会。毕竟，钱难赚，但机会一旦错过，可能就没了。
怎么样，你们觉得呢？
算法题：不同的子序列
s，长度为 n，我们用一个数组 dp 来存储到第 i 个字符时能够形成的子序列个数。初始时，dp[0] = 1，表示空字符串的子序列只有一个，就是空串。s[i]，我们考虑它能新增多少个子序列。如果 s[i] 没有重复出现，那么新增的子序列就是当前子序列数的两倍。原因很简单：我们可以将 s[i] 加入之前的所有子序列中，形成新的子序列。s[i] 在之前的某个位置也出现过，那么我们新增的子序列会有重复的情况。所以，我们需要记录之前 s[i] 出现的位置，以避免重复计数。import java.util.HashMap;
public class DistinctSubsequences {
public int distinctSubseqII(String s) {
int mod = 1000000007;
int n = s.length();
long[] dp = new long[n + 1];
HashMap<Character, Integer> lastIndex = new HashMap<>();
dp[0] = 1; // 空串的子序列数是1
for (int i = 1; i <= n; i++) {
// dp[i] 是 dp[i-1] 的两倍，表示当前字符可以在所有子序列后面加上
dp[i] = dp[i - 1] * 2 % mod;
// 如果当前字符之前出现过，去掉重复的部分
if (lastIndex.containsKey(s.charAt(i - 1))) {
int last = lastIndex.get(s.charAt(i - 1));
dp[i] = (dp[i] - dp[last - 1] + mod) % mod;
}
// 更新当前字符的最后出现位置
lastIndex.put(s.charAt(i - 1), i);
}
// 最后返回 dp[n] - 1, 1 是因为我们不考虑空子序列
return (int) (dp[n] - 1);
}
public static void main(String[] args) {
DistinctSubsequences solution = new DistinctSubsequences();
String s = "aba";
System.out.println(solution.distinctSubseqII(s)); // 输出 6
}
}
dp[i]表示考虑到字符串的前i个字符，能组成多少个不同的子序列。对于每一个 s[i]，我们用dp[i] = dp[i - 1] * 2来计算，因为它可以出现在之前所有子序列的末尾。如果字符 s[i]在之前出现过，我们就减去重复的子序列。这里通过一个哈希表lastIndex来记录每个字符最后一次出现的位置，避免重复计算。最后返回 dp[n] - 1，因为我们不计空子序列。
这个问题的核心思想是动态规划，通过状态转移来计算不同子序列的个数。 我们通过哈希表来避免重复的计算，以此降低了时间复杂度。 最后，我们的时间复杂度是 O(n)，空间复杂度也是 O(n)，相较于暴力枚举所有子序列的 O(2^n)，这简直就是一场大胜。
对编程、职场感兴趣的同学，可以链接我，微信：coder301 拉你进入“程序员交流群”。
