题意整理 给定一颗有n个节点的树，每个节点的值初始为0或1。 求有多少条从根节点到叶子节点的路径（要求路径上节点值得累加和小于等于2）。 方法一（DFS） 1.解题思路 首先建立邻接表，用于访问某个节点的所有子节点。 从根节点开始递归，并且初始化一个num为2，每到一个节点，num减去对应节点值。如果num小于0，直接终止掉这条路径。否则，遍历当前节点得所有子节点，继续递归，同时判断是否是叶子节点，如果是叶子节点，路径数加一。 2.代码实现 import java.util.*; /* * public class Point { * int x; * int y; ...

题意整理 给定一颗有n个节点的树，每个节点权值初始为0。 现在有一个查询集合，集合中每一项提供两个参数r和v，每次查询将r节点及其子节点的权值增加v。 返回最终每个节点的权值。 方法一（DFS） 1.解题思路 首先建立邻接表，用于访问某个节点的所有子节点。 初始化查询中当前根节点的权值。 按照建立的邻接表，递归地遍历当前根节点下每个子节点，如果没有访问过，则加上对应权值。按照这个规则访问完所有的节点。 由于测试数据较大，运行报栈深度溢出（StackOverflowError）。可以通过自定义栈深度，防溢出。 2.代码实现 import java.util.*; /* * publi...

题意整理 给定n件带水的衣服，用一个数组记录每个衣服的水滴数。 现在要将所有衣服烘干，有两种方式，一种是自然烘干，每件衣服减少一滴水；另一种是机器烘干，其中一件衣服减少k滴水，剩下的衣服减少一滴水（自然烘干）。 求最少花多长时间将所有衣服烘干。 方法一（枚举） 1.解题思路 首先确定花费时间的左右边界，n大于等于1，说明至少有一件衣服待烘干，至少花费1分钟，左边界为1。如果所有衣服均自然烘干，花费时间最长，此时水滴最多的衣服即是总花费时间，对应右边界。 然后判断某个时间time内，是否能烘干所有衣服，如果a数组内衣服水滴数小于等于time，说明能自然烘干，所以只需考虑大于time的情况。...

题意整理 给定一个集合包含1到n共n个数，从中选若干数出来组成新的集合。 规定一个限制数组，限制数组里的每一个数对不能同时出现在新集合中。 求这样的新集合有多少个。 方法一（二进制枚举） 1.解题思路 定义1个mask，表示1到n有没有出现过，若mask最低位为1，则表示1出现过，次低位为1，则表示2出现过。比如mask=101mask=101mask=101时，表示出现了1和3，对应集合[1,3][1,3][1,3]。 根据二进制位可以很容易判断某个数有没有出现过，从而枚举二进制位的时候，根据限制数组，看里面的数对是否同时出现过，如果同时出现，则当前集合不合法。 如果没有同时出现，则计...

题意整理 给定一个长度为n+1的序列，包含1到n之间的数。 有一个数重复了，找出重复的数。 方法一（数学） 1.解题思路 先计算出序列中所有数字的和。 然后计算1到n所有数字的和。 由于序列中有一个重复了，所以序列和中多算了一次，从序列和中减去1到n所有数的和，即时那个重复的数字。 动图展示： 2.代码实现 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int * ...

题意整理 给定一颗二叉树的先序遍历序列和后序遍历序列。 求中序遍历序列（如果某个节点只有一个子节点，则必是左子节点）。 方法一（递归+重建二叉树） 1.解题思路 在每次递归中，可以确定当前根节点在先序遍历开头处，后续遍历结尾处。在后续遍历中找到当前节点的第一个左子节点，则后续遍历中，该节点之前的一定是左子树(包括该节点)，该节点之后的一定是右子树（不包括当前根节点）。前序遍历怎么划分左右子树，可以参考后续遍历，因为一旦确认后续遍历的左右子树，对应左右子树节点个数也就确定了，而前序遍历划分的开始以及结束位置是知道的，根据开始处加上对应区间长度减一，即可得到左子树边界，同理确定右子树边界。 ...

题意整理 给定一个序列，序列中每个下标对应一个值，选定一个下标i，则从i到的区间所有数都做一个标记。 最后的目标是将所有的数都打上标记，问所有可能的方案中期望步数是多少。 方法一（排列+费马小定理+快幂法） 1.解题思路 对于任意均满足条件：若，则这两个条件一定满足其中1个。所以，如果，要么，此时不包含j；要么，此时一定包含。可以推断，这一定是一个树形结构。 确定树形结构之后，再考虑一个点被标记的概率，为了让一个点被标记，它之前一定没被标记，从而它一定要在其前置节点之前被标记上，只要找到其前置节点的个数（不包括它本身，记为k-1），则此节点可以放在所有前置节点之间的k个空中，由于放在第...

题意整理 给定一个数组。 求所有的区间中，满足区间最大值大于等于最小值对应的区间个数。 方法一（暴力） 1.解题思路 先确定左端点，然后遍历所有的右端点。 每次记录最大值和最小值，只要最大值大于等于最小值，则结束内循环。将满足条件的区间数加入到结果变量。 直到确定完所有的左端点。 动图展示： 2.代码实现 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param array int整型一维数组...

题意整理 有一段长度为n的消息，要将消息分成若干组，每组2个消息。 第一个消息长度必须是4，第二个消息长度不能为0。 求有多少种分割方法。 方法一（递归） 1.解题思路 递归终止条件：如果剩下的长度为0，说明正好完成分割，返回一种方案。 递归如何推进：首先减去4，表示第一个消息的长度，然后第二个消息的长度可选1到rest之间的任意长度，统计所有的情况，作为当前层的方案数。 每一层返回什么：返回当前层的方案数。 当数据比较大时，运行超时，如果进一步加大数据，会造成栈内存溢出（StackOverflowError）。 2.代码实现 import java.util.*; public c...

题意整理 给定1-9共9个数字，a数组记录了每个数字的价格。 牛牛手上有n元钱，为了凑出最大的数字带回家，问牛牛应该怎么买，并返回最大的数字。 方法一（贪心） 1.解题思路 首先计算最便宜的数字是多少。 然后根据最便宜的数字，得到最多买多少个数字，以及买了之后，剩余多少钱。因为要凑出最大的数字，所以数字个数应尽可能多。 先假设买的全是最便宜的数字，如果某个数字比最便宜数字大，并且可以用剩余的钱来补，则将当前数字替换为这个较大的数字。 动图展示： 2.代码实现 import java.util.*; public class Solution { /** * 代码中...

题意整理 给定完全二叉树的层序遍历序列。 还原二叉树，并计算树中所有边的节点间异或值的累加和。 方法一（重建二叉树） 1.解题思路 首先根据层序遍历序列，重建二叉树，找到根节点。 利用重建的二叉树，遍历所有边，将对应异或和累加到结果变量。 返回结果变量res。 2.代码实现 import java.util.*; //树结构 class TreeNode{ TreeNode left=null; TreeNode right=null; int val; TreeNode(int val){ this.val=val; } } ...

题意整理 在所有组合数中，找到第k小的，并返回其值。 方法一（小顶堆） 1.解题思路 枚举从k个数中取若干个数的所有组合数，然后依次添加到堆，如果已经在堆，则不再添加。然后从堆里弹出k-1个数，此时的堆顶元素一定是第k小的组合数，直接返回。由于数据量大，运行超时。 动图展示： 2.代码实现 import java.util.*; import java.math.BigInteger; public class Solution { /** * * @param k int整型 * @return int整型 */ //大数常...

