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

Cong_Go_De_Su · 18/9/22

Daily hôm nay dễ thế nhỉ, bọn leetcode này rating đề vớ vẩn thật

Mã:

defmodule Solution do
  def trap([]), do: 0
  def trap([_]), do: 0
  def trap([_, _]), do: 0
  def trap([left, mid, right]), do: max(0, min(left, right) - mid)
  def trap(heights) do
    heights
    |> Enum.reduce({[], 0}, fn mid, {columns, max_left} ->
      {[[max_left, mid] | columns], max(mid, max_left)}
    end)
    |> elem(0)
    |> Enum.reduce({0, 0}, fn [max_left, mid], {water, max_right} ->
      {water + trap([max_left, mid, max_right]), max(mid, max_right)}
    end)
    |> elem(0)
  end
end

dynamic programming · 18/9/22

NudeDuck đã nói:
contest nay dễ thế nhỉ, Cơ mà sao câu cuối làm hash bị TLE nhỉ, là O(nm) = O(10^6) mà

Bác hash 1 string thì dù gì hash function cũng phải duyệt qua cả string đó rồi mới gen ra được một số nên ko phải O(nm). Vd như hash("a") với hash("aaaaaaaa") thì thời gian ko giống nhau đâu.
Bác đọc trong này có ví dụ về 1 hàm polynomial rolling hash này
https://cp-algorithms.com/string/string-hashing.html

NudeDuck · 18/9/22

bribnt đã nói:
Tại vì nó bản chất là O(nm^2)
Các fen nên đọc kỹ lại về hàm hash và cách implement hash map.

dynamic programming đã nói:
Bác hash 1 string thì dù gì hash function cũng phải duyệt qua cả string đó rồi mới gen ra được một số nên ko phải O(nm). Vd như hash("a") với hash("aaaaaaaa") thì thời gian ko giống nhau đâu.
Bác đọc trong này có ví dụ về 1 hàm polynomial rolling hash này
https://cp-algorithms.com/string/string-hashing.html

Ồ hiểu rồi thank you 2 fen nhiều nha

Arishem the Judge · 18/9/22

bạn nào có solution cho cái này ko nhỉ https://leetcode.com/submissions/detail/802749118/ . Mình pass 32/38 testcase, dính cái TLE .độ phức tạp của mình là 0(n*m)^2

Aristides · 18/9/22

leetcode hôm nay khá dễ

Code bằng python thử

Python:

class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height) == 0:
            return 0
        l = 0
        r = len(height) - 1
        max_l = height[l]
        max_r = height[r]
        ans = 0
        while l < r:
            if max_l < max_r:
                l += 1
                max_l = max(max_l, height[l])
                ans += max_l - height[l]
            else:
                r -= 1
                max_r = max(max_r, height[r])
                ans += max_r - height[r]
        return ans

Aristides · 18/9/22

nhân tiện, OOP trong python không có keyword private, protected hay public à?

Implement encapsulation trong Python thì làm sao?

sau_tim_thiep_hong · 18/9/22

Aristides đã nói:
nhân tiện, OOP trong python không có keyword private, protected hay public à?

Implement encapsulation trong Python thì làm sao?

Convention thôi bác xài _ trước biến

Aristides · 18/9/22

sau_tim_thiep_hong đã nói:
Convention thôi bác xài _ trước biến

what the.....? Convention?
Không phải syntax à?

sau_tim_thiep_hong · 18/9/22

Aristides đã nói:
what the.....? Convention?
Không phải syntax à?

ko bác tự hiểu :beat_brick:

Blue Amethyst · 18/9/22

Không liên quan tới bài daily hôm nay, em có 2 cái submission này https://leetcode.com/submissions/detail/802613078/
và cái này https://leetcode.com/submissions/detail/802614077/

Time complexity của từng cái là bao nhiêu vậy mấy bác? Cái sau thì em đoán là O(nk), n là số node còn k là số list, nhưng còn cái đầu là bao nhiêu mà nhanh hơn nhiều thế nhỉ :burn_joss_stick:

Làm thì làm ra được, mà tính không được :beat_brick:

Kân team v3 · 19/9/22

Blue Amethyst đã nói:
Không liên quan tới bài daily hôm nay, em có 2 cái submission này https://leetcode.com/submissions/detail/802613078/
và cái này https://leetcode.com/submissions/detail/802614077/

Time complexity của từng cái là bao nhiêu vậy mấy bác? Cái sau thì em đoán là O(nk), n là số node còn k là số list, nhưng còn cái đầu là bao nhiêu mà nhanh hơn nhiều thế nhỉ Làm thì làm ra được, mà tính không được

n là cái gì thấy k ko à

cái đầu chắc là O(k^2) ~ 10^8

do merge list bự liên tục, ví dụ k[1] + k[2] = k[1&2], rồi k[1&2] + k[3] = k[1&2&3], v.v... thì k[1] sẽ bị merge đi merge lại k lần, nếu k[1] có số phần tử ~ k phần tử thì O(k^2)
cái thứ 2 là O(klogk) ~ 140k

do list bự được push về phía sau queue nên nó ko bị lặp k lần như vậy nữa, mà chỉ lặp tối đa O(logk) lần thoy. Ví dụ k=10, k[1]...k[10] nó sẽ gộp thành k[1&2], k[3&4], ..., k[9&10] rồi mới gộp tiếp k[1&2] và k[3&4], mỗi lần gộp số lượng lists giảm 2 lần thì chỉ bị gộp logk lần như vậy thoy nên là O(klogk)

The sum of lists[\i].length will not exceed 10^4.

nó cho điều kiện thế lày thì trường hợp xấu nhứt là 10^4 lists, mỗi list 1 phần tử. Cách đầu gộp 1 & 1 thành 2 tốn 2, rồi gộp 2 & 1 thành 3 tốn 3, v.v... gộp i & 1 thành i+1 tốn i+1. Tổng cộng tốn 2+3+...+(i+1)+...+k là O(k^2)

còn cái kia thì gộp k list 1 phần tử thành k/2 list 2 phần tử, tốn 2 * k/2 = k. Gộp tiếp k/2 list 2 phần tử thành k/4 list 4 phần tử, tốn 4 * k/4 = k. Lặp tới khi k/2^x = 1 nghĩa la x = logk lần, mỗi lần tốn k vậy tổng cộng là O(klogk)

Kân team v3 · 19/9/22

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

vừa viết lại bài daily hôm qua 105 dòng thoy

Ma na chơ + Trie O(nk) mà mất toàn 2.5s, hên xao có lần submit này 1.4s cho đỡ nhục

_Gia_Cat_Luong_ · 19/9/22

Kân team v3 đã nói:
https://leetcode.com/submissions/detail/803224349/

vừa viết lại bài daily hôm qua 105 dòng thoy

Ma na chơ + Trie O(nk) mà mất toàn 2.5s, hên xao có lần submit này 1.4s cho đỡ nhục

How about z function ?
https://leetcode.com/submissions/detail/803297184/

Kân team v3 · 19/9/22

_Gia_Cat_Luong_ đã nói:
How about z function ?
https://leetcode.com/submissions/detail/803297184/

toy ko biết z function là cái gì

bribnt · 19/9/22

220919 - 609. Find Duplicate File in System

Lâu lắm mới được 100% time và hơn 99% mem.

Cơ bản là hạn chế tối đa việc cấp phát và copy string. Bằng những cách sau:

Dùng unordered_map<string_view, vector<string>>. string_view để chứa file content thay cho string để không phải copy và cấp phát mới string mỗi lần thao tác với map,
Dùng tìm kiếm index của ký tự cần tìm thay cho các thể loại string split,
Lần duy nhất phải tạo string mới mà không dùng được string_view là tạo file path hoàn chỉnh vì trong chuỗi gốc không tồn tại đoạn liên tục nào chứa nó. Thì cũng làm theo kiểu alloc trước toàn bộ độ dài và copy các phần vào thay vì dùng toán tử + ghép chuỗi.

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

