1. 强密码检验器 II
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
按题意模拟即可。
代码
class Solution {
public:
bool strongPasswordCheckerII(string password) {
if (password.size() < 8) return false;
bool small = false, big = false, num = false, special = false, same = true;
for (int i = 0; i < password.size(); ++i) {
if (password[i] - 'a' >= 0 && password[i] - 'a' < 26) small = true;
else if (password[i] - 'A' >= 0 && password[i] - 'A' < 26) big = true;
else if (password[i] - '0' >= 0 && password[i] - '0' < 10) num = true;
else if (password[i] == '!' || password[i] == '@' || password[i] == '#' || password[i] == '$' || password[i] == '%' || password[i] == '^' || password[i] == '&' || password[i] == '*' || password[i] == '(' || password[i] == ')' || password[i] == '-' || password[i] == '+') special = true;
if (i > 0) {
if (password[i] == password[i - 1]) same = false;
}
}
return small && big && num && special && same;
}
};2. 咒语和药水的成功对数
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
二分查找 + map记录避免重复查找。
需要注意的是，当查找到与目标值相等的值时，需要逐个向前搜索是否还存在相等值。
不过这要是在周赛中碰到超时，我估计又会做不出来。以后遇到搜索的题，要注意是否存在重复查找。
代码
class Solution {
public:
vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
vector<int> pairs;
map<int, int> mp;
sort(potions.begin(), potions.end());
int n = potions.size();
for (auto& spell : spells) {
if (mp[spell]) {
pairs.push_back(mp[spell]);
continue;
}
int low = 0, high = n - 1;
double target = (double)success / (double)spell;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (potions[mid] == target) {
while (mid >=0 && potions[mid] == target) --mid;
low = mid + 1;
break;
}
else if (potions[mid] > target) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
pairs.push_back(n - low);
mp[spell] = n - low;
}
return pairs;
}
};3. 替换字符后匹配
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
暴力解法是可以通过的。可能是因为要求连续子串，长度有限。
代码
class Solution {
public:
bool matchReplacement(string s, string sub, vector<vector<char>>& mappings) {
int n = s.size(), m = sub.size();
unordered_map<char, unordered_set<char>> mp;
for (auto& mapping : mappings) mp[mapping[0]].emplace(mapping[1]);
for (int i = 0; i <= n - m; ++i) {
string t = s.substr(i, m);
bool flag = true;
for (int j = 0;j < m; ++j) {
if (sub[j] == t[j]) continue;
else {
if (mp[sub[j]].count(t[j])) continue;
else {
flag = false;
break;
}
}
}
if (flag) return true;
}
return false;
}
};4. 统计得分小于 K 的子数组数目
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
参考这篇
使用双指针去解。对于连续子数组，且有单调性的题，都可以用双指针做。本题中虽然元素无序，但显然子数组多一位时，分数一定是涨的。
代码
class Solution {
public:
long long countSubarrays(vector<int>& nums, long long k) {
long long ans = 0LL, sum = 0LL;
for (int left = 0, right = 0; right < nums.size(); ++right) {
sum += nums[right];
while (sum * (right - left +1) >= k) {
sum -= nums[left++];
}
ans += right - left + 1;
}
return ans;
}
};5. 极大极小游戏
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
按题意模拟即可。
代码
class Solution {
public:
int minMaxGame(vector<int>& nums) {
int n = nums.size();
while (n != 1) {
n = n >> 1;
for (int i = 0; i < n; ++i) {
if ((i & 1) == 0) nums[i] = min(nums[(i << 1)], nums[(i << 1) + 1]);
else nums[i] = max(nums[(i << 1)], nums[(i << 1) + 1]);
}
}
return nums[0];
}
};6. 划分数组使最大差为 K
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
分析题意，题目要求是非连续子序列，且最大差与元素顺序其实无关，那么实际上 整个题目跟元素顺序都是无关的，所以可以直接排序后再做。
正序遍历，如果当前元素减起始元素的差大于k，说明需要划分一次序列，且将起始位置放到当前位置。
最后注意，需要返回ans + 1，因为最后一个子序列没有被统计。
代码
class Solution {
public:
int partitionArray(vector<int>& nums, int k) {
int ans = 0;
sort(nums.begin(), nums.end());
int n = nums.size();
int start = 0;
for (int i = 0;i < n; ++i) {
if (nums[i] - nums[start] > k) {
++ans;
start = i;
}
}
return ans + 1;
}
};7. 替换数组中的元素
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
按题意模拟即可。由于数组中元素互不相同，用map存储每个元素的位置即可。
代码
class Solution {
public:
vector<int> arrayChange(vector<int>& nums, vector<vector<int>>& operations) {
unordered_map<int, int> numToPos;
int n = nums.size(), m = operations.size();
for (int i = 0; i < n; ++i) numToPos[nums[i]] = i;
for (auto& operation : operations) {
int pos = numToPos[operation[0]];
numToPos.erase(operation[0]);
nums[pos] = operation[1];
numToPos[operation[1]] = pos;
}
return nums;
}
};8. 设计一个文本编辑器
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
我用的数组方法，虽然功能可以完整实现，但有用例超时。
题解用的链表。
实际上cpp的list是双向链表，可以比较方便地实现。
看评论区说数据比较弱，用字符串模拟可以过。估计是周赛时还没添加能让字符串模拟超时的数据，所以就当时的情境而言，这个代码是可以过的？
代码
class TextEditor {
private:
string s;
int cursorPos;
public:
TextEditor() {
s = "";
cursorPos = 0;
}
void addText(string text) {
s = s.substr(0, cursorPos) + text + s.substr(cursorPos, s.size() - cursorPos);
cursorPos += text.size();
}
int deleteText(int k) {
int delLen;
if (k >= cursorPos) {
s = s.substr(cursorPos, s.size() - cursorPos);
delLen = cursorPos;
cursorPos = 0;
}
else {
s = s.substr(0, cursorPos - k) + s.substr(cursorPos, s.size() - cursorPos);
cursorPos -= k;
delLen = k;
}
return delLen;
}
string cursorLeft(int k) {
if (k >= cursorPos) {
cursorPos = 0;
return "";
}
else {
cursorPos -= k;
int subLen;
if (cursorPos > 10) subLen = 10;
else subLen = cursorPos;
return s.substr(0 + cursorPos - subLen ,subLen);
}
}
string cursorRight(int k) {
if (k + cursorPos >= s.size()) cursorPos = s.size();
else cursorPos += k;
int subLen;
if (cursorPos > 10) subLen = 10;
else subLen = cursorPos;
return s.substr(0 + cursorPos - subLen ,subLen);
}
};
Comments NOTHING