thuyduong2007
Member
Bài cuối hôm nay dùng topo sorting, setup bằng C++ mà mất tgian lâu quá. Sau đó chuyển qua python dùng https://docs.python.org/3/library/graphlib.html mà vẫn k kịp giờ, 
thảo luận Leetcode mỗi ngày
- Người tạo chủ đề _Gia_Cat_Luong_
- Ngày bắt đầu
- Trạng thái
thuyduong2007
Member
Bài 1 nó lừa đó, đọc kỹ cái đề bài: longest subsequence with limited sum
Nay t làm xong hết 3 bài đầu tầm 30p. Bài 4 setup cái topo sorting bằng C++ lâu quá, còn 1 tiếng mà k kịp,
. Biết thế dùng python luôn là kịp rồi, 
Lập Trình Viên Số Khổ
Senior Member
Python:
def toposort(graph):
res, found = [], [0] * len(graph)
stack = list(range(len(graph)))
while stack:
node = stack.pop()
if node < 0:
res.append(~node)
elif not found[node]:
found[node] = 1
stack.append(~node)
stack += graph[node]
# cycle check
for node in res:
if any(found[nei] for nei in graph[node]):
return None
found[node] = 0
return res[::-1]Code của thằng top1, ko đệ quy. Không phải Kahn vì nó select các node có in_degree = 0 vào trước.
Hình như là khử đệ quy, ai hiểu tại sao nó code như này ko.
Mà mấy cái vừa thi xong thì vào đâu để xem bọn nó giải thích nhỉ, trước có mục discuss mà giờ tìm hoài ko thấy
thuyduong2007
Member
Nó dùng dfs, kahn là bfs
firefox_nxh
Đã tốn tiền
Đọc đề k biết sai không nhưng hiểu đáp án cố định.
1 hướng là viết thẳng các số theo chiều dọc, từng cột. Xong roll mỗi hàng tương ứng với index của nó.
Mà submit fail, đến cách thứ 3 vẫn k được đành bỏ
1 hướng là viết thẳng các số theo chiều dọc, từng cột. Xong roll mỗi hàng tương ứng với index của nó.
Mà submit fail, đến cách thứ 3 vẫn k được đành bỏ
Lập Trình Viên Số Khổ
Senior Member
Cách làm hơi ma đạo tý, sửa mãi mới đúng 
Python:
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
parent_node ={}
def f_find(k):
if parent_node[k] == k:
return k
return f_find(parent_node[k])
def f_union(a, b):
x = f_find(a)
y = f_find(b)
parent_node[x] = y
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == "1":
parent_node[(i, j)] = (i, j)
arr = [item for item in parent_node]
for i, j in arr:
if i > 0 and grid[i-1][j] == "1": # above = 1
f_union((i, j), (i-1, j))
if j > 0 and grid[i][j-1] == "1": # left side = 1
f_union((i, j-1), (i-1, j))
else:
if j > 0 and grid[i][j-1] == "1": # left side = 1, above = 0
f_union((i, j), (i, j-1))
cnt = set()
for i, j in arr:
cnt.add(f_find((i, j)))
return len(cnt)
Cong_Go_De_Su
Senior Member
Bài hôm nay giải theo kiểu day 09 advent of code 2021 có vẻ dc, để tối về thử
Cách làm hơi ma đạo tý, sửa mãi mới đúng
Không có path compression và balance à?
Lập Trình Viên Số Khổ
Senior Member
chưa thuộc code bác
), đoạn code simple nhất cũng là lấy từ folder ra, áp vào thấy chạy nên chưa tối ưu
Kân team v3
Senior Member
Sửa lần cuối:
Lập Trình Viên Số Khổ
Senior Member
Đệ quy với neighbor là DFS chứ nhỉ bác
https://www.tutorialspoint.com/pyth...d-components-using-dfs-in-an-undirected-graph
Zayt__
Senior Member
Kân team v3
Senior Member
thì loang như MS Paint fill color ấy, dfs bfs gì cũng được, cách cũ xì
cách xịn hơn là weighted union find with path compression gì đấy, hình như mỗi operation union/find gần như là O(1)
đáng lẽ đánh dấu đã duyệt là ký tự '2' cũng được O(1) nhưng thoy tạo cái mảng khác tô màu luôn cho nó đẹp
Sửa lần cuối:
Arik97
Senior Member
Mấy cái tính %memory này cũng hơi ảo 
Cách làm cơ bản tạo mảng seen để đánh dấu thay vì modify input , vẫn beat 98% mem, 93% speed.
https://leetcode.com/submissions/detail/785949196/
Cách làm cơ bản tạo mảng seen để đánh dấu thay vì modify input , vẫn beat 98% mem, 93% speed.
https://leetcode.com/submissions/detail/785949196/
Cong_Go_De_Su
Senior Member
Đã xong
. Bọn leetcode chơi dơ, cái list input của elixir nó để code ascii của 0 và 1 là 48 và 49, làm debug cả buổi
Mã:
defmodule Solution do
@move_steps [{0, 1}, {0, -1}, {1, 0}, {-1, 0}]
def num_islands(grid) do
{row, col, ocean} = to_map(grid, 0, 0, %{})
for r <- 0..(row - 1), reduce: {MapSet.new(), 0} do
{visited, islands} ->
for c <- 0..(col - 1), reduce: {visited, islands} do
{visited, islands} ->
if MapSet.member?(visited, {r, c}) or Map.get(ocean, {r, c}) == ?0 do
{visited, islands}
else
{scan_island(ocean, visited, row, col, {r, c}), islands + 1}
end
end
end
|> elem(1)
end
defp scan_island(ocean, visited, max_row, max_col, point) do
if MapSet.member?(visited, point) or Map.get(ocean, point) == ?0 do
visited
else
@move_steps
|> Stream.map(&move(point, &1))
|> Stream.filter(&in_bound(max_row, max_col, &1))
|> Enum.reduce(
MapSet.put(visited, point),
fn p, v -> scan_island(ocean, v, max_row, max_col, p) end
)
end
end
defp move({r, c}, {vr, vc}), do: {r + vr, c + vc}
defp in_bound(row, col, {r, c}), do: not (r < 0 or r >= row or c < 0 or c >= col)
defp to_map([], row, col, map), do: {row, col, map}
defp to_map([[x]], row, col, map), do: {row + 1, col + 1, Map.put(map, {row, col}, x)}
defp to_map([[] | rest], row, _col, map), do: to_map(rest, row + 1, 0, map)
defp to_map([[x | r_rest] | rest], row, col, map),
do: to_map([r_rest | rest], row, col + 1, Map.put(map, {row, col}, x))
end
Sửa lần cuối:
firefox_nxh
Đã tốn tiền
Beat 5% python3. Học mấy cái graph mệt quá các cụ
30/08/2022
Ý tưởng: viết lại cái iterator để duyệt matrix theo chiều kim đồng hồ, sau đó dùng std::rotate(top-left, bottom-left, top-left) để quay trái, đưa bottom-left trở thành top-left.
Độ phức tạp: O(n^2) time, O(1) space
https://leetcode.com/submissions/detail/786807820/
Ý tưởng: viết lại cái iterator để duyệt matrix theo chiều kim đồng hồ, sau đó dùng std::rotate(top-left, bottom-left, top-left) để quay trái, đưa bottom-left trở thành top-left.
Độ phức tạp: O(n^2) time, O(1) space
https://leetcode.com/submissions/detail/786807820/
Zayt__
Senior Member
mỗi vị trí thì liệt kê 3 thằng còn lại rồi đổi chỗ 
Time O(n^2) với space O(1)
https://leetcode.com/submissions/detail/786807659/
Time O(n^2) với space O(1)
https://leetcode.com/submissions/detail/786807659/
- Trạng thái
Chủ đề tương tự
