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

8/7/2022:
  • 1 Câu hard khó, nhưng khó ở chỗ code khá dài vì nhiều dữ liệu
  • Nhìn vào đề bài: yêu cầu min cost cho target group, 1 group là gồm các nhà có màu liên tiếp
-> dẽ thấy có thể dùng backtracking, mỗi nhà có thể tô n màu -> time O(n^m) -> tle
  • như vậy phải tối ưu
  • nhận thấy 1 key khá quan trọng, số group sẽ tăng nếu houses[i.] != houses[i - 1]
-> dùng qhđ
  • tạo mảng 2 chiều dp, trong đó dp[i.][j.] là min cost có i group và kết thúc tại màu j
  • tạo hàm add để xét màu nhà thứ i vào cái dp
Xét lần lượt các ngôi nhà:
nếu houses[i.] == 0 -> nhà này có thể có nhiều màu, add lần lượt các màu và cost của có vào dp
nếu houses[i,] != 0 -> chỉ add màu nhà đó và cost lúc đó bằng 0
  • Về hàm add thì nhìn vào code :), làm câu này 1 tiếng nên h mệt, lúc nào khỏe thì viết tiếp
  • Nói chung là câu này ý tưởng cx khá dễ đoán mất 10p để nghĩ ra, không quá khó để nghĩ ra mà lúc code loạn vl vì nhiều dữ kiện quá dẫn đến code mất 50 phút:beat_brick::beat_brick:
  • Code : https://leetcode.com/submissions/detail/741509252/ (đã cố gắng viết gọn nhất có thể)
 
Last edited:
Violet_7 said:
8/7/2022:
  • 1 Câu hard khó, nhưng khó ở chỗ code khá dài vì nhiều dữ liệu
  • Nhìn vào đề bài: yêu cầu min cost cho target group, 1 group là gồm các nhà có màu liên tiếp
-> dẽ thấy có thể dùng backtracking, mỗi nhà có thể tô n màu -> time O(n^m) -> tle
  • như vậy phải tối ưu
  • nhận thấy 1 key khá quan trọng, số group sẽ tăng nếu houses[i.] != houses[i - 1]
-> dùng qhđ
  • tạo mảng 2 chiều dp, trong đó dp[i.][j.] là min cost có i group và kết thúc tại màu j
  • tạo hàm add để xét màu nhà thứ i vào cái dp
Xét lần lượt các ngôi nhà:
nếu houses[i.] == 0 -> nhà này có thể có nhiều màu, add lần lượt các màu và cost của có vào dp
nếu houses[i,] != 0 -> chỉ add màu nhà đó và cost lúc đó bằng 0
  • Về hàm add thì nhìn vào code :), làm câu này 1 tiếng nên h mệt, lúc nào khỏe thì viết tiếp
  • Nói chung là câu này ý tưởng cx khá dễ đoán mất 10p để nghĩ ra, không quá khó để nghĩ ra mà lúc code loạn vl vì nhiều dữ kiện quá dẫn đến code mất 50 phút:beat_brick::beat_brick:
  • Code :https://leetcode.com/submissions/detail/741406332/ (đã cố gắng viết gọn nhất có thể)
Click to expand...
Bài nàm làm bottom-up dài vậy nhỉ. Top down có chút:
https://leetcode.com/submissions/detail/741438343/
 
