首页 > 其他 > 详细

ARTS Challenge- Week 1 (2019.03.25~2019.03.31)

时间:2019-03-27 00:31:50      阅读:168      评论:0      收藏:0      [点我收藏+]

1.Algorithm - at least one leetcode problem per week(Medium+)

986. Interval List Intersections https://leetcode.com/problems/interval-list-intersections/  Medium

Basic sorting and one time scan, be sure to process the start and end of each interval, set flag and output.

# Definition for an interval.
# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution:
    def intervalIntersection(self, A: List[Interval], B: List[Interval]) -> List[Interval]:
        L = []
        for item in A:
            L.append((item.start,1))
            L.append((item.end,4))
        
        for item in B:
            L.append((item.start,2))
            L.append((item.end,8))   

        L = sorted(L)
        ans = []

        nowL1 = -100
        nowL2 = -100
        stat = 0
        for value,color in L:
            if color ==1:
                nowL1 = value
                stat |= color
            elif color == 2:
                nowL2 = value
                stat |= color
            elif color == 4:
                if stat == 3:
                    ans.append(Interval(max(nowL1,nowL2),value))
                stat &= 2
            elif color == 8:
                if stat == 3:
                    ans.append(Interval(max(nowL1,nowL2),value))
                stat &= 1
        return ans

 

1014. Capacity To Ship Packages Within D Days https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/  Medium

Given a capacity it‘s easy to check the anwser, simply do a binary search.

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        
        def minDays(C):
            
            now = 0
            ans = 0
            for x in weights:
                if now + x <= C:
                    now +=x
                else:
                    ans +=1
                    now = x
            ans += now != 0
            return ans
        
        L = max(weights)
        R = L*len(weights)
        ans = L
        while L<=R:
            M = (L+R)//2
            if minDays(M)<=D:
                ans = M
                R = M-1
            else:
                L = M+1
        return ans
        

2. Review a technical article

3. Learn a technical tip

4. Share a technical article

 

ARTS Challenge- Week 1 (2019.03.25~2019.03.31)

原文:https://www.cnblogs.com/programCaiCai/p/arts_challenge_week_1.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!