thảo luận Leetcode contest, đường tới Guardian

freedom.9 · 27/4/24

Đm nó làm câu 1 submit sai 1 lần ạ :ah:

thiếu mẹ cái if tốn thời gian quá
Làm câu 2 8 phút câu 1 mất tận 15 phút, qua đi nhậu về sáng đầu óc ngơ ngơ quá =((

ti_say_hi · 27/4/24

Nay em cũng chỉ được có 2 câu.
Lúc đầu làm câu 1, em nhảy qua câu 3 liền. Xong hơn 1h không giải được mwois qua câu 2.

Câu 3 em đếm tổ hợp. Tuy nhiên bị bí đoạn xử lí giao nhau.
Ví dụ zero = 4, one = 3, limit 2

Thì answer là 7C4 - (Số subarray có 3 số 0 liền kề) - (số subarray có 4 số 0 liền kề) - (số sub array có 3 số 1 liền kề).

Nhưng bị bí ở chỗ là (số subarray có 4 số 0 liền kề) có chứa phần đếm của (Số subarray có 3 số 0 liền kề)

LmaoSuVuong · 27/4/24

freedom.9 đã nói:
Đm nó làm câu 1 submit sai 1 lần ạ thiếu mẹ cái if tốn thời gian quá

nay e làm chay ko xài ide, câu 1 thì bỏ biến đếm nhầm chỗ, chạy tay hơn chục lần đúng r mà sao báo wrong hoài.
câu 2 thì biến đếm int ngồi hơn 1 tiếng ko biết vì sao sai

ti_say_hi · 27/4/24

honda stone đã nói:
ý tưởng dp cho q3 với q4 nó là xét f[j][0] và f[j][1]
ý nghĩa là số lượng dãy độ dài i, có j số bằng 0 (hoặc 1) và kết thúc bằng 0 và 1
em cũng làm giống các bố top đầu nhưng cài hàm dp bị sai sml

Hợp lý nhể, dp['i'][j][0/1] là số dãy độ dài i, có j phần tử bằng 0 và kết thúc bằng 0/1. (i-j) = số lương phần tử 1 trong mảng rồi.
Sao em lại đâm đầu giải bài này theo math

Đúng hơn là cái hint là tuần này câu khó phải giải bằng dp, vì daily tuần này là dp

honda stone · 27/4/24

ti_say_hi đã nói:
Hợp lý nhể, dp['i'][j][0/1] là số dãy độ dài i, có j phần tử bằng 0 và kết thúc bằng 0/1. (i-j) = số lương phần tử 1 trong mảng rồi.
Sao em lại đâm đầu giải bài này theo math

Đúng hơn là cái hint là tuần này câu khó phải giải bằng dp, vì daily tuần này là dp

hic em mới chơi voz không quen cú pháp
nên nãy gõ chỗ đấy bị sai xong xoá

hieunm3538 · 27/4/24

Bài 3 xem giải dp theo kết thúc bằng 0 và kết thúc bằng 1 hay thật =((

LmaoSuVuong · 28/4/24

hôm qua rank 14k chỉ hơn dalit 1 tí

hôm nay gỡ gạc nào

freedom.9 · 28/4/24

Rank về ae ơi :ah:

JustAnOtherClone · 28/4/24

lại nghỉ sớm rồi, mấy cái bit bủng này có làm bao giờ đâu @@

lovelyly · 28/4/24

Làm được 3 câu rồi, câu 4 khó quá

hieunm3538 · 28/4/24

Câu 4 khoai thật sự =((

Các bác cố lên, câu 3 bitwise chỉ là cái vỏ thôi chứ không phải thao tác bitwise đâu

honda stone · 28/4/24

từ hôm qua đến giờ em làm bài như

nay q2 q3 còn phải submit mấy lần mới ac
thôi đi ngủ :cautious:

TLE_WA · 28/4/24

Câu cuối phân tích thay đổi của frequency sau khi gặp phần tử trùng khó thật :big_smile:

lovelyly · 28/4/24

Câu 4 có tầm 500 người làm được, trong đó không có tôi

Câu 3 thì t làm theo ý tưởng thế này:

nums[0] = x
nums[k]: giữ nguyên các bit 1 của x, thay các bit 0 của x thành biểu diễn nhị phân của k

Ví dụ mà Leetcode cho:
Input: n = 3, x = 4
Output: 6
Explanation: nums can be [4,5,6] and its last element is 6.

x biểu diễn theo bit là 0100
0 = 0b000 => nums[0] biểu diễn theo bit: 0100
1 = 0b001 => nums[1] biểu diễn theo bit: 0101
2 = 0b010 => nums[2] biểu diễn theo bit: 0110

ti_say_hi · 28/4/24

Haizz, câu 3 làm hơn 1h mà không ra. Em thấy cũng là flip các bit 0 của X với (n-1) lần thì được nhưng vấn đề là có xen kẽ bit 1 ở giữa nhưng lại không hanlde được


class Solution {
public:
    long long minEnd(int n, int x) {
        if (n == 1) return x;
      
        bool bitZero[32];
        int bit[32];
      
        for (int i = 0; i < 32; i++) {
            if (((1 << i) & x) == 0) {
                bitZero[i] = true;
            }
        }
      

        int t = 0;
        for (int i = 1; i <= n-1; i++) {
            int numbit = (t > 0) ? static_cast<int>(ceil(log2(t))) : 0;
            if (bitZero[numbit]) {
                t = t + 1;
            } else {
                t = t + x + (1 << numbit);
            }
        }
      
        return t + x;
    }
};

honda stone · 28/4/24

tại sao em không nghĩ ra là binary search để đi đếm số dãy con có tối đa k phần tử đôi một khác nhau nhỉ

nó là biến thể của bài này LC992

ti_say_hi · 28/4/24

lovelyly đã nói:
Câu 4 có tầm 500 người làm được, trong đó không có tôi
Câu 3 thì t làm theo ý tưởng thế này:

nums[0] = x
nums[k]: giữ nguyên các bit 1 của x, thay các bit 0 của x thành biểu diễn nhị phân của k

Ví dụ mà Leetcode cho:
Input: n = 3, x = 4
Output: 6
Explanation: nums can be [4,5,6] and its last element is 6.

x biểu diễn theo bit là 0100
0 = 0b000 => nums[0] biểu diễn theo bit: 0100
1 = 0b001 => nums[1] biểu diễn theo bit: 0101
2 = 0b010 => nums[2] biểu diễn theo bit: 0110

Em cũng nhận thấy tính chất như này, nhưng lúc cài đặt không handle được do có bit 1 xen kẽ

TLE_WA · 28/4/24

ti_say_hi đã nói:
Em cũng nhận thấy tính chất như này, nhưng lúc cài đặt không handle được do có bit 1 xen kẽ

thì bạn chỉ cần chọn ra các vị trí có bit = 0 để add thôi mà

honda stone · 28/4/24

ti_say_hi đã nói:
Em cũng nhận thấy tính chất như này, nhưng lúc cài đặt không handle được do có bit 1 xen kẽ

em đặt y = n - 1
duyệt các bit từ bit 0 trở đi
nếu có bit i nào của x bằng 1, thì gán bit i của y cũng bằng 1, tất cả các bit ở trước (i + 1 đến ...) thì dịch sang trái

honda stone · 28/4/24

chắc còn phải chôn chân ở knight dài dài =((

còn lâu mới lên được guardian

thảo luận Leetcode contest, đường tới Guardian

Senior Member

Junior Member

Senior Member

Junior Member

Junior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Junior Member

Junior Member

Senior Member

Junior Member

Junior Member

Junior Member

Junior Member

Junior Member

Junior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này