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

Người quan sát cô đơn · 10/11/24

LmaoSuVuong đã nói:
chém bit như chém bún thế lày thì @Cố Trường Ca quay lại thì tiểu đơn hiệp sĩ r mất

có tí bitwise, bitshift tự dưng thấy code mình sang hẳn ra :beauty:

Someone... · 10/11/24

Python:

class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        ans = inf
        d = dict()  # `d` is a dictionary where the key is the OR result of a subarray ending at index `i`, and the value is the largest left endpoint of that subarray
        for i, x in enumerate(nums):
            # Update `d` by calculating the OR between `x` and each current key (OR result of previous subarrays).
            # Note: Since dictionaries in Python maintain insertion order, if the OR result is the same,
            # it will automatically keep the subarray with the larger `left` endpoint as the value.

            d = {or_ | x: left for or_, left in d.items()}
            d[x] = i  # Add a new entry for the subarray containing only `x` (new beginning left)


            # Now check each subarray OR result stored in `d`
            for or_, left in d.items():
                if or_ >= k:  # If the OR result is greater than or equal to `k`
                    # Update `ans` with the minimum length of the subarray that meets the requirement
                    ans = min(ans, i - left + 1)
           
       
        # Return the smallest valid subarray length if found; otherwise, return -1 if no such subarray exists
        return ans if ans < inf else -1

đây là lời giải của thằng nhanh nhất trong python, không hiểu sao nó lại nhanh như vậy, ae ai biết tính độ phức tạp không? vòng lặp bên ngoài là số lượng num là O(N),

còn bên trong là loop qua dict, nhưng không biết tính số lượng phần tử của dict như nào, chỉ biết nó không vượt quá N

tại mỗi thời điểm i trong vòng lặp ngoài thì cái dict chứa tất cả các giá trị OR có thể của các subarray kết thúc tại i, nếu hai subarray kết thúc tại i có cùng giá trị OR thì cái ngắn hơn (index bắt đầu lớn hơn) sẽ được giữ lại.

mrsimonle · 10/11/24

Python:

class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        bit1 = [0] * 32
        l = 0
        res = 100000000
        curr = 0
        for r in range(len(nums)):
            curr |= nums[r]
            
            # Count bit 1
            tmp = nums[r]
            i = 0
            while tmp:
                if tmp & 1 == 1:
                    bit1[i] += 1
                tmp >>= 1
                i += 1
            
            while curr >= k and l <= r:
                res = min(res, r - l + 1)
                
                # Remove bit 1
                tmp = nums[l]
                i = 0
                while tmp:
                    if tmp & 1 == 1:
                        if bit1[i] == 1:
                            curr -= pow(2, i)
                        bit1[i] -= 1
                    tmp >>= 1
                    i += 1

                l += 1

        return res if res != 100000000 else -1

Tinh Hoa Đông Lào · 10/11/24

Someone... đã nói:
tại mỗi thời điểm i trong vòng lặp ngoài thì cái dict chứa tất cả các giá trị OR có thể của các subarray kết thúc tại i, nếu hai subarray kết thúc tại i có cùng giá trị OR thì cái ngắn hơn (index bắt đầu lớn hơn) sẽ được giữ lại.

quy tắc là thế nhưng vẫn chưa có gì để tính được độ phức tạp, số lượng phần tử trong dict là bao nhiêu mỗi vòng lặp tại i fen, nếu tất cả các OR subarrray đều khác nhau thì sẽ là i phần tử à, như vậy độ phức tạp sẽ lên O(N^2), nhưng nó lại còn nhanh hơn cả O(32*N) như cái mọi người viết bằng sliding

Someone... · 10/11/24

Tinh Hoa Đông Lào đã nói:
quy tắc là thế nhưng vẫn chưa có gì để tính được độ phức tạp, số lượng phần tử trong dict là bao nhiêu mỗi vòng lặp tại i fen, nếu tất cả các OR subarrray đều khác nhau thì sẽ là i phần tử à, như vậy độ phức tạp sẽ lên O(N^2), nhưng nó lại còn nhanh hơn cả O(32*N) như cái mọi người viết bằng sliding

nhiều nhất cũng chỉ trong 32 phần tử thôi, bởi vì càng OR thì càng bật bit 1 lên, mà đã bật lên thì đâu có tắt được nữa, cho nên cùng lắm 32 phần tử

Cố Trường Ca · 11/11/24

LmaoSuVuong đã nói:
chém bit như chém bún thế lày thì @Cố Trường Ca quay lại thì tiểu đơn hiệp sĩ r mất

Cộng thêm 2 năm reset nữa thì còn lâu lắm :beauty:

freedom.9 · 11/11/24

Trả bài hôm nay

Python:

class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        bits = [0]*32
        def greaterOrEqualsK():
            current = 0
            for i in range(32):
                if bits[i] > 0:
                    current |= 1 << i
                    if current >= k:
                        break

            return current >= k

        def add(num):
            for i in range(32):
                if num >> i & 1 == 1:
                    bits[i] += 1

        def remove(num):
            for i in range(32):
                if num >> i & 1 == 1:
                    bits[i] -= 1

        left = 0
        ans = inf
        for right in range(len(nums)):
            add(nums[right])
            while left <= right and greaterOrEqualsK():
                ans = min(ans, right - left + 1)
                remove(nums[left])
                left += 1

        return ans if ans != inf else -1

thangkc89 · 11/11/24

chuỗi NNN có thể bị phá vỡ nhưng chuỗi daily leetcode thì không

C++:

class Solution {
public:
    int minimumSubarrayLength(vector<int>& nums, int k) {
        vector<int> bit_count(32);

        int res = nums.size() + 1;
        for (int l=0, r=0, cur_num = 0; r < nums.size(); ++r) {
            cur_num |= nums[r];
            for (int i=0; 1<<i <= nums[r]; ++i) {
                if (nums[r] & (1<<i)) {
                    bit_count[i]++;
                }
            }
            while (l<r) {
                int new_num = cur_num;
                for (int i=0; 1<<i <= nums[l]; ++i) {
                    if (nums[l] & (1<<i) && bit_count[i] == 1) {
                        new_num ^= (1<<i);
                    }
                }
                if (new_num < k) {
                    break;
                }
                for (int i=0; 1<<i <= nums[l]; ++i) {
                    if (nums[l] & (1<<i)) {
                        bit_count[i]--;
                    }
                }
                cur_num = new_num;
                l++;
            }
            if (cur_num >= k) {
                // cout << l << " " << r << endl;
                res = min(res, r-l+1);
            }
        }
        return res == nums.size() + 1 ? -1 : res;
    }
};

thangkc89 · 11/11/24

LmaoSuVuong đã nói:
bác này chắc cũng ở can hay mẽo gì hả, 5h sáng giải leetcode

đúng rồi bác :surrender:

freedom.9 · 11/11/24

Python:

candidates = []
size = 1001
sieve = [False, False] + [True]*(size - 2)
for i in range(2, size):
    if sieve[i] == True:
        for multiple in range(i*i, size, i):
            sieve[multiple] = False

for i in range(size):
    if sieve[i] == True:
        candidates.append(i)

class Solution:
    def primeSubOperation(self, nums: List[int]) -> bool:
        n = len(nums)
        for i in range(n - 2, -1, -1):
            if nums[i] >= nums[i + 1]:
                distance = nums[i] - nums[i + 1]
                index = bisect_right(candidates, distance)
                if index == len(candidates) or candidates[index] >= nums[i]:
                    return False

                nums[i] -= candidates[index]

        return True

Cố Trường Ca · 11/11/24

hungmessi2 đã nói:
Mới ôn lại 75 bài toán thiếu nhi mai phỏng vấn

Chúc bác phỏng vấn ngon mai có card cho anh em :sweet_kiss:

Cố Trường Ca · 11/11/24

thangkc89 đã nói:
đúng rồi bác

Thêm đối tượng nâng bi rồi :beauty:

freedom.9 · 11/11/24

Cố Trường Ca đã nói:
Thêm đối tượng nâng bi rồi

Đối tượng này chém hard cũng như chém chả, anh em cứ canh me mà xin cạc nhé

via theNEXTvoz for iPhone

Anh Thợ Săn · 11/11/24

C++:

bool Solution::primeSubOperation(vector<int>& nums) {
    vector<int> primes = {2 ,3 ,5 ,7 ,11 ,13 ,17 ,19 ,23 ,29 ,31 ,37 ,41 ,43 ,47 ,53 ,59 ,61 ,67 ,71 ,73 ,79 ,83 ,89 ,97 ,101 ,103 ,107 ,109 ,113 ,127 ,131 ,137 ,139 ,149 ,151 ,157 ,163 ,167 ,173 ,179 ,181 ,191 ,193 ,197 ,199 ,211 ,223 ,227 ,229 ,233 ,239 ,241 ,251 ,257 ,263 ,269 ,271 ,277 ,281 ,283 ,293 ,307 ,311 ,313 ,317 ,331 ,337 ,347 ,349 ,353 ,359 ,367 ,373 ,379 ,383 ,389 ,397 ,401 ,409 ,419 ,421 ,431 ,433 ,439 ,443 ,449 ,457 ,461 ,463 ,467 ,479 ,487 ,491 ,499 ,503 ,509 ,521 ,523 ,541 ,547 ,557 ,563 ,569 ,571 ,577 ,587 ,593 ,599 ,601 ,607 ,613 ,617 ,619 ,631 ,641 ,643 ,647 ,653 ,659 ,661 ,673 ,677 ,683 ,691 ,701 ,709 ,719 ,727 ,733 ,739 ,743 ,751 ,757 ,761 ,769 ,773 ,787 ,797 ,809 ,811 ,821 ,823 ,827 ,829 ,839 ,853 ,857 ,859 ,863 ,877 ,881 ,883 ,887 ,907 ,911 ,919 ,929 ,937 ,941 ,947 ,953 ,967 ,971 ,977 ,983 ,991 ,997};

    for (int i = nums.size() - 1; i >= 0; --i) {
        if (nums[i] < nums[i+1])
            continue;
        int diff = nums[i] - nums[i+1];
        for (int p = 0; p < primes.size(); ++p) {
            if (diff < primes[p] && primes[p] < nums[i]) {
                nums[i] -= primes[p];
                break;
            }
        }
        if (nums[i] >= nums[i+1])
            return false;
    }
    return true;
}

