Leetcode - number-of-islands
Leetcode - Search a 2D Matrix II

Leetcode - 01-matrix

violet posted @ Mar 01, 2020 08:17:15 AM in 算法 with tags Algorithm 算法 BFS ruby Golang , 425 阅读

https://leetcode.com/problems/01-matrix/

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

 

Example 1:

Input:
[[0,0,0],
 [0,1,0],
 [0,0,0]]

Output:
[[0,0,0],
 [0,1,0],
 [0,0,0]]

 

When finding a number which is not 0, use BFS to search latest 0. Use queue for that. Simple and easy.

func updateMatrix(matrix [][]int) [][]int {
	if len(matrix) == 0 {
		return matrix
	}
	result := make([][]int, len(matrix))
	for i := 0; i < len(matrix); i++ {
		result[i] = make([]int, len(matrix[0]))
	}
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[i]); j++ {
			if matrix[i][j] == 0 {
				result[i][j] = 0
				continue
			}
			result[i][j] = step(matrix, i, j)
		}
	}

	return result
}

type position struct {
	x int
	y int
}

func step(matrix [][]int, i, j int) int {
	dirs := [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
	queue := []position{{i, j}}
	steps := 0
	for len(queue) != 0 {
		size := len(queue)
		for m := 0; m < size; m++ {
			p := queue[m]
			x := p.x
			y := p.y
			if matrix[x][y] == 0 {
				return steps
			}
			for _, d := range dirs {
				newX := x + d[0]
				newY := y + d[1]
				if newX >= 0 && newY >= 0 && newX < len(matrix) && newY < len(matrix[0]) {
					queue = append(queue, position{newX, newY})
				}
			}
		}
		queue = queue[size:]
		steps++
	}

	return steps
}

 

# @param {Integer[][]} matrix
# @return {Integer[][]}
def update_matrix(matrix)
    r = matrix.length
    c = matrix[0].length
    result = Array.new(r){Array.new(c, 0)}
    for i in 0..matrix.length-1
        for j in 0..matrix[0].length-1
            if matrix[i][j] == 0
                result[i][j] = 0
                next
            end
            result[i][j] = get_distance(matrix, i, j)
        end
    end
    return result
end

def get_distance(matrix, i, j)
    dirs = [[-1,0],[1,0],[0,-1],[0,1]]
    queue = [[i, j]]
    count = 0
    while queue.length != 0
        size = queue.length
        for i in 0..size-1
            point = queue[i]
            x = point[0]
            y = point[1]
            if matrix[x][y] == 0
                return count
            end
            dirs.each do |d|
                new_x = x + d[0]
                new_y = y + d[1]
                if new_x >= 0 && new_y >= 0 && new_x < matrix.length && new_y < matrix[0].length
                    queue << [new_x, new_y]
                end
            end
        end
        queue = queue[size..-1]
        count += 1
    end
    return count
end
truecaller en ligne 说:
Jul 13, 2023 07:59:41 PM

Nous avons tous reçu un appel d’un numéro inconnu ou d’un appelant indésirable à un moment donné de notre vie. Et au fil du temps, le besoin de connaître l’identité de l’appelant se renforce. truecaller en ligne Le portail Truecaller fournit une recherche de numéro de téléphone en ligne sur sa plate-forme, et nous sommes là pour vous aider et c’est entièrement gratuit.

MBOSE 7th Class Syl 说:
Jul 19, 2023 09:29:05 PM

Students Should Download the Respective Stream wise MBOSE Board 7th Class Exam Syllabus Subjects of Hindi, English, Mathematics, Science, Social Science etc, Pdf Format Provide Check the same From our page here,Students need to Start Their Preparation by first Downloading the Stream wise MBOSE 7th Class Curriculum Syllabus 2024 Latest Edition.Meghalaya Board Class Syllabus 2024 is Designed in MBOSE 7th Class Syllabus 2024 Accordance with the NCERT Based Guidelines and helps Students to get an Overview of the Hindi, English Medium All Subject, MBOSE keeps a Class Exam Pattern with the aim to Provide a Quality Education for All Students, On the basis of the Current Educational Demands


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter