Use bits instead of set for visited nodes. LeetCode #1434
source link: https://donghao.org/2023/03/22/use-bits-instead-of-set-for-visited-nodes-leetcode-1434/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Use bits instead of set for visited nodes. LeetCode #1434
My first idea is depth-first-search: iterate all people, try to give them different hats. The solution got TLE (Time Limit Exceeded). Then as a hint from discussion forum, I started to iterate hat (instead of people), try to give them different people. The solution also got TLE (even I used lru_cache for function):
from collections import defaultdict
class Solution:
def numberWays(self, hats: List[List[int]]) -> int:
hp = defaultdict(set)
for index, hat in enumerate(hats):
for _id in hat:
hp[_id].add(index)
hp = [people for people in hp.values()]
@functools.lru_cache(None)
def dfs(start, path) -> int:
if len(path) == len(hats):
return 1
if start == len(hp):
return 0
total = 0
for person in (hp[start] - set(path)):
total += dfs(start + 1, tuple(list(path) + [person]))
total += dfs(start + 1, path)
return total % (10**9 + 7)
return dfs(0, tuple())from collections import defaultdict
class Solution:
def numberWays(self, hats: List[List[int]]) -> int:
hp = defaultdict(set)
for index, hat in enumerate(hats):
for _id in hat:
hp[_id].add(index)
hp = [people for people in hp.values()]
@functools.lru_cache(None)
def dfs(start, path) -> int:
if len(path) == len(hats):
return 1
if start == len(hp):
return 0
total = 0
for person in (hp[start] - set(path)):
total += dfs(start + 1, tuple(list(path) + [person]))
total += dfs(start + 1, path)
return total % (10**9 + 7)
return dfs(0, tuple())
Using list as data structure to record visited node is not efficient enough in this case. Since there will be no more than 10 people, the most efficient data structure to record visited people is bits.
My final solution is still using dfs (by using lru_cache, it is also a dynamic-programming):
from collections import defaultdict
class Solution:
def numberWays(self, hats: List[List[int]]) -> int:
hp = defaultdict(set)
for index, hat in enumerate(hats):
for _id in hat:
hp[_id].add(index)
hp = [people for people in hp.values()]
@functools.lru_cache(None)
def dfs(start, mask) -> int:
if bin(mask).count('1') == len(hats):
return 1
if start == len(hp):
return 0
total = 0
for person in hp[start]:
if (1 << person) & mask > 0:
continue
mask |= 1 << person
total += dfs(start + 1, mask)
mask ^= 1 << person
total += dfs(start + 1, mask)
return total % (10**9 + 7)
return dfs(0, 0)from collections import defaultdict
class Solution:
def numberWays(self, hats: List[List[int]]) -> int:
hp = defaultdict(set)
for index, hat in enumerate(hats):
for _id in hat:
hp[_id].add(index)
hp = [people for people in hp.values()]
@functools.lru_cache(None)
def dfs(start, mask) -> int:
if bin(mask).count('1') == len(hats):return 1
if start == len(hp):
return 0
total = 0
for person in hp[start]:
if (1 << person) & mask > 0:
continue
mask |= 1 << person
total += dfs(start + 1, mask)
mask ^= 1 << person
total += dfs(start + 1, mask)
return total % (10**9 + 7)
return dfs(0, 0)
Related Posts
- Use recv() instead of read() for socket
When we use read() to read data from a socket like: ret = read(fd, buffer,…
- Divide and Conquer solution for LeetCode #494
The popular solution for LeetCode #494 is dynamic programming. But my first idea is Divide…
- Using keras.layers.Embedding instead of python dictionary
Firstly, I use a function to transform words into word-embedding: def text_to_array(text, embeddings_index): empty_embed =…
March 22, 2023 - 3:17
RobinDong
develop
Algorithm
Leave a comment
Leave a Reply Cancel reply
Your email address will not be published. Required fields are marked *
Comment *
Name *
Email *
Website
Save my name, email, and website in this browser for the next time I comment.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK