thảo luận Leetcode + Codeforces, Competitive programming contest. Đường tới Guardian + Candidate Master.

  • Người tạo chủ đề Người tạo chủ đề freedom.9
  • Ngày bắt đầu Ngày bắt đầu
giờ bắt đầu từ blind75 ổn không ae. :D bỏ lâu rồi cũng quên mất nhiều, giờ muốn bắt đầu lại. với có strategy nào ổn khg ạ. cám ơn ae
Làm 6 tháng liên tục hàng ngày rồi quay lại đây nhé fen
zFNuZTA.gif

Làm theo roadmap 150 của Neetcode
via theNEXTvoz for iPhone
 
Q3 O(n.sqrt(n)) không pass được, cay quá
 

Tệp đính kèm

  • 1000003637.jpg
    1000003637.jpg
    184,8 KB · Lượt xem: 24
Q3 như nào vậy các huynh @@ tiểu đệ đổi từ nsqrt(n) về n.log(n) rồi mà vẫn chết (sieve + lưu first prime)
 
Đề nay khó thể, giải nhanh được Q1 tưởng ngon, ai ngờ cũng là câu duy nhất giải được :shame:
Câu 3 dính TLE chắc là do không có cách tính primes nhanh.
Java:
class Solution {
    public long maximumMedianSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        long res = 0L;
        
        for(int i = n - 2; i >= n/3; i-=2) {
            res += nums[i];
        }

        return res;
    }
}
 
Mẹ nó cái Q1 type nhanh ăn bug, Q2 type ngu cũng ăn bug, Q3 type chuẩn thì ăn 3 bugs do TLE + MLE, đen vãi =((
Q1 cũng dễ mà nghĩ lâu quá, Q2 thì max dễ mà cũng nghĩ lâu lol, Q3 thì gõ lộn =((
Q3 thì dùng bfs thôi, với nhớ check visited của cái số primes để khỏi bị TLE, vì số primes chỉ có giới hạn thôi.
Giả sử arr là số primes thì từ số primes đó sẽ nhảy đc qua pos khác, nếu có arr j = arr i thì ko cần phải xử lí chỗ arr j nữa
Python:
MAX = 10**6 + 2
primes = [True]*MAX
primes[0] = primes[1] = False

for i in range(MAX):
    if primes[i]:
        for j in range(i + i, MAX, i):
            primes[j] = False
            
class Solution:
    def minJumps(self, nums: List[int]) -> int:
        queue = deque()
        indexs = defaultdict(list)
        for i, val in enumerate(nums):
            indexs[val].append(i)

        mx = max(nums)
        queue.append((0, 0))
        n = len(nums)
        visited = [False]*n
        visited[0] = True
        primesSet = set()

        while queue:
            current, step = queue.popleft()
            if current == n - 1:
                return step

            if current + 1 < n and not visited[current + 1]:
                visited[current + 1] = True
                queue.append((current + 1, step + 1))

            if current - 1 >= 0 and not visited[current - 1]:
                visited[current - 1] = True
                queue.append((current - 1, step + 1))

            if primes[nums[current]] and nums[current] not in primesSet:
                c = nums[current]
                mult = 1
                while c*mult <= mx:
                    nx=c*mult
                    for nxt in indexs[c*mult]:
                        if not visited[nxt]:
                            visited[nxt] = True
                            queue.append((nxt, step + 1))

                    mult += 1

                primesSet.add(nums[current])

        return -1



1753589016269.png
 
Sửa lần cuối:

Thống kê chủ đề

Ngày tạo
freedom.9,
Người trả lời cuối
deple20k,
Trả lời
1.686
Lượt xem
107.088
Quay lại
Lên đầu trang