题目描述编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。下一个人继续从 1 开始报数。n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？解题思路最容易想到的就是模拟法。用数组或者链表模拟每一个人，然后暴力计算。不过这种方法容易出错，而且时间复杂度也比较高。注意到题目中每一轮游戏结束后，下一轮游戏将从出局的后一个人开始报数。如果把这个人的编号移动到第一个人，那么不就相当于n - 1个人从头开始玩游戏吗？这里面显然存在某种联系。找到这种联系，就可以使用动态规划。动态规划令dp[n] 表示n个人玩游戏（编号0到n-1）最后剩下的人，我们考虑dp...

题目要求给定一个由 1 - n 组成的数组和一个栈，并按照数组的顺序入栈。在不打乱入栈顺序的情况下，仅利用入栈和出栈两种操作，输出字典序最大的出栈序列解题思路：贪心要想输出的序列字典序尽可能大，必然用到贪心的思想，即每次出栈的数字尽可能大。具体思路如下：1、出栈序列的第一个数字必然为n，我们按顺序入栈，直到n入栈时，将n出栈。2、接下来我们要从尚未入栈的数字中找到其最大值maxi。循环比较maxi和栈顶元素的大小，如果栈顶元素更大，那么该元素出栈，直到栈顶元素小于maxi为止。3、继续按顺序入栈，直到maxi入栈时，将maxi出栈。4、重复步骤2和3，直到数组中所有数字都入栈为止。最后将栈中所...

