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

Lập Trình Viên Gà · 18/6/22

Vào trong này toàn quái vật IQ cao, sợ vc

thuyduong2007 · 18/6/22

tdat00 đã nói:
Oh dĩ nhiên nhanh hơn thì phải tốn mem hơn rồi. Mà thường thì người ta chú trọng thời gian hơn memo.

Sent from Samsung SM-A528B using vozFApp

nó nhanh hơn lúc search thôi, còn lúc build cái trie thì lại chậm hơn rất rất nhiều. VD 1 chuỗi có length là 1000 thì nó phải insert 1000 lần chuỗi có độ dài từ 1002 đến 2001. Trong khi cách dùng 2 trie chỉ cần insert duy nhất 2 lần: chuỗi ban đầu và đảo ngược của nó.

Nên nếu nói cách https://www.geeksforgeeks.org/searc...with-a-given-prefix-and-suffix-for-q-queries/ luôn luôn nhanh hơn là chưa chắc đúng đâu fen. Chuỗi s mà dài quá là vỡ mồm ngay.

**Doremon** · 19/6/22

jupyter đã nói:
liệt kê tất cả số có 3 chữ số tạo bởi 2 số a hoặc b hoặc cả 2 trong ma trận
nếu giải tay thì ta biết dc có 2^3=8 số thỏa mãn,aaa,aab,aba,......,bbb
ví dụ
input:1,2
output:
[
[1, 1, 1]
[1, 1, 2]
[1, 2, 1]
.....
.....
.....
[2, 2, 2]
]
giúp em với

Bài này bác dùng backtracking là ra

thuyduong2007 · 19/6/22

jupyter đã nói:
liệt kê tất cả số có 3 chữ số tạo bởi 2 số a hoặc b hoặc cả 2 trong ma trận
nếu giải tay thì ta biết dc có 2^3=8 số thỏa mãn,aaa,aab,aba,......,bbb
ví dụ
input:1,2
output:
[
[1, 1, 1]
[1, 1, 2]
[1, 2, 1]
.....
.....
.....
[2, 2, 2]
]
giúp em với

Python:

def func(a, b):
    ret = [[]]
    for i in range(0,3):
        ret = [[a] + x for x in ret] + [[b] + x for x in ret]
    return ret
   
print(func(1,2))

đây nhé,

Đời Cơ Bản Là Buồn · 19/6/22

jupyter đã nói:
liệt kê tất cả số có 3 chữ số tạo bởi 2 số a hoặc b hoặc cả 2 trong ma trận
nếu giải tay thì ta biết dc có 2^3=8 số thỏa mãn,aaa,aab,aba,......,bbb
ví dụ
input:1,2
output:
[
[1, 1, 1]
[1, 1, 2]
[1, 2, 1]
.....
.....
.....
[2, 2, 2]
]
giúp em với

a, b có ràng buộc từ 0 - 9 không thế?
Nếu 0 - 9 thì liệt kê 8 cái mảng, nhớ check phần tử đầu của 8 mảng khác 0, chỉ trả về mảng nào phần tử đầu khác 0 :cautious:

v0ztrash · 19/6/22

jupyter đã nói:
liệt kê tất cả số có 3 chữ số tạo bởi 2 số a hoặc b hoặc cả 2 trong ma trận
nếu giải tay thì ta biết dc có 2^3=8 số thỏa mãn,aaa,aab,aba,......,bbb
ví dụ
input:1,2
output:
[
[1, 1, 1]
[1, 1, 2]
[1, 2, 1]
.....
.....
.....
[2, 2, 2]
]
giúp em với

Dùng BFS cho nó dễ hình dung, backtrack đau đầu lắm

C++:

queue<string>q;
        q.push("1");
        q.push("2");
        vector<string>res;
        while(!q.empty()){
            string z=q.front();
            q.pop();
            if(z.size()==3){
                res.push_back(z);
                continue;
            }
            q.push(z+"1");
            q.push(z+"2");
        }
        for(auto x:res) cout<<x<<" ";

realhaidinh · 19/6/22

bài này dạng in ra tất cả các số nhị phân có n chữ số, có thể dùng thuật toán sinh cũng được

Mr Robot · 20/6/22

Hồi ở trường không được học thuật toán nên không có căn bản, bay vô leet code tập làm có được k mấy thím. Hay phải học có bản mới được :beat_brick:

Gửi từ Samsung SM-G996B bằng vozFApp

Gâu Gâu Gâu Gâu · 20/6/22

jupyter đã nói:
liệt kê tất cả số có 3 chữ số tạo bởi 2 số a hoặc b hoặc cả 2 trong ma trận
nếu giải tay thì ta biết dc có 2^3=8 số thỏa mãn,aaa,aab,aba,......,bbb
ví dụ
input:1,2
output:
[
[1, 1, 1]
[1, 1, 2]
[1, 2, 1]
.....
.....
.....
[2, 2, 2]
]
giúp em với

Bài này giống đố mẹo hoặc là mới nhập môn vậy?. Biết trước có 8 cách rồi thì tạo cái mảng 2 chiều với 2 biến a, b sẵn rồi print ra là đc, loop với đệ quy làm gì cho mệt. Khi nào 2 cái số 2 và 3 nó thành n và m thì mới cần giải.

H410 · 21/7/22

vô nhóm IT VOZ Lab này thảo luận trực tiếp luôn, có rất nhiều bạn newbie gà mờ được các anh chỉ dẫn giờ đánh LOL hay vãi nhưng đã có công việc về ngành IT rất ổn định

https://discord.gg/YDpsvad8

