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

Arik97

Senior Member
Weekly contest sáng nay có lộn bộ đề ko mà easy thế nhỉ :D:D

Sent from Samsung SM-G986U1 using vozFApp
 

bribnt

Đã tốn tiền
Công nhận bài hnay khó thật, trước từng làm qua rồi mà h làm lại vẫn thấy chua :ROFLMAO::ROFLMAO:

Không hiểu sao mình thấy bài hard hôm nay dễ hơn bài medium hôm qua. Khá straightforward để tìm quy tắc QHĐ, không lắt léo gì.

Cách nghĩ của bài này là:
  • với dãy có 1, 2, .., n-1,
  • Thử thêm n vào thì sẽ có n vị trí khác nhau,
  • Trừ vị trí cuối thì tất cả các vị trí còn lại đều tăng số Inverse Pair vì n lớn hơn tất cả các số có sẵn trong dãy,
  • Từ đó dễ suy ra công thức QHĐ: T(n, k) = T(n-1, k) + T(n-1, k-1) + ... + T(n-1, k-n+1).

Cái bước thử chèn n vào là khá tự nhiên, còn những phần còn lại chỉ là tính toán + / - cơ bản.

Sent from HUAWEI DBY-W09 using vozFApp
 

trinhtrang22

Junior Member
Không hiểu sao mình thấy bài hard hôm nay dễ hơn bài medium hôm qua. Khá straightforward để tìm quy tắc QHĐ, không lắt léo gì.

Cách nghĩ của bài này là:
  • với dãy có 1, 2, .., n-1,
  • Thử thêm n vào thì sẽ có n vị trí khác nhau,
  • Trừ vị trí cuối thì tất cả các vị trí còn lại đều tăng số Inverse Pair vì n lớn hơn tất cả các số có sẵn trong dãy,
  • Từ đó dễ suy ra công thức QHĐ: T(n, k) = T(n-1, k) + T(n-1, k-1) + ... + T(n-1, k-n+1).

Cái bước thử chèn n vào là khá tự nhiên, còn những phần còn lại chỉ là tính toán + / - cơ bản.

Sent from HUAWEI DBY-W09 using vozFApp

Thế này là do trình bác cao hơn 2 ông bên trên rồi.
 

dynamic programming

Senior Member
nó chỉ rank theo thời gian submit đc accept thôi chứ ko care cách làm có tối ưu hay ko thím nhỉ

Sent from Samsung SM-G986U1 using vozFApp

Tính theo score với finish time thôi thím, chứ 2 người = finish time mà code khác ngôn ngữ thì k so sánh được runtime

Sent from Samsung SM-J730G using vozFApp
 

Arik97

Senior Member
Không hiểu sao mình thấy bài hard hôm nay dễ hơn bài medium hôm qua. Khá straightforward để tìm quy tắc QHĐ, không lắt léo gì.

Cách nghĩ của bài này là:
  • với dãy có 1, 2, .., n-1,
  • Thử thêm n vào thì sẽ có n vị trí khác nhau,
  • Trừ vị trí cuối thì tất cả các vị trí còn lại đều tăng số Inverse Pair vì n lớn hơn tất cả các số có sẵn trong dãy,
  • Từ đó dễ suy ra công thức QHĐ: T(n, k) = T(n-1, k) + T(n-1, k-1) + ... + T(n-1, k-n+1).

Cái bước thử chèn n vào là khá tự nhiên, còn những phần còn lại chỉ là tính toán + / - cơ bản.

Sent from HUAWEI DBY-W09 using vozFApp

