thảo luận [Học Tập] Topic thuật toán

clgslsm216 đã nói:

Thank bác! Mà cái biến cnt dùng để làm gì vậy?

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

• 1 <= n <= 10^5: O(n) là đẹp
• Nhận thấy bài này có thể thực hiện dễ dàng bằng cách sử dụng HashSet với độ phức tạp là O(n) cả thời gian và không gian
• Tuy nhiên trong bài lại kèm điều kiện: You must write an algorithm that runs in O(n) time and uses only constant extra space.
• Để đạt với độ phức tạp không gian O(1), ta cần sử dụng thêm các dữ kiện khác trong bài toán. Mà cụ thể là: all the integers of nums are in the range [1, n]
• Thông thường khi gặp dạng bài có range value = array length như này, ta sẽ cần vận dụng một thông tin giá trị khác, đó là index của array
• Cụ thể hơn, vì mỗi một phần tử đều nằm trong khoảng [1, n], nên nó sẽ tương ứng với một index trong array [0, n - 1]. Ta cần khai thác tối đa đặc điểm này.
• Với bài này, mình sử dụng một kỹ thuật là đánh dấu bằng số âm.
• Với mỗi phần tử đã xuất hiện trong array, ta đánh dấu nó đã xuất hiện bằng cách set giá trị của phần tử tại vị trí tương ứng với nó về âm
• Như vậy, mỗi phần tử trong mảng có thể là âm hoặc dương, nên ta cần sử dụng trị tuyệt đối để lấy value đúng của nó
• Nếu một phần tử có index tương ứng đã bị set thành âm => nó đã xuất hiện trước đó => đây là số cần tìm

• Với mỗi số n trong nums
  • Tính giá trị đúng của n = abs(n)
  • Tính index tương ứng với idx = n - 1
  • Nếu nums[idx] < 0: n là số cần tìm => Thêm vào mảng output
  • Ngược lại: set nums[idx] = -nums[idx]
• Trả về mảng output

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        res = []
        for n in nums:
            absn = abs(n)
            idx = absn - 1
            if nums[idx] < 0:
                res.append(absn)
            else:
                nums[idx] = -nums[idx]
               
        return res

_Gia_Cat_Luong_ đã nói:

Tiếp tục chuyên mục mỗi ngày một leetcode. Các bài mình làm ngày hôm nay:

#440. (Hard) https://leetcode.com/problems/k-th-smallest-in-lexicographical-order/
#441. (Easy) https://leetcode.com/problems/arranging-coins/
#442. (Medium) https://leetcode.com/problems/find-all-duplicates-in-an-array/
#443. (Medium) https://leetcode.com/problems/string-compression/

Mình sẽ share về bài Find All Duplicates in an Array:
#442. (Medium) https://leetcode.com/problems/find-all-duplicates-in-an-array/

Phân tích bài toán:

• 1 <= n <= 10^5: O(n) là đẹp
• Nhận thấy bài này có thể thực hiện dễ dàng bằng cách sử dụng HashSet với độ phức tạp là O(n) cả thời gian và không gian
• Tuy nhiên trong bài lại kèm điều kiện: You must write an algorithm that runs in O(n) time and uses only constant extra space.
• Để đạt với độ phức tạp không gian O(1), ta cần sử dụng thêm các dữ kiện khác trong bài toán. Mà cụ thể là: all the integers of nums are in the range [1, n]
• Thông thường khi gặp dạng bài có range value = array length như này, ta sẽ cần vận dụng một thông tin giá trị khác, đó là index của array
• Cụ thể hơn, vì mỗi một phần tử đều nằm trong khoảng [1, n], nên nó sẽ tương ứng với một index trong array [0, n - 1]. Ta cần khai thác tối đa đặc điểm này.
• Với bài này, mình sử dụng một kỹ thuật là đánh dấu bằng số âm.
• Với mỗi phần tử đã xuất hiện trong array, ta đánh dấu nó đã xuất hiện bằng cách set giá trị của phần tử tại vị trí tương ứng với nó về âm
• Như vậy, mỗi phần tử trong mảng có thể là âm hoặc dương, nên ta cần sử dụng trị tuyệt đối để lấy value đúng của nó
• Nếu một phần tử có index tương ứng đã bị set thành âm => nó đã xuất hiện trước đó => đây là số cần tìm

Solution:

• Với mỗi số n trong nums
  • Tính giá trị đúng của n = abs(n)
  • Tính index tương ứng với idx = n - 1
  • Nếu nums[idx] < 0: n là số cần tìm => Thêm vào mảng output
  • Ngược lại: set nums[idx] = -nums[idx]
• Trả về mảng output

Python:

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        res = []
        for n in nums:
            absn = abs(n)
            idx = absn - 1
            if nums[idx] < 0:
                res.append(absn)
            else:
                nums[idx] = -nums[idx]
              
        return res

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

vexliva đã nói:

Fen này siêng nhẻ lập nhóm cuối tuần chiến leetcode weekly contest fen . Hồi đó siêng mà dạo này lười quá bỏ bê

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

_Gia_Cat_Luong_ đã nói:

Ngày làm mấy bài mất khoảng 1 tiếng thôi chứ cũng k siêng gì. Mình cày để ngày sau pv, còn mấy cái contest thấy chua quá, k hạp . Nên thôi, thank fen, chúc fen siêng năng trở lại.

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

vexliva đã nói:

Thì cũng 4 bài làm 1h30 phút mà chua gì fen, 1 easy, 2 med, 1 hard. Có điều làm dưới áp lực thời gian phê hơn

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

_Gia_Cat_Luong_ đã nói:

Ủa v à, trước h tưởng contest là dành cho tụi đỉnh của chóp thi, nên k đú vào bao h

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

vexliva đã nói:

https://leetcode.com/contest/weekly-contest-253
format 1 tuần nó 4 bài zậy nè fen

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

dangson đã nói:

Bọn này chúng nó có phải là người không vậy nhỉ? Có thằng làm 1 bài có 33s.
Xem tệp đính kèm 706145

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

vexliva đã nói:

Tôi đọc đề xong cũng hết 10 phút mà có thằng nó giải toàn bộ trong vòng 5 phút kìa

. Forum tụi nước ngoài ( bản xứ luôn ) nó cũng comment y chang, éo hiểu giải kiểu gì

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

_Gia_Cat_Luong_ đã nói:

Chắc nó từng làm trước rồi, vào copy paste lại thôi

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

_Gia_Cat_Luong_ đã nói:

Ngày làm mấy bài mất khoảng 1 tiếng thôi chứ cũng k siêng gì. Mình cày để ngày sau pv, còn mấy cái contest thấy chua quá, k hạp . Nên thôi, thank fen, chúc fen siêng năng trở lại.

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

vexliva đã nói:

Tôi đọc đề xong cũng hết 10 phút mà có thằng nó giải toàn bộ trong vòng 5 phút kìa

. Forum tụi nước ngoài ( bản xứ luôn ) nó cũng comment y chang, éo hiểu giải kiểu gì

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

Fire Of Heart đã nói:

tụi nó nhìn input và ouput là đoán dc đề rồi bạn ạ

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

Coffe_Bên_Lề đã nói:

Oh my...

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

• 1 <= n <= 500: O(n^2) hoặc O(n^2*logn)
• Dễ thấy bài toán có thể brute-force đơn giản bằng cách lặp qua mỗi bộ 3 (i, j, k) trong mảng. Tuy nhiên nếu làm vậy sẽ bị TLE vì độ phức tạp là O(n^3).
• Vậy ta cần nghĩ cách giảm độ phức tạp xuống O(n^2), thông thường để giảm từ O(n^3) xuống O(n^2)có 2 hướng (giống bài 3 Sum):
  • Lặp qua mỗi cặp (i, j), sau đó đếm các k thỏa mãn với độ phức tạp O(1)
  • Lặp qua mỗi số i, sau đó đếm các cặp (j, k) thỏa mãn với độ phức tạp O(n)
