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

ngoctan_95 said:

Có 1 bài cũng khá hay, các thím tham khảo thử
https://leetcode.com/problems/trapping-rain-water/
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Ý tưởng sơ bộ: Nhìn hình và output, mình nghĩ ngay tới vét cạn binary (left = 0, right = length - 1)

Click to expand...

, ngược lại sẽ bằng --right
Lưu lại biến cả 2 trường hợp, kiểm tra tất cả phần tử ++left mà nhỏ hơn mức hiện tại, ngược lại kiểm tra tất cả phần tử --right cho tới khi so sánh bằng với mức hiện tại

ngoctan_95 said:

Moá cuối cùng cũng làm xong cái bài này , mất đúng nửa ngày luôn
Ý tưởng: Binary vét cạn left = 0, right = length - 1
Có 2 trường hợp cần xét:
height [ left ] - height [ right ] <= 0 mực nước sẽ bằng container có height bé hơn, ++left ,mực nước sẽ bằng height

, ngược lại sẽ bằng --right
Lưu lại biến cả 2 trường hợp, kiểm tra tất cả phần tử ++left mà nhỏ hơn mức hiện tại, ngược lại kiểm tra tất cả phần tử --right cho tới khi so sánh bằng với mức hiện tại
View attachment 1232162​

Click to expand...

_Gia_Cat_Luong_ said:

Java lúc nào cũng runtime ảo diệu v nhỉ :v

Click to expand...

ngoctan_95 said:

Có 1 bài cũng khá hay, các thím tham khảo thử
https://leetcode.com/problems/trapping-rain-water/
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Ý tưởng sơ bộ: Nhìn hình và output, mình nghĩ ngay tới vét cạn binary (left = 0, right = length - 1)

Click to expand...

ngoctan_95 said:

Moá cuối cùng cũng làm xong cái bài này , mất đúng nửa ngày luôn
Ý tưởng: Binary vét cạn left = 0, right = length - 1
Có 2 trường hợp cần xét:
height [ left ] - height [ right ] <= 0 mực nước sẽ bằng container có height bé hơn, ++left ,mực nước sẽ bằng height

, ngược lại sẽ bằng --right
Lưu lại biến cả 2 trường hợp, kiểm tra tất cả phần tử ++left mà nhỏ hơn mức hiện tại, ngược lại kiểm tra tất cả phần tử --right cho tới khi so sánh bằng với mức hiện tại
View attachment 1232162​

Click to expand...

class Solution {
public:
    int trap(vector<int>& height) {
        vector<int> trap(height.size(), 0);
        int curMax = 0;
        for (int i = 0; i < height.size(); ++i) {
            curMax = max(curMax, height[i]);
            trap[i] = curMax - height[i];
        }
        curMax = 0;
        int ret = 0;
        for (int i = height.size() - 1; i >= 0; --i) {
            curMax = max(curMax, height[i]);
            ret += min(curMax - height[i], trap[i]);
        }
        return ret;
    }
};

thuyduong2007 said:

Ý tưởng của mình đơn giản hơn. Nước sẽ phải chảy qua 2 đầu, hoặc bên trái hoặc bên phải và lượng nước đọng lại + h luôn <= h max bên trái và bên phải. Nên chỉ cần loop 2 lần là sẽ tính được h max trái, phải tại mỗi điểm => lượng đọng lại => lượng nước cần tính.

C++:

class Solution {
public:
    int trap(vector<int>& height) {
        vector<int> trap(height.size(), 0);
        int curMax = 0;
        for (int i = 0; i < height.size(); ++i) {
            curMax = max(curMax, height[i]);
            trap[i] = curMax - height[i];
        }
        curMax = 0;
        int ret = 0;
        for (int i = height.size() - 1; i >= 0; --i) {
            curMax = max(curMax, height[i]);
            ret += min(curMax - height[i], trap[i]);
        }
        return ret;
    }
};

Click to expand...

ngoctan_95 said:

Đúng rồi, chả hiểu, lúc thì 99%, lúc thì 72%, chạy lại thì còn có 30% , nhiều lúc k biết cải thiện ntn hay là code mình ngu mà tìm quài chưa thấy chỗ cải thiện , hoang mang vãi

Click to expand...

• 1 bài khá xàm lol
• Vì số n là tổng các số nhị phân nên cứ mỗi lần ta giảm 1 đơn vị cho 1 chữ số, nếu là chữ số 0 thì ko giảm -> mỗi lần giảm sẽ tạo đc 1 số nhị phân, giảm cho đến khi ra số 0 -> số lần giảm ít nhất là chữ số lớn nhất
• VD: số "5213"

• Nghĩ 2 phút là ra, cơ mà nghĩ xong cứ thấy nó dễ dễ nên éo dám submit, check lại, dẫn đến mất 5p
• Code: https://leetcode.com/submissions/detail/732137726/

tdat00 said:

Thím @Violet_7 dậy sớm thế, tôi mới ăn sáng xong giờ mới bắt đầu uống hớp cafe

Click to expand...

Violet_7 said:

thường ngày dạy 6h30 luyện leetcode r

Click to expand...

Violet_7 said:

27/6/2022:

• 1 bài khá xàm lol
• Vì số n là tổng các số nhị phân nên cứ mỗi lần ta giảm 1 đơn vị cho 1 chữ số, nếu là chữ số 0 thì ko giảm -> mỗi lần giảm sẽ tạo đc 1 số nhị phân, giảm cho đến khi ra số 0 -> số lần giảm ít nhất là chữ số lớn nhất
• VD: số "5213"

"5241" -> "4130" + "1111"
"4130" -> "3010" + "1110"
"3010" -> "2000"+ "1010"
"2000"-> "1000" +"1000"
"1000"-> "0000" +"1000"

• Nghĩ 2 phút là ra, cơ mà nghĩ xong cứ thấy nó dễ dễ nên éo dám submit, check lại, dẫn đến mất 5p
• Code: https://leetcode.com/submissions/detail/732137726/

Click to expand...

• Nếu chuỗi s có 3 ký tự a, b, c
• Nếu chuỗi s có 4 ký tự a, b, c, d
• Néu chuỗi s có K ký tự a, b, c, d, ..., k

Sunday_Sunday said:

câu hôm nay hơi dễ
Ngẫu nhiên thêm câu này
#1982 Hard

Click to expand...

tdat00 said:

Có 1 bài cũng trick tương tự như bài hôm nay nè, tôi đánh giá khá hay, nếu đem đi PV có thể test ứng viên từ mức độ dễ nâng dần đến mức độ khó
https://leetcode.com/problems/remove-palindromic-subsequences/

Mặc dù bài này Easy, các thím có thể mở rộng ra:

• Nếu chuỗi s có 3 ký tự a, b, c
• Nếu chuỗi s có 4 ký tự a, b, c, d
• Néu chuỗi s có K ký tự a, b, c, d, ..., k

Click to expand...