题意理解 m个冰淇淋同时开始制作，每个都有各自的制作所需时间，只有在制作完成后才可以将其运走，并且汽车要返回。每次可以运不超过n个冰淇淋。要求总的运输时间最少，且运输次数也最少。注意，最后一次运输不计算回程的时间。 方法一 贪心 由于必须要等待冰淇淋制作完成才可以运输，所以先对制作时间进行排序，先制作先运输。 初始想法，每当有n个冰淇淋制作完成，我们进行一次运输。但是存在一个问题，如果等待倒数第二批中第n个冰淇淋耗费太长时间，会导致返回后剩下的冰淇淋（小于n个）已经做完很久了，这使得总的运输时间拉长。 举个例子：c=[10,20,30]，n=2，t=10。按照该思路，先送0、1号冰淇淋，再送2...

题意理解 一组数，找出一个合适的排序，是相邻两个数之间差的最大值要最小。注意首位两个数也是相邻的。 方法一 暴力求解。找出所有可能的排序，计算对应差值的最大值，在所有的最大值中输出最小的。 具体代码如下： class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * ​返回按照这些花排成一个圆的序列中最小的“丑陋度” * @param n int整型 花的数量 * @param array int整型vector 花的高度数组 * @return int整型 */ int arrangeFlowers(int n...

题意理解 当第i个字母小于第i+k个字母时，可以交换两个字母顺序，记作一次交换。我们要求给定的字符串中，最多可以进行几次交换，直到不存在符合交换条件的两个对应字母。 方法一 可以看到，第i、i+k、i+2k、i+3k等等这些字母之间进行交换，和其它字母无关，所以可以把这样的字母序列提取出来，依次计算每一个序列里面的最多交换次数再相加。对于一个序列，我们使用逆序对（小的字母在前视为逆序）的个数作为该序列的最多交换次数。 正确性证明： 1、若一个序列存在逆序对，则必存在相邻两个字母是逆序的。 2、交换这两个相邻的逆序字母，只会减少一个逆序对。 有了以上两点就可以保证序列逆序对的个数是该序列的最多交...

题意理解 每个人的活动范围相当于一个闭区间，开始时有一个人被感染。由于闭区间之间可能存在交集，所以当一个闭区间被感染时，与它相交的闭区间也会被感染，这个过程是瞬间完成的。所以，假设被感染的闭区间集合为S，还未被感染的闭区间集合为E，找出E中与S相交的闭区间，它们被感染并加入到S，更新E；不断迭代该过程，直到S,E都不再更新。 方法一 使用并查集。并查集主要由两部分构成，find函数和Union函数。 我们把存在相交的闭区间视为同一类，若A和B相交，B和C相交，无论A和C是否相交，均视为同一类（即相交）。find函数用于寻找某个闭区间所属类的根的索引（该类中任意区间都可以视为根，一般用产生一个新...

题意理解 n个星球可以看作n个结点，之间有零到多条无向边，牛牛和牛妹占领的星球可以看作两个点集。题目要求，从点集A中的某点到点集B中某点的所需要的最短距离。 方法一 最短路径算法有多种。本题中没有给定起点和终点，而是一个起点的集合A和终点的集合B，所以使用Floryd算法，求得所有结点之间的最短路径，再遍历起点在A终点在B的情况，找出其中的最短路径长度。 具体代码如下： class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param serialP intvector 牛牛占领的p个星球的编号 *...

题意理解 对于一维数轴上的一个数，下一步可以加3、7、11，也可以减3、7、11，经过一系列的加减操作后得到目标数值arr[i]，我们要使做的加减操作的次数尽可能少。 方法一 用time[i]记录得到i需要最少的加减操作的次数。我们要得到数值i，可以先得到数值j，再加上i-j就可以了。此时，得到i的操作数time[i]，就等于time[j]加上time[i-j]。示意图如下：  对于j的范围，考虑到对称性，只要在1~i/2之间即可。在求time[i]的时候，要求time[1]~time[i-1]已知，这是一个动态规划的过程。 再看题目中的数值要求范围，当目标数值i较大时，time数组会过大并报...

题目理解： 从两个下标区间中各自读取一个数，判断这个两个数的最大公因数是否为其中较小的数，最后输出满足条件的数对的个数。 方法一 暴力搜索第一重循环：遍历q个询问。第二重循环：遍历询问i中，l1到r1之前的数字。第三重循环：遍历询问i中，第二重循环里的每一个p[j]都与l2到r2之间的所有数字p[h]进行匹配判断。判断是否有。不失一般性，设较小的数为a，较大的数为b，a也可以等于b。如果等式成立，说明a是两者的公因数，从而b可以被a整除；反过来，如果b可以被a整除，那么a是两者的公因数，并且公因数不会大于其中任意一个数字，所以a是两者的最大公因数。 遍历结果的示意图如下：  具体代码如下： c...

题目理解 n个城市对应n个结点，城市之间的路径对应结点之间的边。我们删除某一条边。假设有m条两点之间的路径经过该边，该边的权值为w[i]，输出为m*w[i]的最大值。 方法一 对于题意的理解，我们删除一条边，其权重为w[i]；如果在原来的图中，有m条路径包含了该边，则最后输出代价为w[i]*m。那m是多少呢？ n个城市，n-1条边，意味着这是一个树的结构，图中不存在回路。因此，删除一条边会将树分为两个不连通的子树a,b，即可以把删除的边看作原来a,b之间的桥梁。a中结点到b中结点的路径必然包含了桥梁。所以说，m = a的结点个数*b的结点个数。 示意图如下（以删除3-6之间的边为例，子树a包含...

题意理解 n个房子对应于n个结点，街道就对应于结点之间的边，构成一张连通图。找到这张图中哪两点之间边上的数值之和最大。 方法一 深度优先搜索使用二维数组path存储路径的信息，对于每一个点，要记录它和其它结点所有路径的长度。然后以每一个点分别作为起点，都进行一次深度优先搜索，每走一步都更新一次最长路径ans，注意这里的ans不需要退回。 示意图如下，最终答案对应的路径是1-5-2-3这一条路径的长度：  具体代码如下： class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 返回最终结果 * @param ...

题意理解 给定一个字符串，由()?组成，?可以代替为(或者)，判断能否在替换后，使得字符串变成是括号合法的，若可以则随意输出一种合法的结果。括号合法的要求：1.空字符为合法括号序列2.(+合法括号序列+) 为合法括号序列3.()+合法括号序列为合法括号序列 方法一 首先，对于基础的括号匹配问题，我们通过以下方法判断其可以匹配：对于所有i，从1到字符串长度n，考虑字符串前i个字符，如果左括号个数大于等于右括号个数，则前i个字符匹配成功。这里用到一个计数器all，遇到左括号all++，遇到右括号all--，若某时刻all小于0则匹配失败了。最后i==n时，如果左括号个数等于右括号，即all等于0，...

题意理解 5张扑克牌对应5个数，包含0~13。其中0可以表示1~13之间的任意数字。判断这5个数字是否连成1~13之内的顺子。 方法一 对于5个数字是否能连成顺子，主要观察两方面：（1）如果有重复的数字（0除外），则必然不可能连成顺子。（2）如果最大值和最小值（0除外）的差大于等于5，则必然不可能连成顺子。（3个数填不满中间的间隔） 对于算法的正确性：在满足条件1的情况下，假设存在i(i<5)个0，对于剩下5-i个数，如果满足条件2，即它们的极差为(4-i)~4。当极差为4的时候，把i个0填在中间；当极差变小的时候，i个0一部分填在中间，一部分填在max或者min的外侧即可。（因为数组长...

题意理解 判断一棵树是否为平衡二叉树。平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 方法一 使用一个map来记录每个结点的高度height，每个结点的高度等于max(height左，height右)+1。示意图如下：  然后对二叉树进行先序遍历，比较每个结点的左子树和右子树的高度就可以判断该点是否满足平衡条件，再向左子树和右子树递归。 具体代码如下： class Solution { public: map<TreeNode*, int> height; //计算每...

题意理解 找出数组中和等于目标值的两个数，输出它们的下标，注意先输出小的下标。输出结果存在且唯一。 方法一 题目要求两个数值对应的index，首先想到双指针的方法。 先对数组进行排序，注意在排序时，原先的index也要跟着数值一起交换位置，否则最后输出新的index是错误的。这就需要我们自己定义一个结构体，里面存放数值和对应的旧index。 两个指针（非数据结构的指针）i,j分别指向开头和结尾，如果number[i]+number[j]==target即得到答案。若和小于target，说明加数小了，i就右移；若和大于target，说明加数大了，j左移。每一个数只要扫一遍就可以了。示意图如下： ...

题意理解 判断该二叉树是否为搜索二叉树和完全二叉树。搜索二叉树：父结点大于左子树中所有结点，并且小于右子树中所有结点。完全二叉树：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。 方法一 二叉搜索树中，每一个结点都大于其左子树中的所有结点，且都小于其右子树中的所有结点。使用中序遍历取出树中所有结点的值val，放入数组中，应该得到一个严格单调递增的数组，即a[i]<a[i+1]。 示意图如下：  对于判断是否是完全二叉树，可以考虑进行层次遍历，即当我...