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

sau_tim_thiep_hong · 14/9/22

Python:

from collections import defaultdict
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def dfs(self, node, path):
        if not node: return 0
        else:
            path[node.val]+=1
            res = len([i for i in path.values() if i%2!=0])<=1 if not node.left and not node.right else self.dfs(node.left,path) + self.dfs(node.right,path)
            path[node.val]-=1
            return res
        
    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:
        return int(self.dfs(root, defaultdict(int)))

Kân team v3 · 14/9/22

Aristides đã nói:
giờ mới để ý là bên C++, thao tác trên bit phải dùng kiểu unsigned integer

Bên Java không có unsigned, toàn xài int không biết có sao không?

chắc là ko vì nó defined hết ròi

Zayt__ · 15/9/22

Bài nay định làm O(nlogn) mà chần chừ 1 lúc thế mà cuối cùng lại nghĩ ra được O(n) :sexy_girl:

Ý tưởng là xét frequency của các phần tử trong một chuỗi liên tiếp các phần tử có dạng x, x * 2^1, x * 2^2 dài nhất có trong dãy changed, nếu freq[x] <= freq[x * 2^1] thì thêm x vào đáp án và cập nhật freq[x * 2^1], nếu không thì trả về [] luôn

https://leetcode.com/submissions/detail/800121051/

https://leetcode.com/submissions/detail/800121051/

bribnt · 15/9/22

Ai thử giải bài Hard similar với bài hôm nay chưa?

2122. Recover the Original Array

Dùng hash map không thể AC được dù vẫn là O(n^2) với n = 1000. Đổi sang vector thì qua.

Kân team v3 · 15/9/22

bribnt đã nói:
Ai thử giải bài Hard similar với bài hôm nay chưa?

2122. Recover the Original Array

Dùng hash map không thể AC được dù vẫn là O(n^2) với n = 1000. Đổi sang vector thì qua.

toy vướng chỗ tìm k thế lào qua đọc discussion thì ra

xài std::map chỉ hơn có 5%

edit: xài std::unordered_map cho cái bảng tần suất được mà, còn lẹ hơn

edit phát nữa xài 2 parallel array thay cho cái std::map, cũng search O(logn) nhưng lẹ kinh quàng

optimize thêm tí cũng ko bằng con thùy dê

thuyduong2007 · 15/9/22

Kân team v3 đã nói:
toy vướng chỗ tìm k thế lào qua đọc discussion thì ra

xài std::map chỉ hơn có 5%

Xem tệp đính kèm 1383208

Xài map thì độ phức tạp là O(N*N*logN) à.

bribnt · 15/9/22

Kân team v3 đã nói:
toy vướng chỗ tìm k thế lào qua đọc discussion thì ra

xài std::map chỉ hơn có 5%

Xem tệp đính kèm 1383208

edit: xài std::unordered_map cho cái bảng tần suất được mà, còn lẹ hơn
Xem tệp đính kèm 1383218

Đến mức 2s thì chỉ cần khác biệt nhỏ là đã quyết định qua với không qua rồi.

Kân team v3 · 15/9/22

toy implement thử cái flat map bằng 2 vector keys và values, cũng là O(n^2 logn) mà lẹ kinh quàng kìa

thuyduong2007 · 15/9/22

Sort cái array đầu vào + dùng 1 cái array khác để mark visited,

https://leetcode.com/problems/recover-the-original-array/submissions/

Kân team v3 · 15/9/22

thuyduong2007 đã nói:
Sort cái array đầu vào + dùng 1 cái array khác để mark visited,
Xem tệp đính kèm 1383250
https://leetcode.com/problems/recover-the-original-array/submissions/

bribnt · 15/9/22

Kân team v3 đã nói:
toy implement thử cái flat map bằng 2 vector keys và values, cũng là O(n^2 logn) mà lẹ kinh quàng kìa

thuyduong2007 đã nói:
Sort cái array đầu vào + dùng 1 cái array khác để mark visited,
Xem tệp đính kèm 1383250
https://leetcode.com/problems/recover-the-original-array/submissions/

Chuẩn rồi. Nếu để ý thì thấy không cần phải tìm kiếm gì cả nên không cần hash hay map.
Một cái flat array + 2 con trỏ đầu/cuối. Hay dùng queue cũng được.

Khi tìm được một số dạng ai-k thì push ai+k vào cuối array,
Duyệt đến một số thì check xem số đó có đang ở đầu array hay không. Nếu có thì tức là nó có dạng ai+k đã bị push trước đó. Nếu không thì coi như là dạng ai-k.

thuyduong2007 · 15/9/22

bribnt đã nói:
Chuẩn rồi. Nếu để ý thì thấy không cần phải tìm kiếm gì cả nên không cần hash hay map.
Một cái flat array + 2 con trỏ đầu/cuối. Hay dùng queue cũng được.

Khi tìm được một số dạng ai-k thì push ai+k vào cuối array,

Duyệt đến một số thì check xem số đó có đang ở đầu array hay không. Nếu có thì tức là nó có dạng ai+k đã bị push trước đó. Nếu không thì coi như là dạng ai-k.

t k nghĩ được ntn, cũng chưa hiểu cách này lắm. Cách t làm vẫn phải search. TC cũng là (N*N*logN) thôi. Có điều k dùng red-black tree hay hash table nên cache friendly hơn, chạy nhanh hơn.

Kân team v3 · 15/9/22

toy check k theo kiểu rút từ từ min value của cái map ra như bài hôm nay ấy

mỗi lần check k phải copy cái map từ đầu

optimize cái flat map bằng cách std::copy lại cái original values thoy ko cần cấp phát động toàn bộ 2 mảng mới vẫn ko lẹ nhứt

chắc phải đổi thuật tón thì mới lẹ hơn toy vắt cổ chày thế lày là ko còn nước nữa ròi

thuyduong2007 · 15/9/22

Kân team v3 đã nói:
toy check k theo kiểu rút từ từ min value của cái map ra như bài hôm nay ấy

mỗi lần check k phải copy cái map từ đầu

optimize cái flat map bằng cách std::copy lại cái original values thoy ko cần cấp phát động toàn bộ 2 mảng mới vẫn ko lẹ nhứt

chắc phải đổi thuật tón thì mới lẹ hơn toy vắt cổ chày thế lày là ko còn nước nữa ròi

cái num max là 2000 phần tử, nên chỉ cần array<bool, 2001> là đủ, khỏi phải cấp phát động sau mỗi lần tìm k. Rồi dùng binary search thôi, do cái nums t đã sort rồi.

bribnt · 15/9/22

thuyduong2007 đã nói:
t k nghĩ được ntn, cũng chưa hiểu cách này lắm. Cách t làm vẫn phải search. TC cũng là (N*N*logN) thôi. Có điều k dùng red-black tree hay hash table nên cache friendly hơn, chạy nhanh hơn.

Tạo một queue missing, mục đích để chứa các số dạng ai+k.
Queue này sẽ được push back vào khi gặp số dạng ai-k. Sau này sẽ pop front khi gặp lại nó. Sau khi duyệt hết input nếu queue empty Và đã kiếm đủ n output thì là hợp lệ.
Còn để phân biệt giữa 2 dạng: ưu tiên "trả nợ" ai+k trước, nếu nó bằng với số đầu tiên trong queue.
Dùng array + 2 pointer thì nhanh hơn queue.

Lý do có thể làm như trên là vì:

input đã được sort-> queue cũng mặc nhiên đã sort
cho nên nếu duyệt đến số dạng ai+k thì nó sẽ là số nhỏ nhất trong queue có dạng đó. Số nhỏ hơn thì đã bị pop ra từ trước rồi. Nên chỉ cần check front là đủ.
nếu duyệt đến số dạng ai-k thì nó là số lớn nhất đã gặp có dạng đó -> ai+k tương ứng cũng lớn nhất. Push back vào queue là hợp lý.

https://leetcode.com/submissions/detail/800304114/

thuyduong2007 · 15/9/22

bribnt đã nói:
Tạo một queue missing, mục đích để chứa các số dạng ai+k.
Queue này sẽ được push back vào khi gặp số dạng ai-k. Sau này sẽ pop front khi gặp lại nó. Sau khi duyệt hết input nếu queue empty Và đã kiếm đủ n output thì là hợp lệ.
Còn để phân biệt giữa 2 dạng: ưu tiên "trả nợ" ai+k trước, nếu nó bằng với số đầu tiên trong queue.
Dùng array + 2 pointer thì nhanh hơn queue.

Lý do có thể làm như trên là vì:

input đã được sort-> queue cũng mặc nhiên đã sort

cho nên nếu duyệt đến số dạng ai+k thì nó sẽ là số nhỏ nhất trong queue có dạng đó. Số nhỏ hơn thì đã bị pop ra từ trước rồi. Nên chỉ cần check front là đủ.

nếu duyệt đến số dạng ai-k thì nó là số lớn nhất đã gặp có dạng đó -> ai+k tương ứng cũng lớn nhất. Push back vào queue là hợp lý.

https://leetcode.com/submissions/detail/800304114/

Ok, đã hiểu được ý tưởng của fen rồi. Cảm ơn nhé.

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

cảm thấy mình làm dụng hashtable, ở C++ chắc fail là cái chắc rồi

Python:

class Solution:
    def findOriginalArray(self, changed: List[int]) -> List[int]:
        n = len(changed)
        
        if n%2:
            return []
        
        d = defaultdict(int)
        
        for i in changed:
            d[i] += 1
            
        heapify(changed)
        res = []

        for i in range(n):
            x = heappop(changed)
            if d[x] > 0:
                res.append(x)
                d[x]-=1
                d[x*2]-=1
                
        return res if len(res) == n//2 else []

Kân team v3 · 15/9/22

bribnt đã nói:
Tạo một queue missing, mục đích để chứa các số dạng ai+k.
Queue này sẽ được push back vào khi gặp số dạng ai-k. Sau này sẽ pop front khi gặp lại nó. Sau khi duyệt hết input nếu queue empty Và đã kiếm đủ n output thì là hợp lệ.
Còn để phân biệt giữa 2 dạng: ưu tiên "trả nợ" ai+k trước, nếu nó bằng với số đầu tiên trong queue.
Dùng array + 2 pointer thì nhanh hơn queue.

Lý do có thể làm như trên là vì:

input đã được sort-> queue cũng mặc nhiên đã sort

cho nên nếu duyệt đến số dạng ai+k thì nó sẽ là số nhỏ nhất trong queue có dạng đó. Số nhỏ hơn thì đã bị pop ra từ trước rồi. Nên chỉ cần check front là đủ.

nếu duyệt đến số dạng ai-k thì nó là số lớn nhất đã gặp có dạng đó -> ai+k tương ứng cũng lớn nhất. Push back vào queue là hợp lý.

https://leetcode.com/submissions/detail/800304114/

nhận thấy cái tính chất này cũng ghê thặc

mà toy làm bằng std::queue mất tới 0.4s, vẫn phải optimize bằng vector thoy

https://leetcode.com/submissions/detail/800538430/

code kia của toy vắt cổ chày vẫn ra nước

https://leetcode.com/submissions/detail/800543981/

từ 420MB mem xuống 300MB xuống 75MB xuống 20MB giờ xuống 14MB vắt sữa xướng thặc

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

thuyduong2007 đã nói:
t k nghĩ được ntn, cũng chưa hiểu cách này lắm. Cách t làm vẫn phải search. TC cũng là (N*N*logN) thôi. Có điều k dùng red-black tree hay hash table nên cache friendly hơn, chạy nhanh hơn.

10^5 mà NNlogN là 5*10^10 vẫn được á fen, leetcode cho giới hạn TC 10 mũ mấy vậy

Kân team v3 · 15/9/22

Lập Trình Viên Số Khổ đã nói:
10^5 mà NNlogN là 5*10^10 vẫn được á fen, leetcode cho giới hạn TC 10 mũ mấy vậy

bài hard thím brinbt đưa n có 10^3 à còn bài hôm nay medium thì 10^5

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

Member

Senior Member

Senior Member

Đã tốn tiền

Senior Member

Member

Đã tốn tiền

Senior Member

Member

Senior Member

Đã tốn tiền

Member

Senior Member

Member

Đã tốn tiền

Member

Senior Member

Senior Member

Senior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này