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

LmaoSuVuong · 30/7/25

aNotHeRNo0b đã nói:
Có bác nào gặp DP là bị lối mòn suy nghĩ theo kiểu top-down (backtrack + memo) mà khó nghĩ theo kiểu bottom-up (tabular) không? Như này phỏng vấn có vấn đề gì không nhỉ? Mình thấy tabular dễ kiểm soat mem hơn, cũng gọn hơn, nma mà top-down clear hơn ấy ._.

ko biết giải DP lặng lẽ đi ra

kangtk · 30/7/25

small-lambda đã nói:

đang trong probation mà hơi căng :confused:

C-like:

impl Solution {
    pub fn longest_subarray(nums: Vec<i32>) -> i32 {
        let max =
            nums.iter().copied().
                fold(i32::MIN, |acc, num| acc.max(num));

        let (mut left, mut right) = (usize::MAX, usize::MAX);
        let (mut found, mut result) = (false, 0);

        for (i, num) in nums.iter().copied().enumerate() {
            match (num == max, found) {
                (true, false) => (left, right, found) = (i, i, true),
                (true, true) => right += 1,
                (false, _) => (left, right, found) = (usize::MAX, usize::MAX, false)
            }

            if left != usize::MAX {
                result = result.max(right - left + 1);
            }
        }

        result as i32
    }
}

Đi làm lại nhanh v thím :3.

small-lambda · 30/7/25

kangtk đã nói:
Đi làm lại nhanh v thím :3.

no rest for the wicked

kangtk · 30/7/25

small-lambda đã nói:
no rest for the wicked

Chúc mừng thím nha. Chỗ mới của thím process nhanh nhỉ.

freedom.9 · 30/7/25

aNotHeRNo0b đã nói:
Có bác nào gặp DP là bị lối mòn suy nghĩ theo kiểu top-down (backtrack + memo) mà khó nghĩ theo kiểu bottom-up (tabular) không? Như này phỏng vấn có vấn đề gì không nhỉ? Mình thấy tabular dễ kiểm soat mem hơn, cũng gọn hơn, nma mà top-down clear hơn ấy ._.

Thì thay vì đi Dp topdown xong thì giải bằng bottom up thôi fen, nếu nhìn bottom up mà intuitive hơn top down thì giải.
Thường mình chỉ dùng botttom up với kiểu giải mấy bài dp matrix thôi, còn lại cứ topdown cho nó accepted đã

via theNEXTvoz for iPhone

chiyeuemthoi · 30/7/25

aNotHeRNo0b đã nói:
Có bác nào gặp DP là bị lối mòn suy nghĩ theo kiểu top-down (backtrack + memo) mà khó nghĩ theo kiểu bottom-up (tabular) không? Như này phỏng vấn có vấn đề gì không nhỉ? Mình thấy tabular dễ kiểm soat mem hơn, cũng gọn hơn, nma mà top-down clear hơn ấy ._.

thích tư duy làm theo kiểu top-down hơn h mà vô bắt làm bottom up thì ngửa mà dạng này vs bit mh ngu nhất cmnr đọc giải còn éo hiểu :burn_joss_stick:

chiyeuemthoi · 30/7/25

Mã:

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        max_val = max(nums)
        cnt = ans = 0
        for num in nums:
            if num == max_val: cnt += 1
            else: cnt = 0
            
            ans = max(ans , cnt)
                
        return ans

nay mưa suy quá :cry:

dhl001 · 31/7/25

Optimize từ O(n*n) xuống mà không biết tính TC và SC mới như thế nào.
Dùng tính chất nào để tính max TC, SC cho bài này nhỉ.
ví dụ cho dãy [2, 4, 8, 16, 32,64,128,256,512] thì kết quả ra là n*n. Nhưng khi n đủ lớn thì sẽ có giới hạn nào đó.
Nhưng mình không liên hệ được

Java:

class Solution {
    public int subarrayBitwiseORs(int[] arr) {
        Set<Integer> res = new HashSet<>();
        Set<Integer> last = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            int crr = arr[i];
            Set<Integer> crrSet = new HashSet<>();
            crrSet.add(crr);
            for (var j : last) {
                crrSet.add(crr | j);
            }
            last = crrSet;
            res.addAll(crrSet);
        }
        return res.size();
    }
}

freedom.9 · 31/7/25

Bài nay khoai phết, phải giải theo DP mới pass. Nếu nghĩ i là điểm start của mỗi sub array thì chắc chắn làm ko ra mà phải nghĩ i là điểm end của mỗi sub array thì lúc đấy mới nhìn ra DP

Python:

class Solution:
    def subarrayBitwiseORs(self, arr: List[int]) -> int:
        prev = set()
        total = set()
        for num in arr:
            current = set()
            current.add(num)
            for xor in prev:
                current.add(xor | num)
            total |= current
            prev = current
        return len(total)

dhl001 · 31/7/25

Cái khó là chứng minh TC và SC không phải là O(n^2)

freedom.9 · 31/7/25

dhl001 đã nói:
Optimize từ O(n*n) xuống mà không biết tính TC và SC mới như thế nào.
Dùng tính chất nào để tính max TC, SC cho bài này nhỉ.
ví dụ cho dãy [2, 4, 8, 16, 32,64,128,256,512] thì kết quả ra là n*n. Nhưng khi n đủ lớn thì sẽ có giới hạn nào đó.
Nhưng mình không liên hệ được

