0

我该如何安排。数字......这样每个由排列形成的新数字与前一个最大值的差异最大为 1。

例如，如果输入为 k=1，则输出将为 1

如果 k =2 输出是：11, 12 2,1 是错误的，因为最左边的必须始终为 1。

如果 k = 3 输出为：111,112, 121, 122, 123

如果 k = 4：1111,1112,1121,1122,1123,1212,1211,1213,1223,1221,1222,1233,1234

1423 是错误的 diff b/w 1 和 4 是 3。 1243 是错误的 diff b/w 2 和 4 是 2....

如果可能的话，我如何使用 DP 来做到这一点？

这是上述问题的解决方案之一......任何人都可以帮助我理解这段代码......提前致谢......

public class MaxOneDiff {

    public static void main(String[] args) {
        int k = 4;
        getList(k);
    }

    public static void getList(int k) {
        int arr[] = new int[k];
        int index = 0;
        printRecList(k, arr, index, k);
    }

    public static void printRecList(int k, int arr[], int index, int range) {
        if (k == 0) {
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i]);
            }
            System.out.println();
        } else {
            for (int i = 1; i <= range; i++) {
                if (index == 0) {
                    arr[index] = i;
                    printRecList(k - 1, arr, index + 1, range);
                } else {
                    int t = arr[index-1]-i;
                    t = t > 0 ? t : -t;
                    if (t < 2) {
                        arr[index] = i;
                        printRecList(k - 1, arr, index + 1, range);
                    }
                }
            }
        }
    }
}
4

1 回答 1

0

让我们从简单的部分开始：

public static void getList(int k) {
    int arr[] = new int[k];
    int index = 0;
    printRecList(k, arr, index, k);
}

这是 Print Recursive List 函数的助手，只是设置初始的东西。

public static void printRecList(int k, int arr[], int index, int range) {

这是一个递归函数，它应该（并且确实）包含两个主要部分：

  1. 基本情况（这里，当 k==0 时）
  2. 一种非基本情况，它做某事，将问题简化为更小的问题，并递归。

基本情况：

    if (k == 0) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
        }
        System.out.println();

如果 k==0，则从左到右打印出数组中的数字，然后在末尾换行。

非基本案例：（更复杂的部分）

    else {
        for (int i = 1; i <= range; i++) {
            if (index == 0) {
                arr[index] = i;
                printRecList(k - 1, arr, index + 1, range);
            } else {
                int t = arr[index-1]-i;
                t = t > 0 ? t : -t;
                if (t < 2) {
                    arr[index] = i;
                    printRecList(k - 1, arr, index + 1, range);
                }
            }
        }
    }

'i' 从 1 到范围，

辅助函数使用 index=0 调用 this，因此第一级/顶层递归由将数组的第一个元素（元素 0）设置为 i，并调用递归方法组成。

在递归调用中再也不会索引 == 0，因此我们将注意力转向 else 子句。

这里我们想知道是否可以将值 i 赋给下一个元素，所以我们检查 elementToLeft 减去 i 的绝对值是否大于等于 2。

如果“i”在该位置分配是有效的（即它与左边的值只有 1 或 0 不同，并且“i”只能从 for 循环中获得与 range 一样高的值。）

然后我们分配它，并检查下一个位置。

当我们到达数组中的最后一个元素时，这将结束。

于 2012-07-27T04:59:53.167 回答