手记

2023-05-13：你现在手里有一份大小为 n x n 的 网格 gri

福大大架构师每日一题
2023-05-13 22:40:29浏览 763

2023-05-13：你现在手里有一份大小为 n x n 的 网格 grid,

上面的每个 单元格 都用 0 和 1 标记好了其中 0 代表海洋，1 代表陆地。

请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的,

并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。

我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：

(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

输入：grid = [[1,0,0],[0,0,0],[0,0,0]]。

输出：4。

答案2023-05-13：

大体步骤如下：

1.定义变量：

  • 声明一个二维整数数组grid表示网格，以及整数变量n和m表示网格的行数和列数；

  • 声明一个二维布尔数组visited，用于记录每个单元格是否被访问过；

  • 声明一个二维整数数组queue，用于存储队列中的每个元素；

  • 声明整数变量l和r，分别表示队列的左右端点；

  • 声明整数变量find，统计已经找到的海洋的数量；

  • 声明整数变量seas，统计海洋的总数量；

  • 声明整数变量distance，表示最深能找到的海洋层数，初始化为-1。

2.初始化变量：

  • 将l、r、find、seas和distance全部初始化为0或-1，将visited数组全部设为false；

  • 遍历整个网格，对于每个陆地单元格，将其标记为已访问，并将其加入队列中；对于每个海洋单元格，将seas增加1。

3.进行BFS搜索：

  • 当队列不为空时，取出队列中所有元素进行处理，直到找到所有的海洋单元格；

  • 对于每个队列元素，将其四周的海洋单元格加入队列中，并标记为已访问；同时统计找到的海洋单元格数量，并将distance加1。

4.返回结果：

  • 如果没有找到任何海洋或者陆地，则返回-1；

  • 否则，返回distance。

时间复杂度：

  • 初始化visited数组、queue数组和一些变量的时间复杂度是O(n^2)，其中n为网格边长；

  • 遍历整个网格的时间复杂度也是O(n^2)；

  • BFS搜索的时间复杂度最坏情况下是O(n^2)，因为最多需要遍历整个网格。

因此，总的时间复杂度是O(n^2)。

空间复杂度：

  • visited数组的空间复杂度是O(n^2)；

  • queue数组的空间复杂度是O(n^2)；

  • 其他变量占用常数空间。

因此，总的空间复杂度是O(n^2)。

go语言完整代码如下：

package main

var queue [10000][2]int
var l int
var r int
var visited [100][100]bool
var find int

func maxDistance(grid [][]int) int {
	// 清空变量
	l = 0
	r = 0
	find = 0
	n := len(grid)
	m := len(grid[0])
	// 清空visited
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			visited[i][j] = false
		}
	}
	// 大体思路 :
	// 1) 先把所有的陆地加入队列，并且统计一共有多少海洋
	seas := 0
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] == 1 {
				visited[i][j] = true
				queue[r][0] = i
				queue[r][1] = j
				r++
			} else {
				seas++
			}
		}
	}
	// 2) 从陆地开始广播出去(bfs)，每一块陆地的上、下、左、右所能找到的海洋都是第一层海洋
	// 3) 第一层海洋继续bfs，每一块海洋的上、下、左、右所能找到的海洋都是第二层海洋
	// 4) 第二层海洋继续bfs，每一块海洋的上、下、左、右所能找到的海洋都是第三层海洋
	// ...
	// 也就是说，以陆地做起点，每一层bfs都只找海洋！
	// 看看最深能找到多少层海洋
	distance := -1             // 这个变量就是最深的海洋层数
	for l < r && find < seas { // find < seas说明所有的海洋块没有找全，继续找！
		size := r - l
		for i := 0; i < size && find < seas; i++ {
			row := queue[l][0]
			col := queue[l][1]
			add(row-1, col, n, m, grid)
			add(row+1, col, n, m, grid)
			add(row, col-1, n, m, grid)
			add(row, col+1, n, m, grid)
			l++
		}
		distance++
	}
	if find == 0 {
		return -1
	}
	return distance + 1
}

func add(i int, j int, n int, m int, grid [][]int) {
	if i >= 0 && i < n && j >= 0 && j < m && grid[i][j] == 0 && !visited[i][j] {
		find++
		visited[i][j] = true
		queue[r][0] = i
		queue[r][1] = j
		r++
	}
}

func main() {
	grid := [][]int{{1, 0, 1}, {0, 0, 0}, {1, 0, 1}}
	result := maxDistance(grid)
	println(result)
	grid = [][]int{{1, 0, 0}, {0, 0, 0}, {0, 0, 0}}
	result = maxDistance(grid)
	println(result)
}

rust语言完整代码如下：

