lintcode35

https://www.lintcode.com/contest/35/

1417. Weighing Problem
      每次都分成3堆是optimal的

import math

class Solution:
    """
    @param n: The number of coins
    @return: The Minimum weighing times int worst case
    """
    def minimumtimes(self, n):
        # Write your code here
        t = math.log(n,3)
        if t-int(t)<0.0000001: return int(t)
#        print(math.log(n,3))
        return int(math.ceil(t))
    
s=Solution()
print(s.minimumtimes(999))
print(s.minimumtimes(9)) #2

998. Construction Queue
     跟之前LC一道题类似，排序，然后先插入小的，然后根据排第几位就插入到index为几的地方

class Solution:
    """
    @param n: The array sum
    @param arr1: The size
    @param arr2: How many numbers small than itself 
    @return: The correct array
    """
    def getQueue(self, n, a1, a2):
        # Write your code here
        d = {i:j for (i,j) in zip(a1,a2)}
        a1.sort()
        res = []
        for t in a1:
            res.insert(d[t], t)
        return res
    
s=Solution()
print(s.getQueue(4, [1,3,7,6], [0,1,3,2]))
print(s.getQueue(4, [1,2,3,4,5], [0,0,0,1,3]))

996. Maximum Slope Straight Line
     根据x坐标排序，然后最大slope一定是相邻的2个point

class Point:
    def __init__(self, a=0, b=0):
        self.x = a
        self.y = b

class Solution:
    def getPoints(self, points):
        # Write your code here
        a=[]
        for i,k in enumerate(points):
            a.append((k.x,k.y,i))
        a.sort()
        res = [-1,-1]
        n = len(points)
        ma = -999999999999
        for i in range(1,n):
            if ma<(a[i][1]-a[i-1][1])/(a[i][0]-a[i-1][0]):
                ma=(a[i][1]-a[i-1][1])/(a[i][0]-a[i-1][0])
                res=sorted([a[i-1][2],a[i][2]])
        return res