找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1474|回复: 1
收起左侧

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

[复制链接]

20

主题

5

精华

586

积分

超级会员

Rank: 4

积分
586
发表于 12-18-2014 02:22 PM | 显示全部楼层 |阅读模式

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

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

x
题目(一):Merge Intervals
Given a collection of intervals, merge all overlapping intervals.


For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

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

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.


图片割开参考答案:

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








python参考解答:
题目(一):Merge Intervals
[code]# Definition for an interval.
# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution:
    # @param intervals, a list of Interval
    # @return a list of Interval
    def merge(self, intervals):
        intervals.sort(key = lambda x:x.start)
        length=len(intervals)
        res=[]
        for i in range(length):
            if res==[]:
                res.append(intervals【i】)
            else:
                size=len(res)
                if res[size-1].start<=intervals【i】.start<=res[size-1].end:
                    res[size-1].end=max(intervals【i】.end, res[size-1].end)
                else:
                    res.append(intervals【i】)
        return res[/code]
题目(二):Maximum Subarray
[code]class Solution:
    # @param A, a list of integers
    # @return an integer
    def maxSubArray(self, A):
        ThisSum = 0
        MaxSum = -10000
        
        for i in range( 0, len(A) ):
            if ThisSum < 0:
                ThisSum = 0
            ThisSum = ThisSum + A[ i ]
            MaxSum = max( ThisSum, MaxSum )

        return MaxSum[/code]

本帖被以下淘专辑推荐:

11

主题

1

精华

293

积分

高级会员

Rank: 3Rank: 3

积分
293
发表于 12-18-2014 10:19 PM | 显示全部楼层
友情支持!!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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