欢迎大家加QQ群：623375442，可以方便群里面交流。emm，感觉最后一题还挺难的。居然只有6分。
100461. Find the Original Typed String I
Alice 正在她的电脑上输入一个字符串。但是她打字技术比较笨拙，她 可能 在一个按键上按太久，导致一个字符被输入 多次 。
尽管 Alice 尽可能集中注意力，她仍然可能会犯错 至多 一次。
给你一个字符串 word ，它表示 最终 显示在 Alice 显示屏上的结果。
请你返回 Alice 一开始可能想要输入字符串的总方案数。
测试样例：
输入：word = "abbcccc"
输出：5
解释：
可能的字符串包括："abbcccc" ，"abbccc" ，"abbcc" ，"abbc" 和 "abcccc" 。
解答：默认一种情况，Alice一个按键都没打错。然后遍历word，每个连续相同的字符串（比如aaaa），最多能共享连续次数 - 1种可能。
class Solution {
public int possibleStringCount(String word) {
int count = 0;
List<Integer> cache = new ArrayList<>();
for (int i = 0; i < word.length(); ++i) {
if (i != 0 && word.charAt(i) != word.charAt(i - 1)) {
cache.add(count);
count = 1;
} else {
++count;
}
}
if (count > 0) {
cache.add(count);
}
// 一个都没打错
int res = 1;
for (int n : cache) {
// 连续 - 1种可能。
res += (n - 1);
}
return res;
}
}100430. Find Subtree Sizes After Changes
给你一棵 n 个节点且根节点为编号 0 的树，节点编号为 0 到 n - 1 。这棵树用一个长度为 n 的数组 parent 表示，其中 parent[i] 是第 i 个节点的父亲节点的编号。由于节点 0 是根，parent[0] == -1 。
给你一个长度为 n 的字符串 s ，其中 s[i] 是节点 i 对应的字符。
对于节点编号从 1 到 n - 1 的每个节点 x ，我们 同时 执行以下操作 一次 ：
- 找到距离节点 x 最近 的祖先节点 y ，且 s[x] == s[y] 。
- 如果节点 y 不存在，那么不做任何修改。
- 否则，将节点 x 与它父亲节点之间的边 删除 ，在 x 与 y 之间连接一条边，使 y 变为 x 新的父节点。
请你返回一个长度为 n 的数组 answer ，其中 answer[i] 是 最终 树中，节点 i 为根的子树的 大小 。
一个 子树 subtree 指的是节点 subtree 和它所有的后代节点。
测试样例：
输入：parent = [-1,0,0,1,1,1], s = "abaabc"
输出：[6,3,1,1,1,1]
解释：节点 3 的父节点从节点 1 变为节点 0 。
解答：多次遍历的版本。第一次计算每个节点迁移去的位置。第二次遍历计算子树规模。
class Solution {
public int[] findSubtreeSizes(int[] parent, String s) {
Stack<Integer>[] stacks = new Stack[26];
for (int i = 0; i < 26; ++i) {
stacks[i] = new Stack<>();
}
dfsTree(0, parent, buildListTree(parent), stacks, s);
int[] res = new int[parent.length];
dfsChildCount(0, buildListTree(parent), res);
return res;
}
private List<Integer>[] buildListTree(int[] parent) {
List<Integer>[] children = new List[parent.length];
for (int i = 0; i < parent.length; ++i) {
children[i] = new ArrayList<>();
}
for (int i = 0; i < parent.length; ++i) {
if (parent[i] != -1) children[parent[i]].add(i);
}
return children;
}
private void dfsTree(int cur, int[] parent, List<Integer>[] children, Stack<Integer>[] stacks, String s) {
int o = s.charAt(cur) - 'a';
if (!stacks[o].isEmpty()) {
parent[cur] = stacks[o].peek();
}
stacks[o].push(cur);
for (int n : children[cur]) {
dfsTree(n, parent, children, stacks, s);
}
stacks[o].pop();
}
private int dfsChildCount(int cur, List<Integer>[] children, int[] res) {
res[cur] = 1;
for (int n : children[cur]) {
res[cur] += dfsChildCount(n, children, res);
}
return res[cur];
}
}100438. Maximum Points Tourist Can Earn
给你两个整数 n 和 k ，和两个二维整数数组 stayScore 和 travelScore 。
一位旅客正在一个有 n 座城市的国家旅游，每座城市都 直接 与其他所有城市相连。这位游客会旅游 恰好 k 天（下标从 0 开始），且旅客可以选择 任意 城市作为起点。
每一天，这位旅客都有两个选择：
- 留在当前城市：如果旅客在第 i 天停留在前一天所在的城市 curr ，旅客会获得 stayScore[i][curr] 点数。
- 前往另外一座城市：如果旅客从城市 curr 前往城市 dest ，旅客会获得 travelScore[curr][dest] 点数。
请你返回这位旅客可以获得的 最多 点数。
测试样例：
输入：n = 2, k = 1, stayScore = [[2,3]], travelScore = [[0,2],[1,0]]
输出：3
解释：旅客从城市 1 出发并停留在城市 1 可以得到最多点数。
解答：这题规模不大，直接动态规划。每天可以从上一个城市进行移动，或者待在当前城市。
class Solution {
public int maxScore(int n, int k, int[][] stayScore, int[][] travelScore) {
int[] max = new int[n];
for (int i = 0; i < k; ++i) {
int[] nextMax = new int[n];
for (int j = 0; j < n; ++j) {
// 待在当前城市
nextMax[j] = max[j] + stayScore[i][j];
for (int curr = 0; curr < n; ++curr) {
// 从别的城市移动过来
nextMax[j] = Math.max(max[curr] + travelScore[curr][j], nextMax[j]);
}
}
max = nextMax;
}
int res = 0;
for (int m : max) {
res = Math.max(res, m);
}
return res;
}
}100462. Find the Original Typed String II
Alice 正在她的电脑上输入一个字符串。但是她打字技术比较笨拙，她 可能 在一个按键上按太久，导致一个字符被输入 多次 。
给你一个字符串 word ，它表示 最终 显示在 Alice 显示屏上的结果。同时给你一个 正 整数 k ，表示一开始 Alice 输入字符串的长度 至少 为 k 。
请你返回 Alice 一开始可能想要输入字符串的总方案数。
由于答案可能很大，请你将它对 10^9 + 7 取余 后返回。
测试样例：
输入：word = "aaabbb", k = 3
输出：3
解释：可能的字符串是"abb", "aab", "aaab", "aabb", "abbb", "aaabb", "aabbb"和"aaabbb"
解答：补充一下示例 3的所有可能。第一个需要注意的，每个连续字符串最少需要保留1个字符（比如aaa，最少是a，不能全部清除）。这样，首先计算没有k这个限制的情况下，所有的可能。其次最短情况无法满足之后，我们计算所有不满足要求的可能性。
class Solution {
private static final int mod = 1_000_000_007;
public int possibleStringCount(String word, int k) {
int count = 0;
List<Integer> cache = new ArrayList<>();
for (int i = 0; i < word.length(); ++i) {
if (i != 0 && word.charAt(i) != word.charAt(i - 1)) {
cache.add(count);
count = 1;
} else {
++count;
}
}
if (count > 0) {
cache.add(count);
}
long total = 1;
// 没有k限制的情况下，所有的可能。
for (int i : cache) {
total = total * i % mod;
}
// 最短都能满足k，停止计算
if (cache.size() >= k) {
return (int) (total);
}
// 去除[cache.size(), k)所有的可能性
int remove = k - cache.size();
int[] dp = new int[remove];
dp[0] = 1;
for (int n : cache) {
if (n == 0) continue;
int add = n - 1, tmp = 0;
// 动态规划，计算当前连续字符串可以贡献的次数。
int[] nextDp = new int[remove];
for (int j = 0; j < remove; ++j) {
tmp = (tmp + dp[j]) % mod;
nextDp[j] = tmp;
if (j >= add) {
tmp = (tmp - dp[j - add] + mod) % mod;
}
}
dp = nextDp;
}
for (int n : dp) {
total = (total - n + mod) % mod;
}
return (int) (total);
}
}