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

garanphomai · 1/9/24

Java:

class Solution {
    public int[][] construct2DArray(int[] o, int m, int n) {
        if (m * n != o.length)
            return new int[0][0];
        
        int[][] r = new int[m][n];

        for (int i  = 0; i < o.length; i++) {
            r[i/n][i%n] = o[i];
        }
        return r;
    }
}

Phó GOAT · 1/9/24

Java:

class Solution {
    public int[][] construct2DArray(int[] original, int m, int n) {
        int len = original.length;
        if (len - m * n != 0) {
            return new int[0][0];
        }
        int index = 0;
        int[][] matrix = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = original[index];
                index++;
            }
        }
        return matrix;
    }
}

kangtk · 1/9/24

JavaScript:

function construct2DArray(original: number[], m: number, n: number): number[][] {
    const arraySize =  original.length;
    const result = [];
    if (arraySize !== m * n) {
        return result;
    }
    let row = -1;
    for (let i = 0; i < arraySize; i++) {
        if (i % n === 0) {
            result.push([]);
            row += 1
        }
        result[row].push(original[i])
    }
    return result
};

Thầy ông cố nội · 1/9/24

JavaScript:

/**
 * @param {number[]} original
 * @param {number} m
 * @param {number} n
 * @return {number[][]}
 */
var construct2DArray = function(original, m, n) {
    if (original.length !== m * n) return [];
    const ans = new Array(m).fill(0).map(()=>[]);
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++){
            ans[r][c] = original[r*n + c];
        }
    }
    return ans;
};

aNotHeRNo0b · 1/9/24

Các bác cho em hỏi bài này em giải thì độ phức tạp là bao nhiêu? Em tính là O(N^2) nhưng mà Leetcode bảo O(N^2*M)
Đề: Palindrome Pairs - LeetCode

Java:

class Solution {
    public static final long MOD = 1_000_000_007;
    public static final long BASE = 31;
    public List<List<Integer>> palindromePairs(String[] words) {
        int n = words.length;
        long[] hash = new long[words.length];
        long[] reverseHash = new long[words.length];
        long[] pow = new long[600];
        pow[0] = 1;
        for (int i = 1; i < 600; i++) {
            pow[i] = pow[i - 1] * BASE;
            pow[i] %= MOD;
        }


        for (int i = 0; i < n; i++) {
            hash[i] = getHash(words[i]);
            reverseHash[i] = getReverseHash(words[i]);
        }

        List<List<Integer>> answer = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n;j++) {
                if (i != j) {
                    long concat = (hash[i] * pow[words[j].length()] % MOD + hash[j]) % MOD;
                    long reverseConcat = ((reverseHash[j] * pow[words[i].length()] % MOD) + reverseHash[i]) % MOD;
    
                    if (concat == reverseConcat) {
                        answer.add(List.of(i, j));
                    }
                }
            }
        }

        return answer;
    }

    public long getHash(String word) {
        long hash = 0;
        for (char c : word.toCharArray()) {
            hash = hash * BASE + c - 'a';
            hash %= MOD;
        }

        return hash;
    }

    public long getReverseHash(String word) {
        long hash = 0;
        for (int i = word.length() - 1; i >= 0; i--) {
            hash = hash * BASE + word.charAt(i) - 'a';
            hash %= MOD;
        }

        return hash;
    }
}

small-lambda · 1/9/24

aNotHeRNo0b đã nói:

Các bác cho em hỏi bài này em giải thì độ phức tạp là bao nhiêu? Em tính là O(N^2) nhưng mà Leetcode bảo O(N^2*M)
Đề: Palindrome Pairs - LeetCode

Java:

