牛客500979850号

题解

/ 注册

全部文章 / 题解（共33篇）

题解 | #链表的奇偶重排#

题意：输入一个单链表，将该单链表奇数节点放在前半部分，偶数节点放在后半部分，不改变奇数节点和偶数节点之间的相对顺序，返回新的链表。方法一：解题思路：一次遍历，奇数的节点组成一个链表，偶数的节点组成一个链表，然后将链表合并即可。 oddHead,oddTail记录奇数节点链表的头尾节点;...

2021-07-26

0 565

题解 | #分糖果问题#

题意：给定一个数组，每一个数组元素对应另外一个数组值，求另外一个数组值的总和。要求：每一个数组对应的值不小于1；任意两个相邻的数组元素，大的数组元素对应的值更大，相同无限制。方法一：贪心题目主要的难点是在于实现“任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果”，因此我们利用贪心...

2021-07-26

5 947

题解 | #环形链表的约瑟夫问题#

题意： n个人成环，编号从1到n，从1开始报数，报数到m的人离开，由下一个人继续从1开始报数，循环n-1轮之后只剩下一个人，求这个人的初始编号是多少。方法一：思路分析：因为最后只剩下一个人，所以我们可以从最后剩下的编号入手，看能不能倒推得到最开始的编号。首先画出图尝试找一下规律。如上...

2021-07-26

0 622

题解 | #随时找到数据流的中位数#

题意：设计一个结构，要求可以加入新数，并可以随时返回该结构中所有数据的中位数。方法一:暴力解法使用一个,是一个有序的元素可重复的数据结构,由平衡二叉树实现的,所以添加元素的时间复杂度为.返回中位数时由于multiset迭代器只能执行++,--的操作,不能直接自增一个量,所以时间复杂度是....

2021-07-24

0 597

题解 | #阶乘末尾0的数量#

题意：给定一个非负整数，求该数的阶乘末尾0的数量。方法一: 分析：末尾为0的数量应当取决于质因数5和2的数量，而对于阶乘的数字，显然2的数量在任何情况下都是大于5的数量的，因此直接计算质因数5的数量即可。尝试直接寻找5的数量，遍历含质因数5的数，超时间复杂度。代码如下: class ...

2021-07-22

0 588

题解 | #接雨水问题#

题意：将一个数组看成柱子高度，求柱子组成的容器最多能装的水的量。方法一：记录左侧最高柱子以及右侧最高柱子，蓄水的条件是两侧的高度取较小的值。因此取两者的较小值，减去当前值即为接雨水的值。图解如下：输入： [3,1,2,5,2,4] 红色线表示左侧最高柱子，黄色线表示右侧最高柱子，黄...

2021-07-22

1 478

题解 | #最长公共子串#

题意：求两个字符串的最长公共子串。方法一：暴力法对于str1和str2的最长公共子串，最直接的办法就是穷举他们的子串并判断是否是公共拥有的。思路：（1）穷举两字符串起始位置（2）寻找以该起始位置开始的公共子串，判断是否是最长的并更新代码如下： class Solution { pub...

2021-07-22

1 2743

题解 | #换钱的最少货币数#

题意：给定一个整数数组和目标值求用该数组的数构成目标值的最小数量。方法一：解题方法首先看起来像是贪心，但是因为给定的aim需要相等，所以可以使用动态规划，其存在的最优子结构如下：一维数组dp[i]代表的是，aim为i的情况下的最少货币数，j是数组arr的索引。最初将dp[i] (i&...

2021-07-22

0 458

题解 | #复杂链表的复制#

方法一：哈希表 1.使用一个哈希表来映射原节点和新节点 2.通过将原节点和新节点的键值对添加进去代表当前节点已经复制 3.利用next和random的指向递归遍历链表代码如下： class Solution { public: unordered_map<RandomListNode*,...

2021-07-18

3 1074

题解 | #二叉树中和为某一值的路径#

方法一：递归DFS 使用DFS递归加回溯的方法。图解过程如下：代码如下： class Solution { public: vector<vector<int>> ans; vector<int> path; vector<...

2021-07-18

5 873