Kân team v3 đã nói:
toy ko biết z function là cái gì

z function thuật toán cũng na ná Manacher thôi.

nhân vật phụ · 19/9/22

cái này còn tối ưu được chỗ nào không các fen?

Java:

class Solution {
    public List<List<String>> findDuplicate(String[] paths) {
        Map<String, List<String>> map = new HashMap<>();
       
        for (String dirPath : paths) {
            String[] dirParts = dirPath.split(" ");
           
            for (int i = 1; i < dirParts.length; i++) {
                String[] fileParts = dirParts[i].split("\\(");
                map.putIfAbsent(fileParts[1], new ArrayList<>());
                map.get(fileParts[1]).add(dirParts[0] + "/" + fileParts[0]);
            }
        }
       
        List<List<String>> duplicatedFilePaths = new ArrayList<>();
       
        for (List<String> filePaths : map.values()) {
            if (filePaths.size() > 1) {
                duplicatedFilePaths.add(filePaths);
            }
        }
       
        return duplicatedFilePaths;
    }
}

dangson · 19/9/22

Nghĩ gì viết nấy vậy. :3
Hơi chậm vì phải string split, cuối dùng lại phải duyệt dict một lần nữa để lọc chỉ những thằng có duplicate.

Python:

class Solution:
    def findDuplicate(self, paths: List[str]) -> List[List[str]]:
        files = defaultdict(list)
        for _folder in map(lambda n: n.split(), paths):
            for file in _folder[1:]:
                content_s = file.index("(")
                content_e = file.index(")")
                files[file[content_s:content_e]].append(_folder[0] + "/" + file[:content_s])
        return [files[dup] for dup in files if len(files[dup]) > 1] # Returns duplicate only

nhân vật phụ · 19/9/22

dangson đã nói:
Nghĩ gì viết nấy vậy. :3
Hơi chậm vì phải string split, cuối dùng lại phải duyệt dict một lần nữa để lọc chỉ những thằng có duplicate.

Python:

class Solution: def findDuplicate(self, paths: List[str]) -> List[List[str]]: files = defaultdict(list) for _folder in map(lambda n: n.split(), paths): for file in _folder[1:]: content_s = file.index("(") content_e = file.index(")") files[file[content_s:content_e]].append(_folder[0] + "/" + file[:content_s]) return [files[dup] for dup in files if len(files[dup]) > 1] # Returns duplicate only

fen thay cái content_e bằng len - 1 hoặc bỏ luôn cũng được, content của mọi file đều có thêm ")" thì lúc so sánh nó vẫn là giống nhau thôi mà

Cong_Go_De_Su · 19/9/22

Pattern matching to the rescue

Mã:

defmodule Solution do
  def find_duplicate(paths) do
    paths
    |> Enum.reduce(%{}, fn path, map ->
      [dir | files] = String.split(path, " ")

      files
      |> Stream.map(&String.split(&1, "("))
      |> Enum.reduce(map, fn [name, content], map ->
        Map.update(map, content, [dir <> "/" <> name], &[dir <> "/" <> name | &1])
      end)
    end)
    |> Map.filter(fn
      {_, [_, _ | _]} -> true
      _ -> false
    end)
    |> Map.values()
  end
end

Kân team v3 · 19/9/22

toy viết code trong xáng ko có optimize gì cũng 90ms đây https://leetcode.com/submissions/detail/803269577/

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

Senior Member

Junior Member

Junior Member

Junior Member

Senior Member

Senior Member

Member

Senior Member

Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Đã tốn tiền

Tệp đính kèm

Senior Member

Đã tốn tiền

Senior Member

Senior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này