Ivecia
Ivecia
全部文章
分类
每日一题(1)
题目解析(10)
归档
标签
去牛客网
登录
/
注册
Johnson's Blog
Woooooooooooooooooooooo
全部文章
(共9篇)
[题解] 碱基消消乐
本题需要使用栈进行模拟,可以参考括号的匹配进行匹配(A对应T,C对应G)。 class Solution { public: bool pairgame(string origin) { stack<char> s; int n = origin....
2021-02-21
0
600
[题解] 数学实验
按照题目要求模拟即可,注意第一个循环是n>=10而不是n>10。 class Solution { public: int mathexp(long long n) { while (n >= 10) { long long m =...
模拟
数学
2020-08-08
1
533
[题解] String II
考察知识点:字符串操作,枚举 枚举答案子序列的字母 判断尽可能多的将其他字母变换为该字母的最长子序列的长度 在这些可能的答案中取最大值 时间复杂度 参考代码: class Solution { public: int string2(int k, string s) { ...
字符串
枚举
2020-06-06
0
597
[题解] String I
考察知识点:字符串操作,枚举,二分 首先,我们不难发现朴素算法: 枚举答案串长度 检验所有长度为该长度的串变为26个字母需要的操作数量 然后回答即可 事实上,该算法在某些处理速度较快的语言中可以通过,时间复杂度为。 然而,将枚举改为二分,时间复杂度即可降为,可以轻松通过本题。 参考代码: cla...
二分
字符串
2020-06-06
0
735
[题解] Tree III
“第二直径”显然其一端的端点在直径的一端。可以尝试用反证法来进行证明,这里给出一个简单的证明,具体细节留给读者自证:若第二直径的两端都不在直径的端点,那么将第二直径的某一端向直径端点延申,得到的路径长度不降。 因此,我们只需要任意找到一条直径,分别找到他们到每个点的距离,然后寻找到“第三大”的位置(...
Dfs
树
2020-05-28
1
700
[题解] Tree VI
考察点:完全二叉树的含义及其推广,Dfs序列遍历顺序 需要理解完全二叉树的含义:即每个结点的子结点之多有两个子结点。 不妨我们先考虑最简单的一种情况,即结点编号按照一棵“标准”完全二叉树给出,即结点的两个子结点分别为与,根据这棵树,我们可以非常容易的用一次Dfs来“发掘”整棵树的构造。 由此,我们可...
树
Dfs
2020-05-28
0
601
[题解] Tree II
考察点:完全二叉树的含义及其推广,Bfs序列遍历顺序 需要理解完全二叉树的含义:即每个结点的子结点之多有两个子结点。 不妨我们先考虑最简单的一种情况,即结点编号按照一棵“标准”完全二叉树给出,即结点的两个子结点分别为与,根据这棵树,我们可以非常容易的用一次Dfs来“发掘”整棵树的构造。 由此,我们可...
树
Bfs
2020-05-28
0
693
[题解] Tree IV
60~70% 可以直接对整棵树进行Dfs,即从根结点1号点开始,若当前结点为,则递归搜索两个子结点、,然后暴力计算答案,时间复杂度为,根据语言选择的不同可能会有不同的得分。 100% 本题利用了两个性质,同时这也是完全二叉树最常用的两个性质: 若父结点为,则其两个子结点分别为、 每一层均有个结点 ...
树
完全二叉树
2020-05-27
0
726
[牛客每日一题] 2020-03-24
Gate: https://ac.nowcoder.com/acm/contest/1080/C 题目大意 给你个物品,每个物品有价值,限制表示最多选择多少个物品(要求最终选出来的数量满足所有选出来物品带有的限制) 思路 枚举选择多少个物品,显然所有不低于此限制的物品均能选择,则使用一个优先队列储存...
2020-03-24
9
2049