题目可以转化为求每个位置上面能装多少水比如题目中给出来的例子：左右两边边界(0和5位置)上是一定不会有水的，然后1位置上能装2格水，2位置上能装1格水，3位置上不能装水，4位置上能装2格水。所以对于这一个例子来说，一共能装5格水。那么我们就再来考虑一下，每个位置上面能装多少水怎么求对于位置 来说，它上面能装的水其实取决于例：2位置上能装的水= 这里注意一下，像3位置这样本身高度大于 的 上面能装的水是0。要特判一下，直接带公式的话会减出负数这样的话这道题已经可以解了。最简单的做法就是建两个数组:   表示 位置左边的最大值  表示 位置右边的最大值  然后按照我们的步骤来求就可以了。时间复杂度...

这道题目和合并有序数组得思路是基本上一致的。就是每次选两个链表中的较小值。注意当一个链表中的元素被选空了以后，剩下都要选择另一个链表里的元素 c++  class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { // write code here if(l1==NULL)return l2; if(l2==NULL)return l1; ListNode* ans=new ListNode(-1); ListNode* now = ans; while( l1!=NULL || l2!=NULL...

题号 NC200547名称 划分树 来源 牛客练习赛57 每日一题三期汇总贴~ 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389每日一题QQ群:659028468 题解 作者：喵渺淼妙的死忠粉前言=  题解的解法的赋初值是真没看懂..看了大佬的代码顺便问了大佬数组的含义才懂的这个题..  思路 首先可以知道为根的只有当子树的异或和为才有答案.其他情况是没有答案的,所以我们可以重构一下树,将树中异或和为的点存起来.假如为,答案显然是.假如非,那么就需要跑树形...

利用二进制，记录一下每一位上1出现的次数。然后除k，如果余1的话就说明只出现了一次的数这一位是1。c++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param arr intvector * @param k int * @return int */ int foundOnceNumber(vector<int>& arr, int k) { // write code here int cnt[32]={0}; for(int i = 0 ; i < arr....

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。先考虑另一个问题，一个整型数组里除了一个数字之外，其他的数字都出现了两次，那把所有的数据异或起来，异或的结果就是那一个数字。（因为出现过两次的数字异或起来就抵消了） 对于这个题来说，如果把数字全异或起来，最后异或出来的结果是不同的那两个数的异或，然后随便从异或结果里面找一位1，因为某一位上异或结果是1的话，说明要找两个数，这一位上一个是1，一个是0。那么就可以把原来数组中，这一位是1的分成一组，这一位是0的分成一组。这样就有了两组每一组中会包含一个不同的数和一部分出现两次的数。 然后组内异或就可以了。c...

题号 NC19995名称 [HAOI2015]树上操作 来源 [HAOI2015]每日一题三期汇总贴~ 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389每日一题QQ群:659028468 题解 这个题用述链剖分的话是模板题，题解也很多，我这里给大家介绍dfs+线段树的做法。dfs序在去年4月7日的每日一题 里有介绍，11月9-13日也有过dfs序专题，没有做过的同学们可以查看学习。将树的dfs序记下来之后，对子树的修改就变成了对区间的修改，如果只有这个修改...

比赛名称: 牛客练习赛79活动具体内容 比赛结束以后-4月25日,在牛客博客写 牛客练习赛79 的题解,并发到本帖下。即可获得牛币~ 发放牛币的数量取决于题目难度，题目数量，题解质量  小建议：比赛结束之后点击每题后的进入题解->写题解，博客会被收录在每道题目之下  在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~我们将在5月5日审核，并给参与活动的同学发放10-100牛币  PS：如果题解写的非常好， 将会增加其获得的牛币如果题解写的非常水， 将会减少获得其获得的牛币如果题解有抄袭行为，将会取消其获得牛币的资格 如何开通牛客博客: https://www.nowcod...

这道题目其实和输出链表的倒数第n个结点是基本上一致的。https://blog.nowcoder.net/n/4e57664df6974486bc352aa5a1e4613c和上一道题一样，定义快慢指针，快指针先走n步，然后快慢指针一起走，快指针走到空的时候慢指针正好在倒数第n个结点上。区别的地方只是在于要删除某个结点的话，我们需要知道它的前一个结点是什么。如果要删除的结点是链表头结点的话（这个时候没有前一个结点）。这种情况下我们进行一下特判就可以了。c++ class Solution { public: ListNode* removeNthFromEnd(ListNode* head, ...

解法：  定义两个指针，fast，slow指向链表的头结点。 fast指针先走k步，走的时候要注意判断一下链表的长度是否大于等于k。如果链表的长度也等于k的话，快指针走k步正好会走到空。如果在走第k步之前链表就指向空的话，说明链表长度小于k，直接返回空。 然后fast指针和slow指针一起走。当fast指针指向空的时候，slow指针指向的就是倒数第k个节点。  例：k=2fast先走两步fast指向空的时候，slow指的就是倒数第二个结点了c++ class Solution { public: ListNode* FindKthToTail(ListNode* pHead, int k) {...

题号 NC24444名称 Landscaping 来源 USACO 每日一题三期汇总贴~ 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389每日一题QQ群:659028468 题解 作者：jxnu19-软技1班-刘晟 中文题意 现在你一共有个花坛，每个花坛有一定量的起始泥土，现在你要把每个花坛泥土数量变成。 你有三种操作分别是：  花费直接给这个花坛填入一单位泥土， 花费直接给这个花坛移除一单位泥土， 如果你想把第个花坛的泥土移动到第个花坛，那么花费就是， ...

题号 NC20278名称 [SCOI2010]幸运数字 来源 [SCOI2010]每日一题三期汇总贴~ 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389每日一题QQ群:659028468 题解 考虑容斥——先处理出所有的含有6/8的数字，然后用容斥计算他们的倍数的个数。含有6/8的数字虽然多，但是几个数共同的倍数就是他们lcm的倍数，在求lcm的过程中很快就会超出询问的范围，这个时候剪枝剪掉就好（所以容斥的时候幸运数字从大到小枚举，这样会更早的剪枝）。另外...

比赛名称: 牛客小白月赛32活动具体内容 比赛结束以后-4月19日,在牛客博客写 牛客小白月赛32 的题解,并发到本帖下。即可获得牛币~ 发放牛币的数量取决于题目难度，题目数量，题解质量  小建议：比赛结束之后点击每题后的进入题解->写题解，博客会被收录在每道题目之下  在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~我们将在4月19日审核，并给参与活动的同学发放10-100牛币  PS：如果题解写的非常好， 将会增加其获得的牛币如果题解写的非常水， 将会减少获得其获得的牛币如果题解有抄袭行为，将会取消其获得牛币的资格 如何开通牛客博客: https://www.now...

做这道题目之前可以先看一下 NC78 反转链表 https://blog.nowcoder.net/n/31e6abf3dd5d4970a03f7a483ca8e0ab先举一个例子：原链表：m = 2 ，n = 4反转后  观察可以发现我们需要进行的步骤有以下三条：  从 𝑚+1 到 𝑛 的这些节点将 𝑛𝑒𝑥𝑡 指针指向前一个节点。 𝑚 节点的 𝑛𝑒𝑥𝑡 指针指向 𝑛 节点的 𝑛𝑒𝑥𝑡 𝑚−1 节点的 𝑛𝑒𝑥𝑡 指针指向 𝑛 节点  然后我们来考虑两种特殊情况：第一种：如果m和n相等，即：指定的区间只有一个节点，这个时候按这个步骤进行的话，是没有问题...

题号 NC19987名称 [HAOI2012]ROAD 来源 [HAOI2012]每日一题三期汇总贴~ 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389每日一题QQ群:659028468 题解 首先，如果起点确定，那么和最短路完全没有关系的那些边是没有用处的，即在枚举起点的前提下我们只需要在最短路图上求解。所以第一步枚举起点，然后建最短路图（当一条边对应的两个点u，v满足时，这条边保留，其他边忽略）。接下来在这个最短路图上，求经过了每一条边的路径有多少——...