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

Lập Trình Viên Số Khổ đã nói:

là cách pop ra khỏi list chứ sao lại tạo list là sao fen, vẫn tạo list thì nó vẫn thêm bộ nhớ mà

Nhấp để mở rộng...

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        if not root:
            return list()
        if root.val == targetSum and not root.left and not root.right:
            return [[root.val]]
        left = self.pathSum(root.left, targetSum - root.val)
        for x in left:
            x.insert(0, root.val)
        right = self.pathSum(root.right, targetSum - root.val)
        for x in right:
            x.insert(0, root.val)
        return left + right

thuyduong2007 đã nói:

Đọc nghiền ngẫm mãi cuối cùng cũng hiểu được ý tưởng.

Cái đoạn từ s[i, len] tính ra được s[i,len*2] trong O(1) thấy hack vkl.

Nhấp để mở rộng...

bribnt đã nói:

Cuối cùng cũng xong cách O(log^2 n)

https://leetcode.com/submissions/detail/806772612/


Xem tệp đính kèm 1398644

Spoiler: code

Ngoài việc chia các đoạn với các bit nhỏ. Thì trong trường hợp n không phải dạng 2^k-1 cần phải chia tiếp như sau.

Giả sử n = 1001'0011. Tính từ bit 1 thứ 2 từ phải sang:

• 1001'0011: [1000'0000 -> 1000'1111]
• 1001'0011: [1001'0000 -> 1001'0001]
• 1001'0011: [1001'0010 -> 1001'0011]

Tẩ cả các đoạn trên đều có độ dài dạng 2^k và có thể áp dụng thuật toán O(k) để tính tổng.

C++:

#define M 1'000'000'007
// return 2^x % M
uint64_t powM(uint64_t p, uint64_t x) {
    uint64_t base = p, res = 1;
    while (x) {
        if (x & 1) res = (res * base) % M;
        base = (base * base) % M;
        x >>= 1;
    }
    return res;
}

uint64_t prod(uint64_t x, uint64_t y) {
    return (x * y) % M;
}

uint64_t sum(uint64_t x, uint64_t y) {
    x += y;
    return x - (M & -(x >= M));
}

uint64_t diff(uint64_t x, uint64_t y) {
    int d = (int) x - (int) y;
    return d + (M & -(d < 0));
}

class Solution {
    // k: number bit
    // g: gap
    // pk: 4^(k*(2^(k-2))) - 1
    // p2gk: 2^(gk)
    // -> sum from [end - l + 1 .. end]
    uint64_t helper(uint64_t k, uint64_t pk, uint64_t p2gk, uint64_t l, uint64_t end, uint64_t g = 1)
    {
        if (g == l) return end;

        auto p4gk = prod(p2gk, p2gk); // 4^(gk)
        auto s1 = helper(k, pk, p4gk, l, end, g << 1);

        // s0 = 2^(gk) { s1 - g * [4^(k*2^k) - 1] / [4^(gk) - 1] }
        auto s0 = prod(
            p2gk, // 2^(gk)
            diff (
                s1,
                prod(
                    g,
                    prod(
                        pk,
                        powM(diff(p4gk, 1), M-2) // invmod of 4^(gk) -1 = (4^(gk) - 1) ^ (M - 2)
                    )
                )
            )
        );

        return sum(s0, s1);
    }

public:
    int concatenatedBinary(int n) {
    if (n == 1) return 1;

        uint64_t p2k = 4, // 2^k
                 p42k2 = 4, // 4^(2^(k-2)) = 2^(2^(k-1))
         res = 1,
                 k = 2;
        // sum from [1 .. 2^k)
        for (; p2k <= n + 1;
             p2k = sum(p2k, p2k), p42k2 = prod(p42k2, p42k2), ++k)
        {
            auto pk = powM(p42k2, k); // 4^(k*2^(k-2))
            // p2gk = 2^(gk) = 2^k = p2k
            // calculate sum from [ 2^(k-1) .. 2^k )
            auto h = helper(k, diff(pk, 1), p2k, 1 << (k - 1), (1 << k) - 1, 1);
            // res = h + res * 2^(k * 2^(k-1)) = res + h * pk
            res = sum(prod(res, pk), h);
        }

        // return if n = 2^k-1
        if (!(n & (n + 1))) return res;

        // sum from [2^k .. n)
        // check every 1-bit of n
        for (int kk = k - 2; kk >= 1; --kk) {
            if (n & (1 << kk)) {
                auto l = 1 << kk;
                auto pk = powM(p2k, l);
                auto h = helper(k, diff(pk, 1), p2k, l, (n ^ l) | (l - 1), 1);
                res = sum(prod(res, pk), h);
            }
        }

        // last bit
        if (n & 1) res = sum(prod(res, p2k), n^1);
        res = sum(prod(res, p2k), n);
        return res;
    }
};

Nhấp để mở rộng...

uint64_t powM(uint64_t p, uint64_t x) {
    uint64_t base = p, res = 1;
    while (x) {
        if (x & 1) res = (res * base) % M;
        base = (base * base) % M;
        x >>= 1;
    }
    return res;
}

Lập Trình Viên Số Khổ đã nói:

đâu ra O(1) có vòng for mà, nhưng mà chơi ko sang xài cái constexpr thì hôm nọ nghe bảo ko tính vào độ phức tạp gì ấy

Nhấp để mở rộng...

