xinxinxxyy 2023-02-01 23:10 采纳率: 100%
浏览 19
已结题

java算法题求解,记忆化递归问题

img

这是leetcode上面的题 我是用的暴力和记忆化做的,我想问为什么我用map记忆化过不了照样找出时间限制,没有任何效率提升,相反更慢了,而我用二维数组就能过呢,这两者有什么区别吗?还是我写错了呢?
这一张是用map记忆化:

img

这一张是二维数组:

img

  • 写回答

2条回答 默认 最新

  • m0_54204465 2023-02-02 07:16
    关注

    问题:718. 最长重复子数组

    算法提示:暴力 + 哈希表

    思路:

    使用暴力算法,将nums1中每一个子数组,与nums2进行比较。
    使用哈希表,将nums2中的每一个子数组映射到表中。
    在比较nums1中的子数组时,可以判断该子数组是否在哈希表中。
    代码实现:

    class Solution {
        public int findLength(int[] A, int[] B) {
            int n = A.length, m = B.length;
            int[][] dp = new int[n + 1][m + 1];
            int ans = 0;
            for (int i = n - 1; i >= 0; i--) {
                for (int j = m - 1; j >= 0; j--) {
                    if (A[i] == B[j]) {
                        dp[i][j] = dp[i + 1][j + 1] + 1;
                        ans = Math.max(ans, dp[i][j]);
                    }
                }
            }
            return ans;
        }
    }
    
    

    在第一份代码中,你使用了HashMap作为记忆化数据结构,但是该数据结构的查询和插入的时间复杂度为O(1)的理想情况下,但由于存在hash冲突的情况,所以实际情况下查询和插入的时间复杂度往往为O(n)。因此,在你的代码中,每次对map的查询和插入的时间复杂度都很高,使得程序的效率降低。

    相反,在第二份代码中,你使用了二维数组作为记忆化数据结构,查询和插入的时间复杂度都是O(1),所以该代码的效率要比第一份代码高得多。因此,你的二维数组代码能够通过,而HashMap代码超时。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 2月11日
  • 已采纳回答 2月3日
  • 创建了问题 2月1日

悬赏问题

  • ¥30 微信小程序请求失败,网页能正常带锁访问
  • ¥15 对语音信号进行变调时,间接改变时序从而实现语音变速,进而将变调与变速同时实现、参数合成法换为波形合成法
  • ¥15 Python实现hog特征图可视化
  • ¥30 德飞莱51单片机实现C4炸弹
  • ¥50 CrossLink-LIF-MD6000 型 FPGA 的 CMOS 转 MIPI D-PHY IP 核功能使用异常
  • ¥15 proteus控制16x16LED点阵显示屏的设计
  • ¥30 求会做山景bp1048b2程序的。做直播声卡用
  • ¥15 求数学建模论文问题指导
  • ¥15 51单片机与数码管实现电子琴
  • ¥15 h3.6m 人类行为预测论文复现