递归思路看到题目很容易想到用递归去求解。1、递归终止条件：如果root1和root2都为nullptr，则返回true。两者中一个为nullptr，一个不为nullptr，则返回false。2、如果root1和root2的val相同，则递归判断root1的左子树是否包含root2的左子树，同时root1的右子树是否包含root2的右子树。3、如果root1和root2的val不同，则递归判断root1的左子树是否包含root2，或者root1的右子树是否包含root2。下面给出代码。 /** * struct TreeNode { * int val; * struct TreeNode *l...

思路根据完全二叉树的特性，其左右子树至少有一棵是满二叉树。情况1：若左右子树高度相同，则左子树必然为满二叉树；情况2：若左子树高度大，那么右子树必然是满二叉树；不存在其他情况。满二叉树的结点数，可以用其高度很容易算出，num = 2^h - 1。递归设左子树高度为lh，右子树高度为rh。那么——情况1：若左右子树高度相同，则左子树必然为满二叉树。总的结点数 = 根节点 + 满二叉树节点个数（左子树） + 完全二叉树节点个数（递归右子树）注意：此时右孩子的左子树高度为rh - 1，不用重复数一遍。情况2：若左右子树高度相同，则左子树必然为满二叉树。总的结点数 = 根节点 + 满二叉树节点个数（右...

排除错误思路乍看一眼示例，可能会有这样的想法：每次找出和最小的两个相邻元素合并。这是贪心的思路，但其实是错误的。看下面的示例：{ 3，3，2，4 }。贪心法过程如下：第一次合并为{ 3，5，4 }，代价5；第二次合并为{ 8，4 }，代价8；第三次合并为{ 12 }，代价12；总代价为5 + 8 + 12 = 25。正确的合并过程如下：第一次合并为{ 6，2，4 }，代价6；第二次合并为{ 6，6 }，代价6；第三次合并为{ 12 }，代价12；总代价为6 + 6 + 12 = 24。此题正确的思路是动态规划，标题区间dp已经给出了明确的提示。动态规划我们使用分治的思想，一个大区间可以由两个小...

思路多重背包每种物品可以选择多个（有上限）。将思路转化一下，多重背包可以等价变换为01背包，即把多个数量的同种物品也看成是多个不同种类的物品，那么就可以用01背包的解法来做题了。当然结果毫无疑问超时。好在题目有提示，可以采用二进制优化或者单调队列优化。说明：看这篇题解之前，请先完全理解01背包问题，其中的dp数组用的是一维数组。如果你还在用二维数组，那么请先理解了一维数组再来看。二进制优化假设某种物品的数量为1000件，拆分成1000种不同类型的物品当然也可以计算，但是时间过久。一种好的办法是将之拆分成10个种类，每个种类分别包含1、2、4、8、16、32、64、128、256、489件。为什...

整体思路先定义一个概念【叶子】节点：该节点为白色节点，有且只有一个相邻节点可以一起涂成红色。若某个白色节点A存在多个相邻节点，但其中只有一个相邻的白色节点，满足双方权值的乘积是完全平方数，那么节点A也是叶子节点。本题有一个关键的说明，也就是第一句话：小美拿到了一棵树。既然是树，那么就不存在环。因此根据贪心的思想，我们每次只取【叶子】节点和【叶子】节点相邻的节点涂成红色，然后再把红色部分剪枝。这样若干次操作之后，非【叶子】节点要么被转化成新的【叶子】节点，要么直接和【叶子】节点凑对被剪枝了。最后当【叶子】节点全部消失，那么全部涂色也就完成了，我们得到答案。这里我使用了c++的set容器。该容器底...

题目求的是合法的括号序列数量，那么必然左括号和右括号数量相等，都是字符串长度的二分之一，设为n。这里首先排除字符串长度是奇数的情况，直接输出0。我们使用动态规划，令dp[i]表示左括号比右括号多i个的数量，那么i的取值范围可以是0-n。初始化状态，左右括号都为0个，只有这一种情况，dp[0] = 1。接下来遍历字符串。分别对字符 ( ) ? 进行处理，得到状态转移方程。当字符为 ( 时，dp[i + 1] = dp[i]。i的取值范围是 i < n。当字符为 ) 时，dp[i - 1] = dp[i]。i的取值范围是 i > 0。当字符为 ? 时，dp[i] = dp[i - 1]...

知识点1：二分答案对于一个问题，它的答案属于一个区间，当这个区间很大时，暴力超时。但重要的是——这个区间是对题目中的某个量有单调性的，此时，我们就会二分答案。每一次二分会做一次判断（check函数），看是否对应的那个量达到了需要的大小，如果满足check，就放弃右半区间（或左半区间），如果不满足，就放弃左半区间（或右半区间）。一直往复，直至到最终的答案。题目求的是车重量的最大值，显然符合单调性。因为随着重量的增加，可选的路径在变少，就有可能无法到达终点。反之，若车重为w时若可以到达终点，那么车重小于w时也必然可以到达终点，因为可选的路径增加了。知识点2：单源最短路径给定一个带权有向图 G=(V...

最小生成树一般有两种方法，即Kruskal（克鲁斯卡尔）算法和Prim（普里姆）算法。前者以边来生成，后者以顶点来生成。这里介绍Kruskal算法。具体思路是，将所有m条边按照权重w从小到大排序，然后遍历其中的每一条边，判断该边的两个顶点是否联通，若没有联通，则选取该边，并将两个顶点联通。这里一个比较关键步骤就是判断两个点是否联通，可以使用并查集。若两个点联通，则这两个点在同一个集合中，否则不在一个集合中。下面是代码。 #include <algorithm> #include <iostream> #include <vector> using names...

step1：创建一个数组，表示从起点s到每个顶点的最短路径。初始化值为-1。step2：创建一个队列，起点s的最短路径设为0，将起点s加入队列中。step3：从队列首部取出一个顶点u，依次判断该顶点连接到的每一个顶点v。若v的最短路径为-1，则更新为u的最短路径+1，并将v加入到队列末尾。step4：重复step3，直至队列为空。因为一个顶点u可能连接到多个顶点v，因此这里用到哈希表，哈希表的key为顶点编号，value为v的数组。下面是代码。 #include <iostream> #include <queue> #include <unordered_map...

由题意可知，饭局的隔阂值为隔阂最大的那一对朋友的隔阂，也就是所有参与饭局的朋友中财富最大的减去财富最小的。根据贪心的思想，如果邀请了其中两名成员和，那么想要让愉悦值最大，应当尽可能多的邀请财富值在两者之间的其他朋友。将所有成员按照财富从小到大排序，就可以将题目转化为求连续区间的愉悦值之和大于等于k的情况下，首尾元素财富值之差的最小值。我们很容易想到用前缀和与双指针的思想来解题。我们维护一个愉悦值的前缀和数组sum，那么连续区间[l, r]的愉悦值之和为sum[r] - sum[l-1]。双指针的处理就很简单了，具体处理方法直接看代码吧。统计下时间复杂度：排序O(nlogn)，计算前缀和数组O(...

设加油时间为 t，那么总用时 = t + y / (v0 + xt) = t + (y / x) / (v0 / x + t)令 c = y / x，a = v0 / x，那么原式 = t + c / ( t + a) = (t + a) + c / (t + a) - a <= 2 * sqrt(c) - a。根据基本不等式，我们知道两个数的算术平均值小于等于两个数的几何平均值，当且仅当两者相等时，才取等号。注意这里有一个隐含条件，t >=0。那么a的平方大于c时，取不到这个最小值。不过没关系，此时原式随着t的增加单调递增，因此t = 0时就是最小值。 #include <...

函数 f(x) = | kx + a | + b，当x = -a/k 时最小，函数图像是一个V字形，有最小值。看到这个形状，我们很容易想到用三分法寻找最小值的位置。然而题目中的F(x) 是多个f(x) 的和，如果要用三分法，就必须保证F(x)在最小值左边单调递减（或平），在右边单调递增（或平），否则可能找到别的谷点（函数图形可以参考W的形状）。这个证明我暂时没想到，但看到题目的标题是整数域三分，那么不管三七二十一先用再说。三分法的具体做法是，计算区间[l, r]之间的两个三等分点mid1, mid2。比较 F(mid1) 和 F(mid2) 的大小，然后缩小范围（每次缩小三分之一），让其中较小...