君鸿

分类

题解(1)

/ 注册

全部文章（共22篇）

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

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

2025-01-13

1 25

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

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

2025-01-09

0 40

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

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

2025-01-09

0 47

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

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

2025-01-08

0 46

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

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

2025-01-07

0 26

题解 | 【模板】区间dp

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

2024-12-27

0 30

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

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

2024-12-26

1 71

题解 | 小美的树上染色

整体思路先定义一个概念【叶子】节点：该节点为白色节点，有且只有一个相邻节点可以一起涂成红色。若某个白色节点A存在多个相邻节点，但其中只有一个相邻的白色节点，满足双方权值的乘积是完全平方数，那么节点A也是叶子节点。本题有一个关键的说明，也就是第一句话：小美拿到了一棵树。既然是树，那么就不存在环。因此根...

2024-12-25

1 39

题解 | 合法的括号序列一维数组动态规划

题目求的是合法的括号序列数量，那么必然左括号和右括号数量相等，都是字符串长度的二分之一，设为n。这里首先排除字符串长度是奇数的情况，直接输出0。我们使用动态规划，令dp[i]表示左括号比右括号多i个的数量，那么i的取值范围可以是0-n。初始化状态，左右括号都为0个，只有这一种情况，dp[0] = 1...

2024-12-24

0 53

题解 | 游游出游 c++ 二分答案&单源最短路径

知识点1：二分答案对于一个问题，它的答案属于一个区间，当这个区间很大时，暴力超时。但重要的是——这个区间是对题目中的某个量有单调性的，此时，我们就会二分答案。每一次二分会做一次判断（check函数），看是否对应的那个量达到了需要的大小，如果满足check，就放弃右半区间（或左半区间），如果不满足，就...

2024-12-24

0 44