我的力扣主页:
https://leetcode.cn/u/cutesnake/
我的PAT仓库:
https://github.com/suchacutesnake/pat
2023.1.1
然而竞赛积分还是掉了1分……做太慢也不行吗……
2023.1.6
花了很多时间,还是好菜,难受~~
PAT 1064 Complete Binary Search Tree
https://pintia.cn/problem-sets/994805342720868352/exam/problems/994805407749357568
难点:
1.对于以层序遍历数组表示的树,如何进行各种遍历。
2.对BST,中序(左根右)遍历结果是递增的。
3.对CBST的某一节点i,其左右子树分别表示为2i,2i+1。
Leetcode 1803. Count Pairs With XOR in a Range (hard)
https://leetcode.cn/problems/count-pairs-with-xor-in-a-range/
字典树。答案都看不懂,可以竞争我遇到过最难的力扣题。倒不是不明白字典树这个数据结构,就是想不明白为什么要用字典树???有没有人来教教我啊~~~
2023.1.9
Leetcode 6306. Time to Cross a Bridge (hard)
https://leetcode.cn/problems/time-to-cross-a-bridge/
周赛327场的hard,比起力扣感觉更像PAT的题目,涉及很繁琐的数据结构设计。周赛做完T3只剩10分钟了,时间不够就没做。这种复杂的模拟题对大家来说原来都很困难,头一次见到周赛接近半小时大佬们才全通的。
2023.1.11
Leetcode753. Cracking the Safe(hard)
https://leetcode.cn/problems/cracking-the-safe/
初见欧拉回路题,只能看答案。算法看明白了,但是代码实现是怎么做到的看不明白……
2023.1.14
Leetcode 1819. Number of Different Subsequences GCDs (H)
https://leetcode.cn/problems/number-of-different-subsequences-gcds/
比较有趣的暴力枚举,杂了一点数学
2023.1.16
题外话,前几天折腾xray,第一次GitHub上交了pull request,秒merge了,还挺兴奋的。
2023.1.18
- Finding MK Average (H)
https://leetcode.cn/problems/finding-mk-average/
很多讨论的有序集合+队列题, 奋斗数小时后tle,耻辱看答案。不是自己写的代码真的不想cv提交啊,这每日一题打卡不打也罢!明明就是不会嘛,不会的题却显示通过给一种自欺欺人的感觉……评论区acm爷普遍用的树状数组,我什么时候能学学这个数据结构啊……
2023.3.23
https://leetcode.cn/problems/word-ladder-ii/solution/dan-ci-jie-long-ii-by-leetcode-solution/
要做吐了,错了一遍又一遍,到后面几乎和题解一模一样的写法就差cv了,还是超时。时间复杂度肯定是一样的,卡剪枝了,好难受啊真的好难受。错误的代码先贴着。
class Solution {
public:
void backtrack(unordered_map<string, unordered_set<string>>& from, vector<vector<string>>& res, vector<string>& cur, string beginWord) {
for (auto& next : from[cur.back()]) {
cur.emplace_back(next);
if (next == beginWord) {
res.emplace_back(cur);
reverse(res.back().begin(), res.back().end());
}
backtrack(from, res, cur, beginWord);
cur.pop_back();
}
}
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> dict({wordList.begin(), wordList.end()});
unordered_map<string, int> steps;
unordered_map<string, unordered_set<string>> from;
queue<string> q;
vector<vector<string>> res;
int ansSize = 0x3f3f3f3f;
if (dict.find(endWord) == dict.end()) return res;
q.emplace(beginWord);
steps[beginWord] = 1;
int step = 1;
while (!q.empty()) {
step++;
int n = q.size();
for (int j = 0; j < n; ++j) {
string s = move(q.front());
string ss = s;
q.pop();
for (char& ch : s) {
char temp = ch;
for (int i = 0; i < 26; ++i) {
ch = i + 'a';
if (ch == temp || !dict.count(s) || (steps.count(s) && steps[s] < step)) continue;
steps[s] = step;
from[s].emplace(ss);
if (s == endWord) {
break;
}
q.emplace(s);
}
ch = temp;
}
}
}
vector<string> cur({endWord});
backtrack(from, res, cur, beginWord);
return res;
}
};