Leetcode: 1434. Number of Ways to Wear Different Hats to Each Other

1864 단어

Descpition

There are n people and 40 types of hats labeled from 1 to 40.
Given a list of list of integers hats, where hats[i] is a list of all hats preferred by the i-th person.
Return the number of ways that the n people wear different hats to each other.
Since the answer may be too large, return it modulo 10^9 + 7.

Example

Input: hats = [[1,2,3],[2,3,5,6],[1,3,7,9],[1,8,9],[2,5,7]]
Output: 111

Note

n == hats.length
1 <= n <= 10
1 <= hats[i].length <= 40
1 <= hats[i][j] <= 40
hats[i] contains a list of unique integers.

분석

      ,  dict  。 。
 

code

TLE  

class Solution(object):
    def _do(self, hats):
        hat = 0
        for i in hats:
            for j in i:
                hat |= (1<
AC  
class Solution(object):
    def _do(self, hats):
        hat_set, hat_sorted = set(), []
        for i, v in enumerate(hats):
            hat_set |= set(v)

        hat_sorted = sorted(list(hat_set))
        dp = [[0 for _ in range(0, 1<

총결산

  • 사고방식은 매우 간단하다. 바로 일반적인 상태 압축 dp이다.그러나 사용하지 않는 사물을 dp압축으로 선택하면 큰 차이가 있다
  • Runtime: 472 ms, faster than 54.46% of Python online submissions for Number of Ways to Wear Different Hats to Each Other.
    Memory Usage: 13.7 MB, less than 61.46% of Python online submissions for Number of Ways to Wear Different Hats to Each Other.
    

    좋은 웹페이지 즐겨찾기