本文介绍: 这里, 表示向上移动, 表示向右移动, 表示向下移动, 表示向左移动。1.2 方向数组的一维表示方法一维数组表示:另一种方法是使用一维数组结合模运算来表示方向。例如,可以定义一个一维数组 和 ,分别表示 x 轴和 y 轴的变化:这里的数组同样表示上、右、下、左四个方向。1.3 旋转的处理初始化方向:假设机器人最初面向北方,可以用一个变量 来表示当前方向,初始设为 (表示向右)。右旋转 90 度:向右旋转意味着 的值增加 1。可以使用模运算来确保 的值不超过方向数组的长度:左
1 总结
1.1 方向数组的二维表示方法
1.2 方向数组的一维表示方法
1.3 旋转的处理
1.4 应用示例
这篇文章不仅对理解相关的编程题目有帮助,而且也能够加深对方向控制和数组操作的理解。
2 岛屿系列问题
利用1.1和1.2中的行走表示法就可以解决
3 旋转系列问题
3.1 第一题
3.1.1 LC1041. 困于环中的机器人
3.1.2 改编题:LC1041. 困于环中的机器人: 原题中的一条字符串指令是原子花执行完之后看是否有环,但是现在认为”每一个instruction指令不再原子化执行,而是每一个instruction中的字符原子化执行”, 请问在无限执行instruction中,是否会碰到环?
3.2 LC874. 模拟行走机器人
3.2.1 原题答案
1 代码
2 Q1: “set.add(obstacles[i][0]*60002+obstacles[i][1]);中, 60001 怎么来的?10001就不行“
obstacle的坐标范围是正负3w。如果10001, (1, 0)和(0, 10001)就会撞到一起,但是如果乘以一个比6w严格大的数,那么每一个二维坐标被一个一维度的id标识时能保证唯一性
3 Q1: 机器人如何以最快的速度知道自己能走的最大步子, 而不是走一步看一步?
3.2.2 在3.2.1中规定机器人一次性走的步子最大是9, 那么可以把所有的障碍点都存到set中,然后枚举每一步,查看是否撞倒了障碍点,这样复杂度还是不高,假如现在机器人每一次走的最大步子是1000,如何让机器人以最小的复杂度知道自己可以向前走多少步呢?
1 思路一:可以用两个二维set存储所有的坐标,一个存储所有横轴上的障碍物,另一个存储纵轴,遍历当前方向上的哈希表,判断是否有在[from, to]的中间值,有则直接截断
2 思路二:(通过了100%的case)
可以用两个二维treeset存储所有的坐标,一个存储所有横轴上的有序障碍物,另一个存储纵轴,利用二分查找前方距离自己最近的障碍物,看看自己当前可以最多向前移动多少步。
二分查找时需要注意floor,ceil,lower和higher这几个函数的区别:
在使用 Java 的 TreeMap
和 TreeSet
进行二分查找时,确实需要注意 floor
, ceil
, lower
和 higher
这几个函数的区别。它们都是用来在有序集合中查找特定元素的,但行为略有不同:
对于 TreeMap
:
代码:
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。