xapziat · 17/11/22

các bác giúp e bài này với ạ

Violet_7 · 17/11/22

xapziat đã nói:
Xem tệp đính kèm 1505065
các bác giúp e bài này với ạ

Thuật toán Floyde Bellman cơ bản thôi. Không nhớ viết đúng ko. Hoặc tra trên vnoi các thuật toán đường đi ngắn nhất là ra

xapziat · 17/11/22

Violet_7 đã nói:
Thuật toán Floyde Bellman cơ bản thôi. Không nhớ viết đúng ko. Hoặc tra trên vnoi các thuật toán đường đi ngắn nhất là ra

ý bác là tìm đường đi ngắn nhất rồi chọn min đúng kh ạ, có thuật nào tối ưu hơn không ạ

BetterNextTime · 17/11/22

xapziat đã nói:
ý bác là tìm đường đi ngắn nhất rồi chọn min đúng kh ạ, có thuật nào tối ưu hơn không ạ

Mỗi lần tìm xong đường đi ngắn nhất từ 1 đỉnh v tới đích t thì bác lưu tất cả các đỉnh trên đường đi từ v tới t (kèm khoảng cách) lại.

Sau đó ko cần xét lại các đỉnh đã lưu nữa hoặc sử dụng đỉnh đã cache từ trước để tính toán cho đỉnh mới thay vì đi lại.

Sửa Dijkstra lại 1 chút là được

Violet_7 · 17/11/22

xapziat đã nói:
ý bác là tìm đường đi ngắn nhất rồi chọn min đúng kh ạ, có thuật nào tối ưu hơn không ạ

H đọc lại đề thì thấy cần 3 đỉnh thôi thì dùng djstra thôi.

thuyduong2007 · 17/11/22

BetterNextTime đã nói:
Mỗi lần tìm xong đường đi ngắn nhất từ 1 đỉnh v tới đích t thì bác lưu tất cả các đỉnh trên đường đi từ v tới t (kèm khoảng cách) lại.

Sau đó ko cần xét lại các đỉnh đã lưu nữa hoặc sử dụng đỉnh đã cache từ trước để tính toán cho đỉnh mới thay vì đi lại.

Sửa Dijkstra lại 1 chút là được

K cần đâu làm vậy đâu, suy nghĩ ngược lại thay vì tìm đường đi ngắn nhất từ tất cả các đỉnh đến t thì từ t đi ngược lại 3 đỉnh bằng djstra ấy. 3 đỉnh reachable đầu tiên là 3 đỉnh có đường đi ngắn nhất đến t.

bribnt · 17/11/22

thuyduong2007 đã nói:
K cần đâu làm vậy đâu, suy nghĩ ngược lại thay vì tìm đường đi ngắn nhất từ tất cả các đỉnh đến t thì từ t đi ngược lại 3 đỉnh bằng djstra ấy. 3 đỉnh reachable đầu tiên là 3 đỉnh có đường đi ngắn nhất đến t.

Không được đâu, vì theo đề bài thì đồ thị là có hướng, đường đi ở hai chiều không nhất thiết tương đương.

--
Edited: Nếu dùng với đồ thị ngược của input thì có khi được.

Vậy thuật toán sẽ là như này:

B1: đặt E' = <đảo chiều các cạnh của E>
B2: Chạy Dijkstra (V, E') với bắt đầu là t. Dừng khi tìm được đường đi ngắn nhất đến tất cả N điểm nguồn,
B3: Output 3 đường đi ngắn nhất trong số N

xapziat · 17/11/22

thuyduong2007 đã nói:
K cần đâu làm vậy đâu, suy nghĩ ngược lại thay vì tìm đường đi ngắn nhất từ tất cả các đỉnh đến t thì từ t đi ngược lại 3 đỉnh bằng djstra ấy. 3 đỉnh reachable đầu tiên là 3 đỉnh có đường đi ngắn nhất đến t.

reachable đầu tiên chưa chắc là ngắn nhất bác, đỉnh nào phải là được chọn để đi tiếp mới là ngắn nhất chứ ạ

xapziat · 17/11/22

bribnt đã nói:
Không được đâu, vì theo đề bài thì đồ thị là có hướng, đường đi ở hai chiều không nhất thiết tương đương.

--
Edited: Nếu dùng với đồ thị ngược của input thì có khi được.

Vậy thuật toán sẽ là như này:

B1: đặt E' = <đảo chiều các cạnh của E>

B2: Chạy Dijkstra (V, E') với bắt đầu là t. Dừng khi tìm được đường đi ngắn nhất đến tất cả N điểm nguồn,

B3: Output 3 đường đi ngắn nhất trong số N

tức là vẫn phải tìm từ t đến N đỉnh kia xong chọn 3 thằng min đúng k ạ, quan trọng phải đảo chiều đồ thị ban đầu

BetterNextTime · 17/11/22

thuyduong2007 đã nói:
K cần đâu làm vậy đâu, suy nghĩ ngược lại thay vì tìm đường đi ngắn nhất từ tất cả các đỉnh đến t thì từ t đi ngược lại 3 đỉnh bằng djstra ấy. 3 đỉnh reachable đầu tiên là 3 đỉnh có đường đi ngắn nhất đến t.

Thanks thím. Như vậy vừa trong khi dijsktra từ t thì reverse hướng dần dần nhỉ. Cho đến khi số đỉnh đã tìm shortest path finish == 3 dừng là đc

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

Senior Member

Member

Senior Member

Member

Junior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Junior Member

Member

Junior Member

Senior Member

Member

Member

Đã tốn tiền

Junior Member

Junior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này