class Solution {
    public static final long MOD = 1_000_000_007;
    public static final long BASE = 31;
    public List<List<Integer>> palindromePairs(String[] words) {
        int n = words.length;
        long[] hash = new long[words.length];
        long[] reverseHash = new long[words.length];
        long[] pow = new long[600];
        pow[0] = 1;
        for (int i = 1; i < 600; i++) {
            pow[i] = pow[i - 1] * BASE;
            pow[i] %= MOD;
        }


        for (int i = 0; i < n; i++) {
            hash[i] = getHash(words[i]);
            reverseHash[i] = getReverseHash(words[i]);
        }

        List<List<Integer>> answer = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n;j++) {
                if (i != j) {
                    long concat = (hash[i] * pow[words[j].length()] % MOD + hash[j]) % MOD;
                    long reverseConcat = ((reverseHash[j] * pow[words[i].length()] % MOD) + reverseHash[i]) % MOD;
  
                    if (concat == reverseConcat) {
                        answer.add(List.of(i, j));
                    }
                }
            }
        }

        return answer;
    }

    public long getHash(String word) {
        long hash = 0;
        for (char c : word.toCharArray()) {
            hash = hash * BASE + c - 'a';
            hash %= MOD;
        }

        return hash;
    }

    public long getReverseHash(String word) {
        long hash = 0;
        for (int i = word.length() - 1; i >= 0; i--) {
            hash = hash * BASE + word.charAt(i) - 'a';
            hash %= MOD;
        }

        return hash;
    }
}

code nhìn giống O(m + n^2), LC có vẻ xài LLM nên có khi nó đoán sai

Cố Trường Ca · 1/9/24

Thử xem có thím nào còn nhớ không, lúc em đọc đề y chang như một câu chưa từng giải cmnr

LmaoSuVuong · 1/9/24

Cố Trường Ca đã nói:
Xem tệp đính kèm 2661328
Thử xem có thím nào còn nhớ không, lúc em đọc đề y chang như một câu chưa từng giải cmnr

bit manipulation làm sao nhìn ra dc :ah:

cái này còn khó hơn dp, graph

freedom.9 · 1/9/24

Cố Trường Ca đã nói:
Xem tệp đính kèm 2661328
Thử xem có thím nào còn nhớ không, lúc em đọc đề y chang như một câu chưa từng giải cmnr

Xor toàn bộ ra kết quả thôi

via theNEXTvoz for iPhone

freedom.9 · 1/9/24

aNotHeRNo0b đã nói:

Các bác cho em hỏi bài này em giải thì độ phức tạp là bao nhiêu? Em tính là O(N^2) nhưng mà Leetcode bảo O(N^2*M)
Đề: Palindrome Pairs - LeetCode

Java:

class Solution {
    public static final long MOD = 1_000_000_007;
    public static final long BASE = 31;
    public List<List<Integer>> palindromePairs(String[] words) {
        int n = words.length;
        long[] hash = new long[words.length];
        long[] reverseHash = new long[words.length];
        long[] pow = new long[600];
        pow[0] = 1;
        for (int i = 1; i < 600; i++) {
            pow[i] = pow[i - 1] * BASE;
            pow[i] %= MOD;
        }


        for (int i = 0; i < n; i++) {
            hash[i] = getHash(words[i]);
            reverseHash[i] = getReverseHash(words[i]);
        }

        List<List<Integer>> answer = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n;j++) {
                if (i != j) {
                    long concat = (hash[i] * pow[words[j].length()] % MOD + hash[j]) % MOD;
                    long reverseConcat = ((reverseHash[j] * pow[words[i].length()] % MOD) + reverseHash[i]) % MOD;
    
                    if (concat == reverseConcat) {
                        answer.add(List.of(i, j));
                    }
                }
            }
        }

        return answer;
    }

    public long getHash(String word) {
        long hash = 0;
        for (char c : word.toCharArray()) {
            hash = hash * BASE + c - 'a';
            hash %= MOD;
        }

        return hash;
    }

    public long getReverseHash(String word) {
        long hash = 0;
        for (int i = word.length() - 1; i >= 0; i--) {
            hash = hash * BASE + word.charAt(i) - 'a';
            hash %= MOD;
        }

        return hash;
    }
}

