Leetcode Solution

Cho ma trận 2D, tìm tổng lớn nhất k phần tử từ ma trận 2D

• Số lượng phần tử được lấy từ hàng không vượt quá limit[i]

Input : grid = [[1,2],[3,4]], limits = [1,2], k = 2

Ouput : 7

Giải thích :

• Từ hàng thứ hai, ta có thể lấy nhiều nhất 2 phần tử. Các phần tử lấy được là 4 và 3.
• Tổng lớn nhất có thể của tối đa 2 phần tử được chọn là 4 + 3 = 7.

🔹 Bài này ta sẽ sử dụng Priority_queue và sorting

Quy trình thực hiện:

• 🟢 Bước 1: tại mỗi hàng ta sẽ sort và lấy ra limit[i] phần tử lớn nhất, cho vào priority_queue
• 🟡 Bước 2: duyệt vòng for để lấy ra k giá trị lớn nhất từ priority_queue

📋 Copy

class Solution {
public:
    long long maxSum(vector<vector<int>>& grid, vector<int>& limits, int k) {
        if(k == 0) return 0;
        long long total = 0, n = grid.size(), m = grid[0].size(), lid = 0;
        priority_queue<int>pq;
        for(int i = 0; i < n; i++) {
            sort(grid[i].rbegin(), grid[i].rend());
            for(int j = 0; j < min((int)grid[i].size(), limits[i]); j++) {
                pq.push(grid[i][j]);
            }
        }
        for(int i = 0; i < k; i++) {
            total = total + pq.top();
            pq.pop();
        }
       // cout << total << endl;
        return total;
    }
};

Cho một chuỗi dấu ngoặc đơn s, mỗi lần di chuyển, bạn có thể chèn thêm một dấu ngoặc đơn vào bất kỳ vị trí nào trong chuỗi.

• Nhiệm vụ: Tìm số lần chèn tối thiểu để chuỗi trở thành một chuỗi hợp lệ.

Input : ())

Ouput : 1

Giải thích : ta có thể chèn nó vào vị trí trước dấu ngoặc đầu tiên

Bài này ta sử dụng thuật toán tham lam

• nếu có 1 dấu (, ta tăng số lượng open lên 1
• nếu có 1 dấu ), ta giảm số lượng open với đk : (open > 0) còn không ta sẽ tăng số lượng dấu close

Quy trình thực hiện:

• 🟢Bước 1 : ta sử khởi tạo 2 biến close và open lần lượt = 0
• 🟡Bước 2 : làm theo các điều nêu bên trên, và kết quả chính là số lượng ngoặc đóng + mở, còn thiếu trong chuỗi

📋 Copy

class Solution {
public:
    int minAddToMakeValid(string s) {
        int open = 0, del = 0, close = 0;
        for(int i = 0; i < s.length(); i++) {
            if(s[i] == '(') {
                open++;
            } else {
                if(open > 0) {
                    open--;
                } else {
                    close++;
                }
            }
        }
        return open + close;
    }
};

Cho n các số nguyên không âm biểu diễn bản đồ độ cao, trong đó chiều rộng của mỗi thanh là 1, hãy tính lượng nước mà thanh có thể giữ lại sau khi mưa.

Input : height = [0,1,0,2,1,0,1,3,2,1,2,1]

Ouput : 6

Giải thích : bạn hãy bấm vào link để xem kỹ hình ảnh hơn

Bài này ta sử dụng 2 vector left và right, lần lượt di chuyển tử từ trái và phải qua 2 bên, để kiếm cột lớn nhất bên trái và lớn nhất bên phải

• 🔹 Ta có công thức để tính left và right là :
• ✔️ coleft[i] = max(coleft[i - 1], a[i]);
• ✔️ colright[i] = max(colright[i + 1], a[i]);

Quy trình thực hiện:

• 🟢 Bước 1: với mỗi lần duyệt qua một cột, ta sẽ tìm cột nhỏ, bên trái nhất và bên phải nhất, vì đó là giới hạn để lượng nước có thể ở trong bể mà không bị tràn ra
• 🟡 Bước 2: trừ cho giá trị a[i] tại cột hiện tại để biết lượng nước còn lại trong cột a[i]

📋 Copy

class Solution {
public:
    int trap(vector<int>& a) {
        int n = a.size(), water = 0;;
        vector<int>coleft(n, a[0]), colright(n, a[n - 1]);
        for(int i = 1; i < n; i++) {
            coleft[i] = max(coleft[i - 1], a[i]);
        }
        for(int i = n - 2; i >= 0; i--) {
            colright[i] = max(colright[i + 1], a[i]);
        }
        for(int i = 0; i < n; i++) {
            water = water + min(coleft[i], colright[i]) - a[i];
        }
        return water;
    }
};