static mut QUEUE: [[i32; 2]; 10000] = [[0; 2]; 10000];
static mut L: usize = 0;
static mut R: usize = 0;
static mut VISITED: [[bool; 100]; 100] = [[false; 100]; 100];
static mut FIND: i32 = 0;

fn main() {
    let grid = vec![vec![1, 0, 1], vec![0, 0, 0], vec![1, 0, 1]];
    unsafe {
        let ans = max_distance(grid);
        println!("ans = {}", ans);
    }
    let grid = vec![vec![1, 0, 0], vec![0, 0, 0], vec![0, 0, 0]];
    unsafe {
        let ans = max_distance(grid);
        println!("ans = {}", ans);
    }
}

unsafe fn max_distance(grid: Vec<Vec<i32>>) -> i32 {
    // 清空变量
    // 只要l = 0，r = 0，队列就算被清空了
    L = 0;
    R = 0;
    FIND = 0;
    let n = grid.len();
    let m = grid[0].len();
    // 清空visited
    for i in 0..n {
        for j in 0..m {
            VISITED[i][j] = false;
        }
    }

    // 初始化队列
    let mut queue: [[i32; 2]; 10000] = [[0; 2]; 10000];

    // 大体思路 :
    // 1) 先把所有的陆地加入队列，并且统计一共有多少海洋
    let mut seas = 0;
    for i in 0..n {
        for j in 0..m {
            if grid[i][j] == 1 {
                VISITED[i][j] = true;
                queue[R][0] = i as i32;
                queue[R][1] = j as i32;
                R += 1;
            } else {
                seas += 1;
            }
        }
    }

    // 2) 从陆地开始广播出去(bfs)，每一块陆地的上、下、左、右所能找到的海洋都是第一层海洋
    // 3) 第一层海洋继续bfs，每一块海洋的上、下、左、右所能找到的海洋都是第二层海洋
    // 4) 第二层海洋继续bfs，每一块海洋的上、下、左、右所能找到的海洋都是第三层海洋
    // ...
    // 也就是说，以陆地做起点，每一层bfs都只找海洋！
    // 看看最深能找到多少层海洋
    let mut distance = 0; // 这个变量就是最深的海洋层数
    while L < R && FIND < seas {
        // find < seas说明所有的海洋块没有找全，继续找！
        let size = R - L;
        for i in 0..size {
            if FIND >= seas {
                break;
            }
            let row = queue[L][0];
            let col = queue[L][1];
            add(row - 1, col, n, m, grid.clone(), &mut queue);
            add(row + 1, col, n, m, grid.clone(), &mut queue);
            add(row, col - 1, n, m, grid.clone(), &mut queue);
            add(row, col + 1, n, m, grid.clone(), &mut queue);
            L += 1;
        }
        distance += 1;
    }

    if FIND == 0 {
        return -1;
    } else {
        return distance;
    }
}

unsafe fn add(
    i: i32,
    j: i32,
    n: usize,
    m: usize,
    grid: Vec<Vec<i32>>,
    queue: &mut [[i32; 2]; 10000],
) {
    if i >= 0
        && i < n as i32
        && j >= 0
        && j < m as i32
        && grid[i as usize][j as usize] == 0
        && !VISITED[i as usize][j as usize]
    {
        FIND += 1;
        VISITED[i as usize][j as usize] = true;
        queue[R][0] = i;
        queue[R][1] = j;
        R += 1;
    }
}

c语言完整代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_SIZE 10000

int queue[MAX_SIZE][2];
int l;
int r;
bool visited[100][100];
int find;

void add(int i, int j, int n, int m, int** grid);

int maxDistance(int** grid, int gridSize, int* gridColSize) {
    l = 0;
    r = 0;
    find = 0;
    int n = gridSize;
    int m = *gridColSize;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            visited[i][j] = false;
        }
    }

    int seas = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 1) {
                visited[i][j] = true;
                queue[r][0] = i;
                queue[r++][1] = j;
            }
            else {
                seas++;
            }
        }
    }

    int distance = 0;
    while (l < r && find < seas) {
        int size = r - l;
        for (int i = 0; i < size && find < seas; i++, l++) {
            int row = queue[l][0];
            int col = queue[l][1];
            add(row - 1, col, n, m, grid);
            add(row + 1, col, n, m, grid);
            add(row, col - 1, n, m, grid);
            add(row, col + 1, n, m, grid);
        }
        distance++;
    }

    return find == 0 ? -1 : distance;
}

void add(int i, int j, int n, int m, int** grid) {
    if (i >= 0 && i < n && j >= 0 && j < m && grid[i][j] == 0 && !visited[i][j]) {
        find++;
        visited[i][j] = true;
        queue[r][0] = i;
        queue[r++][1] = j;
    }
}

