Johnson_sky

题目解析

每日一题(1)

/ 注册

全部文章 / 题目解析（共8篇）

[题解] 碱基消消乐

本题需要使用栈进行模拟，可以参考括号的匹配进行匹配（A对应T，C对应G）。 class Solution { public: bool pairgame(string origin) { stack<char> s; int n = origin....

2021-02-21

0 456

[题解] 数学实验

按照题目要求模拟即可，注意第一个循环是n>=10而不是n>10。 class Solution { public: int mathexp(long long n) { while (n >= 10) { long long m =...

模拟数学

2020-08-08

1 403

[题解] String II

考察知识点：字符串操作，枚举枚举答案子序列的字母判断尽可能多的将其他字母变换为该字母的最长子序列的长度在这些可能的答案中取最大值时间复杂度参考代码： class Solution { public: int string2(int k, string s) { ...

字符串枚举

2020-06-06

0 441

[题解] String I

考察知识点：字符串操作，枚举，二分首先，我们不难发现朴素算法：枚举答案串长度检验所有长度为该长度的串变为26个字母需要的操作数量然后回答即可事实上，该算法在某些处理速度较快的语言中可以通过，时间复杂度为。然而，将枚举改为二分，时间复杂度即可降为，可以轻松通过本题。参考代码： cla...

二分字符串

2020-06-06

0 532

[题解] Tree III

“第二直径”显然其一端的端点在直径的一端。可以尝试用反证法来进行证明，这里给出一个简单的证明，具体细节留给读者自证：若第二直径的两端都不在直径的端点，那么将第二直径的某一端向直径端点延申，得到的路径长度不降。因此，我们只需要任意找到一条直径，分别找到他们到每个点的距离，然后寻找到“第三大”的位置（...

Dfs 树

2020-05-28

1 545

[题解] Tree VI

考察点：完全二叉树的含义及其推广，Dfs序列遍历顺序需要理解完全二叉树的含义：即每个结点的子结点之多有两个子结点。不妨我们先考虑最简单的一种情况，即结点编号按照一棵“标准”完全二叉树给出，即结点的两个子结点分别为与，根据这棵树，我们可以非常容易的用一次Dfs来“发掘”整棵树的构造。由此，我们可...

树 Dfs

2020-05-28

0 480

[题解] Tree II

考察点：完全二叉树的含义及其推广，Bfs序列遍历顺序需要理解完全二叉树的含义：即每个结点的子结点之多有两个子结点。不妨我们先考虑最简单的一种情况，即结点编号按照一棵“标准”完全二叉树给出，即结点的两个子结点分别为与，根据这棵树，我们可以非常容易的用一次Dfs来“发掘”整棵树的构造。由此，我们可...

树 Bfs

2020-05-28

0 523

[题解] Tree IV

60~70% 可以直接对整棵树进行Dfs，即从根结点1号点开始，若当前结点为，则递归搜索两个子结点、，然后暴力计算答案，时间复杂度为，根据语言选择的不同可能会有不同的得分。 100% 本题利用了两个性质，同时这也是完全二叉树最常用的两个性质：若父结点为，则其两个子结点分别为、每一层均有个结点 ...

树完全二叉树

2020-05-27

0 555