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

[tdat00]

30/6/2022:

• 1 câu medium hay
• do hôm qua thức khuyêa nên sáng nay đầu loạn vl
• Nghĩ 30p ms ra cái solution dùng prefix sum mạc dù time vẫn là O(nlogn) nhưng khá ngáo, nên cách này khỏi nói luôn
• Code solution 1: https://leetcode.com/submissions/detail/734675197/
• Đọc discuss thì thấy cách này ms chuẩn:
• Ví dụ ta có 2 số 6 và 9 để chuyển 2 số này theo yêu cầu thành 2 số giống nhau thì chọn bất kì số giống nhau đó từ 6->9 đều đc
• [6, 9] -> [7, 7] thì số lần chuyển sẽ là (7 - 6) + (9 - 7) = 3
• [6, 9] - [9, 9] thì số lần chuyển là (9 - 6) + (9 - 9) = 3
• ...
• Để chứng minh thì tưởng tưởng 6 là điểm A, 9 là điểm B;

View attachment 1238418

• Chọn 1 điểm C bất kì trên AB giống như việc chọn 1 số trong khoảng [6, 9]
• d1 + d2 = AB sẽ ko đổi -> đã cm
• nếu chọn điểm C ngoài khoảng AB thì tổng AC + CB > AB giống như việc chọn 1 số ngoài khoảng [6, 9]

• Như vậy sau khi sort thì giả sử đc mảng [1, 3, 7, 11, 12]
• xét số 1 và số 12 thì chọn 1 số trong khoảng 1 -> 12
• Khi bỏ 2 số 1 và 12 thì đc mảng [3, 7, 11] -> và lại chọn số có khoảng 3->7 nhỏ hơn khoảng trc
• cứ làm như vậy sẽ ra số cần chọn là nums[n / 2]
• Nguồn: https://leetcode.com/problems/minim...scuss/94932/Why-median-is-better-than-average
• Code: https://leetcode.com/submissions/detail/734675989/

Theo cái link của thím thì thấy 1 cách giải thích có vẻ dễ hiểu hơn, tôi đang thẩm

I have a simpler proof. The meet point must be somewhere between current min and max. No matter which point you pick, the total running length for min and max is the same, i.e. abs(min_point-meet_point)+abs(max_point-meet_point) = SOME_CONSTANT.



So, we can effectively reduce the problem size from n to n-2 by discarding min and max points. Do you see it? That is the definition of median, isn't it?



Let's have an example. suppose we have an array, [1,2,3,4,5,6,7]. The meet point must lie between 1 and 7. For any value in this range, the total running length for 1 and 7 is the same. So, array => [2,3,4,5,6]...



I hope it can help people who don't want to read some long proofs.

 

[Violet_7]

Theo cái link của thím thì thấy 1 cách giải thích có vẻ dễ hiểu hơn, tôi đang thẩm

đầu sáng này đang hơi loạn nên giải thích hơi khó hiểu xíu

 

[dagedage]

30/6
link problem: https://leetcode.com/problems/k-th-symbol-in-grammar/
1 bài đệ quy nhẹ nhàng đầu ngày

• độ dài của dãy luôn là số chẵn trừ dãy đầu tiên
• dãy n = dãy (n-1) + flip (dãy(n-1))

https://leetcode.com/submissions/detail/734458196/
hiih bài mình tự chọn vì làm dc nhé

 

[Sunday_Sunday]

hehe cuối tháng rồi show Badge nào
lâu lắm mới làm full 1 tháng

 

[Violet_7]

View attachment 1238527
hehe cuối tháng rồi show Badge nào
lâu lắm mới làm full 1 tháng

cx đc 3 tháng r

 

[dynamic programming]

30/6/2022:

• 1 câu medium hay
• do hôm qua thức khuyêa nên sáng nay đầu loạn vl
• Nghĩ 30p ms ra cái solution dùng prefix sum mạc dù time vẫn là O(nlogn) nhưng khá ngáo, nên cách này khỏi nói luôn
• Code solution 1: https://leetcode.com/submissions/detail/734675197/
• Đọc discuss thì thấy cách này ms chuẩn:
• Ví dụ ta có 2 số 6 và 9 để chuyển 2 số này theo yêu cầu thành 2 số giống nhau thì chọn bất kì số giống nhau đó từ 6->9 thì tổng số lần chuyển đều nhỏ nhất
• [6, 9] -> [7, 7] thì số lần chuyển sẽ là (7 - 6) + (9 - 7) = 3
• [6, 9] - [9, 9] thì số lần chuyển là (9 - 6) + (9 - 9) = 3
• ...
• Để chứng minh thì tưởng tưởng 6 là điểm A, 9 là điểm B;

