[Mock] Amazon 12

346. Moving Average from Data Stream

My Answer 1: Accepted (Runtime: 88 ms - 48.04% / Memory Usage: 17.2 MB - 83.85%)

class MovingAverage(object):
    """
    @param: size: An integer
    """
    def __init__(self, size):
        # do intialization if necessary
        self.size = size
        self.nums = []

    """
    @param: val: An integer
    @return:  
    """
    def next(self, val):
        # write your code here
        if len(self.nums) == self.size:
            self.nums.pop(0)

        self.nums.append(val)

        return sum(self.nums) / len(self.nums)


# Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param = obj.next(val)

size 만큼 꽉 차면 맨 처음 값 pop 해주기

아니면 deque 써서 popleft 해도 될듯

lintcode 야 고마워..^^

---

1128. Number of Equivalent Domino Pairs

Given a list of dominoes, dominoes[i] = [a, b] is equivalent to dominoes[j] = [c, d] if and only if either (a==c and b==d), or (a==d and b==c) - that is, one domino can be rotated to be equal to another domino.

Return the number of pairs (i, j) for which 0 <= i < j < dominoes.length, and dominoes[i] is equivalent to dominoes[j].

My Answer 1: Accepted (Runtime: 256 ms / Memory Usage: 24 MB)

import math

class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        dic = collections.defaultdict(int)
        
        for i in range(len(dominoes)):
            if dominoes[i][0] >= len(dominoes) or dominoes[i][1] >= len(dominoes):
                continue
            if dominoes[i][0] < dominoes[i][1]:
                dic[(dominoes[i][0],dominoes[i][1])] += 1
            else:
                dic[(dominoes[i][1],dominoes[i][0])] += 1
        
        #print(dic)
        
        ans = 0
        for k, v in dic.items():
            if v > 1:
                nCr = math.factorial(v) // (math.factorial(v-2)*2)
                ans += nCr
        
        return ans

도미노 조건에 만족하는 pair 의 개수 X
unique 한 도미노의 개수 X
결론은 도미노 pair 의 조합 개수였다...

문제를 왤케 그지같이 써놨는지ㅡㅡ

0 <= i < j < dominoes.length 라는 조건도 있어서
if dominoes[i][0] >= len(dominoes) or dominoes[i][1] >= len(dominoes):
가 아닐때만

dic 에 pair 개수 세주고 nCr 구해서 더해줌