retyrn

分类

题解(3)

/ 注册

全部文章（共206篇）

题解 | #草原牛群集合# 数组模拟

知识点模拟思路要求不能使用额外的空间，因为原数组的大小一定不小于不等于val的数量，所以可以记录一个大小sz，每次把对应的元素放到这个位置后 sz += 1最后遍历整个数组之后，得到的sz就是题目的要求。时间复杂度遍历数组的每个位置最多2次，是线性复杂度的AC code（C++） class Sol...

2023-07-20

0 219

题解 | #牛群编号的回文顺序# 判断回文串

知识点回文串思路这道题需要判断链表的值是不是构成了回文串。遍历链表，取出这些值，然后判断是不是回文即可。时间复杂度只需要遍历链表若干次时间复杂度为 vector单次在尾部插入元素的均摊复杂度是，插入n次为总体时间复杂度为AC code （C++） /** * struct ListNode { ...

2023-07-20

0 219

题解 | #牛群的相似结构# 递归解法

知识点二叉树递归思路本题是要判断给出根节点的两个二叉树是不是完全相同。可以自顶向下递归的方法。首先确定递归出口，如果p和q均为空，或者均不为空且值相等，那么可以判断为true；否则判断为false如果在该点满足了相等，那么它们的左右儿子也应该对应相等，这样递归下去。时间复杂度访问每个结点最多一次...

2023-07-20

0 256

题解 | #重量级的一层# 层序遍历

知识点层序遍历二叉树思路题目需要我们找出val和最大的一层，可以用层序遍历来找到每一层的所有元素。实现上，因为层序遍历是边权为1的BFS，在任意时刻queue中的idx的差值最大为1；因此我们整个层序遍历的过程中idx是非递减的，所以可以逐个累加val，如果出现idx和当前的idx不同，则更新结...

2023-07-20

0 254

题解 | #牛群的身高排序# 排序应用题

知识点快速排序计数排序链表思路分析求的是整个链表的按值排序后的结果，可以把所有的值取出来进行排序后再重新连接为新的链表。在实现上可以建立虚拟头结点简化代码逻辑。排序可以选择快速排序或者计数排序时间复杂度遍历链表的复杂度为排序的复杂度为或者瓶颈在排序上AC code (C++) /** ...

2023-07-19

0 263

题解 | #牛群Z字型排列# 层序遍历

知识点层序遍历二叉树思路和上一道题非常类似。要求Z字形遍历，只需要在正常的层序遍历结果后翻转奇数层的结果。或者在加入答案的时候从后向前加入即可。时间复杂度层序遍历，遍历每个节点1次，AC code（C++） /** * struct TreeNode { * int val; * stru...

2023-07-19

0 278

题解 | #牛群分层排列# 层序遍历

知识点层序遍历二叉树思路分析把二叉树同一层的值拼接成一个字符串，然后把这些字符串返回。很经典的层序遍历题，我们只需要对二叉树跑层序遍历，把每次遍历到的val加入到对应的字符串中即可。在遍历的过程中遇到第一次出现的层的值，需要建立一个新的位置的空串来拼接，这里我是写的while循环（实际上最多只会...

2023-07-19

0 281

题解 | #翻转牛群结构# 递归解法

知识点递归二叉树思路分析给出一个二叉树根节点，要我们翻转整棵二叉树。首先，如果只有一个节点（只有根节点），我们不需要翻转。假如有子节点，需要先各自让左右子节点翻转之后，再交换左右子节点。而让子节点翻转显然是原问题的一个规模变小的子问题，可以用递归解决。显然递归出口是当二叉树到达树底端，出现空节点...

2023-07-19

0 315

题解 | #牛群的轴对称结构# 二叉树应用题

知识点二叉树思路分析要判断一棵二叉树是不是对称的。首先空树一定是满足条件的。假如这个树非空，我们从根节点自顶向下，除了根节点以外应该可以找到对称的匹配节点（只有根节点找不到对称节点）。那么我们定义一个函数check，来判断以r1和r2两个节点为根节点的子树是否是对称的。对于两个节点来说要求他们是满足...

2023-07-19

0 283

题解 | #牛群的合并# 多路归并

知识点多路归并 / 优先队列（堆）思路解析链表形式的多路归并题，由于原来的k个序列每一个都是递增的，只需要先把k个序列的头结点加入小顶堆，依次抛出堆顶元素后把堆顶元素的非空的next结点加入堆。即可实现多路归并得到有序序列。时间复杂度堆的每次插入的时间复杂度是添加n个元素的总时间复杂度是 n是全部链...

2023-07-19

2 407