thuyduong2007 đã nói:

T hiểu ý fen rồi. K muốn tạo ra list mới như code hiện tại của t thì pop ra như fen nói cũng ok. Còn không thì đừng có tạo list ở lượt đi, traverse xuống lá. sum = target thì đi ngược lại tạo list.

Python:

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        if not root:
            return list()
        if root.val == targetSum and not root.left and not root.right:
            return [[root.val]]
        left = self.pathSum(root.left, targetSum - root.val)
        for x in left:
            x.insert(0, root.val)
        right = self.pathSum(root.right, targetSum - root.val)
        for x in right:
            x.insert(0, root.val)
        return left + right

Độ phức tạp cách này O(NLogN). Cách copy tại mỗi node bên trên của t thì là O(N^2). Cách pop của fen là O(N)

Nhấp để mở rộng...

​

Lập Trình Viên Số Khổ đã nói:

C++:

uint64_t powM(uint64_t p, uint64_t x) {
    uint64_t base = p, res = 1;
    while (x) {
        if (x & 1) res = (res * base) % M;
        base = (base * base) % M;
        x >>= 1;
    }
    return res;
}

powM(diff(p4gk, 1), M-2)


Ở trong C++ với x = M - 2 như này thì độ phức tạp bao nhiu vậy bác, log 2 ra hữu hạn, vẫn tính O(1) lun à

Nhấp để mở rộng...

thuyduong2007 đã nói:

Đầu vào là int nên cái len nó giới hạn <= 32, nên nó là hằng số => O(1)
Còn cái constexpr thì nó được tính tại compile time rồi, k tính vào run time.
Mà leetcode nó tính cả build time của C++ vào đó bác Kân,

Nhấp để mở rộng...

Kân team v3 đã nói:

mark constexpr để tính cái mảng kLe lúc compile time cho soành điệu thoy (tạo mảng magic number cũng y hệt) chứ còn cho biến số vào tham số nó vẫn chạy code như hàm bình thường

Nhấp để mở rộng...

Lập Trình Viên Số Khổ đã nói:

C++:

uint64_t powM(uint64_t p, uint64_t x) {
    uint64_t base = p, res = 1;
    while (x) {
        if (x & 1) res = (res * base) % M;
        base = (base * base) % M;
        x >>= 1;
    }
    return res;
}

powM(diff(p4gk, 1), M-2)


Ở trong C++ với x = M - 2 như này thì độ phức tạp bao nhiu vậy bác, log 2 ra hữu hạn, vẫn tính O(1) lun à

Nhấp để mở rộng...

Kân team v3 đã nói:

nó tính compile time vào thời gian chạy hèn gì run mãi ko được 0ms

bữa toy đọc code hỏi thằng kia sao mày ko để hằng số 0x... luôn đi mà viết constexpr tính ra hằng số đó làm mọe gì, nó bảo viết hằng xố thế đại loại là ko có self-documentation, viết constexpr cho dễ đọc (đéo dễ đọc tí nào)

đáng lẽ toy bảo thế mày viết thêm 1 dòng // explain nó là gì ko được à, tiết kiệm compile time mà thoy kệ mọe thằng khùng

bây giờ toy viết code tâm thần y hệt

Nhấp để mở rộng...

Lập Trình Viên Số Khổ đã nói:

Không của tui là NLogN fen
Traversal Complexity là đã O(N) rồi, nhưng ở mỗi lần dừng lại ở nút là: dừng N/2 lần (ví có N/2 nút lá) thì tui lại phải vòng for LogN nữa để lấy ra cái list

​

Nhấp để mở rộng...

bribnt đã nói:

Chắc không có chuyện đó đâu. Code nhiều template với constexpr thì compile mất cả giây là bình thường. Trong khi thời gian nó báo vẫn chỉ cỡ ms.

Sent from Xiaomi M2007J20CG using vozFApp

Nhấp để mở rộng...

bribnt đã nói:

Chắc không có chuyện đó đâu. Code nhiều template với constexpr thì compile mất cả giây là bình thường. Trong khi thời gian nó báo vẫn chỉ cỡ ms.

Sent from Xiaomi M2007J20CG using vozFApp

Nhấp để mở rộng...

Kân team v3 đã nói:

có cái tricky nữa là tính add.
bắt đầu từ add = 0001, tính add tiếp theo bằng cách tính add' = add << 1, rồi tính add = (add' << 4) + add' là được
add=0010.0010 thì tính ra 0100.0100.0100.0100 tương tự tính add' = add << 1 = 0100.0100, rồi dịch trái add; 8 bit (ko còn là 4 nữa) và cộng add' là ra next add = 0100.0100.0100.0100

vậy 1000.1001.1010.1011.1100 có thể tính lẹ 1000.1001.1010.1011 và 1100 là s (0,4) và s(4,1) rồi gộp lại bằng dịch trái và phép cộng, tất cả O(1)* hết

Nhấp để mở rộng...

KimSoHyunGoddness đã nói:

Em có thể góp ý là ngoài giải các bài toán trên leetcode ra thì các anh em trong group mỗi ngày tự nghĩ ra 1 bài toán nào đó, rồi đăng lên để các anh em cùng giải với nhau được không ạ.
Vừa giải quyết đc vấn đề cá nhân lại giúp anh em xử đc những case thân thuộc hơn.

Nhấp để mở rộng...