java - 超过时间限制

Question

对于问题(SPOJ.com - 问题 FARIDA)。我使用的方法与 ( https://codinghangover.wordpress.com/2014/01/15/spojfarida-princess-farida/ ) 上给出的方法相同。

以下是我的解决方案==>

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

class FARIDA {
    public static long maxC(Map<String, Long> map, long c[], int s, int e)
    {
        if(s>e)
            return 0;
        if(map.containsKey(s+"|"+e))
            return map.get(s+"|"+e);
        if(s==e)
            map.put(s+"|"+e, c[s]);
        else 
            map.put(s+"|"+e, Math.max(c[s]+ maxC(map,c,s+2,e),maxC(map,c,s+1,e)));

        return map.get(s+"|"+e);

    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for(int j=1;j<=t;j++)
        {
            int n=in.nextInt();
            long c[]= new long[n];
            for(int i=0; i<n; i++)
             c[i]=in.nextLong();
            Map<String, Long> map = new  HashMap<String, Long>();
            System.out.println("Case "+j+": "+maxC(map,c,0,n-1));
        }
        in.close();
    }
}

为什么我在 java 中得到 TLE ？需要什么样的优化？ HashMap 有问题吗？

Answer 1

我认为您获得 TLE 的唯一可能原因是您使用了使用字符串作为键的 HashMap。因此，当您尝试访问 HashMap，并且 HashMap 将您输入的字符串与 HashMap 中已有的所有键相匹配时，您会浪费一些时间。不需要使用HashMap。您可以简单地使用数组来实现所有这些，并将数组的索引作为键。我已将 map 从 HashMap 更改为 long 数组。

类似这样的东西::

public static long maxC(long map[], long coins[], int n) // n is the total number of monsters
{
    if(n == 0) // If there are no monsters in the path
        return 0;
    if(n == 1) // Just in case there is only one monster in the way
        return coins[0];
    map[0] = coins[0];
    map[1] = Math.max(map[0], coins[1]);
    for(int i = 2; i < n; i++) {
        map[i] = Math.max(map[i-2] + coins[i], map[i-1]);
    }
    return map[n - 1];
}

在 for 循环中，我首先考虑是否只有 2 个怪物挡道，如果有 3 个怪物，则使用此解决方案，依此类推。

这显着降低了程序的复杂性，因为现在您不必匹配字符串。而且，这里我已经使用了自下而上的方法，你完全可以修改上面的方法并使用自上而下的方法。虽然我更喜欢自下而上的方法，因为我们在这里不进行任何递归调用，我相信这可以节省一些时间，因为我们没有从堆栈中推送和弹出函数状态。

编辑::

自上而下的方法::

public static long maxC(long map[], long coins[], int n)
{
    if(n-1 < 0)
        return 0;
    if(map[n - 1] != 0) {
        return map[n - 1];
    }
    map[n - 1] = Math.max(maxC(map, coins, n-2) + coins[n - 1], maxC(map, coins, n-1));
    return map[n - 1];
}

在这里，如果没有怪物，我返回0，如果我已经有了之前计算过的解决方案，则返回map[n-1]。

您对该函数的初始调用如下所示(来自 main)::

maxC(map, c, n);

无论如何我们都不需要较低的索引，所以我删除了它。

我相信，您可以尝试上述任何一种方法，您都会获得 AC。 :D