View attachment 1238418

• Chọn 1 điểm C bất kì trên AB giống như việc chọn 1 số trong khoảng [6, 9]
• tổng số lần chuyển sẽ là d1 + d2 = AB sẽ ko đổi và sẽ nhỏ nhất
• nếu chọn điểm C ngoài khoảng AB thì tổng AC + CB > AB giống như việc chọn 1 số ngoài khoảng [6, 9]

• Như vậy sau khi sort thì giả sử đc mảng [1, 3, 7, 11, 12]
• xét số 1 và số 12 thì chọn 1 số trong khoảng 1 -> 12
• Khi bỏ 2 số 1 và 12 thì đc mảng [3, 7, 11] -> và lại chọn số có khoảng 3->7 nhỏ hơn khoảng trc
• cứ làm như vậy sẽ ra số cần chọn là nums[n / 2]
• Nguồn: https://leetcode.com/problems/minim...scuss/94932/Why-median-is-better-than-average
• Code: https://leetcode.com/submissions/detail/734675989/

Nếu như vậy thì khi size của mảng chẵn (có 2 giá trị ở giữa) thì chọn bất kì một giá trị nào giữa 2 giá trị đó đều phù hợp, nên cũng không hẳn là median bác nhỉ?

 

[thuyduong2007]

Nếu như vậy thì khi size của mảng chẵn (có 2 giá trị ở giữa) thì chọn bất kì một giá trị nào giữa 2 giá trị đó đều phù hợp, nên cũng không hẳn là median bác nhỉ?

thử làm đi, lấy median mà.

 

[GircoBoy]

Bài này mình chứng minh kiểu gọi khoảng cách từ tất cả đến thằng x là dist(x)
Đối với n lẻ, thằng median sẽ phân dãy thành 2 tập nhỏ hơn và lớn hơn nó, mỗi tập size m = (n-1)/2. Khi đó nếu dịch thằng median lên 1 thì dist(median+1) = dist(median) + (m+1) - m = dist(median) + 1 (m thằng nhỏ hơn + thằng median sẽ bị cộng lên 1, trong khi m thằng lớn hơn trừ đi 1). Tương tự khi dịch thằng median xuống 1. Khi đó đồ thị của hàm dist(x) sẽ có dạng hình chữ V với đáy min là thằng median.
Đối với n chẵn có thể chứng minh tương tự nhưng đồ thị sẽ có dạng \__/, với đáy là khoảng của 2 giá trị median trong mảng.
Tìm median thì sort lại là xong, hoặc rảnh thì có thể dùng quick select cải tiến xuống O(N) cũng đc

 

[Violet_7]

Nếu như vậy thì khi size của mảng chẵn (có 2 giá trị ở giữa) thì chọn bất kì một giá trị nào giữa 2 giá trị đó đều phù hợp, nên cũng không hẳn là median bác nhỉ?

đúng r đó bác, size lẻ lấy giá trị ở vị trí n / 2, còn size chẵn thì lấy trong khoảng 2 số ở giữa mảng, từ nums[n/2 - 1] -> nums[n/2] đều đc, mà cả 2 th đều có số nums[n / 2] nên lấy số đó luôn

 

[Đời Cơ Bản Là Buồn]

Spoiler

class Solution {
  public:
    int minMoves2(vector<int> &nums) {
        nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end());
        int median = nums[nums.size() / 2];
        int count = 0;
        for (int num : nums) {
            count += abs(num - median);
        }
        return count;
    }
};

Cách của bổn tọa

 

[ngoctan_95]

View attachment 1238527
hehe cuối tháng rồi show Badge nào
lâu lắm mới làm full 1 tháng

Tháng này làm bữa đực bữa cái

 

[_Gia_Cat_Luong_]

Mới start từ hồi mở topic tới h. Hy vọng tháng 7 sẽ được badge.

 

[trinity]

mọi người khi làm mà submit bị sai, thì có dùng testcase sai đó để sửa không hay là tự tìm lỗi vậy?

 

[ngoctan_95]

30/6/2022:

• 1 câu medium hay
• do hôm qua thức khuyêa nên sáng nay đầu loạn vl
• Nghĩ 30p ms ra cái solution dùng prefix sum mạc dù time vẫn là O(nlogn) nhưng khá ngáo, nên cách này khỏi nói luôn
• Code solution 1: https://leetcode.com/submissions/detail/734675197/
• Đọc discuss thì thấy cách này ms chuẩn:
• Ví dụ ta có 2 số 6 và 9 để chuyển 2 số này theo yêu cầu thành 2 số giống nhau thì chọn bất kì số giống nhau đó từ 6->9 thì tổng số lần chuyển đều nhỏ nhất
• [6, 9] -> [7, 7] thì số lần chuyển sẽ là (7 - 6) + (9 - 7) = 3
• [6, 9] - [9, 9] thì số lần chuyển là (9 - 6) + (9 - 9) = 3
• ...
• Để chứng minh thì tưởng tưởng 6 là điểm A, 9 là điểm B;