题意整理 给定n个盘子以及a、b两种蛋糕，蛋糕各有一定数量。 要求每个盘子都有蛋糕，且只有一种蛋糕。 求蛋糕数最少的盘子最多能分多少蛋糕。 方法一（枚举） 1.解题思路 由于a、b两种蛋糕的盘子数之和固定为n，只要枚举出a蛋糕的盘子数，b蛋糕盘子数也确定了。 然后计算最少a蛋糕数量的最大值，以及最少b蛋糕数量的最大值，取较小的，用计算出的值跟新结果，找到所有满足条件的最大的结果。 2.代码实现 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 ...

题意整理 给定的矩阵以及个点。 现在要将这个点放在矩阵里，并且保证第一行，第一列，最后一行，最后一列都有点。 求总共有多少种方案。 方法一（动态规划） 1.解题思路 初始化一个组合数组，表示在i个格子里取j个点的组合数，即。 根据组合递归公式，可得：。 计算出所有的组合数之后，首先取对应的所有组合数，然后排除第1列或最后一列没点的情况以及第1行或最后一行没点的情况，加上多排除的1行1列没点的情况，加上多排除的第1列和最后一列没点的情况，加上多排除的第1行和最后一行没点的情况，继续排除2行1列没点的情况，继续排除1行2列没点的情况，加上多排除的2行2列没点的情况。 动图展示： 2.代码...