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

Kân team v3 · 26/10/22

bài hôm lay toy là người có học tưởng là qhd classic trong cuốn CLRS nên code O(nlogn), beat 5%

chọn số ở giữa cho là nó thuộc subarray chia hết cho k, tìm subarray chứa số ở giữa này trong O(n), nếu ko tìm ra thì đệ quy 2 nửa mảng trái và phải, tối đa đệ quy logn lần, mỗi lần O(n) là O(nlogn)
https://leetcode.com/problems/continuous-subarray-sum/submissions/830331101/

C++:

struct Solution {
    array<int, 100'001> buf;
    bool checkMid(const int* first, const int* last, const int k) {
        const int n = last - first;
        if (n < 2) return false;
        if (n == 2) return (first[0] + first[1]) % k == 0;
        buf[n / 2] = first[n / 2] % k;
        for (int i = n / 2; i--;)
            if ((buf[i] = (buf[i + 1] + first[i]) % k) == 0) return true;
        unordered_set<int> rems;
        rems.insert((buf[n / 2 + 1] = first[n / 2 + 1] % k));
        for (int i = n / 2 + 2; i < n; ++i)
            rems.insert((buf[i] = (buf[i - 1] + first[i]) % k));
        for (int i = n / 2 + 1; i--;)
            if (rems.find(buf[i] == 0 ? 0 : k - buf[i]) != end(rems)) return true;
        return checkMid(first, first + n / 2, k) || checkMid(first + n / 2 + 1, last, k);
    }
    bool checkSubarraySum(vector<int>& nums, int k) {
        return checkMid(&nums[0], &nums[0] + nums.size(), k);
    }
};

bấm xem đáp án thấy nó chơi công thức tón học

còn O(n) thoy nên toy code lại "1" dòng

https://leetcode.com/problems/continuous-subarray-sum/submissions/830338382/

C++:

struct Solution {
    bool checkSubarraySum(vector<int>& nums, int k) {
        return any_of(begin(nums), end(nums), [=, i = 0, s = 0, prefixSums = unordered_map<int, int>{{0, -1}}](int n) mutable {
            if (auto it = prefixSums.find(s = (s + n) % k); it != end(prefixSums)) {
                return i++ - it->second >= 2;
            } else {
                return prefixSums[s] = i++, false;
            }
        });
    }
};

Aristides · 26/10/22

bởi mới nói

"IT cần đéo gì giỏi toán" :confident:

mấy thằng ranh con trên voz Facebook cho hay

P/s: may là leetcode méo có Machine Learning chứ phải làm mấy cái design regression model mới biết quý trọng toán trong lập trình

IT_VOZ_2005 · 26/10/22

Venjsen đã nói:
cho ai muốn tryhard contest:
cái site này tổng hợp bài leetcode theo dạng rating chứ không phải độ khó (easy, medium, hard), thay vì pick bừa theo độ khó để làm (easy, medium, hard) các bác có thể pick bài theo kiểu rating của mình +vài trăm để luyện tăng trình dần dần, tránh trường hợp pick bài quá khó hoặc quá dễ dẫn đến tốn thời gian.

Không biết nó tính như nào, nhưng chắc là chia trung bình rating của những người solve được bài đó trong live contest.
https://zerotrac.github.io/leetcode_problem_rating/#/

Mấy cái này điền như thế nào bác

bribnt · 26/10/22

Venjsen đã nói:
cho ai muốn tryhard contest:
cái site này tổng hợp bài leetcode theo dạng rating chứ không phải độ khó (easy, medium, hard), thay vì pick bừa theo độ khó để làm (easy, medium, hard) các bác có thể pick bài theo kiểu rating của mình +vài trăm để luyện tăng trình dần dần, tránh trường hợp pick bài quá khó hoặc quá dễ dẫn đến tốn thời gian.

Không biết nó tính như nào, nhưng chắc là chia trung bình rating của những người solve được bài đó trong live contest.
https://zerotrac.github.io/leetcode_problem_rating/#/

Cũng đang cày theo list này, làm bài từ rating thấp đến cao.

chiyeuemthoi · 26/10/22

