题目的主要信息： 已知完全二叉树的DFS正序遍历序列 求所有边两个端点异或的和 方法一：DFS 题目告诉我们这棵树是完全二叉树，根据完全二叉树的性质，对于编号为i的节点，它的左孩子的编号为2i，右孩子的编号为2i+1。因此我们可以根据这个性质，从根节点开始，通过性质得到左右孩子的编号，计算孩子和父节点的异或，再用DFS让左右孩子作为根节点，递归计算。 上图展示了二叉树编号和DFS顺序之间的关系，因为题目给出的数组a是以DFS遍历得到的，现在我们计算端点异或也是用DFS遍历，所以第i个遍历到的端点，权重为a[i]。在DFS实现中，我们需要一个变量count用于保存目前遍历的端点个数。 示例...

题目的主要信息： 已知带权无向图，每个节点之间仅有一条路径 求经过所有节点最小权重之和 方法一：DFS 如果不考虑路径长度，那么把所有路径走一遍必定可以经过所有节点。 要经过每一个节点，且每个节点之间只有一条路径，那么至少需要把所有的路径走一遍，假设权重之和为weight。在最坏的情况，每条路径都需要走两遍才能遍历所有节点，权重之和为2weight。最优解在[weight,2weight]范围中。如上图所示，在这种做法每段路径都重复走了一遍，如果能把重复路径的权重和最小化，即最大化只有一遍的路径权重之和。因此，我们需要找到从树的一端到另一端最长的路径，把这条最长不回溯路径长度剔除后，才是...

题目的主要信息： 烘干机可以每分钟烤干k滴水，自然烘干每分钟烘干1滴水；使用烘干机的时候可以同时进行自然烘干； 已经烘干机每分钟烤干水滴数和需要烘干的衣服的数量和水滴数，求解需要多长时间将所有衣服晾干。 方法一：暴力枚举法 最长的时间是所有衣服全部自然晾干需要的时间，即a数组中最多水滴数的为最大时间max。由于每件衣服都是湿的，所以所需时间至少为1，遍历一遍1到max的时间，判断是否能晾干所有衣服，若能晾干则是最小的时间。 具体做法： class Solution { public: bool isAvailable(int time,vector<int>& ...

思路： 题目的主要信息：题目需要对一个长为n的序列p进行排序，但是排序不是简单的进行，只能通过交换第x和第y的值。需要我们求解最小的序列。需要注意的地方： 交换序列对中的值为p中元素的下标，而非p中元素的值 方法一：并查集 首先我们考虑，有m对可以交换，其中可能会出现（a,b） (b,c)这种情况，即a能与b交换，b能与c交换，变相等于a能与c交换，[a,b,c]这三个元素可以互通，如果我们能把所有互通的元素集合都按照从小到大的顺序排序，那么最后得到的序列就是最小序列。这个思想就是并查集，通过不断的合并查找找到互通的集合。首先我们先对序列中的每个节点的根节点初始化为它本身，通过对可交换序列...

思路： 题目很短，主要信息为： 序列a中的数字为1到n的整数，只有一个数字重复 时间复杂度为 O(n)，额外空间复杂度为 O(1)。 方法一：求和相减 具体做法：1到n的整数之和为sum=若a中重复的数字为i，则a中所有数字之和可以表示为a_sum=这样就能够得到重复的数字为a_sum-sum=i。图解示例： class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int * @param a intvector ...

思路： 题目的主要信息： 已知build的询问过程，对于T个n，运行build(1,1,n)后，输出每个n询问过程中最大的ans。 ans在每一次询问结束后都清零。 方法一：递归 根据题目意思，直接构造一个函数模拟build的询问过程。同时设置两个全局变量ans和max_ans，设为全局变量的原因是，ans在每次查询后都会清零，同时为了减少在执行build函数时，每次都传递ans参数；max_ans由于要记录每次最大的ans值，设为全局变量比较方便。总共有T个过程需要查询，构建一个循环依次查询，查询结束后清零ans，同时记录下本次查询中最大的ans值。 具体做法： class Soluti...

思路： 题目的主要信息： 皮卡丘的生命值是HP，攻击力是ACK；杰尼龟的生命值是HP2，攻击力是ACK2。 杰尼龟在每回合开始前可以吃药满血复活，但吃药后不得在本回合发动攻击。 皮卡丘比杰尼龟先发动攻击。若能成功击败皮卡丘则返回最少回合数，否则返回-1。 方法一：暴力 首先解决一些特殊情况：a.HP2<ACK，杰尼龟第一局就被皮卡丘打倒，返回-1；b.HP<=ACK2，杰尼龟第一局就把皮卡丘打倒，返回1；其他情况以模拟战斗过程进行分析，若第round局结束后杰尼龟当前的血量低于ACK，表示杰尼龟必须吃药恢复血量，同时本局不能进攻，仍受到皮卡丘的攻击；若杰尼龟当前的血量高于ACK...

思路： 题目的主要信息：种花土地大小为3*n，1≤n≤1e5，根据题目要求，种花时需要满足以下两种条件： 土地上至少要有一朵花 每朵花的上下左右不能有花 方法一：动态规划 根据题目信息，总共有n列3x1的土地，如果用1代表在这格上种花，0代表这格不种花，在3x1的土地上种花有以下几种情况：我们用0、1、2、3、4、5、6、7来代表这八种种花方案。题目要求每朵花的上下左右不能有花，所以对于每一列3x1的土地都排除3、6、7三种情况，这三种情况会发生上下冲突。因此每一列土地可能的种花情况有0、1、2、4、5五种情况。我们用动态规划进行求解，首先建立一个nx8的dp数组。n代表总共有n列，依次是...

思路： 题目的主要信息：题目比较简短，需要注意的是哥德巴赫猜想，任意大于2的偶数都可以拆分成两个质数之和。该猜想尚未严格证明，但暂时没有找到反例。 已知的信息有一个整数N，需要计算N能表示为多少个素数的和，并返回个数 需要注意的是2是唯一的偶质数 方法一：数学方法 首先判断N是否为素数，分为两种情况：a.N为素数，N不能拆分为两个数相加，因此只能表示为1个素数的和，这个素数就是它本身，返回1。b.N不为素数，又分为两种情况：-1.若N为偶数，根据哥德巴赫猜想，任意大于2的偶数都可以拆分成两个质数之和。因此能表示为2个素数的和，返回2。-2.若N为奇数，由于奇数=奇数+偶数，偶数有素数偶数和...

思路： 题目的主要信息：题目较长，要记住的是每个人只能解决难度小于等于他自己能力的问题，自己解决不了的问题就要交给更厉害的朋友： 已知的信息有群友数量n，群友i的等级a[i]，群友i的朋友p[i-1],每个人产生问题难度k[i]. 求解每个人解决的问题数量，每个人解决的问题包括自己的问题和别人的问题。 方法一：暴力法 具体做法：先计算自己能够解决的问题，然后再计算帮别人解决的问题数量，需要注意的是牛牛无法解决的问题就不再管了。由于牛牛没有朋友，所以p数组是不包含牛牛朋友信息的，且牛牛编号默认为1，因此编号为i的群友的朋友是p[i-1].在此解法中，num为最终结果，编号为i的群友的解决问题...