humanversion9x
Junior Member
Thuật toán này có Time complexity là 1 + 2 + 4 + 8 + .. + 2^k = 2^(k+1) - 1 = O(2^k) rồi bạn.À mấy fence cho mình hỏi thử sao bài 2 giải bằng DFS thì nó throws TLE nhỉ
Time complexity với space complexity chỉ là O(n) thôi mà, vì worst case ở mỗi trường hợp nó tăng lên từ 1 -> 10^5 thôi chứ nhỉ
Python:from collections import deque class Solution: def minOperations(self, k: int) -> int: visited = set() queue = deque() queue.append((0, 1, 1)) while queue: operations, total, lastNum = queue.popleft() if total >= k: return operations if (total, lastNum) in visited: continue visited.add((total, lastNum)) queue.append((operations + 1, total + lastNum, lastNum)) queue.append((operations + 1, total + 1, lastNum + 1)) return -1