thảo luận Leetcode mỗi ngày

Zayt__ · 20/8/22

_Gia_Cat_Luong_ đã nói:
Bài hôm nay đọc vào là nghĩ ngay đến greedy rồi, nhưng lại bị chệch hướng. Ban đầu tư duy đơn giản: - Với một vị trí start t và lượng nhiên liệu f, mình sẽ đi được tối đa đến vị trí t + f

Vậy nếu đổ xăng, mình sẽ đổ tại station nào đó trong khoảng từ t -> t + f mà có lượng xăng lớn nhất

Vị trí đổ không quan trọng vì lượng xăng còn tồn vẫn được giữ lại

=> Bị lỗi trường hợp đôi khi mình cần đổ 2 3 station (hoặc hơn nữa) mới đến được vị trí tiếp theo

Vậy nếu không đến được vị trí tiếp theo thì sẽ đổ thêm tại các trạm khác

Mà nếu đã đổ thì cứ lựa trạm lớn nhất có thể mà đổ

=> Dùng heap

Mình sai cái trường hợp đầu tận 4 lần :beat_brick:

cứ nghĩ mình đúng cho tới khi gặp cái test case lỗi (3 lần đầu là code ngu dính edge case nên chưa phát hiện, lần 4 mới phát hiện là lỗi logic)
Cách làm thì cũng dùng heap như fen

the_gioi_that_dep · 20/8/22

ngoctan_95 đã nói:
C

Công ty nào mà 1 line code bị xuống làm tester vậy thím. Nói để anh em né
Ngoại trừ BoschRBVH VN còn làm chiêu đó cho fresher thôi chớ.

Có người kể cho em thế mà em cũng không dám hỏi thêm bác ạ.

.
Còn bài hôm nay em đọc thấy cái constraint số trạm xăng chỉ có 500 là O(n^2) duyệt hết làm 1 quả dp. Java được có 10% time mà cứ thấy pass là bỏ đi chơi gem

.

nhung_doi_hoa_simp · 21/8/22

thread này bổ ích vkl : ))))

HangingTree · 21/8/22

Mình đang có một bài toán liên quan tới task scheduling. Đại loại là có 1 tập các task cần thực thi, mỗi task bao gồm thời gian hoàn thành và một bộ các task cần phải hoàn thành trước khi bắt đầu. Và có một số lượng workers độc lập.
Câu hỏi là phân chia task như thế nào để:
1. Task không được thực thi trước khi tất cả các required task hoàn thành.
2. Không để xảy ra trường hợp idling workers và available tasks. (đại loại là task có thể start now nhưng không assign cho worker).

Các bác có cao kiến gì giúp với

bribnt · 21/8/22

Bài hôm nay đúng là trò lừa, thêm cái điều kiện target.lengh() * 10 nhìn cũng sợ nhưng thực ra chả bao giờ cần đến quá target.length() lần đóng dấu.

Ý tưởng:

Truy ngược từ target về đầu,
Ở mỗi bước, tìm trong chuỗi target một substring match* được cái stamp. Replace hết tất cả các ký tự trong đó thành '?',

*match: match ở đây có nghĩa là ký tự trong target là '?' hoặc bằng ký tự trong stamp. Nhưng yêu cầu phải có ít nhất một ký tự không phải '?',

Nếu không tìm thấy substring nào tức là không có cách giải, trả về vector rỗng,
Nếu toàn bộ chuỗi target bị replace thành _ thì dừng lại.

Lúc đầu thấy cái target * 10 tưởng là sẽ có case hiểm nào khác nên submit bừa theo ý tưởng trên để xem sai chỗ nào, không ngờ làm phát ăn luôn.
https://leetcode.com/submissions/detail/779163302/

HangingTree đã nói:
Mình đang có một bài toán liên quan tới task scheduling. Đại loại là có 1 tập các task cần thực thi, mỗi task bao gồm thời gian hoàn thành và một bộ các task cần phải hoàn thành trước khi bắt đầu. Và có một số lượng workers độc lập.
Câu hỏi là phân chia task như thế nào để:
1. Task không được thực thi trước khi tất cả các required task hoàn thành.
2. Không để xảy ra trường hợp idling workers và available tasks. (đại loại là task có thể start now nhưng không assign cho worker).

Các bác có cao kiến gì giúp với

Có cần tối ưu gì không? VD như cần thời gian hoàn thành tất cả task là nhỏ nhất.
Nếu không thì cứ greedy mà làm thôi. Tạo danh sách task available, có bao nhiêu worker thì phân hết vào, hoàn thành thì update danh sách.