int main() {
    int gridSize = 3;
    int gridColSize[3] = { 3, 3, 3 };
    int** grid = (int**)malloc(gridSize * sizeof(int*));
    for (int i = 0; i < gridSize; i++) {
        grid[i] = (int*)malloc(gridColSize[i] * sizeof(int));
    }
    grid[0][0] = 1;
    grid[0][1] = 0;
    grid[0][2] = 1;
    grid[1][0] = 0;
    grid[1][1] = 0;
    grid[1][2] = 0;
    grid[2][0] = 1;
    grid[2][1] = 0;
    grid[2][2] = 1;

    int result = maxDistance(grid, gridSize, gridColSize);
    printf("%d\n", result);

    grid[0][0] = 1;
    grid[0][1] = 0;
    grid[0][2] = 0;
    grid[1][0] = 0;
    grid[1][1] = 0;
    grid[1][2] = 0;
    grid[2][0] = 0;
    grid[2][1] = 0;
    grid[2][2] = 0;

    result = maxDistance(grid, gridSize, gridColSize);
    printf("%d\n", result);

    for (int i = 0; i < gridSize; i++) {
        free(grid[i]);
    }
    free(grid);

    return 0;
}

c++语言完整代码如下：

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int queue[10000][2];
int l;
int r;
bool visited[100][100];
int find0;

int maxDistance(vector<vector<int>>& grid) {
    // 清空变量
    // 只要l = 0，r = 0，队列就算被清空了
    l = 0;
    r = 0;
    find0 = 0;
    int n = grid.size();
    int m = grid[0].size();
    // 清空visited
    memset(visited, false, sizeof(visited));
    // 大体思路 :
    // 1) 先把所有的陆地加入队列，并且统计一共有多少海洋
    int seas = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 1) {
                visited[i][j] = true;
                queue[r][0] = i;
                queue[r++][1] = j;
            }
            else {
                seas++;
            }
        }
    }
    // 2) 从陆地开始广播出去(bfs)，每一块陆地的上、下、左、右所能找到的海洋都是第一层海洋
    // 3) 第一层海洋继续bfs，每一块海洋的上、下、左、右所能找到的海洋都是第二层海洋
    // 4) 第二层海洋继续bfs，每一块海洋的上、下、左、右所能找到的海洋都是第三层海洋
    // ...
    // 也就是说，以陆地做起点，每一层bfs都只找海洋！
    // 看看最深能找到多少层海洋
    int distance = 0; // 这个变量就是最深的海洋层数
    while (l < r && find0 < seas) { // find < seas说明所有的海洋块没有找全，继续找！
        int size = r - l;
        for (int i = 0; i < size && find0 < seas; i++, l++) {
            int row = queue[l][0];
            int col = queue[l][1];
            if (row - 1 >= 0 && row - 1 < n && col >= 0 && col < m && grid[row - 1][col] == 0 && !visited[row - 1][col]) {
                find0++;
                visited[row - 1][col] = true;
                queue[r][0] = row - 1;
                queue[r++][1] = col;
            }
            if (row + 1 >= 0 && row + 1 < n && col >= 0 && col < m && grid[row + 1][col] == 0 && !visited[row + 1][col]) {
                find0++;
                visited[row + 1][col] = true;
                queue[r][0] = row + 1;
                queue[r++][1] = col;
            }
            if (row >= 0 && row < n && col - 1 >= 0 && col - 1 < m && grid[row][col - 1] == 0 && !visited[row][col - 1]) {
                find0++;
                visited[row][col - 1] = true;
                queue[r][0] = row;
                queue[r++][1] = col - 1;
            }
            if (row >= 0 && row < n && col + 1 >= 0 && col + 1 < m && grid[row][col + 1] == 0 && !visited[row][col + 1]) {
                find0++;
                visited[row][col + 1] = true;
                queue[r][0] = row;
                queue[r++][1] = col + 1;
            }
        }
        distance++;
    }
    return find0 == 0 ? -1 : distance;
}

int main() {
    vector<vector<int>> grid = { {1,0,1}, {0,0,0}, {1,0,1} };
    cout << maxDistance(grid) << endl; 
    grid = { {1,0,0}, {0,0,0}, {0,0,0} };
    cout << maxDistance(grid) << endl;
}

相关标签
Go
1人推荐
随时随地看视频
慕课网APP

相关阅读

2023-05-15：对于某些非负整数 k ，如果交换 s1 中两个字母的位
2023-05-16：给你一个 严格升序排列 的正整数数组 arr 和一个整
2023-05-17：一个正整数如果能被 a 或 b 整除，那么它是神奇的