• Để làm được như trên, dĩ nhiên ta phải vận dụng các thuật toán / CTDL khác vào để tối ưu.
  
  
• Trong bài này mình áp dụng cách thứ 2, lặp qua mỗi phần tử i và tìm các cặp (j, k) phù hợp với đpt O(n)
• Vậy giả sử ta đã có i. Một cặp (j, k) như thế nào sẽ được gọi là phù hợp. Một cách tự nhiên, sẽ là khi (i, j, k) tạo thành một bộ ba thỏa mãn yêu cầu bài toán.
• Nhưng vì thứ tự trong bộ 3 là quan trọng. Nói (i, j, k) tạo thành bộ phù hợp, thì có thể là (i, j, k), hoặc (j, i, k) hoặc một (vài) hoán vị nào đó của 3 số này thỏa mãn ycbt, chứ k phải tất cả.
• Khá rắc rối! Để đơn giản hóa, ta cân nhắc 2 đặc điểm sau đây:
  • Việc đếm như trên sẽ bị trùng, giả sử với i = 1, ta tìm ra được cặp (2, 3) sẽ tạo thành bộ (1, 2, 3) phù hợp. Vậy khi xét i = 2, ta cũng sẽ tìm ra cặp (1, 3) thỏa mãn. Nếu ta đếm cả 2 thì sẽ bị trùng vì bộ (1, 2, 3) được đếm 2 lần.
  • Nếu (i, j, k) là một bộ thỏa mãn, thì dễ thấy (k, j, i) cũng sẽ thỏa mãn, vì khoảng cách i -> j bằng khoảng cách j -> k.
• Giải quyết ý thứ nhất, nhằm tránh trùng lắp, ta sẽ chỉ xét i tại một vị trí cố định. Ví dụ ta chỉ xét i ở vị trí đầu tiên, thì khi xét i = 1, ta chỉ xét các bộ (1, j, k) và (1, k, j) chứ không xét (j, 1, k) hay (j, k, 1),....
• Từ đó, ta kết hợp với ý thứ 2, giải pháp tối ưu sẽ là cố định i tại vị trí giữa, vì khi đó cả (j, i, k) và (k, i, j) đều là bộ phù hợp, không cần kiểm tra thêm.
  
  
• Bài toán tiếp theo là làm thế nào đếm được số lượng các cặp (j, k) phù hợp với độ phức tạp O(n)
• Để tìm được phương pháp, ta cần phân tích xem j và k có những tính chất gì đặc biệt
• Với bài này, vì (j, i, k) là một bộ phù hợp, nên dễ thấy khoảng cách từ j -> i bằng khoảng cách từ k -> i
• Hay nói ngược lại, nếu distance(i, j) = distance(i, k) thì (j, k) sẽ là một cặp phù hợp (và dĩ nhiên (k, j) cũng vậy)
• Nếu có thêm điểm q mà distance(i, q) cũng bằng distance(i, j) thì sao ? Khi đó mỗi bộ (j, i, q), (q, i, j), (q, i, k)... đều thỏa mãn
• Mở rộng ra, nếu có n điểm mà khoảng cách đến i bằng nhau, thì bất kì một cặp nào trong n điểm đó đều sẽ phù hợp. Ta cũng có thể dễ dàng suy ra công thức để đếm số lượng các cặp này.
• Đến đây, bài toán trở thành đếm số lượng các điểm có khoảng cách đến i bằng nhau. Và có thể giải đơn giản bằng Dictionary với độ phức tạp O(n).

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        res = 0
        d = defaultdict(int)
        for p in points:
            d.clear()
            for q in points:
                dis = (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1])
                if dis > 0:
                    d[dis] += 1
         
            for n in d.values():
                res += n * (n - 1)
                 
        return res