leetcode题解

class (object):
    def find_median_sorted_arrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        len_1, len_2 = len(nums1), len(nums2)
        if (len_1 + len_2) % 2 == 1:
            return self.get_kth(nums1, nums2, (len_1 + len_2) // 2 + 1)
        else:
            return (self.get_kth(nums1, nums2, (len_1 + len_2) // 2) +
                    self.get_kth(nums1, nums2, (len_1 + len_2) // 2 + 1)) * 0.5

    def get_kth(self, nums1, nums2, k):
        length_1, length_2 = len(nums1), len(nums2)
        if length_1 > length_2:
            return self.get_kth(nums2, nums1, k)
        if length_1 == 0:
            return nums2[k - 1]
        if k == 1:
            return min(nums1[0], nums2[0])

        pa = min(k // 2, length_1)
        pb = k - pa
        return self.get_kth(nums1[pa:], nums2, k - pa) if nums1[pa - 1] <= nums2[pb - 1] else self.get_kth(nums1, nums2[pb:], k - pb)

def permutations(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

def combinations(iterable, r):
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

import re
from collections import Counter


class (object):
    def countOfAtoms(self, formula):
        """
        :type formula: str
        :rtype: str
        """
        parse = re.findall(r"([A-Z][a-z]*)(d*)|(()|())(d*)", formula)
        stk = [Counter()]
        for name, m1, left_open, right_open, m2 in parse:
            if name:
                stk[-1][name] += int(m1 or 1)
            if left_open:
                stk.append(Counter())
            if right_open:
                top = stk.pop()
                for k, v in top.items():
                    stk[-1][k] += v * int(m2 or 1)
        stk = stk[-1]
        return ''.join(name + str(stk[name] if stk[name] > 1 else '') for name in sorted(stk))

class (object):
    def splitListToParts(self, root, k):
        """
        :type root: ListNode
        :type k: int
        :rtype: List[ListNode]
        """
        n = 0
        curr = root
        while curr:
            curr = curr.next
            n += 1
        width, remainder = divmod(n, k)

        result = []
        curr = root
        for i in range(k):
            head = curr
            for j in range(width-1+int(i < remainder)):
                if curr:
                    curr = curr.next
            if curr:
                curr.next, curr = None, curr.next
            result.append(head)
        return result

class (object):
    def selfDividingNumbers(self, left, right):
        """
        :type left: int
        :type right: int
        :rtype: List[int]
        """
        return [num for num in range(left, right+1) if self.is_dividing_number(num)]

    def is_dividing_number(self, n):
        return all([int(divisor) != 0 and n % int(divisor) == 0  for divisor in list(str(n))])

class MyCalendarTwo(object):
    def __init__(self):
        self.over_flaps = []
        self.calendar = []

    def book(self, start, end):
        """
        :type start: int
        :type end: int
        :rtype: bool
        """
        for i, j in self.over_flaps:
            if start < j and end > i:
                return False
        for i, j in self.calendar:
            if start < j and end > i:
                self.over_flaps.append((max(start, i), min(j, end)))
        self.calendar.append((start, end))
        return True

class (object):
    def asteroidCollision(self, asteroids):
        """
        :type asteroids: List[int]
        :rtype: List[int]
        """
        res = []
        for asteroid in asteroids:
            while res and asteroid < 0 < res[-1]:
                if res[-1] < abs(asteroid):
                    res.pop()
                    continue
                elif res[-1] == abs(asteroid):
                    res.pop()
                break
            else:
                res.append(asteroid)
        return res