Venjsen đã nói:
cho ai muốn tryhard contest:
cái site này tổng hợp bài leetcode theo dạng rating chứ không phải độ khó (easy, medium, hard), thay vì pick bừa theo độ khó để làm (easy, medium, hard) các bác có thể pick bài theo kiểu rating của mình +vài trăm để luyện tăng trình dần dần, tránh trường hợp pick bài quá khó hoặc quá dễ dẫn đến tốn thời gian.

Không biết nó tính như nào, nhưng chắc là chia trung bình rating của những người solve được bài đó trong live contest.
https://zerotrac.github.io/leetcode_problem_rating/#/

thanks thím

bribnt · 27/10/22

221027 - 835. Image Overlap

Một bài bit shift cơ bản: https://leetcode.com/submissions/detail/831111728/

C++:

class Solution {
public:
    int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {
        int n = img1.size(), res = 0;
        vector<int64_t> bits1(n), bits2(n);
        for (int r = 0; r < n; ++r)
            for (int c = 0; c < n; ++c) {
                bits1[r] |= (img1[r][c] - 0) << c;
                bits2[r] |= (img2[r][c] - 0) << c;
            }

        // left / right shift
        for (int l = -n + 1; l < n; ++l) {
            // up / down shift
            for (int u = -n + 1; u < n; ++u) {
                int cnt = 0;
                for (int r = 0; r < n; ++r) {
                    auto r1 = (((r + u >= 0) & (r + u < n)) ? bits1[r + u] : 0);
                    r1 = (l >= 0) ? r1 >> l : r1 << (-l);
                    cnt += __builtin_popcount(r1 & bits2[r]);
                }
                res = max(cnt, res);
            }
        }
        return res;
    }
};

afatnan · 27/10/22

C++:

class Solution {
public:
    vector<int> convert_matrix_to_rows(vector<vector<int>>& img){
        vector<int> rows;
        for(auto &row : img){
            int tmp = 0;
            for(int &e : row){
                tmp <<= 1;
                tmp |= e;
            }
            rows.push_back(tmp);
        }
        return rows;
    }
    int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {
        int res = 0, n = img1.size();
        vector<int> rows1 = convert_matrix_to_rows(img1);
        vector<int> rows2 = convert_matrix_to_rows(img2);
        // sr, n-rc: shared row/column
        for(int sr = 1; sr <= n; sr++){
            for(int sc = 0; sc < n; sc++){
                int tmp1 = 0, tmp2 = 0, tmp3 = 0, tmp4 = 0;
                for(int r1 = n - sr, r2 = 0; r1 < n; r1++, r2++){
                    int row1 = rows1[r1], row2 = rows2[r2];
                    tmp1 += __builtin_popcount((row1 >> sc) & row2);
                    tmp2 += __builtin_popcount((row2 >> sc) & row1);
                    row1 = rows1[r2], row2 = rows2[r1];
                    tmp3 += __builtin_popcount((row1 >> sc) & row2);
                    tmp4 += __builtin_popcount((row2 >> sc) & row1);
                }
                res = max(res, tmp1);
                res = max(res, tmp2);
                res = max(res, tmp3);
                res = max(res, tmp4);
            }
        }
        return res;
    }
};

Violet_7 · 27/10/22

Ừ nhỉ n nhỏ nên dùng bit tìm overlap luôn, thành n^3.

bribnt · 27/10/22

Violet_7 đã nói:
Ừ nhỉ n nhỏ nên dùng bit tìm overlap luôn, thành n^3.

Xem discussion thấy có nhiều cách khá hay, hiệu quả cho ma trận thưa.
Trong thực tế thì thường n sẽ lớn và ma trận cực thưa.

Violet_7 · 27/10/22

bribnt đã nói:
Xem discussion thấy có nhiều cách khá hay, hiệu quả cho ma trận thưa.
Trong thực tế thì thường n sẽ lớn và ma trận cực thưa.

Ma trận thưa là ít số 1 đúng ko. Mình làm cách đấy đầu tiên, lưu hết tọa độ số 1 vào 1 mảng rồi mỗi lần dịch ảnh thì duyệt cái mảng đó. Độ phức tạp O(n^2 * số bit 1)

bribnt · 27/10/22