e cũng nghĩ ra công thức qhđ ntn nhưng mà vẫn dính TLE ko biết optimize thế nào :(

Sent from Samsung SM-G986U1 using vozFApp
 

_Gia_Cat_Luong_

Senior Member
e cũng nghĩ ra công thức qhđ ntn nhưng mà vẫn dính TLE ko biết optimize thế nào :(

Sent from Samsung SM-G986U1 using vozFApp
Thím dùng @cache của python à ? Vì cái này cái hashmap lớn quá nên bị chậm đó. Thím đổi lại dùng memo tay = array là được.

Edit: Vẫn hong được, thôi dùng bottom up cho dễ ông giáo ạ :(
 
Last edited:

Arik97

Senior Member
Thím dùng @cache của python à ? Vì cái này cái hashmap lớn quá nên bị chậm đó. Thím đổi lại dùng memo tay = array là được.

Edit: Vẫn hong được, thôi dùng bottom up cho dễ ông giáo ạ :(

Bottom up đây vẫn TLE bác ơi
Python:
class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        # ## Top-down
        # @lru_cache(None)
        # def dp(n,k):
        #     if n==0:
        #         return 0
        #     if k==0:
        #         return 1
        #     res=0
        #     for i in range(min(k,n-1)+1):
        #         res+=dp(n-1,k-i)
        #     return res
        # return dp(n,k)
        
        ## Bottom-up: convert recursion to iterative
        dp=[[0]*(k+1) for _ in range(n+1)]
        for i in range(1,n+1):
            for j in range(k+1):
                if j==0:
                    dp[i][j]=1
                else:
                    for t in range(min(j,i-1)+1):
                        dp[i][j]+=dp[i-1][j-t]
        return dp[-1][-1]
Cách này độ phức tạp vẫn là O(n*k*min(n,k)). Bài này tag hard nên nó chỉ accept O(n*k) thôi :(
 

bribnt

Đã tốn tiền
Bottom up đây vẫn TLE bác ơi

Cách này độ phức tạp vẫn là O(n*k*min(n,k)). Bài này tag hard nên nó chỉ accept O(n*k) thôi :(

Cái chỗ sum đó là sliding window nên có thể giảm từ O(min(n,k)) xuống O(1) nhé. Cứ mỗi bước cộng thêm một số mới và trừ đi số cũ là được.

Sent from HUAWEI DBY-W09 using vozFApp
 

Violet_7

Senior Member
18 / 7 / 2022:
  • 1 câu hard khá quen thuộc
  • Đề bài yêu cầu tìm 1 submatrix có tổng bằng target -> nghĩ ngay tới two sum
  • Ý tưởng dễ nhất: gọi điểm đầu submatrix là (x1, y1) và điểm cuối là (x2, y2)
_ Tạo mảng 2d sum sao cho sum[i.][j.] là tổng của submatrix có điểm đầu (0, 0) và điểm cuối (i, j)
  • Tính toàn bộ sum -> time O(n^2)
  • tại mỗi submatrix có điểm đầu (x1, y1) và điểm cuối (x2, y2) có tổng = sum[x2.][y2.] - sum[x1 - 1][y2] - sum[x2.][y1 - 1] + sum[x1 - 1][y1 - 1]
-> cần 4 vòng for cho mỗi biến x1, y1, x2, y2
-> ra đáp án
  • Time O(n ^ 4)
  • Code: https://leetcode.com/submissions/detail/749851671/
  • đến đây có thể tối ưu giống bài two sum
  • chỉ cần 3 biến x, y1, y2 và tạo 1 hash map
  • chọn 2 điểm y1, y2 bất kì thuộc khoảng (1 -> n)
  • chạy biến x từ 1-> m
  • ở mỗi lần x, map[tổng submatrix có điểm đầu (0, y1) và điểm cuối (x, y2)]++;
  • result += map[tổng submatrix trên - target];
-> ra đáp án
 

_Gia_Cat_Luong_

Senior Member
18 / 7 / 2022:
  • 1 câu hard khá quen thuộc
  • Đề bài yêu cầu tìm 1 submatrix có tổng bằng target -> nghĩ ngay tới two sum
  • Ý tưởng dễ nhất: gọi điểm đầu submatrix là (x1, y1) và điểm cuối là (x2, y2)
_ Tạo mảng 2d sum sao cho sum[i.][j.] là tổng của submatrix có điểm đầu (0, 0) và điểm cuối (i, j)
  • Tính toàn bộ sum -> time O(n^2)
  • tại mỗi submatrix có điểm đầu (x1, y1) và điểm cuối (x2, y2) có tổng = sum[x2.][y2.] - sum[x1 - 1][y2] - sum[x2.][y1 - 1] + sum[x1 - 1][y1 - 1]
-> cần 4 vòng for cho mỗi biến x1, y1, x2, y2
-> ra đáp án
  • Time O(n ^ 4)
  • Code: https://leetcode.com/submissions/detail/749851671/
  • đến đây có thể tối ưu giống bài two sum
  • chỉ cần 3 biến x, y1, y2 và tạo 1 hash map
  • chọn 2 điểm y1, y2 bất kì thuộc khoảng (1 -> n)
  • chạy biến x từ 1-> m
  • ở mỗi lần x, map[tổng submatrix có điểm đầu (0, y1) và điểm cuối (x, y2)]++;
  • result += map[tổng submatrix trên - target];
-> ra đáp án
Spoil thế. Huhu. Bài này tui nghĩ sáng h mất 30p còn chưa ra ý tưởng nào :(
 

the_gioi_that_dep

Junior Member
Không liên quan lắm mà các bác các anh code Java trên Leetcode đừng dùng global static mà khai báo sẵn giá trị nhá, nó cache vào làm code bug xỉu lên xỉu xuống :surrender:, sửa 7749 lần vẫn ra kết quả cũ :feel_good:

via theNEXTvoz for iPhone
 

bribnt

Đã tốn tiền
Bài hôm nay kích thước có 100 nên dùng cách O(n^4) nhanh hơn O(n^3) hash map.

1658120755933.png


https://leetcode.com/submissions/detail/749963010/

C++:
// std::array<std::array<int, 128>, 128> sum{};

class Solution {
public:
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
               
        // find
        int res = 0;
        // std::unordered_map<int, int> count{};
        for (int r1 = -1; r1 < m-1; ++r1) {
            std::array<int, 101> sum{0};
           
            for (int r2 = r1 + 1; r2 < m; ++r2) {
                // count.clear();
                // count[0] = 1;
                int prev = 0;
               
                for (int c2 = 0; c2 < n; ++c2) {
                    int old = sum[c2+1];
                    int nnew = (sum[c2+1] += sum[c2] - prev + matrix[r2][c2]);
                    prev = old;
                   
                    res += std::count(&sum[0], &sum[c2+1], nnew - target);
                   
//                     if (auto it = count.find(nnew-target); it != count.end()) {
//                         res += it->second;
//                     }
                   
//                     ++count[nnew];
                }
            }
        }
        return res;
    }
};

auto _ = []() {
    std::cin.sync_with_stdio(false);
    std::cin.tie(0);
    return 0;
}();
 

NudeDuck

Junior Member
Bài hôm nay kích thước có 100 nên dùng cách O(n^4) nhanh hơn O(n^3) hash map.

View attachment 1271205

https://leetcode.com/submissions/detail/749963010/

C++:
// std::array<std::array<int, 128>, 128> sum{};

class Solution {
public:
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
              
        // find
        int res = 0;
        // std::unordered_map<int, int> count{};
        for (int r1 = -1; r1 < m-1; ++r1) {
            std::array<int, 101> sum{0};
          
            for (int r2 = r1 + 1; r2 < m; ++r2) {
                // count.clear();
                // count[0] = 1;
                int prev = 0;
              
                for (int c2 = 0; c2 < n; ++c2) {
                    int old = sum[c2+1];
                    int nnew = (sum[c2+1] += sum[c2] - prev + matrix[r2][c2]);
                    prev = old;
                  
                    res += std::count(&sum[0], &sum[c2+1], nnew - target);
                  
//                     if (auto it = count.find(nnew-target); it != count.end()) {
//                         res += it->second;
//                     }
                  
//                     ++count[nnew];
                }
            }
        }
        return res;
    }
};

auto _ = []() {
    std::cin.sync_with_stdio(false);
    std::cin.tie(0);
    return 0;
}();
Bác nói chuẩn quá em làm cách O(mmn) nhanh hơn được 5% :LOL:
 

_Gia_Cat_Luong_

Senior Member
Sau 2 ngày ra bài Hard loạn hết cả não thì hnay đc thư giãn một hôm :D. Đen vâu keep it real, code theo kiểu đơn giản nhất:

Code:
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        if numRows <= 0:
            return []
        
        output = [[1]]
        
        for i in range(2, numRows + 1):
            row = [1]
            for j in range(1, i-1):
                row.append(output[-1][j-1] + output[-1][j])
            row.append(1)
            output.append(row)
            
        return output
 
Top