25 – 09 – 09(补于 25 – 09 – 13)
我有一个小秘密,就不告诉你(
今日份题面
在第
1天，有一个人发现了一个秘密。给你一个整数
delay，表示每个人会在发现秘密后的delay天之后，每天 给一个新的人 分享 秘密。同时给你一个整数forget，表示每个人在发现秘密forget天之后会 忘记 这个秘密。一个人 不能 在忘记秘密那一天及之后的日子里分享秘密。给你一个整数
n，请你返回在第n天结束时，知道秘密的人数。由于答案可能会很大，请你将结果对109 + 7取余 后返回。
看上去像是模拟或者差分/前缀和,事实上也确实如此,不过官解中的模拟解法用到了双端队列我倒是没想到的(鉴定为武德不够充沛还不够暴力)
考虑维护一个 known 数组,表示在有几个人第 i 天得知秘密,注意此处不是总数,是当天得知密码的人数.
为什么这么写?因为算总数相当于前缀和,但我们不需要对过程中的总人数进行维护,只关注最后一天的情况,若中间在原数组基础上维护会导致逻辑混乱.
那么根据题意，恰好在第 i 天得知秘密的人，会在第 i+delay~i+forget−1 天分享秘密，也就是把 known[ i + delay, i + forget − 1 ] 增加 known[i]。答案要求在第 n 天知晓秘密的人数,也就是 $i \geq n – \text{forget} + 1$,所以对 known 进行:
$$\sum\limits_{i = n – \text{forget} + 1}^nknown[i]$$
即可
class Solution {
public int peopleAwareOfSecret(int n, int delay, int forget) {
final int MOD = (int)(1e9 + 7);
int[] diff = new int[n + 1];
diff[1] = 1;
diff[2] = -1;
int known = 0;
long ans = 0;
for (int i = 1; i <= n; i++) {
// 加上 diff[i] 后，known 表示恰好在第 i 天得知秘密的人数
known = (known + diff[i]) % MOD;
// 统计在第 n 天没有忘记秘密的人数
if (i >= n - forget + 1) {
ans += known;
}
if (i + delay <= n) {
diff[i + delay] = (diff[i + delay] + known) % MOD;
}
if (i + forget <= n) {
diff[i + forget] = (diff[i + forget] - known + MOD) % MOD; // +MOD 保证结果非负
}
}
return (int) (ans % MOD);
}
}
以上
25 – 09 -10 (补于 25 – 09 -14)
“坦克你没有后视镜的，枪炮是不长眼的，还有[-数据缺失-]哥们的语言是不通的。”(摇头眯眼，死亡微笑)
——Jing Wu
今日份题面：
在一个由
m个用户组成的社交网络里，我们获取到一些用户之间的好友关系。两个用户之间可以相互沟通的条件是他们都掌握同一门语言。给你一个整数
n，数组languages和数组friendships，它们的含义如下：
- 总共有
n种语言，编号从1到n。languages[i]是第i位用户掌握的语言集合。friendships[i] = [ui, vi]表示ui 和vi为好友关系。你可以选择 一门 语言并教会一些用户，使得所有好友之间都可以相互沟通。请返回你 最少 需要教会多少名用户。请注意，好友关系没有传递性，也就是说如果
x和y是好友，且y和z是好友，x和z不一定是好友。
最开始我想到的是维护一个并查集，然后检查并查集的大小与总人数，选取最多的作为目标语言。不过后来发现这思路有点问题，主要是维护并查集的同时我们难以对个体间的关系做出维护，直接剩下的全学肯定不符合题意，而单开另一个有向图的话效率就不如暴力贪心了。
所以思来想去，最终还是决定暴力枚举，通过标记无共同语言的成员后进行检查语言互通情况，选取剩余集合中被掌握的最多的那门语言作为目标即可
class Solution {
public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
int m = languages.length; // 用户数量
// 预计算每种语言的使用成员
Set<Integer>[] userLangs = new Set[m];
for (int i = 0; i < m; i++) {
userLangs[i] = new HashSet<>();
for (int lang : languages[i]) {
userLangs[i].add(lang);
}
}
// 标记无共同语言的成员
List<int[]> noCommon = new ArrayList<>();
for (int[] friend : friendships) {
int u = friend[0] - 1;
int v = friend[1] - 1;
// 检查
boolean common = false;
for (int lang : userLangs[u]) {
if (userLangs[v].contains(lang)) {
common = true;
break;
}
}
if (!common) {
noCommon.add(new int[]{u, v});
}
}
// 如果都有，返回 0 即可
if (noCommon.isEmpty()) {
return 0;
}
int minTeach = Integer.MAX_VALUE;
for (int lang = 1; lang <= n; lang++) {
Set<Integer> teachSet = new HashSet<>();
for (int[] pair : noCommon) {
int u = pair[0];
int v = pair[1];
if (!userLangs[u].contains(lang)) {
teachSet.add(u);
}
if (!userLangs[v].contains(lang)) {
teachSet.add(v);
}
}
minTeach = Math.min(minTeach, teachSet.size());
}
return minTeach;
}
}
所以想到了另一个问题，如果题目对我们能教授的语言不做限定，那应该怎么办？
发表回复