1. 第一个出现两次的字母
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
简单模拟即可。
代码
class Solution {
public:
char repeatedCharacter(string s) {
unordered_map<char, int> ump;
for (auto& ch : s) {
++ump[ch];
if (ump[ch] == 2) return ch;
}
return '0';
}
};2. 相等行列对
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
直接用map应该不算作弊吧？记录下每行的出现次数，依次构造每列，加总每列在map中的出现次数即可。
代码
class Solution {
public:
int equalPairs(vector<vector<int>>& grid) {
map<vector<int>, int> mp;
for (auto& row : grid) ++mp[row];
int ans = 0;
for (int i = 0; i < grid[0].size(); ++i) {
vector<int> col(grid.size());
for (int j = 0; j < grid.size(); ++j) {
col[j] = grid[j][i];
}
ans += mp[col];
col.clear();
}
return ans;
}
};3. 设计食物评分系统
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
我想的是用三个无序map，里面要套个vector，且比较绕，dalao也是用无序map，不同的是套了pair，以及套个set再套个pair，应该是利用了set本身的特性，使得插入和删除都自动排好序，最后直接返回首元素即可。
代码
class FoodRatings {
private:
unordered_map<string, pair<int, string>> foodToRateCus;
unordered_map<string, set<pair<int, string>>> cusToRateFood;
public:
FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {
for (int i = 0; i < foods.size(); ++i) {
foodToRateCus[foods[i]] = pair(-ratings[i], cuisines[i]);
cusToRateFood[cuisines[i]].emplace(pair(-ratings[i], foods[i]));
}
}
void changeRating(string food, int newRating) {
cusToRateFood[foodToRateCus[food].second].erase(pair(-foodToRateCus[food].first, food));
cusToRateFood[foodToRateCus[food].second].emplace(-newRating, food);
foodToRateCus[food].first = -newRating;
}
string highestRated(string cuisine) {
return cusToRateFood[cuisine].begin()->second;
}
};4. 优质数对的数目
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
又用到了 __builtin_popcount 函数。
本题关键在于分析出题设的隐含关系，即两个位运算所的数的1加和总数，实际上就等于两个数的1的总位数。
代码
class Solution {
public:
long long countExcellentPairs(vector<int>& nums, int k) {
unordered_map<int, int> ump;
long ans = 0L;
for (auto& num : unordered_set<int>(nums.begin(), nums.end())) ++ump[__builtin_popcount(num)]; //直接利用set的特性去重
for (auto& elem1 : ump) {
for (auto& elem2 : ump) {
if (elem1.first + elem2.first >= k) ans += elem1.second * elem2.second;
}
}
return ans;
}
};5. 最好的扑克手牌
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
分类计算即可。
代码
class Solution {
public:
string bestHand(vector<int>& ranks, vector<char>& suits) {
int m = unordered_set<char>(suits.begin(), suits.end()).size();
if (m == 1) return "Flush";
unordered_map<int, int> mp;
for (auto& r : ranks) ++mp[r];
int n = mp.size();
if (n == 5) return "High Card";
if (n < 3) return "Three of a Kind";
for (auto& elem : mp) if (elem.second >= 3) return "Three of a Kind";
return "Pair";
}
};6. 全 0 子数组的数目
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
第一个思路比较慢，第二个思路好多了。
当出现连续0的时候，这些连续零能组成的全0数组个数是固定的（等差数列），所以只要遍历一次数组，每次出现连续0后计算加总即可。
代码
class Solution {
public:
long long zeroFilledSubarray(vector<int>& nums) {
// vector<long long> dp(nums.size(), 0L);
// if (nums[0] == 0) dp[0] = 1L;
// long long ans = dp[0];
// for (int i = 1; i < nums.size(); ++i) {
// if (nums[i] == 0) {
// if (nums[i - 1] == 0) dp[i] = dp[i - 1] + 1;
// else dp[i] = 1;
// ans += dp[i];
// }
// }
// return ans;
long long ans = 0L;
long long cnt = 0L;
for (auto& num : nums) {
if (num == 0) ++cnt;
else {
ans += (1 + cnt) * cnt / 2;
cnt = 0;
}
}
ans += (1 + cnt) * cnt / 2;
return ans;
}
};7. 设计数字容器系统
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
与后面一期周赛的第三题有点类似。根据上次的经验，用一个无序map记录下标到数字的映射，再用一个无序map嵌套一个set记录数字对应的下标有哪些。由于set是有序的，所以查询时返回set的首元素即可，若其首元素不存在，则返回-1。成功通过，时间超过89%。
代码
class NumberContainers {
private:
unordered_map<int, int> indexToNum;
unordered_map<int, set<int>> numToIndex;
public:
NumberContainers() {
}
void change(int index, int number) {
int originNum = indexToNum[index];
if (originNum) numToIndex[originNum].erase(index);
indexToNum[index] = number;
numToIndex[number].emplace(index);
}
int find(int number) {
int index = -1;
if (numToIndex[number].begin() != numToIndex[number].end()) index = *(numToIndex[number].begin());
return index;
}
};8. 不可能得到的最短骰子序列
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
思路比较抽象，参考这篇 ，一时间看不太懂。
代码
Comments NOTHING