大家好,我是吴师兄。
今天继续给大家分享一个 LeetCode 评论区的骚操作,直接看截图!
这个骚操作的评论来源于 LeetCode 上剑指 Offer 51. 数组中的逆序对。
首先给没有见过这道题目的小伙伴补充一下前置知识, 这道题目讲的是,在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。
输入一个数组,求出这个数组中的逆序对的总数。
那比如给定一个数组 [ 7 , 5 , 6 ,4 ]
,在这个数组中 7 比 5 更大,同时在 5 的前面,那么 【 7 , 5 】就构成了一个逆序对,而在整个数组中,总共操作 5 组逆序对。
- 【 7 , 5 】
- 【 7 , 6 】
- 【 7 , 4 】
- 【 5 , 4 】
- 【 6 , 4 】
理解题目意思之后,最直观的解法就是使用暴力统计法,即遍历数组的所有数字对并统计逆序对数量。
暴力解法的时间复杂度为 O(N^2),由于题目给出的数组长度可以高达 50000,因此使用这种暴力解法是行不通的。
实际上,这道题目考察的还是我们基础知识的掌握程度。
具体的解法我在之前的文章中详细说明了,可以点击查看。
这篇文章主要来看看这个骚操作。
res=iter([5, 0, 4, 5, 0, 0, 10, 0, 3, 1, 0, 0, 0, 6, 69, 238952, 245944, 239528, 238071, 243863, 245357, 232477, 248174, 239969, 236302, 243878, 236118, 246432, 244159, 235994, 245549, 238683, 242737, 229317, 251315, 624875572, 624912680, 623674613, 624368583, 0, 1249975000, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 2, 1, 2, 2, 2, 1, 3, 2, 1, 0, 4, 5, 5, 1, 0, 4, 0, 4, 0, 3, 7, 8, 9, 8, 3, 2, 1, 3, 5, 7, 5, 5, 7, 9, 9, 8, 7, 3, 5, 5, 16, 14, 5, 11, 8, 9, 12, 13, 4, 7, 7, 7, 16, 14, 9, 6, 17, 9, 5, 16, 23, 17, 13, 22, 10, 17, 16, 17, 23, 18, 24, 21, 18, 24, 27, 30, 18, 17, 24, 625017023])
class Solution:
def reversePairs(self, nums: List[int]) -> int:
return next(res)
二话不说,先提交看看。
虽然没有双百,但也是很靠前的,关键是,这个代码咋就通过了呢?
答案和上一篇的思路一样,面向测试用例编程。
虽然不知道他是怎么样弄出这些测试用例来,但看他的评论时间是 2020 年 4 月 24 号,已经快过去两年,这代码依旧跑的通,说明现在 LeetCode 还是没有更新测试用例。
这里并非鼓励大家在刷题是投机取巧,只不过想分享这种骚操作出来,在苦闷的刷题的间隙博君一笑。