Others

1 Kth Largest Element in an Array

哈哈哈哈

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        return sorted(nums)[len(nums) - k]

2 Find the Celebrity

这不是脑筋急转弯么，如果一个人认识另一个人，那么这个人就一定不是高冷的celebrity。所以每次比较都能排除一个。扫一遍就能把唯一的可能人选确定下来。然后再确定所有人认识这个人，并且这个人不认识所有其他的人。

# The knows API is already defined for you.
# @param a, person a
# @param b, person b
# @return a boolean, whether a knows b
# def knows(a, b):

class Solution(object):
    def findCelebrity(self, n):
        """
        :type n: int
        :rtype: int
        """
        cela = 0
        for i in range(1, n):
            if knows(cela, i):
                cela = i

        for i in range(n):
            if i!=cela and not knows(i, cela):
                return -1
            if i!=cela and knows(cela, i):
                return -1
        return cela

3 Task Scheduler

这道题，非常巧妙，我终于知道这个为什么要放到Other里面了。因为这里面的题目都是一拍脑袋灵关一闪题型

class Solution(object):
    def leastInterval(self, tasks, n):
        """
        :type tasks: List[str]
        :type n: int
        :rtype: int
        """
        c = collections.Counter(tasks).values()
        pop_appear = max(c)
        pop_cnt = c.count(pop_appear)
        return max(len(tasks), (pop_appear-1)*(n+1) + pop_cnt )

用Priority queue来写一个。

import collections
import heapq
class Solution(object):
    def leastInterval(self, tasks, n):
        """
        :type tasks: List[str]
        :type n: int
        :rtype: int
        """
        n = n+1
        ans = 0
        counts = collections.Counter(tasks).values()
        heap = [-c for c in counts]
        heapq.heapify(heap)
        while heap:
            stack = []
            cnt = 0
            for _ in range(n):
                if heap:
                    task = heapq.heappop(heap)
                    cnt += 1
                    task += 1
                    if task < 0:
                        stack.append(task)
            for t in stack:
                heapq.heappush(heap, t)
            ans += n if heap else cnt
        return ans


s = Solution()
print s.leastInterval(["A","A","A","B","B","B"], 2)

4 Divide Two Integers

有点不好写。哎，人老了，真是越刷越回去了。

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        if divisor==0:
            return -1
        sign = 1 if (dividend<0) == (divisor<0) else -1
        dividend, divisor = abs(dividend), abs(divisor)
        ans = 0
        while dividend>=divisor:
            tmp = divisor
            cnt = 1
            while dividend>=tmp:
                dividend -= tmp
                ans += cnt
                cnt = cnt<<1
                tmp = tmp<<1
        return min(1<<31-1, max(-1<<31, sign*ans))

s = Solution()
print s.divide(-2147483648, -1)