nchhnchh · 11/11/24

Python:

class Solution:
    def primeSubOperation(self, nums: List[int]) -> bool:
        nums = [0] + nums
        n = len(nums)

        def isPrime(num):
            if num < 2:
                return False
            for i in range(2, int(sqrt(num)) + 1):
                if num % i == 0:
                    return False
            return True
        
        for i in range(1, n):
            if nums[i] < nums[i-1]:
                return False
            for j in range(nums[i] - nums[i-1] - 1, -1, -1):
                if isPrime(j):
                    nums[i] -= j
                    break
        
        for i in range(1, n - 1):
            if nums[i] >= nums[i+1]:
                return False
        return True

DancingBoy · 11/11/24

Nhiều bro giải nhanh quá, hâm mộ ghê.

anoldvozer1710.v2 · 11/11/24

Tìm số nguyên tố x gần nhất để nums[j] > nums[j-1]
Nếu ko thể tìm ra x, và nums[j] <= nums[j-1] thì tức là false.
Có cái hàm tìm số nguyên tố đi chôm :ops:

JavaScript:

function primeSubOperation(nums: number[]): boolean {
    let ok = false, prev = 0;
    const check = (num: number): boolean => {
        if (num <= 1) return false;
        if (num <= 3) return true;
        if (num % 2 === 0 || num % 3 === 0) return false;
        for (let i = 5; i * i <= num; i += 6) {
            if (num % i === 0 || num % (i + 2) === 0) {
                return false;
            }
        }
        return true;
    };

    const find = (num: number, target: number) => {
        if (num < target) return 0;
        for (let i = num - 1; i > 1; i--) {
            if (check(i) && num - i > target) return i
        }
        return 0;
    }   

    for (let i = 0; i < nums.length; i++) {
        const val = find(nums[i], prev);
        if (!val && nums[i] <= prev) return false;
        prev = nums[i] - val
    }
    return true;
};

DangToiCao · 11/11/24

Cách làm beat 100% không dùng binary search và sàng lọc số nguyên tố, lướt qua không thấy ai làm cách này hết.

C++:

class Solution {
public:
    bool isprime(int n) {
        if (n <= 1) {
            return false;
        }
        for (int i = 2; i*i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
    bool primeSubOperation(vector<int>& nums) {
        int n = nums.size();
        int mx  = 2000;
        for (int i = n - 1; i >= 0; i--) {
            if (nums[i] >= mx) {
                for (int k = nums[i] - mx + 1;k < nums[i]; k++) {
                    if (isprime(k)) {
                        nums[i] -= k;
                        break;
                    }
                }
                if (nums[i] >= mx) return false;
                mx = nums[i];
            }
            else mx = nums[i];
        }
        return true;
    }
};

Takeitiz · 11/11/24

C++:

class Solution {
public:
    bool primeSubOperation(vector<int>& nums) {
        bool isGood = true;
        int n = nums.size();
            
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] >= nums[i + 1]) {
                for (int number = 2; number < nums[i]; number++) {
                    if (isPrime(number) && nums[i] - number < nums[i + 1]) {
                        nums[i] = nums[i] - number;
                        break;
                    }
                }
                if (nums[i] >= nums[i + 1]) {
                    isGood = false;
                    break;
                }
            }
        }

        return isGood;
    }

    bool isPrime(int n) {
        bool isPrime = true;
        for (int i = 2; i <= sqrt(n); i++) {
            if (n % i == 0) {
                isPrime = false;
                break;
            }
        }
        return isPrime;
    }   

};

EzLink · 11/11/24

case này em thấy có thể trừ đi thành [0,1,3] thì phải là true chứ các bác

Edit: đọc ko kỹ đề, tự gạch :beat_brick:

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

Senior Member

Junior Member

Junior Member

Junior Member

Junior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Member

Senior Member

Senior Member

Senior Member

Junior Member

Senior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này