wywzxxz

题解

/ 注册

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

题解 | #链表中环的入口节点#

>>>>>>>>>>>>>>>我使用了同余!!!点此了解解题思路及数学原理!<<<<<<<<<<<<<<<<...

2021-04-25

0 600

题解 | #最长回文子串#

Manacher算法，O(n)。思路写在注释里了。可能有有同学好奇为啥是O(N)的。太麻烦没自己证明，不过可以粗略体会下：for循环毫无疑问是O(n)的，问题在于“统计未知部分”这里的while循环不好估计。已知是统计未知部分时起始位置由，得，则，而更新时i-ans[i]<=best-ans[...

2021-04-25

0 498

牛客网真题-71-选区间

时间复杂度O(nlogn) 我觉得大家的方案都有点太麻烦了……观察目标函数：区间中的最小数*区间所有数的和第一反应就是按照值从小到大处理点，这样的话区间中的最小数*就已知了，我们只用考虑区间就行。那么，区间有多大呢？其实题目中又一个很强的约束区间内的所有数字都在[0, 100]的范围内; 因...

2021-01-23

1 637

题解：字节跳动-编程题2

同志们想复杂了，用的方法既满又难写，实际上解法还是很简单的。注意这道题有一个限制：数字都在[0, 100]的范围内，这其实可以拆解为两点：1.值非负，这决定了我们的算法2.值小与100，这省了我们很多事，对笔试非常友好。注意看目标函数：区间中的最小数 * 区间所有数一个非常自然的想法是我们从小到大...

2021-01-23

0 974

牛客网真题-72-最大点集

有同学用优先级队列/最大堆做，其实不用那么麻烦。将点按照x坐标从大到小排序并遍历，那么实际上就可以无视X坐标，只关心Y坐标就行。换句话说：只需要知道之前遍历的点的最大Y值是多少即可 n=int(input()) points=[ [int(x) for x in input().split()] ...

2021-01-23

2 694

极简解法

我亲爱的小同学们，这其实是个脑筋急转弯…… - -|||一个位置的液柱高度只取决于三个因素：左边最高多高、右边最高多高、底多高。所以，O(n)扫描记录一下前两个参数，然后直接算就行…… int n=arr.size(); auto lm=new int[n+10];l...

2020-12-31

1 1644

题解：在行列都排好序的矩阵中找指定的数

O(n),其他解法未免也太啰嗦了。 j=M-1; for (int i=0;i<n;++i) { while (j>0 && val[i][j]>K) --j; if (val[i][j]==K) {cout<...

C++

2020-11-27

6 1345