Có ý tưởng dùng đồ thị như này chưa có thời gian code, bác nào thử xem có vấn đề gì không:

  • Vertex là |V| = {s, (i, j,k) } với s là một vertex ảo đánh dấu điểm bắt đầu, (i, j,k) là đại diện cho việc house i được tô bởi color j và đã có k neighborhood,
  • Edge nối từ s -> (0, j, 1) hoặc (i, j,k) -> (i + 1, j,k) hoặc (i,j,k) -> (i+1,j', k+1) với weight là cost[i+1][j],
  • Dùng Dijkstra để tìm đường đi ngắn nhất từ s tới n điểm có dạng (m-1, j, target).
  • Trick tối ưu:
    • Loại bỏ những vertex bất khả thi ngay từ đầu. VD có dạng (i, j, k) với k < i, hoặc (m-1, j, k) với k < target.
    • Trong quá trình tìm kiếm nếu gặp (i, j, target) thì chỉ lấy những vertex kề có cùng color j
 
Last edited:
_Gia_Cat_Luong_ said:
Bài nàm làm bottom-up dài vậy nhỉ. Top down có chút:
https://leetcode.com/submissions/detail/741438343/
Click to expand...
Sao em implement y hệt code java của nó phần TOP-DOWN nhưng bị TLE. Xoá hết mảng memo, dùng decorator @cache thì lại chạy được. Ảo diệu quá, bác biết tại sao lại thế k :(

Python: 
class Solution:

    def minCost(self, houses, cost, m, n, target):

        memo = [[[None for _ in range(21)] for _ in range(100)] for _ in range(100)]
        MAX_COST = 1000001

        def find_min_cost(curr_index: int, neighbors_cnt: int, prev_color: int ):

            if curr_index == len(houses):
                return 0 if neighbors_cnt == target else MAX_COST

            if neighbors_cnt > target:
                return MAX_COST
           
            print(curr_index, neighbors_cnt, prev_color)
            if memo[curr_index][neighbors_cnt][prev_color] is not None:
                return memo[curr_index][neighbors_cnt][prev_color]

            min_cost = MAX_COST

            # Nếu nhà tại index này đã tô màu -> update neighbors_cnt và prev_color
            if houses[curr_index] != 0:
                new_neighbors_cnt = neighbors_cnt + (0, 1)[houses[curr_index] != prev_color]
                min_cost = find_min_cost(curr_index + 1, new_neighbors_cnt, houses[curr_index])

            # Nếu nhà tại index này chưa tô màu -> tô từ màu 1 đến màu cuối
            else:
                for color in range(1, len(cost[0])+1):
                    print(curr_index, color)
                    new_neighbors_cnt = neighbors_cnt + (0, 1)[color != prev_color]
                    curr_cost = cost[curr_index][color-1] + find_min_cost(curr_index+1, new_neighbors_cnt, color)
                    min_cost = min(min_cost, curr_cost)

            memo[curr_index][neighbors_cnt][prev_color] = min_cost
            return min_cost

        answer = find_min_cost(0, 0, 0)
        return (answer, -1)[answer == MAX_COST]
 
Lập Trình Viên Số Khổ said:
Sao em implement y hệt code java của nó phần TOP-DOWN nhưng bị TLE. Xoá hết mảng memo, dùng decorator @cache thì lại chạy được. Ảo diệu quá, bác biết tại sao lại thế k :(

Python: 
class Solution:

    def minCost(self, houses, cost, m, n, target):

        memo = [[[None for _ in range(21)] for _ in range(100)] for _ in range(100)]
        MAX_COST = 1000001

        def find_min_cost(curr_index: int, neighbors_cnt: int, prev_color: int ):

            if curr_index == len(houses):
                return 0 if neighbors_cnt == target else MAX_COST

            if neighbors_cnt > target:
                return MAX_COST
          
            print(curr_index, neighbors_cnt, prev_color)
            if memo[curr_index][neighbors_cnt][prev_color] is not None:
                return memo[curr_index][neighbors_cnt][prev_color]

            min_cost = MAX_COST

            # Nếu nhà tại index này đã tô màu -> update neighbors_cnt và prev_color
            if houses[curr_index] != 0:
                new_neighbors_cnt = neighbors_cnt + (0, 1)[houses[curr_index] != prev_color]
                min_cost = find_min_cost(curr_index + 1, new_neighbors_cnt, houses[curr_index])

            # Nếu nhà tại index này chưa tô màu -> tô từ màu 1 đến màu cuối
            else:
                for color in range(1, len(cost[0])+1):
                    print(curr_index, color)
                    new_neighbors_cnt = neighbors_cnt + (0, 1)[color != prev_color]
                    curr_cost = cost[curr_index][color-1] + find_min_cost(curr_index+1, new_neighbors_cnt, color)
                    min_cost = min(min_cost, curr_cost)

            memo[curr_index][neighbors_cnt][prev_color] = min_cost
            return min_cost

        answer = find_min_cost(0, 0, 0)
        return (answer, -1)[answer == MAX_COST]
Click to expand...
Submit được mà, có TLE đâu bác ?
https://leetcode.com/submissions/detail/741670142/
 
https://voz.vn/t/leetcode-moi-ngay.568742/post-18821562

Cách làm OK.
Lâu không code đồ thị tốn thời gian quá.

1657289374649.png


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

Để giảm không gian tìm kiếm thì ban đầu vào đưa những vertex (i, j, t) dạng sau vào danh sách invalid:
  • i < t: vì sau i house chắc chắn sẽ có ít nhất i neighborhood,
  • Tương tự: m - i < target - t: trường hợp này sẽ không đạt được neighborhood bằng target.

Những trường hợp sau chắc chắn là invalid để đảm bảo tính đúng đắn:
  • house[i] > 0 && house[i] != j + 1
 
bribnt said:
https://voz.vn/t/leetcode-moi-ngay.568742/post-18821562

Cách làm OK.
Lâu không code đồ thị tốn thời gian quá.

View attachment 1254429

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

Để giảm không gian tìm kiếm thì ban đầu vào đưa những vertex (i, j, t) dạng sau vào danh sách invalid:
  • i < t: vì sau i house chắc chắn sẽ có ít nhất i neighborhood,
  • Tương tự: m - i < target - t: trường hợp này sẽ không đạt được neighborhood bằng target.

Những trường hợp sau chắc chắn là invalid để đảm bảo tính đúng đắn:
  • house[i] > 0 && house[i] != j + 1
Click to expand...
Quá đỉnh mai fen
 
7/9/2022:
  • 1 câu medium khá quen
  • Ý tưởng là 1 câu biến tấu câu max window: https://leetcode.com/problems/sliding-window-maximum/
  • lời giải câu trên https://vnoi.info/wiki/algo/data-structures/deque-min-max.md
  • tạo mảng dp với dp[i.] là max score khi con ếch đến ô thứ i
  • vì con ếch chỉ nhảy đc từ 1 đến k bước nên để đến đc ô thứ i thì trước đó con ếch có thể đứng ở 1 trong k ô trước đó
  • vậy nếu biết dp của k ô trước đó thì dp[i.] = max(dp[i - k] -> dp[i - 1]) + nums[i.]
  • như vậy áp dụng công thức qhđ trên và ý tưởng câu tìm max trên 1 đoạn tịnh tiến k sẽ ra đáp án
  • Lúc đầu cx áp dụng cái câu max window kia mà phức tạp xét âm dương nên code hơi dài, đọc solution thì chả cần phải tách âm dương làm j nên đã tối ưu code lại:
https://leetcode.com/submissions/detail/742162855/
 
Last edited:
Violet_7 said:
7/9/2022:
  • 1 câu medium khá quen
  • Ý tưởng là 1 câu biến tấu câu max window: https://leetcode.com/problems/sliding-window-maximum/
  • lời giải câu trên https://vnoi.info/wiki/algo/data-structures/deque-min-max.md
  • tạo mảng dp với dp[i.] là max score khi con ếch đến ô thứ i
  • vì con ếch chỉ nhảy đc từ 1 đến k bước nên để đến đc ô thứ i thì trước đó con ếch có thể đứng ở 1 trong k ô trước đó
  • vậy nếu biết dp của k ô trước đó thì dp[i.] = max(dp[i - k] -> dp[i - 1]) + nums[i.]
  • như vậy áp dụng công thức qhđ trên và ý tưởng câu tìm max trên 1 đoạn tịnh tiến k sẽ ra đáp án
  • Lúc đầu cx áp dụng cái câu max window kia mà phức tạp xét âm dương nên code hơi dài, đọc solution thì chả cần phải tách âm dương làm j nên đã tối ưu code lại:
https://leetcode.com/submissions/detail/742162855/
Click to expand...
Ý tưởng dùng deque hay đó.
Tuy nhiên phần đề cập đến độ phức tạp của deque trong bài viết của vnoi là không đúng.
1657337142900.png

https://en.cppreference.com/w/cpp/container/deque/operator_at
 
Lập Trình Viên Số Khổ said:
cay, giải giống hôm qua rồi mà bị
View attachment 1255197
Click to expand...
t submit lần đầu cũng bị ntn. Do k chịu đọc kỹ chỗ đề bài
1657338230835.png

Cách làm này độ phức tạp là O(nums.length*k) nên với constraints như trên thì TLE là đúng rồi.

Coi cách làm bên trên chỗ xử lý cái max để giảm độ phức tạp thì sẽ pass đc. :p
 
thuyduong2007 said:
t submit lần đầu cũng bị ntn. Do k chịu đọc kỹ chỗ đề bài
View attachment 1255199
Cách làm này độ phức tạp là O(nums.length*k) nên với constraints như trên thì TLE là đúng rồi.

Coi cách làm bên trên chỗ xử lý cái max để giảm độ phức tạp thì sẽ pass đc. :p
Click to expand...
chứng minh kiểu gì để ra độ phức tạp là O(NK) với top-down memo vậy bác
 

Similar threads

buiduchanh1995
thắc mắc Cách thiết kế database cho hệ thống lớn
2
Replies
37
Views
3K
khonganhit19
khonganhit19
meekoo
thắc mắc [Hỏi AI] Cách làm sao để train AI hiểu một task nào đấy?
Replies
9
Views
994
weed_bông
weed_bông
IM LANG
thắc mắc Cần cao nhân giúp đỡ về WordPress (có sử dụng custom theme bằng HTML, CSS)
Replies
3
Views
319
zaizai_vjp
zaizai_vjp
quangpt12345
kiến thức Join Anchor Consortium trading crypto sàn Odyssey kiếm lợi nhuận 2-3% mỗi ngày
Replies
4
Views
162
quangpt12345
quangpt12345
J
kiến thức Mod Mộng Liêu Trai mới nhất
Replies
0
Views
95
jivrus
J

Share this page

Back
Top