LeetCode周赛277场，10分钟A三题，第四题翻车了……
LeetCode周赛277场，10分钟A三题，第四题翻车了……
作者 |
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，我是梁唐。
非常难受，在昨天的LeetCode周赛中翻车了，最后一题没解出来……
不知道小伙伴们战果如何，废话不多说，我们来看下题目吧。
元素计数
给定一个整数数组nums，要求数组当中有一个严格较小元素和较大元素的的元素数目。
我们来看下它给的样例：
不知道大家有没有注意到题目的坑点，题目中说的是一个严格较小和较大的元素，说了严格较小，但没有说是严格一个。其实题目的意思是至少有一个，也就是说多于一个也OK，但偏偏样例当中无法体现……
解法
只要理解了正确的意思，其实非常简单，我们只需要进行排序即可。
class Solution {
public:
int countElements(vector<int>& nums) {
int n = nums.size();
if (n <= 2) return 0;
sort(nums.begin(), nums.end());
// 排序之后很容易求出最大最小值
int mini = nums[0];
int maxi = nums[n-1];
int ret = 0;
for (int i = 1; i < n-1; i++) {
if (nums[i] > mini && nums[i] < maxi) ret++;
}
return ret;
}
};
按符号重排数组
给你一个下标从 0 开始的整数数组 nums ，数组长度为 偶数 ，由数目相等的正整数和负整数组成。
你需要 重排 nums 中的元素，使修改后的数组满足下述条件：
- 任意 连续 的两个整数 符号相反
- 对于符号相同的所有整数，保留 它们在 nums 中的 顺序 。
重排后数组以正整数开头。重排元素满足上述条件后，返回修改后的数组。
解法
非常简单的模拟题，直接照着题目的意思做即可。我们把正负数先分开，然后按照题目要求合并即可。
class Solution {
public:
vector<int> rearrangeArray(vector<int>& nums) {
vector<int> neg, pos;
int n = nums.size();
for (int i = 0; i < n; i++) {
if (nums[i] > 0) pos.push_back(nums[i]);
else neg.push_back(nums[i]);
}
vector<int> ret;
for (int i = 0; i < n/2; i++) {
ret.push_back(pos[i]);
ret.push_back(neg[i]);
}
return ret;
}
};
找出数组中的孤独数字
给你一个整数数组 nums 。如果数字 x 在数组中仅出现 一次 ，且没有 相邻 数字（即，x + 1 和 x - 1）出现在数组中，则认为数字 x 是 孤独数字 。
返回 nums 中的 所有 孤独数字。你可以按 任何顺序 返回答案。
解法
同样是一道模拟题，难度也不是很大。
首先，我们可以创建一个map，用来存储每一个数字出现的次数。之后我们遍历map，对于所有只出现了一次的数字x，判断
x-1和x+1是否出现即可。
class Solution {
public:
vector<int> findLonely(vector<int>& nums) {
vector<int> ret;
map<int, int> mp;
int n = nums.size();
for (int i = 0; i < n; i++) {
if (mp.count(nums[i]) == 0) mp[nums[i]] = 0;
mp[nums[i]]++;
}
for (auto it = mp.begin(); it != mp.end(); it++) {
int v = it->first;
if (it->second == 1 && mp.count(v-1) == 0 && mp.count(v+1) == 0) ret.push_back(v);
}
return ret;
}
};
基于陈述统计最多好人数
游戏中存在两种角色：
- 好人：该角色只说真话。
- 坏人：该角色可能说真话，也可能说假话。
给你一个下标从 0 开始的二维整数数组 statements ，大小为 n x n ，表示 n 个玩家对彼此角色的陈述。具体来说，statements[i][j] 可以是下述值之一：
0表示i的陈述认为j是 坏人 。1表示i的陈述认为j是 好人 。2表示i没有对j作出陈述。
另外，玩家不会对自己进行陈述。形式上，对所有 0 <= i < n ，都有 statements[i][i] = 2 。
根据这 n 个玩家的陈述，返回可以认为是 好人 的 最大 数目。
解法
这题是重头戏，老梁比赛的时候花了一个小时都没有能够AC。
首先，题目就非常复杂，可能出现的情况非常多。我们想要理清楚题目当中所有的含义就不容易，简单来说，每个人都会给其他人一个评价。0表示坏人，1表示好人，2表示不评价。表面上来看，只是一种评价而已，但稍微深入想一些会发现很多有意思的洞见。
我们知道坏人可以说假话，但好人必须说真话。意味着当有两个人的言论冲突时，必然至少有一个坏人。言论冲突其实很好判断，一种情况比较简单，体现在两人对于同一个人的评价不同。有人说是好人，有人说是坏人。还有一种情况稍微复杂一些，就是A判断B是好人。如果B是好人，A不一定是好人， 但如果B是坏人，A一定是坏人。
判断到这里，就会发现有些关系是双向的，比如互相矛盾，两人之间可以有一人为真，而有些关系是双向的，比如A觉得B是好人。它们之间没有直接的联系，但B的结果显然会影响A的情况，这种关联就是单向的。
另外我们还可以发现，对于坏人来说，我们分析它的言论没有意义。因为坏人天生是可以说谎的，所以我们去纠结坏人的言论没有意义，我们只需要关注被我们认为是好人的一波即可。
老梁当时就是被困在这里了，想来想去不知道该如何处理，一直觉得可能可以使用并查集，但苦思冥想调试了半天总有反例出现。
等比赛结束之后才灵光一闪，其实题目当中已经有了提示，就是n的范围。n的范围非常小，最大只有15。所以我们完全可以枚举每个人是好人或者是坏人的情况，当n=15时，一共有32768种，远远没有到达超时的标准。
想到这里就容易多了，首先我们枚举所有的状态，接着我们对于每一个状态算出每一个人是好是坏的情况，最后我们检查一下当前这种情况是否会构成矛盾，如果不构成矛盾，那么更新答案。
判断是否构成矛盾我们同样只需要从好人入手，因为坏人可说真话可说假话，怎么说都能逻辑自洽，我们只需要判断只说真话的好人之间是否有矛盾即可。由于我们已经预先枚举了好人坏人的分布方式，我们只需要遍历一下每一个好人对于大家的判断是否有冲突的地方即可。
AC代码如下：
class Solution {
public:
bool dfs(int n, vector<vector<int>>& sta, int u, vector<bool>& good, vector<bool> &vis) {
if (vis[u]) return true;
vis[u] = true;
for (int i = 0; i < n; i++) {
// 如果u对i没有看法，跳过
if (sta[u][i] == 2) continue;
// 如果u对i的看法和当前枚举的i的情况不同
if (sta[u][i] != good[i]) return false;
}
bool ret = true;
for (int i = 0; i < n; i++) {
// 通过递归继续判断下一个好人，是否构成矛盾
if (vis[i] == false && good[i]) ret &= dfs(n, sta, i, good, vis);
}
return ret;
}
int maximumGood(vector<vector<int>>& sta) {
int n = sta.size();
int ret = 0;
vector<bool> good(n, 0);
// 枚举所有可能的状态，从至少有一个好人开始
for (int s = 1; s < (1 << n); s++) {
int cur = 0;
int start = 0;
// good[i]表示i号是否是好人，0表示坏人，1表示好人
for (int i = 0; i < n; i++) {
good[i] = s & (1 << i);
cur += good[i];
if (good[i]) start = i;
}
vector<bool> vis(n, 0);
// 递归判断是否存在矛盾，没有矛盾更新答案
if (dfs(n, sta, start, good, vis)) ret = max(ret, cur);
}
return ret;
}
};
老实讲这道题比较麻烦，我在比赛的时候一直纠结着使用图论或者是并查集的算法去进行建模，忽略了题目当中给定的n很小的信息，以至于没有想到直接枚举的方法。
赛后，有大佬指出本题是一道NP-hard问题，所以一定没有多项式复杂度内的解，那么肯定就要考虑状态枚举了。只能说是比赛的时候还是思维不够敏捷，没有想到这一层。
好了，关于这次的周赛就聊到这里，感谢大家的阅读。