HangingTree · 21/8/22

bribnt đã nói:
Có cần tối ưu gì không? VD như cần thời gian hoàn thành tất cả task là nhỏ nhất.
Nếu không thì cứ greedy mà làm thôi. Tạo danh sách task available, có bao nhiêu worker thì phân hết vào, hoàn thành thì update danh sách.

Mình nghĩ cần phải tìm cách nào đó tối ưu thứ tự ưu tiên của task ấy. VD có 3 task (A,B,C) không phụ thuộc, task D depends on B và C, 2 workers, thì mình assign cho B và C chạy trước, đại loại vậy.

thuyduong2007 · 21/8/22

HangingTree đã nói:
Mình đang có một bài toán liên quan tới task scheduling. Đại loại là có 1 tập các task cần thực thi, mỗi task bao gồm thời gian hoàn thành và một bộ các task cần phải hoàn thành trước khi bắt đầu. Và có một số lượng workers độc lập.
Câu hỏi là phân chia task như thế nào để:
1. Task không được thực thi trước khi tất cả các required task hoàn thành.
2. Không để xảy ra trường hợp idling workers và available tasks. (đại loại là task có thể start now nhưng không assign cho worker).

Các bác có cao kiến gì giúp với

Các task phụ thuộc vào nhau thì build thành DAG, sau đó dùng topology sorting để sort thì sẽ ra thứ tự thực thi. Tuy nhiên nên tìm hiểu rồi dùng airflow nhé. Tự build thì bao giờ mới xong.

Arik97 · 21/8/22

HangingTree đã nói:
Mình nghĩ cần phải tìm cách nào đó tối ưu thứ tự ưu tiên của task ấy. VD có 3 task (A,B,C) không phụ thuộc, task D depends on B và C, 2 workers, thì mình assign cho B và C chạy trước, đại loại vậy.

Đọc về topological sort đi thím https://www.interviewcake.com/concept/java/topological-sort
Problem của bác giống mấy bài parallel courses ở trên leetcode nhưng mà có yếu tố thời gian vs cả số lượng k worker cố định nên e thử propose 1 cách làm topological sort+ greedy 1 chút nhé.

Đầu tiên là build 1 cái DAG dựa vào các dependencies kia. Xong r xác định các node(từ giờ coi node = task) có indegree=0. Giả sử L là list các node có indegree=0
Schedule các node trong L vào k workers theo ưu tiên node nào có tg hoàn thành sớm hơn thì schedule trước.
Mỗi khi có 1 task được hoàn thành thì update lại indegree của các task phụ thuộc vào nó. Nếu thấy đc node nào có indegree =0 thì add node đó vào L
Cứ có worker nào rảnh (vd worker vừa thực hiện task xong, hoặc schedule ở b2 xong còn thừa worker rảnh) thì cho worker đó thực hiện task có tg hoàn thành ngắn nhất trong L ( Dùng heap pop để lấy phần tử nhỏ nhất cho nhanh)

Nếu thím chưa biết về topological sort hay heap thì đọc để hiểu mấy khái niệm cơ bản như là DAG, indegree, heap,... nhé. Trong này toàn tay to leetcode nên mấy cái khái niệm trên mấy bác ý dùng như cơm bữa thôi

Kân team v3 · 21/8/22

bribnt đã nói:
Lúc đầu thấy cái target * 10 tưởng là sẽ có case hiểm nào khác nên submit bừa theo ý tưởng trên để xem sai chỗ nào, không ngờ làm phát ăn luôn.

nghĩ ra case bí hiểm đi hình như submit test case được 100 coin = x10 số lượng coin AC đóa

thuyduong2007 · 22/8/22

nay bài dễ, tiếp tục 1 line,

Python:

return True if n == 1 else False if n%4 != 0 or n <= 0 else self.isPowerOfFour(n//4)

Python:

return any(x for x in [1,4,16,64,256,1024,4096,16384,65536,262144,1048576,4194304,16777216,67108864,268435456,1073741824] if x == n)

Lập Trình Viên Số Khổ · 22/8/22

Tham gia bài dễ :sexy_girl:

Python:

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        if n < 0:
            return False
        
        for i in range(16):
            if 4**i == n:
                return True
        
        return False

ngoctan_95 · 22/8/22

Bài hôm nay làm nhớ tới 4 nam trc pvan o cty outsource (Yêu cầu là không được dùng các hàm hỗ trợ)

Mã:

if(n == 0) {
    return false
}
  while(n > 1)
  {   
   if(n % 4 != 0) {
      return false
   }
    n = n / 4;     
  }
  return true

_Gia_Cat_Luong_ · 22/8/22

Đây mới đích thực là one-liner:

Python:

return n in [0x1, 0x4, 0x10, 0x40, 0x100, 0x400, 0x1000, 0x4000, 0x10000, 0x40000, 0x100000, 0x400000, 0x1000000, 0x4000000, 0x10000000, 0x40000000]

ngoctan_95 · 22/8/22

_Gia_Cat_Luong_ đã nói:
Đây mới đích thực là one-liner:

Python:

return n in [0x1, 0x4, 0x10, 0x40, 0x100, 0x400, 0x1000, 0x4000, 0x10000, 0x40000, 0x100000, 0x400000, 0x1000000, 0x4000000, 0x10000000, 0x40000000]

4 nam truoc lam gi nghi duoc toi nhu the nay =((

, 4 nam sau van vay

bribnt · 22/8/22

Cách giải không cần loop, không cần hàm hỗ trợ (__builtin_clz là một instruction có sẵn, gọi trực tiếp assembly thay vào cũng được). Test n in array bản chất vẫn là loop rồi.

C++:

    bool isPowerOfFour(int n) {
        auto lg2 = n > 0 ? sizeof(n)*8 - 1 - __builtin_clz(n) : -1;
        return n > 0 && (lg2 % 2 == 0) && ((1LL << lg2) == n);
    }

Cách khác:

C++:

    bool isPowerOfFour(int n) {
        return n > 0 && (n & (n-1) == 0) && (n & 0x55555555));
    }

Giải thích: để là lũy thừa của 4 thì cần:

Lớn hơn 0
Là lũy thừa của 2. Tức biểu diễn nhị phân có dạng 1000...000. Khi đó n & (n-1) == 10...000 & 01...111 = 0
Bit 1 phải nằm ở vị trí lẻ. Số 0x55555555 có biểu diễn nhị phân là 010101...01, khi and với n sẽ trả về khác 0 nếu trong n có 1 bit ở vị trí lẻ.

dangson · 22/8/22

Python:

return n in (1, 4, 16, 64, 256, 1024, 4096, 16384, 65536, 262144, 1048576, 4194304, 16777216, 67108864, 268435456, 1073741824)

DoiToi CoDon · 22/8/22

Java:

 public boolean isPowerOfFour(int n) {
        
        if (n <= 0) return false;
        while (n  > 1){
            if (n % 4 != 0) return false;
            else {
                n = n/4;
            }
        }
        return true;
    }

Kân team v3 · 22/8/22

bribnt đã nói:
Giải thích: để là lũy thừa của 4 thì cần:

Lớn hơn 0

Là lũy thừa của 2. Tức biểu diễn nhị phân có dạng 1000...000. Khi đó n & (n-1) == 10...000 & 01...111 = 0

Bit 1 phải nằm ở vị trí lẻ. Số 0x55555555 có biểu diễn nhị phân là 010101...01, khi and với n sẽ trả về khác 0 nếu trong n có 1 bit ở vị trí lẻ.

não to thặc, đáng lẽ nên để đọc giả tự tìm hiểu

thuyduong2007 · 22/8/22

bribnt đã nói:
Giải thích: để là lũy thừa của 4 thì cần:

Lớn hơn 0

Là lũy thừa của 2. Tức biểu diễn nhị phân có dạng 1000...000. Khi đó n & (n-1) == 10...000 & 01...111 = 0

Bit 1 phải nằm ở vị trí lẻ. Số 0x55555555 có biểu diễn nhị phân là 010101...01, khi and với n sẽ trả về khác 0 nếu trong n có 1 bit ở vị trí lẻ.

Kân team v3 đã nói:
não to thặc, đáng lẽ nên để đọc giả tự tìm hiểu

K có đoạn giải thích này thì sao mà hiểu được, :beat_shot:

Kân team v3 · 22/8/22

thuyduong2007 đã nói:
K có đoạn giải thích này thì sao mà hiểu được,

có 2 điểm ko ngờ thoy mà có gì khó đâu

tự tìm hiểu não mới to bằng người viết được

trừ cái code inverse square root gì ra ko tự hiểu được thoy

thảo luận Leetcode mỗi ngày

Senior Member

Junior Member

Senior Member

Senior Member

Đã tốn tiền

Senior Member

Member

Senior Member

Senior Member

Member

Senior Member

Senior Member

Senior Member

Senior Member

Đã tốn tiền

Đã tốn tiền

Senior Member

Senior Member

Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này