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

tdat00

Đã tốn tiền
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:

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

C++:
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);
        });
    }
};

Vozer chỉ giỏi code chứ có giỏi toán đâu, nhìn cứ như chó đọc bảng cửu chương :(

Sent from Samsung SM-A528B using vozFApp
 

bribnt

Đã tốn tiền
Vozer chỉ giỏi code chứ có giỏi toán đâu, nhìn cứ như chó đọc bảng cửu chương :(

Sent from Samsung SM-A528B using vozFApp

Còn một cách chứng minh nữa khá đơn giản.

Bài toán: tìm min f(b) = min sum( |b - a_i |).

Lấy đạo hàm ta có f'(b) = sum[ (b - a_i) / |b - a_i| ]
Để ý thấy phần bên trong sum chỉ có giá trị là 1 hoặc -1. Để đạo hàm bằng 0 thì số lượng phần tử 1 phải bằng số lượng phần từ -1, tức b phải là median của a.

Vấn đề ở đây là hàm |x| không khả vi tại x = 0, nên có thể cần phải sửa chứng minh đôi chút để tránh trường hợp b bằng một số trong list a.
 
Tui lại giải thích như này:
chọn điểm move là giữa 2 mút (2 số trên array) hoặc mút (số trên array) là như nhau.

Suy ra ta xét điểm move đến là mút (tức là các điểm trên array)
ví dụ: A,B*,C,D,E,F,G

nếu điểm cần move đến là B, ta tìm điểm tối ưu hơn bằng cách move đến điểm [C]
lý do tối ưu hơn là: Thiệt hại ít và lợi nhiều.

thiệt hại đoạn BC đối với số lương điểm bên trái của B (là điểm A) tức là thiệt hại 1*BC , còn lại lợi BC với số lượng điểm bên phải của B là c,d,e,f,g. vậy là lợi 4*BC. (4 điểm này ko phải chạy đến tận B nữa mà chỉ cần chạy đến C thôi)

Suy ra Move đến giữa là ra điểm tối ưu.

Move sang phải tiếp thì lại thành thiệt nhiều hơn lợi.
 

_Gia_Cat_Luong_

Senior Member
Tui lại giải thích như này:
chọn điểm move là giữa 2 mút (2 số trên array) hoặc mút (số trên array) là như nhau.

Suy ra ta xét điểm move đến là mút (tức là các điểm trên array)
ví dụ: A,B*,C,D,E,F,G

nếu điểm cần move đến là B, ta tìm điểm tối ưu hơn bằng cách move đến điểm [C]
lý do tối ưu hơn là: Thiệt hại ít và lợi nhiều.

thiệt hại đoạn BC đối với số lương điểm bên trái của B (là điểm A) tức là thiệt hại 1*BC , còn lại lợi BC với số lượng điểm bên phải của là c,d,e,f,g. vậy là lợi 4*BC. (4 điểm này ko phải chạy đến tận B nữa mà chỉ cần chạy đến C thôi)

Suy ra Move đến giữa là ra điểm tối ưu.

Move sang phải tiếp thì lại thành thiệt nhiều hơn lợi.
Vẫn là câu cũ. Thím là CTO mạo danh fresher à.
 

Zayt__

Senior Member
Bài nay mất 1 lần ngu submit trung bình cộng, lần sau dùng median thấy đúng mà không biết chứng minh nên thôi làm trâu bằng prefix sum mất thêm 1 vòng lặp:sure:
Sort dãy.
Với mỗi vị trí i chia dãy làm 2 nửa với left và right là số moves để biến dãy trái và phải thành nums.
Nếu dãy biến từ nums[i-1] thành nums thì phần dư (nums - nums[i-1]) sẽ được cộng lần lượt cho i thằng bên trái và trừ đi cho (nums.length -i) thằng bên phải.
Số moves tối ưu sẽ là của thằng i có left + right nhỏ nhất
Python:
class Solution:
    def minMoves2(self, nums: List[int]) -> int:
        nums.sort()
    
        left = 0
        right = 0
        for i in range(1, len(nums)):
            right += nums[i] - nums[0]

        res = right
        for i in range(1, len(nums)):
            delta = nums[i] - nums[i-1]
            left +=  delta * i
            right -= delta * (len(nums) - i)
            res = min(res, left + right)

        return res
 
không nhìn được testcase mà tự tìm bug thì kinh dị quá :confused::confused::confused:
Trước làm bên hackerrank nó chỉ hiện số lượng testcase bị fail. Muốn mở phải mất point gì đó nên toàn tự mò dựa vào kn, dò lại code tìm bug, :big_smile:. Thường nếu thấy sai nhiều testcase tức là cách làm sai luôn rồi, còn nếu chỉ sai vài testcase thì do tràn số.
 

ngoctan_95

Senior Member
Hôm nay rảnh lên xem thử 1 bài lạ
https://leetcode.com/problems/divide-two-integers
Thím nào rảnh giải chung cho vui nhé


Code:
Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2.

Return the quotient after dividing dividend by divisor.

Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For this problem, if the quotient is strictly greater than 231 - 1, then return 231 - 1, and if the quotient is strictly less than -231, then return -231.
 

tdat00

Đã tốn tiền
Hôm nay rảnh lên xem thử 1 bài lạ
https://leetcode.com/problems/divide-two-integers
Thím nào rảnh giải chung cho vui nhé


Code:
Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2.

Return the quotient after dividing dividend by divisor.

Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For this problem, if the quotient is strictly greater than 231 - 1, then return 231 - 1, and if the quotient is strictly less than -231, then return -231.

Bài này chỉ rườm rà ở cái edge case chia int.Min hoặc int.Max cho -1 thôi, chứ các case khác cứ trừ dần là ra. Dùng mấy ngôn ngữ ko giới hạn kiểu dữ liệu như python thì lại càng dễ.

Sent from Samsung SM-A528B using vozFApp
 

ngoctan_95

Senior Member
Bài này chỉ rườm rà ở cái edge case chia int.Min hoặc int.Max cho -1 thôi, chứ các case khác cứ trừ dần là ra.

Sent from Samsung SM-A528B using vozFApp
Dễ vậy thì em đã không fail vì lí do Time Exceed Limit tới 7 lần =((
 

bribnt

Đã tốn tiền
Hôm nay rảnh lên xem thử 1 bài lạ
https://leetcode.com/problems/divide-two-integers
Thím nào rảnh giải chung cho vui nhé


Code:
Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2.

Return the quotient after dividing dividend by divisor.

Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For this problem, if the quotient is strictly greater than 231 - 1, then return 231 - 1, and if the quotient is strictly less than -231, then return -231.

Bài này xem lại mới thấy đã làm 5 năm rồi.
Không cho * / % thì dùng | -.

Cách làm thì giống hết cách chia hồi tiểu học nhưng còn dễ hơn vì chỉ phải thao tác với số nhị phân.
Lấy đoạn đầu tiên của số bị chia rồi dịch bit, trừ dần cho số chia.
 

ngoctan_95

Senior Member
Bài này xem lại mới thấy đã làm 5 năm rồi.
Không cho * / % thì dùng + -.

Cách làm thì giống hết cách chia hồi tiểu học nhưng còn dễ hơn vì chỉ phải thao tác với số nhị phân.
Lấy đoạn đầu tiên của số bị chia rồi dịch bit, trừ dần cho số chia.
Yes nó đó hehe, e nãy không tìm ra cách dịch bit, quên mất nên 7 lần submit bị time exceed :D
 

tdat00

Đã tốn tiền
Yes nó đó hehe, e nãy không tìm ra cách dịch bit, quên mất nên 7 lần submit bị time exceed :D

Đầu tiên tôi trừ dần divisor xem thử ra sao thù bị TLE, thấy vậy nên biết chỉ còn cách dùng bitwise thôi, ngồi ngẫm 1 hồi là ra.

Sent from Samsung SM-A528B using vozFApp
 

Violet_7

Senior Member
Hôm nay rảnh lên xem thử 1 bài lạ
https://leetcode.com/problems/divide-two-integers
Thím nào rảnh giải chung cho vui nhé


Code:
Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2.

Return the quotient after dividing dividend by divisor.

Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For this problem, if the quotient is strictly greater than 231 - 1, then return 231 - 1, and if the quotient is strictly less than -231, then return -231.
Làm cách đây 1 tháng. Câu này khá xàm lol nhà thím, nó bảo đ đc dùng x, /, mod thì nói mẹ là dùng bit đi thế mà cứ dấu dấu. Nhìn lượng dislike là bt
 

ngoctan_95

Senior Member
Làm cách đây 1 tháng. Câu này khá xàm lol nhà thím, nó bảo đ đc dùng x, /, mod thì nói mẹ là dùng bit đi thế mà cứ dấu dấu. Nhìn lượng dislike là bt
Hahaha, dù sao cũng nhớ dc thêm techstack thôi :love:
 

tdat00

Đã tốn tiền
Làm cách đây 1 tháng. Câu này khá xàm lol nhà thím, nó bảo đ đc dùng x, /, mod thì nói mẹ là dùng bit đi thế mà cứ dấu dấu. Nhìn lượng dislike là bt

Tôi nghĩ dislike do cái edge case tràn số kìa, tôi fail mấy lần cũng vì mấy test đó. Điên quá hard code mấy cái edge case luôn :rolleyes:

Sent from Samsung SM-A528B using vozFApp
 

Violet_7

Senior Member
Tôi nghĩ dislike do cái edge case tràn số kìa, tôi fail mấy lần cũng vì mấy test đó. Điên quá hard code mấy cái edge case luôn :rolleyes:

Sent from Samsung SM-A528B using vozFApp
Case tràn số thì phải nghĩ từ đầu chứ thím, vì lúc đầu chắc chắn phải giá trị tuyệt đối cả 2 số nên phải loại trừ th số INT_MIN luôn.
 

tdat00

Đã tốn tiền
Case tràn số thì phải nghĩ từ đầu chứ thím, vì lúc đầu chắc chắn phải giá trị tuyệt đối cả 2 số nên phải loại trừ th số INT_MIN luôn.

Solution của tôi là đổi dấu trước để hàm chia luôn nhận 2 số nguyên dương => đổi dấu trước khi chia nó nhập nhằng giữa INT_MIN và INT_MAX
ONplOnR.png


Sent from Samsung SM-A528B using vozFApp
 

_Gia_Cat_Luong_

Senior Member
Hôm nay có vẻ bài dễ quá ae không quan tâm luôn nhỉ:
https://leetcode.com/problems/maximum-units-on-a-truck/

  • Để có units lớn nhất thì cứ lựa loại box nào có numberOfUnitsPerBox lớn nhất bỏ vào xe trước là được
  • Sort mảng lại theo numberOfUnitsPerBox giảm dần
  • Duyệt mảng, cộng số lượng unit tương ứng với số box nếu còn có thể
  • Đầy xe hoặc hết mảng thì dừng, trả về kết quả

Mồm nói sort chứ implement bằng heap, tại thích:
https://leetcode.com/submissions/detail/735512136/
 

tdat00

Đã tốn tiền
Nay bài dễ quá thì thảo luận mấy cái ngoài lề đi các thím. Các thím hay debug test case như thế nào? Trường hợp đệ quy thì làm sao để dễ theo dõi...

Cá nhân tôi thì cứ out ra console thôi. Tôi thường ghi output 2 lần: 1 lần ở đầu hàm, 1 lần ở cuối hàm. Dựa vào đó có thể hình dung ra flow:

Code:
public void func(int a, int b, int c)
{
    Console.WriteLine("starting func($0, $1, $2)", a, b, c);
    ........
    Console.WriteLine("finished func($0, $1, $2)", a, b, c);
}

Sent from Samsung SM-A528B using vozFApp
 
Top