Violet_7 đã nói:
Ma trận thưa là ít số 1 đúng ko. Mình làm cách đấy đầu tiên, lưu hết tọa độ số 1 vào 1 mảng rồi mỗi lần dịch ảnh thì duyệt cái mảng đó. Độ phức tạp O(n^2 * số bit 1)

Chỉ cần O(n^2 + a * b) với a/b là số bit 1 của hai ma trận.

Cũng lưu hết tọa độ nhưng sau duyệt theo từng cặp ((x1, y1), (x2, y2)), mỗi lần gặp như vậy thì tăng số overlap của transformation vector (x1 - x2, y1 - y2) lên 1.

chiyeuemthoi · 27/10/22

các thím cho em xin cách học phần qhđ với má hc phần này cảm thấy mk ngu quá xem mãi k hiểu tại sao nó lại có công thức đấy

ai có nguồn hc phần này cho em xin lun thanks các thím

Arik97 · 27/10/22

bribnt đã nói:
Chỉ cần O(n^2 + a * b) với a/b là số bit 1 của hai ma trận.

Cũng lưu hết tọa độ nhưng sau duyệt theo từng cặp ((x1, y1), (x2, y2)), mỗi lần gặp như vậy thì tăng số overlap của transformation vector (x1 - x2, y1 - y2) lên 1.

Ban đầu e làm kiểu bruteforce thì bị TLE. Làm theo cái idea này của bác gọn hơn hẳn

Python:

class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        n=len(img1)
        s,t=[],[]
        for i in range(n):
            for j in range(n):
                if img1[i][j]==1:
                    s.append((i,j))
                if img2[i][j]==1:
                    t.append((i,j))
        h=collections.defaultdict(int)
        for p1 in t:
            for p2 in s:
                move=(p1[0]-p2[0],p1[1]-p2[1])
                h[move]+=1
        if h:
            return max(h.values())
        return 0

qhai_2009 · 27/10/22

up cho bác nào cần:
"𝐃𝐨𝐧’𝐭 𝐉𝐮𝐬𝐭 𝐋𝐞𝐞𝐭𝐂𝐨𝐝𝐞; 𝐅𝐨𝐥𝐥𝐨𝐰 𝐭𝐡𝐞 𝐂𝐨𝐝𝐢𝐧𝐠 𝐏𝐚𝐭𝐭𝐞𝐫𝐧𝐬 𝐈𝐧𝐬𝐭𝐞𝐚𝐝

𝐂𝐨𝐝𝐢𝐧𝐠 𝐩𝐚𝐭𝐭𝐞𝐫𝐧𝐬 𝐞𝐧𝐡𝐚𝐧𝐜𝐞 𝐨𝐮𝐫 “𝐚𝐛𝐢𝐥𝐢𝐭𝐲 𝐭𝐨 𝐦𝐚𝐩 𝐚 𝐧𝐞𝐰 𝐩𝐫𝐨𝐛𝐥𝐞𝐦 𝐭𝐨 𝐚𝐧 𝐚𝐥𝐫𝐞𝐚𝐝𝐲 𝐤𝐧𝐨𝐰𝐧 𝐩𝐫𝐨𝐛𝐥𝐞𝐦.”
---
https://www.linkedin.com/posts/suji...2--9R9?utm_source=share&utm_medium=member_ios

afatnan · 27/10/22

Arik97 đã nói:

Ban đầu e làm kiểu bruteforce thì bị TLE. Làm theo cái idea này của bác gọn hơn hẳn

Python:

class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        n=len(img1)
        s,t=[],[]
        for i in range(n):
            for j in range(n):
                if img1[i][j]==1:
                    s.append((i,j))
                if img2[i][j]==1:
                    t.append((i,j))
        h=collections.defaultdict(int)
        for p1 in t:
            for p2 in s:
                move=(p1[0]-p2[0],p1[1]-p2[1])
                h[move]+=1
        if h:
            return max(h.values())
        return 0

Cach nay nhin gon hon, cung kha de hieu. Minh viet lai bang C++.

C++:

class Solution {
public:
    int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {
        int res = 0, n = img1.size();
        vector<int> coor1, coor2;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++){
                if(img1[i][j]) coor1.push_back(i * n * n + j);
                if(img2[i][j]) coor2.push_back(i * n * n + j);
            }
        unordered_map<int, int> um;
        for(int &e1 : coor1)
            for(int &e2 : coor2)
                um[e1 - e2]++;
        
        for(auto &it : um)
            res = max(res, it.second);
        return res;
    }
};

SiDinh1994 · 27/10/22

bribnt đã nói:
Tại vì nó xài hash.
Hash có hằng số lớn hơn nhiều so với array.

Đẹp gì, tự dưng lại xài hash map trong khi set là đủ rồi, tốn gấp đôi bộ nhớ.

Bác @bribnt cho em hỏi trong sollution trên leetcode, dòng 10 đến 14 là làm gì thế?

bribnt · 27/10/22

SiDinh1994 đã nói:
Bác @bribnt cho em hỏi trong sollution trên leetcode, dòng 10 đến 14 là làm gì thế?Xem tệp đính kèm 1464806

Có comment rồi mà:

Kiểm tra xem số dư này đã xuất hiện hay chưa
Nếu chưa thì gán là vị trí hiện tại đã xuất hiện,
Nếu có thì kiểm tra xem vị trí xuất hiện có phải là ngay trước số hiện tại hay không
Nếu không phải thì trả về true. Bởi vì điều kiện dãy con có độ dài tối thiểu 2.

Sent from HUAWEI DBY-W09 using vozFApp

beztdefender · 28/10/22

Java:

/**
     *  Shift the matrix M in up-left and up-right directions
     *    and count the ones in the overlapping zone.
     */
    protected int shiftAndCount(int xShift, int yShift, int[][] M, int[][] R) {
        int leftShiftCount = 0, rightShiftCount = 0;
        int rRow = 0;
        // count the cells of ones in the overlapping zone.
        for (int mRow = yShift; mRow < M.length; ++mRow) {
            int rCol = 0;
            for (int mCol = xShift; mCol < M.length; ++mCol) {
                if (M[mRow][mCol] == 1 && M[mRow][mCol] == R[rRow][rCol])
                    leftShiftCount += 1;
                if (M[mRow][rCol] == 1 && M[mRow][rCol] == R[rRow][mCol])
                    rightShiftCount += 1;
                rCol += 1;
            }
            rRow += 1;
        }
        return Math.max(leftShiftCount, rightShiftCount);
    }

    public int largestOverlap(int[][] A, int[][] B) {
        int maxOverlaps = 0;

        for (int yShift = 0; yShift < A.length; ++yShift)
            for (int xShift = 0; xShift < A.length; ++xShift) {
                // move the matrix A to the up-right and up-left directions.
                maxOverlaps = Math.max(maxOverlaps, shiftAndCount(xShift, yShift, A, B));
                // move the matrix B to the up-right and up-left directions, which is equivalent to moving A to the down-right and down-left directions
                maxOverlaps = Math.max(maxOverlaps, shiftAndCount(xShift, yShift, B, A));
            }

        return maxOverlaps;
    }

Bác nào giải thích giùm em chỗ leftShiftCount, rightShiftCount. Đọc solution khó hiểu quá =((

afatnan · 28/10/22

Khong toi uu cho lam :LOL:

C++:

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> um;
        for(string &s : strs){
            int tab[26] = {0};
            for(char &c : s) tab[c - 'a']++;
            string tmp = "";
            for(int i = 0; i < 26; i++)
                tmp += "." + to_string(tab[i]);
            um[tmp].push_back(s);
        }
        vector<vector<string>> res;
        for(auto &it : um) res.push_back(it.second);
        return res;
    }
};

Lập Trình Viên Số Khổ · 28/10/22

Python:

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        d = defaultdict(list)
        for s in strs:
            d[tuple(sorted(s))].append(s)
        return d.values()

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

Senior Member

Senior Member

Member

Đã tốn tiền

Senior Member

Đã tốn tiền

Senior Member

Member

Đã tốn tiền

Member

Đã tốn tiền

Senior Member

Senior Member

Senior Member

Senior Member

Junior Member

Đã tốn tiền

Senior Member

Senior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này