Java:

class Solution { public int subarrayBitwiseORs(int[] arr) { Set<Integer> res = new HashSet<>(); Set<Integer> last = new HashSet<>(); for (int i = 0; i < arr.length; i++) { int crr = arr[i]; Set<Integer> crrSet = new HashSet<>(); crrSet.add(crr); for (var j : last) { crrSet.add(crr | j); } last = crrSet; res.addAll(crrSet); } return res.size(); } }

Keypoint: Vì chỉ có maximum là 32 bits, và mỗi operation thì chỉ có tăng số bit 1 nên maximum chỉ có 32 giá trị cho 1 sub array từ i đến n.
Độ phức tạp đơn giản là khoảng 0(32*n) thôi cho cả time + space complexity.

aNotHeRNo0b · 31/7/25

Sort để số sau lớn hơn số trước. Với mỗi số mới lớn hơn do có 1 bit mới được bật lên, sẽ tạo ra tối đa num_prev_bit số mới. Mà chỉ có tối đa 32 bit thì số or tối đa có thể tạo của 1 dãy là 32*31/2 or. Vậy nên cứ ghi nhận các or mới được tạo và or thì độ phức tạp tối đa là O(n.32.32) -> pass

freedom.9 · 31/7/25

aNotHeRNo0b đã nói:
Sort để số sau lớn hơn số trước. Với mỗi số mới lớn hơn do có 1 bit mới được bật lên, sẽ tạo ra tối đa num_prev_bit số mới. Mà chỉ có tối đa 32 bit thì số or tối đa có thể tạo của 1 dãy là 32*31/2 or. Vậy nên cứ ghi nhận các or mới được tạo và or thì độ phức tạp tối đa là O(n.32.32) -> pass

Đề nó kêu tính cho sub array mà sao lại đi sort

via theNEXTvoz for iPhone

aNotHeRNo0b · 31/7/25

freedom.9 đã nói:
Đề nó kêu tính cho sub array mà sao lại đi sort

via theNEXTvoz for iPhone

Thì wost case là số i = 1 << i ý bác, thì lúc đó số lượng or sẽ là lớn nhất.

LmaoSuVuong · 31/7/25

aNotHeRNo0b đã nói:
Thì wost case là số i = 1 << i ý bác, thì lúc đó số lượng or sẽ là lớn nhất.

Subsequence mới dc delete phần tử ở giữa bác. subarray phải đúng thứ tự

aNotHeRNo0b · 31/7/25

LmaoSuVuong đã nói:
Subsequence mới dc delete phần tử ở giữa bác. subarray phải đúng thứ tự

Í em là case só sắp xếp tăng dần á, 2 4 8 16 32 ...

aNotHeRNo0b · 31/7/25

Với case chỉ toàn số luỹ thừa của 2. Với mỗi số mới lớn hơn do có 1 bit mới được bật lên, sẽ tạo ra tối đa num_prev_bit số mới. Mà chỉ có tối đa 32 bit thì số or tối đa có thể tạo của 1 dãy là 32*31/2 or. Vậy nên cứ ghi nhận các or mới được tạo và or thì độ phức tạp tối đa là O(n.32.32) -> pass

aNotHeRNo0b · 31/7/25

aNotHeRNo0b đã nói:
Sort để số sau lớn hơn số trước. Với mỗi số mới lớn hơn do có 1 bit mới được bật lên, sẽ tạo ra tối đa num_prev_bit số mới. Mà chỉ có tối đa 32 bit thì số or tối đa có thể tạo của 1 dãy là 32*31/2 or. Vậy nên cứ ghi nhận các or mới được tạo và or thì độ phức tạp tối đa là O(n.32.32) -> pass

Với case chỉ toàn số luỹ thừa của 2. Với mỗi số mới lớn hơn do có 1 bit mới được bật lên, sẽ tạo ra tối đa num_prev_bit (số bit đk bật của or lớn nhất) số mới. Mà chỉ có tối đa 32 bit thì số or tối đa có thể tạo của 1 dãy là 32*31/2 or. Vậy nên cứ ghi nhận các or mới được tạo và or thì độ phức tạp tối đa là O(n.32.32) -> pass

dhl001 · 31/7/25

aNotHeRNo0b đã nói:
Sort để số sau lớn hơn số trước. Với mỗi số mới lớn hơn do có 1 bit mới được bật lên, sẽ tạo ra tối đa num_prev_bit số mới. Mà chỉ có tối đa 32 bit thì số or tối đa có thể tạo của 1 dãy là 32*31/2 or. Vậy nên cứ ghi nhận các or mới được tạo và or thì độ phức tạp tối đa là O(n.32.32) -> pass

Bài này sub array mà thím, mới vô đã nêu giải pháp sort thì thấy cấn cấn

aNotHeRNo0b · 31/7/25

dhl001 đã nói:
Bài này sub array mà thím, mới vô đã nêu giải pháp sort thì thấy cấn cấn

Em sửa lại comment rồi bác ạ

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

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Đã tốn tiền

Senior Member

Đã tốn tiền

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Đã tốn tiền

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này