Fence dùng rolling hash hả, bài này chỉ là 0(m + n^2)

via theNEXTvoz for iPhone

Cố Trường Ca · 1/9/24

freedom.9 đã nói:
Xor toàn bộ ra kết quả thôi

via theNEXTvoz for iPhone

Dùng cái on-site interview của LC để luyện tập contest ổn không thím

Cố Trường Ca · 1/9/24

LmaoSuVuong đã nói:
bit manipulation làm sao nhìn ra dc cái này còn khó hơn dp, graph

Giống như là não lúc nào cũng loại trừ cái cách bitwise luôn cmnr, trừ khi đề nó đề cập trực tiếp thì mới nghĩ tới dùng bit

Cố Trường Ca · 1/9/24

Bài hard lấy số

https://leetcode.com/problems/unique-paths-iii/description/

freedom.9 · 2/9/24

Cố Trường Ca đã nói:
Dùng cái on-site interview của LC để luyện tập contest ổn không thím

Không ổn, fence phải thi để lấy rating, xong rồi upsolve theo rating những câu hỏi ở đây.

rating

zerotrac.github.io

Ví dụ như fence rating 1k6 chả hạn, thì fence nên focus để giải những câu hỏi từ 1k6 - 1k8, xong rồi tập luyện dần dần tới khi rating được cải thiện.
Ví dụ như contest trước giải đc 2 câu thì đặt target giải đc 3 câu đổ lên, mỗi lần giải bài thì nên bấm giờ để giải nhanh nhất có thể.
Constrain rất quan trọng trong contest, nhìn vô fence sẽ biết solution có time complexity nào sẽ đc accept, contest chỉ cần giải nhanh, vừa đủ constrain là sẽ pass chứ ko cần optimal solution.
Ví dụ fence rating 1k6 mà giải những bài 2k2+ thì ko giúp ích gì được nhiều đâu.

freedom.9 · 2/9/24

https://leetcode.com/problems/minimum-number-of-moves-to-make-palindrome/description/

Mấy nay contest ăn hành mấy bài palindrome quá, quyết tâm luyện lấy số

aNotHeRNo0b · 2/9/24

freedom.9 đã nói:
Fence dùng rolling hash hả, bài này chỉ là 0(m + n^2)

via theNEXTvoz for iPhone

khi pv mình đề xuất thuật và sau đó sử dụng Rolling Hash để cải tiến và có nhắc tới collision, thì có bị dí để ra được thuật chuẩn không bác?

freedom.9 · 2/9/24

aNotHeRNo0b đã nói:
khi pv mình đề xuất thuật và sau đó sử dụng Rolling Hash để cải tiến và có nhắc tới collision, thì có bị dí để ra được thuật chuẩn không bác?

Quan trọng là fence nêu được ý tưởng, mà có thời gian thì sẽ được tạo điều kiện để implement thôi.
Còn bài này thì mình nghĩ chỉ cần xài cái trie là xong mà

aNotHeRNo0b · 2/9/24

Cố Trường Ca đã nói:
Bài hard lấy số

https://leetcode.com/problems/unique-paths-iii/description/

bài này LC để constrain nhỏ :v Backtrack cái là được, chưa cần dùng đến Memo luôn

aNotHeRNo0b · 2/9/24

freedom.9 đã nói:
Quan trọng là fence nêu được ý tưởng, mà có thời gian thì sẽ được tạo điều kiện để implement thôi.
Còn bài này thì mình nghĩ chỉ cần xài cái trie là xong mà

Để mai em thử làm Trie thử, em optimize từ thuật Naive O(n^2*m), nghĩ ra cái check Palindrome O(1) bằng Hash. Còn chưa thử nghĩ hướng kia

freedom.9 · 2/9/24

https://leetcode.com/problems/minimum-incompatibility/description/

https://leetcode.com/problems/race-car/description/

Cơm chó ae ơi :ah:

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

Member

Senior Member

Senior Member

Junior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này