找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 3475|回复: 6
收起左侧

[刷题记录板] [leetcode] (Dec,6)每天两道题目,配 python参考解答

[复制链接]

20

主题

5

精华

586

积分

超级会员

Rank: 4

积分
586
发表于 12-6-2014 07:15 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
题目(一):Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.



题目(二):Maximum Product Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.


图片割开参考答案:

题目(一):                                                              题目(二):









python参考解答:
题目(一): Min Stack
[code]class MinStack:
    # @param x, an integer
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    # @return an integer
    def push(self, x):
        self.stack1.append(x)
        if len(self.stack2) == 0 or x <= self.stack2[-1]:
            self.stack2.append(x)

    # @return nothing
    def pop(self):
        top = self.stack1[-1]
        self.stack1.pop()
        if top == self.stack2[-1]:
            self.stack2.pop()
        
    # @return an integer
    def top(self):
        return self.stack1[-1]

    # @return an integer
    def getMin(self):
        return self.stack2[-1][/code]

题目(二):Maximum Product Subarray
[code]class Solution:
    # @param A, a list of integers
    # @return an integer
    def maxProduct(self, A):
        if len(A) == 0:
            return 0
        min_tmp = A[0]
        max_tmp = A[0]
        result = A[0]
        for i in range(1, len(A)):
            a = A【i】 * min_tmp
            b = A【i】 * max_tmp
            c = A【i】
            max_tmp = max(max(a,b),c)
            min_tmp = min(min(a,b),c)
            result = max_tmp if max_tmp > result else result
        return result[/code]

本帖被以下淘专辑推荐:

3

主题

2

精华

63

积分

资深会员

Rank: 2

积分
63
发表于 12-6-2014 10:51 PM | 显示全部楼层
第二题中请问为何还要记录min_tmp

20

主题

5

精华

586

积分

超级会员

Rank: 4

积分
586
 楼主| 发表于 12-7-2014 11:46 AM | 显示全部楼层
royzxq 发表于 12-6-2014 10:51 PM
第二题中请问为何还要记录min_tmp

方便理清思路啦

不要在意细节
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表