每日leetcode第0044天 0403. Frog Jump

马上就要七夕节了,青蛙要出来喊“孤寡孤寡”了。就做一道青蛙过河题目吧。

这是一道递归的题目。

思路和深度优先搜索差不多,但最终要记忆化递归。

n保存石头数量。使用了vector保存具体每块石头位置。

使用了hashmap来保存是否存在这块石头。

这样的话如果存在这位置上的石头就可以跳过去试试看了。

由于石头位置的数字是在2^31范围,所以只能用hashmap来保存,数组会爆炸。

尝试跳的前先判断跳的步数是不是大于0,不是就不用尝试了。

并且判断要去的那个石头有没有,没有也不用去了。

其实这样做数据量大并且前面都中断可能是会超时的,时间复杂度实在太高了。

 

做了半天的记忆化,终于做出来了,用了一个hashmap嵌套hashmap。

外层键是石头的位置,内层键是k,值是是否去过。其实内存也可以用hashset。

接下来在跳之前先检查这个位置k步之前有没有跳过。

检查的逻辑是先根据石头位置找哈希表里面有没有,也就是去没去过这个石头。

如果没去过,那么就记录下这个石头和当前k值。

否则再判断这个去过的石头有没有尝试过当前k值,

如果尝试过直接返回,否则记录下这个石头和当前k值。

这样就完成了记忆化搜索的任务了。



关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。