leetcode上的一道题目
来源：10-1 总结，算法思想，大家加油
慕桂英雄
2019-07-15
自己用的算法超时了。里面有个很长很长的测试用例。。。
然后看了大神代码，可耻的没看懂，o(╥﹏╥)o
class Solution:
def longestWPI(self, hours: List[int]) -> int:
s = list()
s.append(0)
for h in hours:
s.append(s[-1] + (h > 8))
for i in range(len(s)):
s[i] = s[i] * 2 - i
print(s)
q = list()
q.append(0)
ans = 0
for i in range(1, len(s)):
if s[i] <= s[q[-1]]:
q.append(i)
else:
l, r, choose = 0, len(q) - 1, -1
while l <= r:
mid = (l + r) // 2
if s[i] > s[q[mid]]:
r = mid - 1
choose = mid
else:
l = mid + 1
#print(“chs =”, i, choose)
ans = max(ans, i - q[choose])
#print(q, ans)
return ans
已经决定转ai，所以搬了python的代码。。
不知道其中的奥秘，s，q 存的东西代表什么意思？
1回答
-
抱歉，我也看不懂。程序的缩进是乱的，变量名的语义也不清晰。你需要请教程序的原作者。
==========
简单的说，把 > 8的时间记为1，<= 8 的时间记为-1。题目就是求一个最长的区间，区间和 > 0。
可以使用二分搜索法，验证整个序列是否存在某个区间，长度 >= mid，且区间和 > 0。
具体验证的时候，使用了一个辅助数组presum。这是看区间和问题的常用套路。presum[i] 表示 arr[0...i]的数字和，看区间[x, y]的数字和，只需要看presuum[y] - presum[x - 1]。
继续加油！：）
012019-07-16
相似问题