楼主最近在刷fb的tag 一天10道吧 分享一下几道比较经典和难题
489. Robot Room Cleaner
给了4个API函数可供我们调用,让我们实现打扫房间。给的例子中有房间和起始位置的信息,但是代码中却没有,想想也是难道我们在给扫地机器人编程时,还必须要知道用户的房间信息么?当然不能够的。 对于这种图的遍历的题目还是采用递归DFS来做,因为不知道具体的起始位置所以要采用相对位置的想法。我们先初始化位置为(0, 0), 然后建一个方向数组,使用一个变量dir来从中取数。特别注意的是这个方向数组一定要遵从一定原则,比如楼主写的时候就是上->右->下->左
,因为在每次调用turn的方向函数的时候一定要和方法数组对应起来。在递归函数中,我们首先对起始位置调用clean函数,因为题目中说了起始位置是能到达的,即是为1的地方。然后就要把起始位置加入visited。然后我们循环四次,因为有四个方向,由于递归函数传进来的dir是上一次转到的方向,那么此时我们dir加上i,为了防止越界,对4取余,就是我们新的方向了,然后算出新的位置坐标X和Y。此时先要判断visited不含有这个新位置,即新位置没有访问过,还要调用move函数来确定新位置是否可以到达,若这两个条件都满足的话,我们就对新位置调用递归函数。注意递归函数调用完成后,我们要回到调用之前的状态,因为这里的robot是带了引用号的,是全局通用的,所以要回到之前的状态。回到之前的状态很简单,因为这里的机器人的运作方式是先转到要前进的方向,才能前进。那么我们后退的方法就是,旋转180度,前进一步,再转回到原来的方向。同理,我们在按顺序试上->右->下->左的时候,每次机器人要向右转一下,因为move函数只能探测前方是否能到达,所以我们必须让机器人转到正确的方向,才能正确的调用move函数。
-
Palindrome Pairs
不能用暴力来解会出现通不过oj的。
考虑的情况:只是处理了bat和tab的情况,还存在abcd和cba,dcb和abcd这些情况需要考虑,然后使用hashmap来对应。 -
Shortest Subarray with Sum at Least K
楼主参考了大神的思路,一般求这种连续的子序列和的题目可以考虑:
Calculate prefix sum B of list A.
B[j] - B[i] represents the sum of subarray A[i] ~ A[j-1]
Deque d will keep indexes of increasing B[i].
For every B[i], we will compare B[i] - B[d[0]] with K.