扫地机器人清扫过的空间个数
难度:
标签:
题目描述
代码结果
运行时间: 39 ms, 内存: 19.3 MB
/*
* 题目思路:
* 1. 使用Java Stream处理数据,模拟机器人移动并记录清扫的空间。
* 2. 使用集合存储清扫过的空间,使用流操作来处理和过滤数据。
*/
import java.util.HashSet;
import java.util.Set;
import java.util.stream.IntStream;
public class Solution {
public int cleanedSpaces(int[][] room, int[] start) {
Set<String> visited = new HashSet<>();
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int[] position = {start[0], start[1]};
int[] dirIndex = {0};
visited.add(position[0] + "," + position[1]);
IntStream.range(0, room.length * room[0].length).forEach(i -> {
int newX = position[0] + directions[dirIndex[0]][0];
int newY = position[1] + directions[dirIndex[0]][1];
if (newX >= 0 && newX < room.length && newY >= 0 && newY < room[0].length && room[newX][newY] != 1 && !visited.contains(newX + "," + newY)) {
position[0] = newX;
position[1] = newY;
visited.add(position[0] + "," + position[1]);
} else {
dirIndex[0] = (dirIndex[0] + 1) % 4;
}
});
return visited.size();
}
}
解释
方法:
这个题解利用模拟行走过程的方式来确定扫地机器人可以清扫的区域。它通过定义一个移动函数 move,根据当前方向和位置来决定下一步的动作。如果下一步的位置是可行走的(即为0),机器人就向该方向移动;否则,它就原地转向。整个过程中,机器人的位置和方向被记录在集合 vis 中以避免重复行动。同时,已清扫的位置被添加到另一个集合 ans 中。最后,函数返回 ans 集合的大小,即不重复的清扫过的格子数量。
时间复杂度:
O(m * n)
空间复杂度:
O(m * n)
代码细节讲解
🦆
在模拟行走过程中,`move` 函数是如何处理机器人遇到不可行进区域(即非0格子)的情况?
▷🦆
题解中提到,如果机器人无法向前行走就会原地转向,那么转向的具体规则是什么?是否总是顺时针转向下一个方向?
▷🦆
题解中使用了两个集合 `vis` 和 `ans`,请问 `vis` 集合中存储的 `(x, y, tt)` 中的 `tt` 具体代表什么意思?
▷🦆
机器人清扫的过程中,`ans` 集合用于存储已清扫的格子,那么这个集合是否有可能重复记录某个格子?如果是,为什么?
▷