![]() |
|
Thread Tools |
#1
|
||
|
||
![]()
Hi các bác, em đang trong giai đoạn trau dồi thêm kiến thức với mong muốn làm remote cho mấy a US.
Cơ mà bọn này test nó toàn lôi thuật toán ra khè nhau, mà món này nói thực em dùng ko nhiều nên ngu lắm. Nay em muốn nhờ ae chỉ chút đường đi nước bước với lại có vài bài thuật toán tặng các bác. Mời các bác xuất chiêu a ![]() Đề: Cho ma trận string [m][n] với m, n là số nguyên > 0. Ma trận này random các giá trị là 1 và 0. Định nghĩa: 1 là người, 0 là tường. Với những người đứng gần nhau thì được coi là 1 nhóm, 1 người cũng được coi là 1 nhóm. Khoảng không bên ngoài ma trận coi là tường. ==> Tìm số lượng nhóm người có trong mảng? VD: string[4][5]: 1 0 0 1 1 1 0 0 0 1 1 0 1 0 0 1 1 1 0 1 -> ở đây có 3 nhóm người. |
#2
|
|||
|
|||
Re: Lượm nhặt 1 số bài test thuật toán mời ae vào giải cho vui :D
Bài này là căn bản của thuật toán duyệt đồ thị. Bạn đọc về DFS và BFS là sẽ giải được.
|
#3
|
||
|
||
Re: Lượm nhặt 1 số bài test thuật toán mời ae vào giải cho vui :D
ờ sắp đến tháng 12 rồi đấy, chủ thread có tham gia advent of code 2019 không
![]() |
#4
|
||
|
||
Re: Lượm nhặt 1 số bài test thuật toán mời ae vào giải cho vui :D
Kiểu bài này 20 năm trước mấy ông thầy ôn cấp 2 toàn gọi là giải thuật Loang. Và nhóm gọi là miền liên thông.
Nhớ vãi :( Sent from my iPhone using vozForums
__________________
M.Eng MEBF CFA ACCA OCP MCSE CEPP PMP CDMP |
#5
|
||
|
||
Re: Lượm nhặt 1 số bài test thuật toán mời ae vào giải cho vui :D
Quote:
Hiện tại cách e đang dùng là: 1. - với mỗi người ("1") sẽ check những người liền kề, và đệ quy ở đây để check toàn bộ 2. - khi không còn liền kề (trên, dưới, trái, phải) -> là kết thúc một nhóm 3. - lưu lại thông tin nhóm này vào ignore list để bỏ qua cho lần search tiếp 4. - làm lại với bước 1 và check trong ignore list |
#6
|
|||
|
|||
Re: Lượm nhặt 1 số bài test thuật toán mời ae vào giải cho vui :D
Quote:
![]() ![]() |
#7
|
||
|
||
Re: Lượm nhặt 1 số bài test thuật toán mời ae vào giải cho vui :D
Chuẩn miền liên thông rồi
![]() |
#8
|
||
|
||
Re: Lượm nhặt 1 số bài test thuật toán mời ae vào giải cho vui :D
Bookmark nghiên cứu sau
![]() |
#9
|
||
|
||
Re: Lượm nhặt 1 số bài test thuật toán mời ae vào giải cho vui :D
Code:
package main import "fmt" func dfs(matrix [][]int, row, col int) { if matrix[row][col] == 0 { return } matrix[row][col] = 0 if row >= 1 && matrix[row-1][col] == 1 { dfs(matrix, row-1, col) } if row < len(matrix)-1 && matrix[row+1][col] == 1 { dfs(matrix, row+1, col) } if col > 0 && matrix[row][col-1] == 1 { dfs(matrix, row, col-1) } if col < len(matrix[0])-1 && matrix[row][col+1] == 1 { dfs(matrix, row, col+1) } } func findNumberOfGroup(matrix [][]int) int { var result int for i := 0; i < len(matrix); i++ { for j := 0; j < len(matrix[i]); j++ { if matrix[i][j] == 1 { dfs(matrix, i, j) result++ } } } return result } func main() { fmt.Println(findNumberOfGroup( [][]int{ []int{1, 0, 0, 1, 1}, []int{1, 0, 0, 0, 1}, []int{1, 0, 1, 0, 0}, []int{1, 1, 1, 0, 1}, }, )) } ![]() |
#10
|
||
|
||
Re: Lượm nhặt 1 số bài test thuật toán mời ae vào giải cho vui :D
^:
có thể viết lại cái dfs thế này: Code:
func dfs(matrix [][]int, row, col int) { if row < 0 || row >= len(matrix) { return } if col < 0 || col >= len(matrix[0]) { return } if matrix[row][col] == 0 { return } matrix[row][col] = 0 dfs(matrix, row-1, col) dfs(matrix, row+1, col) dfs(matrix, row, col-1) dfs(matrix, row, col+1) } ![]() |
![]() |
Thread Tools | |
|
|