Leetcode:152、乘积最大子序列；295、数据流的中位数

152、乘积最大子序列

中等 给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例 1:

输入: [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

笔记： 自己写的，时间复杂度太高不能通过， 找资料看的两种解法，动态规划和遍历，动态真的真的真的是重中之重，加油 一个比较完整健全的解决思路（来自网友）：

在第i个元素时，我们能够取到的子序列的最大乘积可能来自：

（1）nums[i]本身

（2）nums[i-1]能够取到的最大子序列的乘积

（3）包含nums[i-1]的最大连乘值 * nums[i] (两个部分均为正数)

（4）包含nums[i-1]的最小连乘值 * nums[i] (两个部分均为负数)

因此对于第i个元素，我们需要记录的值有三个：

（1）能够取到的子序列的最大乘积

（2）包含当前位置的最大连乘值

（3）包含当前位置的最小连乘值 记录最小连乘值，是因为可能有负数，负数乘负数

原文：https://blog.csdn.net/Try_my_best51540/article/details/84750798 代码读一下，走一遍很清楚

class Solution: def maxProduct(self, nums: List[int]) -> int: temp = nums[0] n = len(nums) dp_max = [0 for i in range(n)] dp_min = [0 for i in range(n)] for i in range(n): if i == 0: dp_max[0] = nums[0] dp_min[0] = nums[0] else: dp_max[i] = max(max(dp_max[i-1]*nums[i],dp_min[i-1]*nums[i]),nums[i]) dp_min[i] = min(min(dp_max[i-1]*nums[i],dp_min[i-1]*nums[i]),nums[i]) temp = max(temp,dp_max[i]) return temp

解法2：

先计算从左到右的相乘的最大值，再计算从右到左的最大值；再将两组最大值相比

还有一点要注意的是，上面说的一列负数的要求是负数之间是不存在零的，假如有零的话，就要分段考虑。 class Solution: def maxProduct(self, A): B = A[::-1] for i in range(1, len(A)): A[i] *= A[i - 1] or 1 B[i] *= B[i - 1] or 1 return max(max(A),max(B))

189、旋转数组 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右旋转 1 步: [7,1,2,3,4,5,6] 向右旋转 2 步: [6,7,1,2,3,4,5] 向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入: [-1,-100,3,99] 和 k = 2 输出: [3,99,-1,-100] 解释: 向右旋转 1 步: [99,-1,-100,3] 向右旋转 2 步: [3,99,-1,-100]

说明:

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。 要求使用空间复杂度为 O(1) 的原地算法。

笔记：这么简单的刚开始做的并不对，漫漫算法刷题学习之路 解法1：自己写的

class Solution: def rotate(self, nums: List[int], k: int) -> None: """ Do not return anything, modify nums in-place instead. """ k = k%len(nums) t = nums[-k:] nums[k:] = nums[:-k] nums[:k] = t

解法2：

class Solution: def rotate(self, nums: List[int], k: int) -> None: k = k % len(nums) while k: nums.insert(0, nums.pop()) k -= 1

295、数据流的中位数 困难 中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。 double findMedian() - 返回目前所有元素的中位数。

示例：

addNum(1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2

进阶:

如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？ 如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？

笔记;剑指offer有同样的题目，sort(）函数提交可以通过，力扣却不能通过，看了评论解析，大小堆方法，困难真的很难很难

解法1：能通过的大小堆,看得懂，继续学习

class MedianFinder: def __init__(self): """ initialize your data structure here. """ self.vec = [] def binary_insert(self,s,e,tgt): while s <= e: if s == e: if self.vec[s] >= tgt: self.vec.insert(s,tgt) else: self.vec.insert(s+1,tgt) return if e-s == 1 and (self.vec[e] > tgt and self.vec[s] < tgt): self.vec.insert(s+1,tgt) return mid = (s+e)//2 if self.vec[mid] > tgt: e = mid - 1 elif self.vec[mid] < tgt: s = mid + 1 if self.vec[s] < tgt: pass else: self.vec.insert(s,tgt) return else: self.vec.insert(mid,tgt) return return def addNum(self, num: int) -> None: if not self.vec: self.vec.append(num) elif num >= self.vec[-1]: self.vec.append(num) elif num <= self.vec[0]: self.vec.insert(0,num) else: self.binary_insert(0,len(self.vec)-1,num) def findMedian(self) -> float: n = len(self.vec) if n%2 == 0: return (self.vec[n//2] + self.vec[n//2 - 1])/2.0 else: return self.vec[n//2]