深圳国贸网站建设,网站开发保存学习进度的方案,colorway wordpress,个体工商户网上注销绪论 虽然是上周日参加的比赛#xff0c;但是这周没有怎么学习#xff0c;每天就是玩耍。也导致对周赛的总结迟迟没有进行。想着再拖下去下次周赛都要开始了#xff0c;在这里补一下。 这场比赛总体比上场简单一些#xff0c;但是最后一道题因为忘记初始化类内变量导致调试…绪论 虽然是上周日参加的比赛但是这周没有怎么学习每天就是玩耍。也导致对周赛的总结迟迟没有进行。想着再拖下去下次周赛都要开始了在这里补一下。 这场比赛总体比上场简单一些但是最后一道题因为忘记初始化类内变量导致调试好久血泪教训。
题目分析
A:转化时间需要的最少操作数
因为单独考虑小时、分钟太过繁琐我的方法是将其转换成时间戳类似chrono的time_since_epoch方法。
class Solution {
public:int convertTime(string current, string correct) {int h1 (current[0] - 0) * 10 current[1] - 0;int h2 (correct[0] - 0) * 10 correct[1] - 0;int m1 (current[3] - 0) * 10 current[4] - 0;int m2 (correct[3] - 0) * 10 correct[4] - 0;int x1 h1 * 60 m1;int x2 h2 * 60 m2;if (x1 x2) x2 24 * 60;int x x2 - x1;int ans 0;ans x / 60;x % 60;ans x / 15;x % 15;ans x / 5;x % 5;ans x / 1;x % 1;return ans;}
};B:找出输掉零场或一场比赛的玩家
用map去存储每个节点的入度之所以用map是因为要求结果有序。 需要注意的一点是即使是赢家我们也应该更新这个信息因为我们得统计入度为0的节点。
class Solution {
public:vectorvectorint findWinners(vectorvectorint matches) {mapint, int score;int x, y;for (auto arr : matches) {x arr[0]; y arr[1];score[x] 0;score[y] 1;}vectorvectorint ans(2);auto ans0 ans[0];auto ans1 ans[1];for (auto pr : score) {if (pr.second 0) ans0.push_back(pr.first);else if (pr.second 1) ans1.push_back(pr.first);}return ans;}
};
C:每个小孩最多能分到多少糖果
这个题目很关键的一点就是每个小孩拿到的糖果数目是相同的如果没有抓住这一点可能无从下手。如果确定每个小孩拿到的糖果数x那么每堆可以分的孩子数目是确定的。我们可以将其转换成一个判定问题对于x可以分给f(x)个孩子f(x)是否大于等于k。每次判定的复杂度是O(n)的。 很容易发现f(x)是单调递减的。因此我们可以考虑使用二分。 需要注意糖果数目可能超过了整数范围。
class Solution {
public:int maximumCandies(vectorint candies, long long k) {using ll long long;ll r 0;for (auto x : candies) r x;if (r k) return 0;auto check [](ll t) - bool {ll sum 0;for (auto x : candies) sum x / t;return sum k;};ll l 1, mid;ll ans 1;while (l r) {mid l (r - l) / 2;if (check(mid)) {ans mid;l mid 1;} else {r mid - 1;}}return ans;}
};
D:加密解密字符串
最后一道题有一点意思刚开始一看这不就是一个简单的模拟吗对于编码没什么说的这么小的数据闭着眼睛都过了。对于解码却有一些讲究。当时我看着200的数据有点上头觉得这还有什么好考虑的直接模结果果然超时了。。。 开始思考为什么会超时。因为values中可能出现重复的字符串所有一个位置可能有不同的字符。假如values中每个字符串都是一样的而需要解码的字符串就是这些一样的字符串组成的那么每个位置都有很多种组合很容易就超过1e9了。 虽然组合有可能超过1e9但是实际的dictionary却很小所以我们必须对组合进行剪枝而且必须在前缀阶段就进行剪枝如果等到解码结束再进行剪枝已经迟了。我刚开始模拟就没有剪枝 如果我们直接用数据对比前缀每次的时间复杂度都是O(200)左右虽然貌似不大但是也会超时。 为了更好的进行 剪枝我们就必须高效地判断一个前缀是否出现在dictionary。和前缀相关的操作容易联想到字典树。 字典树虽然名字听起来很高大上但是实际上是一个非常容易理解的数据结构每个节点存储一个字符有26个子孩子用来记录在这个字符后是否有其他字符。还需要一个布尔变量用来记录当前字符是否可以作为某个单词的结尾。 因为我们的字典树只进行添加不会删除所以可以使用内存池进行优化。如果直接使用new在堆上分配内存那么每次添加新节点都需要new一次最后程序结束还需要delete。这对内存的管理提出了要求。如果我们使用简易的内存池就可以避免这个问题。具体的讲就是用vector管理内存。vector有自动扩容机制并且不用担心内存泄漏。 每个节点使用下标作为指针指向下一个节点。
struct Trie {struct Node {char c_;bool is_word_;vectorint next_;Node(char c): next_(26, -1), is_word_(false) {}};int root_ 0;vectorNode nodes_;public:Trie() {nodes_.emplace_back( );}void add(const string s) {int root root_, t;for (auto c : s) {int t nodes_[root].next_[c - a];if (t -1) {//节点不存在nodes_.emplace_back(c);t nodes_[root].next_[c - a] nodes_.size() - 1;}root t;}nodes_[root].is_word_ true;}};上面的字典树没有实现search方法匹配前缀。因为在实际搜索的过程中我们是一个字母一个字母进行确认所以可以将前缀匹配和搜索结合起来这样子我们在搜索下一个字符的时候只搜索在字典树的字符优化算法。
class Encrypter {struct Trie {struct Node {char c_;bool is_word_;vectorint next_;Node(char c): next_(26, -1), is_word_(false) {}};int root_ 0;vectorNode nodes_;public:Trie() {nodes_.emplace_back( );}void add(const string s) {int root root_, t;for (auto c : s) {int t nodes_[root].next_[c - a];if (t -1) {//节点不存在nodes_.emplace_back(c);t nodes_[root].next_[c - a] nodes_.size() - 1;}root t;}nodes_[root].is_word_ true;}};vectorchar keys_;vectorstring values_;Trie trie_;unordered_mapchar, int keys_map_;unordered_mapstring, vectorint values_map_;vectorvectorint init(const string s) {vectorvectorint ans;int n s.size();for (int i 0; i n; i 2) {ans.emplace_back();auto arr ans.back();auto t values_map_[s.substr(i, 2)];for (auto x : t) {arr.push_back(keys_[x] - a);}}return ans;}
public:Encrypter(vectorchar keys, vectorstring values, vectorstring dictionary): keys_(keys), values_(values){for (auto s : dictionary) {trie_.add(s);}int n keys.size();for (int i 0; i n; i) {keys_map_[keys[i]] i;}n values.size();for (int i 0; i n; i) {values_map_[values[i]].push_back(i);}}string encrypt(string word1) {string ans;for (auto c : word1) {ans.append(values_[keys_map_[c]]);}return ans;}int decrypt(string word2) {auto arr init(word2);int n arr.size();int ans 0;functionvoid(int, int) dfs;dfs [](int idx, int root) {if (idx n) {if (trie_.nodes_[root].is_word_) ans;return;}auto vec arr[idx];int t;for (auto x : vec) {t trie_.nodes_[root].next_[x];if (t -1) continue;dfs(idx 1, t);}};dfs(0, 0);return ans;}
};
但是在实现字典树的过程中我忘记对Node的is_word_字段进行初始化导致出错。幸亏最终调试出来了。
经验总结
这次周赛偏简单题目思维量不是很大虽然有一些编码量。前三道题里就是第三道的二分比较需要一些思考。第四道题需要考虑到使用字典树进行前缀匹配。
虽然是第一次实现字典树出现了一个bug但是总体还是比较满意的。代码紧凑逻辑完整。
