给出一个数字,找出它是否辉煌

Question

这是一个编程难题,如下所示:"如果其子串的所有数字的乘积都具有唯一值,那么这个数字就会很棒."

例:263(2,6,3,2*6 = 12,6*3 = 18)很棒.

但236(2,3,6,2*3 = 6,3×6 = 18)不辉煌.

我们只采用子串,而不是子序列.

我想也许我们可以在这里应用动态编程,因为重复的产品计算？我们还能有什么其他解决方案吗？(这不是一个家庭作业问题.)

Answer 1

这是使用动态编程解决它的一种方法:

假设我们将数字d ₀ d ₁ ... d _N作为输入.

想法是创建一个表,其中单元格(i,j)存储产品d _i ·d _{i + 1} ·...·d _j.这可以有效地完成,因为(i,j)处的单元可以通过将(i -1,j)处的数乘以d _i来计算.

由于i(起始索引)必须小于或等于j(结束索引),因此我们将关注表格的左下三角形.

生成表后,我们检查重复的条目.

这是输入2673的具体示例解决方案:

1. 我们分配矩阵M,尺寸为4×4.

   

2. 我们首先用d _i填充对角线,M _i,i:

   

3. 然后我们逐行,并用d _i · M _i-1,j填写M _{i ,j}

   

4. 结果看起来像

   

5. 为了检查重复,我们收集产品(2,12,6,84,42,7,252,126,21,3),对它们进行排序(2,3,6,7,12,21,42,84, 126,252),并循环查看两个连续数字是否相等.如果是这样我们返回false,否则为true.

在Java代码中:

这是一个有效的DP解决方案,O(n ²).

public static boolean isColorful(int num) {

    // Some initialization
    String str = "" + num;
    int[] digits = new int[str.length()];
    for (int i = 0; i < str.length(); i++)
        digits[i] = str.charAt(i) - '0';
    int[][] dpmatrix = new int[str.length()][str.length()];

    // Fill in diagonal: O(N)
    for (int i = 0; i < digits.length; i++)
        dpmatrix[i][i] = digits[i];

    // Fill in lower left triangle: O(N^2)
    for (int i = 0; i < str.length(); i++)
        for (int j = 0; j < i; j++)
            dpmatrix[i][j] = digits[i] * dpmatrix[i-1][j];

    // Check for dups: O(N^2)
    int[] nums = new int[digits.length * (digits.length+1) / 2];
    for (int i = 0, j = 0; i < digits.length; i++, j += i)
        System.arraycopy(dpmatrix[i], 0, nums, j, i+1);

    Arrays.sort(nums);

    for (int i = 0; i < nums.length - 1; i++)
        if (nums[i] == nums[i+1])
            return false;

    return true;
}

对于DP感兴趣的读者,我可以在这里推荐一些类似的问题/答案:

• 查找字符串中子序列的出现次数