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

Kân team v3 đã nói:

memoize xao chậm vậy cà https://leetcode.com/submissions/detail/804092306/

Nhấp để mở rộng...

thuyduong2007 đã nói:

memoize làm gì cho phức tạp bác kân,
Xem tệp đính kèm 1391549
https://leetcode.com/submissions/detail/804102162/

Nhấp để mở rộng...

Approach #2: Binary Search with Naive Check [Time Limit Exceeded]​

Lập Trình Viên Số Khổ đã nói:

fen giải thích lời giải cái, sao lại có 2 function vậy

Nhấp để mở rộng...

thuyduong2007 đã nói:

window siding thôi fen. Trước t đi pv gặp bài này rồi, .
Ý tưởng là kéo thằng nums1 qua trái từ 0 đến len(nums1) phần tử rồi so sánh trực tiếp với nums2, lấy max. Làm tương tự với nums2.
VD:
Input:
nums1 = [1,2,3,2,1]
nums2 = [3,2,1,4,7]

compare nums1[0:] với nums2 -> [1, 2, 3, 2, 1] [3, 2, 1, 4, 7] -> 1
compare nums1[1:] với nums2 -> [2, 3, 2, 1] [3, 2, 1, 4, 7] -> 0
compare nums1[2:] với nums2 -> [3, 2, 1] [3, 2, 1, 4, 7] -> 3
....

Nhấp để mở rộng...

Kân team v3 đã nói:

ừ nhỉ đúng bài đơn giản phải xài cách đơn giản này tự dưng đâu chơi cái dp

Nhấp để mở rộng...

Kân team v3 đã nói:

toy chuyển về dp O(n) mem đây https://leetcode.com/submissions/detail/804150842/ code loằng ngoằng

Nhấp để mở rộng...

dagedage đã nói:

bọn này sau mỗi tháng lại add thêm test case à, bài hnay em có submission rồi nhưng ấn submit lại thì bị TLE
Update: Ấn submit phát nữa với code đó lại được rồi

Nhấp để mở rộng...

crushkydvn đã nói:

code này là O(mn) với m,n lần lượt là số phần tử của mỗi vector chứ bác nhỉ?

Nhấp để mở rộng...

Kân team v3 đã nói:

O(mn) time nhưng O(n) memory toy bảo O(n) mem mà

Nhấp để mở rộng...

Lập Trình Viên Số Khổ đã nói:

Leetcode sao sao ấy nhỉ, submit lần đầu TLE với O(N) hơi sốc, submit lại mới được
https://leetcode.com/submissions/detail/804914414/

Spoiler

Python:

class Solution:
    def sumEvenAfterQueries(self, nums: List[int], queries: List[List[int]]) -> List[int]:    
        res = sum([i for i in nums if not i%2])

        arr = []
        for val, index in queries:
            new_num = nums[index] + val
            if nums[index] % 2 == 0:
                if val % 2 == 0:
                    res += val
                else:
                    res -= nums[index]
            else:
                if val % 2 != 0:
                    res += (nums[index] + val)
            nums[index] = new_num

            arr.append(res)
     
        return arr

Nhấp để mở rộng...

class Solution {
public:
    vector<int> sumEvenAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
        vector<int> res; res.reserve(queries.size());
        int sum = 0;
        for (auto i : nums) sum += i & ((i & 1) - 1);
        for (auto &v : queries) {
            auto &n = nums[v[1]];
            sum -= n & ((n & 1) - 1);
            n += v[0];
            res.emplace_back(sum += n & ((n & 1) - 1));
        }
        return res;
    }
};

bribnt đã nói:

Python mà dài thế?

Spoiler: C++ không cần branch

C++:

class Solution {
public:
    vector<int> sumEvenAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
        vector<int> res; res.reserve(queries.size());
        int sum = 0;
        for (auto i : nums) sum += i & ((i & 1) - 1);
        for (auto &v : queries) {
            auto &n = nums[v[1]];
            sum -= n & ((n & 1) - 1);
            n += v[0];
            res.emplace_back(sum += n & ((n & 1) - 1));
        }
        return res;
    }
};

Nhấp để mở rộng...

Lập Trình Viên Số Khổ đã nói:

vì python culture là Explicit is better than Implicit bác

Nhấp để mở rộng...

class Solution(object):
    def sumEvenAfterQueries(self, A, queries):
        S = sum(x for x in A if x % 2 == 0)
        ans = []

        for x, k in queries:
            if A[k] % 2 == 0: S -= A[k]
            A[k] += x
            if A[k] % 2 == 0: S += A[k]
            ans.append(S)

        return ans