使用线性递归合并/乘法数组中的元素

zz2j4svz 于 2021-07-08 发布在 Java

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

我必须实现一个递归方法 merge(long[] arr, int i) 如果相邻元素具有相同的值，则从索引开始将其相乘 i . 例子：

merge({1, 2, 2, 4}, 0)

应该生成如下数组：

{1, 4, 4}

如果一个数字有多个（n）次出现 {1, 2, 2, 2, 2, 5} ，所有这些必须相乘： {1, 16, 5} .
已经合并的号码不能再合并 {1, 4, 4, 16} -> {1, 16, 16} .
所有这些都必须通过只使用一个方法merge来实现，并且在原始数组中每个元素只有一个递归调用。
这是一个使用递归和循环的工作实现：

public static long[] merge(long[] ns, int i) {
    final long[] EMPTY_LONG_ARRAY = {};
    if (i < 0) {
        return merge(ns, 0, m); // if i negative, start at 0
    } else if (i >= ns.length) {
        return EMPTY_LONG_ARRAY; // if out of bounds, return empty array
    } else if (i == ns.length - 1) {
        return ns; // base case
    } else { // recursion in here
        if (ns[i] == ns[i + 1]) { // if next long is equal
            int occurences = 1; // first occurence
            for (int j = i; j < ns.length - 1; j++) {
                if (ns[j] == ns[j + 1])
                    occurences++;
                else
                    break;
            } // add next occurences
            long[] newArray = new long[ns.length - occurences + 1]; // new array is (occurences-1) shorter
            for (int j = 0; j < newArray.length; j++) { // fill new array
                if (j < i) {
                    newArray[j] = ns[j]; // left of i: values stay the same
                } else if (j > i) {
                    newArray[j] = ns[j + occurences - 1]; // pull values right of i (occurences-1) to the left
                } else {
                    int counter = occurences;
                    long mergedValue = ns[j];
                    while (counter > 1) {
                        mergedValue *= ns[j];
                        counter--;
                    }
                    newArray[j] = mergedValue; // at j: value is ns[j]^occurences
                }
            }
            if (i == ns.length - 1)
                return merge(newArray, i, m);
            else
                return merge(newArray, i + 1, m); // if bounds permit it, jump to next number
        } else {
            return merge(ns, i + 1, m); // nothing to merge, go one step forward
        }
    }

这个实现产生正确的结果，但是递归深度是错误的（在原始数组ns[]中每个元素需要一个递归调用）。
我肯定有个天才可以用线性递归来解决这个问题。

Java Arrays Algorithm recursion long-integer

来源：https://stackoverflow.com/questions/64985239/merge-multiply-elements-in-array-using-linear-recursion

1条答案

按热度按时间

6tqwzwtp1#

让我们将循环转换为递归调用。这样做的唯一原因是作业要求它-它不是更具可读性（至少对我来说是这样），而且它实际上更慢。出于效率的考虑，人们通常希望转向另一个方向：从递归到循环。
首先，代码的注解版本：

public static long[] merge(long[] ns, int i) { // i not needed, but useful for recursion
    long[] out = new long[ns.length];          // for result; allocate only once
    for (int j = i; j < ns.length; j++) {      // main loop, condition is "j == length"
        int occurences = 0;
        for (int k = i; k < ns.length; k++) {  // inner loop - can avoid!
            if (ns[j] == ns[k]) {
                occurences++;
            }
        }
        out[j] = (long) Math.pow(ns[j], occurences); // updating the result
    }
    // remove additional elements
    return out; // this does not remove elements yet!
}

首先，让我重写一下，提高效率。由于重复项只有在相邻时才被删除，因此不需要内部循环，可以编写以下内容：

public static long[] merge(long[] ns) {
    long[] out = new long[ns.length];
    int oSize = 0;     // index of element-after-last in array out
    long prev = ns[0]; // previous element in ns; initial value chosen carefully
    out[0] = 1;        // this make the 1st iteration work right, not incrasing oSize
    for (int i=0; i<ns.length; i++) {
        long current = ns[i];
        if (current == prev) {
           out[oSize] *= current;   // accumulate into current position
        } else {
           oSize ++;                // generate output
           out[oSize] = current;    // reset current and prev
           prev = current; 
        }
    }
    // generate final output, but do not include unused elements
    return Arrays.copyOfRange(out, 0, oSize+1);
}

假设这是可行的（注意-我还没有测试过），我现在将把它转换成尾部递归。将有两部分：驱动程序代码（不在循环中的所有内容）和递归代码（循环部分）。

public static long[] merge(long[] ns) {
    long[] out = new long[ns.length];
    int oSize = 0;     
    long prev = ns[0]; 
    out[0] = 1;        
    int i=0;           
    recursiveMerge(ns, i, out, oSize, prev);  // recursion!
    return Arrays.copyOfRange(out, 0, oSize+1);
}

public static void recursiveMerge(long[] ns, int i, long[] out, int oSize, long prev) {

    if (i == n) return; // check "loop" termination condition

    // copy-pasted loop contents
    long current = ns[i];
    if (current == prev) {
        out[oSize] *= current;   // accumulate into current position
    } else {
        oSize ++;                // generate output
        out[oSize] = current;    // reset current and prev
        prev = current; 
    }

    // next loop iteration is now a recursive call. Note the i+1
    recursiveMerge(ns, i+1, out, oSize, prev);     
}

一般的想法是将所有状态作为参数传递给递归函数，并在开始时检查循环终止，将循环代码放在中间，最后为下一次迭代进行递归调用。

赞(0）回复(0）举报 2021-07-08

我来回答

使用线性递归合并/乘法数组中的元素

1条答案

相关问题

热门标签

最新问答