君鸿

分类

题解(1)

/ 注册

全部文章（共35篇）

题解 | 小红统计区间（easy）

解题思路：滑动窗口（双指针）假设区间 [l, r] 的元素之和大于等于k，那么必然有后续区间区间 [l, r+1]、[l, r+2] ……所有这些区间的元素之和必然大于等于k。因此本体可以使用滑动窗口的思路进行解答。下面给出cpp代码。 #include <iostream> #incl...

2025-03-24

2 19

题解 | 小红的蛋糕切割

解题思路看到题目后，我们很容易得出一个结论：令所有蛋糕的美味度总和为sum。那么当s1越接近sum的一半，|s1 - s2|就越小。同时s1 + s2 = sum，故|s1 - s2| = |sum - s1 - s1|。本题的关键是求计算s1，即枚举所有正方形的美味度。将一维数组的前缀和扩展到二维...

2025-03-20

0 33

题解 | 小招喵跑步【二进制解法，不用动态规划】

描述小招喵喜欢在数轴上跑来跑去，假设它现在站在点n处，它只会3种走法，分别是：1.数轴上向前走一步，即n=n+1 2.数轴上向后走一步,即n=n-1 3.数轴上使劲跳跃到当前点的两倍，即n=2*n现在小招喵在原点，即n=0，它想去点x处，快帮小招喵算算最快的走法需要多少步？输入描述：小招喵想去的位置...

2025-03-13

1 19

题解 | 最长严格上升子数组(一)

题目描述给定一个长度为n的正整数数组nums，可以任意改变数组的其中一个元素，原来的和改变的元素范围都在[1,100000]之内，然后返回nums的最长"严格上升"子数组的长度。1.子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,...

2025-01-13

1 57

题解 | 循环右移二叉树【分层递归】

题目描述现有一棵n个节点构成的二叉树，请你将每一层的节点向右循环位移k位。某层向右位移一位(即k=1)的含义为：1.若当前节点为左孩子节点，会变成当前节点的双亲节点的右孩子节点。2.若当前节点为右儿子，会变成当前节点的双亲节点的右边相邻兄弟节点的左孩子节点。(如果当前节点的双亲节点已经是最右边的节点...

2025-01-09

1 59

题解 | 环形链表的约瑟夫问题动态规划保证看懂

题目描述编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。下一个人继续从 1 开始报数。n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？解题思路最容易想到的就是模拟法。用数组或者链表模拟每一个人，然后暴力计算。不过这种方法容易出错，而且时间复杂...

2025-01-09

1 70

题解 | 栈和排序 c++ 贪心/动态规划/set容器

题目要求给定一个由 1 - n 组成的数组和一个栈，并按照数组的顺序入栈。在不打乱入栈顺序的情况下，仅利用入栈和出栈两种操作，输出字典序最大的出栈序列解题思路：贪心要想输出的序列字典序尽可能大，必然用到贪心的思想，即每次出栈的数字尽可能大。具体思路如下：1、出栈序列的第一个数字必然为n，我们按顺序入...

2025-01-08

1 78

题解 | 判断t1树中是否有与t2树完全相同的子树

递归思路看到题目很容易想到用递归去求解。1、递归终止条件：如果root1和root2都为nullptr，则返回true。两者中一个为nullptr，一个不为nullptr，则返回false。2、如果root1和root2的val相同，则递归判断root1的左子树是否包含root2的左子树，同时roo...

2025-01-07

1 33

题解 | 【模板】区间dp

排除错误思路乍看一眼示例，可能会有这样的想法：每次找出和最小的两个相邻元素合并。这是贪心的思路，但其实是错误的。看下面的示例：{ 3，3，2，4 }。贪心法过程如下：第一次合并为{ 3，5，4 }，代价5；第二次合并为{ 8，4 }，代价8；第三次合并为{ 12 }，代价12；总代价为5 + 8 +...

2024-12-27

1 46

题解 | 【模板】多重背包二进制优化&单调队列（超详细，保证看懂）

思路多重背包每种物品可以选择多个（有上限）。将思路转化一下，多重背包可以等价变换为01背包，即把多个数量的同种物品也看成是多个不同种类的物品，那么就可以用01背包的解法来做题了。当然结果毫无疑问超时。好在题目有提示，可以采用二进制优化或者单调队列优化。说明：看这篇题解之前，请先完全理解01背包问题，...

2024-12-26

1 147