这个leetcode问题的java记忆如何记忆这个递归解决方案

j8yoct9x 于 2021-06-30 发布在 Java

关注(0)|答案(1)|浏览(448)

我已经做了所有可能的刷卡，然后在最后我已经通过了数组，以检查它是否增加。这就是问题所在，我编写了递归方法如下

class Solution {
    public int minSwap(int[] A, int[] B) {

        return helper(A,B,0,0);
    }

    boolean helper2(int[] A,int[] B){

        for(int i=0;i<A.length-1;i++){
           if(A[i]>=A[i+1] || B[i]>=B[i+1])
               return false;
        }
        return true;

    }

    int helper(int[] A,int[] B,int i,int swaps){
        if(i==A.length && helper2(A,B)==true)
            return swaps;
        if(i==A.length)
            return 1000;

        swap(A,B,i);
       int c=helper(A,B,i+1,swaps+1);
        swap(A,B,i);
        int b=helper(A,B,i+1,swaps);

      return Math.min(b,c); 
    }
    private void swap(int[] A, int[] B, int index){
        int temp = A[index];
        A[index] = B[index];
        B[index] = temp;
    }

}

在这里，我已经尝试了所有可能的刷卡，然后检查他们，并返回了一个最小的刷卡。我该怎么做这个的记忆。我应该在这个代码的记忆中使用哪些变量。有没有选择记忆变量的经验法则？

Java dynamic-programming memoization

来源：https://stackoverflow.com/questions/65392671/memoization-of-this-leetcode-problem-how-do-i-memoize-this-recursive-solution

1条答案

按热度按时间

v64noz0r1#

维基百科说：
在计算中，记忆是一种优化技术，主要用于存储昂贵函数调用的结果，并在相同输入再次出现时返回缓存结果，从而加快计算机程序的速度。
自 A 以及 B 不要改变，输入是 i 以及 swaps ，所以对于这两种情况的每一个组合，我们都需要存储结果。
一种方法是使用 HashMap 使用具有2个值的键，例如。

class Key {
    int i;
    int swaps;
    // implement methods, especially equals() and hashCode()
}

然后可以在开始处添加以下内容 helper() ，尽管您可能希望在这两个之后添加它 if 声明：

Key key = new Key(i, swap);
Integer cachedResult = cache.get(key);
if (cachedResult != null)
    return cachedResult;

然后更换 return 声明内容：

int result = Math.min(b,c);
cache.put(key, result);
return result;

是否 cache 字段或参数的传递完全由您决定。

赞(0）回复(0）举报 2021-06-30

我来回答

这个leetcode问题的java记忆如何记忆这个递归解决方案

1条答案

相关问题

热门标签

最新问答