本文同步发布在我的个人博客 LeetCode周赛总结 第277场 欢迎访问
本次周赛没想到比上周还要简单，前三题都可以用非常简单的方法快速解决，第四题如果想对了方向其实也比较简单。
元素计数
题目链接
元素计数
解题思路
相当基础的题目，要同时具有一个严格较小元素和一个严格较大元素，只需要保证这个数 num 满足 num > minVal && num < maxVal即可。
解题代码
class Solution {
public:
int countElements(vector<int>& nums) {
int minVal = INT32_MAX, maxVal = INT32_MIN;
for (int i = 0; i < nums.size(); i++) {
minVal = min(minVal, nums[i]);
maxVal = max(maxVal, nums[i]);
}
int res = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] > minVal && nums[i] < maxVal)
res++;
}
return res;
}
};
按符号重排数组
题目链接
按符号重排数组
解题思路
最容易想到和实现的方法显然是将正数和负数分别存入两个数组，再合并到一个数组中，虽然这样做空间复杂度比较高，但思路最为简单，代码实现相对较快。
解题代码
class Solution {
public:
vector<int> rearrangeArray(vector<int>& nums) {
vector<int> posVec;
vector<int> negVec;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] > 0)
posVec.emplace_back(nums[i]);
if (nums[i] < 0)
negVec.emplace_back(nums[i]);
}
vector<int> res;
for (int i = 0; i < posVec.size(); i++) {
res.emplace_back(posVec[i]);
res.emplace_back(negVec[i]);
}
return res;
}
};
找出数组中的所有孤独数字
题目链接
找出数组中的所有孤独数字
解题思路
对数字进行统计，考虑使用哈希表 HashMap 存储数组的数据，哈希表的 key 为数组中的数字，value 为该数字出现的次数。
再次遍历数组，对数组的每一个元素 num 判断 HashMap[num] 是否为 1，并且 HashMap[num - 1] 和 HashMap[num + 1] 是否存在，若都满足，则该数字为孤独数字，加入结果中。
解题代码
class Solution {
public:
vector<int> findLonely(vector<int>& nums) {
unordered_map<int, int> numsMap;
for (int i = 0; i < nums.size(); i++) {
numsMap[nums[i]]++;
}
vector<int> res;
for (int i = 0; i < nums.size(); i++) {
if (numsMap[nums[i]] == 1) {
if (numsMap.count(nums[i] - 1) == 0 && numsMap.count(nums[i] + 1) == 0)
res.emplace_back(nums[i]);
}
}
return res;
}
};
基于陈述统计最多好人数
题目链接
基于陈述统计最多好人数
解题思路
本题测试用例中中 2 <= n <= 15，数据量很小，可以考虑直接枚举所有的情况，并检验该情况下是否合理。
所有可能情况个数为 2n，每种情况用二进制数 anan - 1···a0 来表示，an 为 0 代表该情况下 n 角色为 坏人，an 为 1 代表该情况下 n 角色为 好人。
在统计了该情况下的角色情况后，就对其进行验证。由于坏人既可能说真话也可能说假话，因此对其验证没有意义，我们只需要对该情况下的好人进行验证。验证方法是遍历这个好人的陈述，若出现陈述与该情况不符，则该情况不符合条件，不统计其好人的数目。最终遍历所有的情况后，得到符合条件的好人最大数目。
解题代码
class Solution {
public:
int maximumGood(vector<vector<int>>& statements) {
int n = statements.size();
int res = 0;
for (int i = 0; i < (1 << n); i++) {
int cnt = 0;
vector<bool> isGood(n);
for (int j = 0; j < n; j++) {
if ((i >> j) & 1) { // 统计状态 i 的好人与坏人
isGood[j] = true;
cnt++;
}
else
isGood[j] = false;
}
// 验证状态是否合理
bool isLegal = true;
for (int j = 0; j < n; j++) {
if (isGood[j]) { // 若 j 是好人，则遍历他的陈述是否正确
for (int k = 0; k < n; k++) {
if (statements[j][k] == 1 && !isGood[k]) {
isLegal = false;
break;
}
if (statements[j][k] == 0 && isGood[k]) {
isLegal = false;
break;
}
}
}
}
if(isLegal)
res = max(res, cnt);
}
return res;
}
};