View attachment 1238418

• Chọn 1 điểm C bất kì trên AB giống như việc chọn 1 số trong khoảng [6, 9]
• tổng số lần chuyển sẽ là d1 + d2 = AB sẽ ko đổi và sẽ nhỏ nhất
• nếu chọn điểm C ngoài khoảng AB thì tổng AC + CB > AB giống như việc chọn 1 số ngoài khoảng [6, 9]

• Như vậy sau khi sort thì giả sử đc mảng [1, 3, 7, 11, 12]
• xét số 1 và số 12 thì chọn 1 số trong khoảng 1 -> 12
• Khi bỏ 2 số 1 và 12 thì đc mảng [3, 7, 11] -> và lại chọn số có khoảng 3->7 nhỏ hơn khoảng trc
• cứ làm như vậy sẽ ra số cần chọn là nums[n / 2]
• Nguồn: https://leetcode.com/problems/minim...scuss/94932/Why-median-is-better-than-average
• Code: https://leetcode.com/submissions/detail/734675989/

Bài này bữa mình làm bằng bruteforce, bài này e dùng lại cách của bài đập chặn nước hôm bữa
Xét tất cả chênh lệch delta giữa chặn a và b, chênh lệch sẽ được chọn chênh lệch thấp
Tiếp tục xét chênh lệch giữa tổng các chênh lệch và chênh lệch thấp thì nó là giá trị tổng của các đập chặn, mà cách này hơi chuối, chạy tới 525ms , chưa tìm ra cách khác

public int minMoves2(int[] nums) {
        long res = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            long deltaCounted = 0;
            for (int j = 0; j < nums.length; j++) {
                // Find maximum delta
                int deltaWithBrute = Math.abs(nums[j] - nums[i]);
                deltaCounted = deltaCounted + deltaWithBrute;
            }
            // Check min with min deltaCounted
            res = Math.min(res, deltaCounted);
        }
        return  Math.toIntExact(res);
    }

 

[_Gia_Cat_Luong_]

mọi người khi làm mà submit bị sai, thì có dùng testcase sai đó để sửa không hay là tự tìm lỗi vậy?

Có fen ơi. K đủ trình tự tìm

 

[ngoctan_95]

mọi người khi làm mà submit bị sai, thì có dùng testcase sai đó để sửa không hay là tự tìm lỗi vậy?

Có thím, có test case nào thì phân loại r ném vào test thôi, mình thường ném vào intellij chạy thử trước khi run trên này, trên này k cho debug, cho out println thôi à, nhìn hoa mắt lắm

 

[Sunday_Sunday]

mọi người khi làm mà submit bị sai, thì có dùng testcase sai đó để sửa không hay là tự tìm lỗi vậy?

không nhìn được testcase mà tự tìm bug thì kinh dị quá

 

[_Gia_Cat_Luong_]

Có thím, có test case nào thì phân loại r ném vào test thôi, mình thường ném vào intellij chạy thử trước khi run trên này, trên này k cho debug, cho out println thôi à, nhìn hoa mắt lắm

Trước cũng hay bê về IDE tự làm. Mà sau lười toàn làm trên web luôn. Print riết cũng quen, mệt mấy bài đệ quy thôi.

 

[ngoctan_95]

Trước cũng hay bê về IDE tự làm. Mà sau lười toàn làm trên web luôn. Print riết cũng quen, mệt mấy bài đệ quy thôi.

Làm js thì VS, còn Java thì intellij, mình thì viết ngay tại main )))))

 

[bribnt]

Bài hôm nay đáp án là median của dãy số.

Đây là cách chứng minh tạm với n chẵn:

Spoiler: chứng minh với n chẵn

Với n lẻ chứng minh tương tự. Có thể có cách tổng quát hơn.

Spoiler: code mất 3 dòng

class Solution {
public:
    int minMoves2(vector<int>& nums) {
        std::nth_element(begin(nums), begin(nums) +nums.size() / 2, end(nums));
        auto median = nums[nums.size() / 2];
        return std::accumulate(begin(nums), end(nums), 0LL, [median](auto a, auto b) {
            return a + std::abs(b - median);
        });
    }
};