牛客题解官

分类

题解(475)

/ 注册

全部文章（共488篇）

中位数

题解：考察点：思维，数形结合解法：题目中要求的是让成为新数列的中位数，则说明把新数列按照从小到大顺序排序后，要正好处于的位置，于是采用数形结合的思想来解决此问题最为简单。首先统计原数组中小于的元素个数，大于的元素个数，等于的元素个数。于是会出现有下图种情况：如左边所示，若的元素个数多于...

2020-06-05

1 825

大数乘法

题解：考察点：模拟，字符串易错点：题目中明确说明了是大数的乘法，很显然会是会爆掉int或者long long类型的，所以切不可用这2种类型来记录数据，进行简单的乘法方法一：Python 因为语言支持自动高精度，因此本题如果用来写就会显得尤为简单。需要注意的是的输入是字符串，所以需要自己转化...

2020-06-05

4 1402

二叉搜索树判定

题解：考察点：递归，二叉树，栈易错点：很多同学对于二叉搜索树的概念理解不清，二叉搜索树又被称为二叉排序树，其性质非常简单。首先二叉搜索树，可以为一颗空树，如果不是一颗空树，一定满足如下性质：若左子树非空，则左子树上所有结点均小于它的根结点；若右子树不空，则右子树上所有结点均大于它的根结点；...

2020-06-05

0 1321

连续子区间和

题解：考察点：滑动窗口，数形结合易错点：在本题中数据范围为，如果使用暴力求解是行不通的，因为如果使用复杂度为的暴力，那运算次数将达到，一般来说，在时间范围内所能抗住的运算次数在解法：滑动窗口首先，先从下图来观察出一个很重要的结论：对于一个全由正整数构成的序列来说，如果区间中所有元素...

2020-06-05

0 2244

最小栈

题解：考察点：栈易错点：本题要求、、三种操作都在复杂度内完成，也就是说都必须在常数时间内完成，其中和都是栈本来的操作，很多同学会考虑使用堆来维护最小值，但是这是不对的，因为堆每次找最小值的时间复杂度为题解：可以考虑使用两个栈来共同维护，一个栈用来进行元素常规的出栈和入栈操作，另一个栈维护...

2020-06-05

1 876

中缀表达式转后缀表达式

题解：考察点：栈，模拟易错点：由于习惯，日常生活中接触的一般为中缀表达式，导致很多同学不太明白什么是后缀表达式。后缀表达式被称为逆波兰式，是将运算符写在操作数之后的一种形式。简单来说就是如果存在E1 op E2形式的表达式，op是任意二元操作符，则E的后缀式为E1'E2' op，E1'和E2...

2020-06-05

0 945

k倍多重正整数集合

题解：题目难度：三星考察点：哈希，思维易错点：很多同学在枚举倍数的时候会漏掉当的值为的情况，事实上，这种情况需要单独讨论，的值为1时，集合最大可容纳的元素个数就是集合中元素的种数，也就是让集合中不同的元素只能出现1次。题解：这题的数据范围为，因此如果对于每个位置暴力去探寻它的倍是否存在与...

2020-06-05

0 1020

交换查询

题解：题目难度：三星考察点：哈希表易错点：因为和的范围都有，所以不能直接开成的数组，因为这样内存会爆掉，考虑到这是最大也只有，说明这是一个比较稀疏的矩阵，因此可以用来进行存储。解法：定义map<pair<int,int>,int>这样一个数据结构来存储方格中的数...

2020-06-05

0 721

两两配对差值最小

题解：题目难度：二星考察点：贪心，排序，哈希解法一：贪心+排序将一个数列中的所有数两两配对并求和，在这些和中选出最大和最小值，使得二者差距最小。很显然就是要让所有的配对的和的大小尽量相等，试想一下，如果让大的和大的配对，小的和小的配对，那么最大值和最小值的差距将会进一步拉大，因此一种可行的...

2020-06-05

0 1536

回合制游戏

题解：题目难度：二星考察点：思维，数学易错点： C++中的除法是向下去整，也就是说当和均为整数时，只取整数部分，因此当全由构成时，其结果应该为，否则不能整除时就会少计算一个解法：数学当使用时，需要一个回合来蓄力，一个回合来攻击，需要两个回合。因此，当倍的都无法超过时，才使用，否则使用一定...

2020-06-05

0 687