13

这是一个编程难题，类似于：“如果一个数字的子字符串的所有数字的乘积都具有唯一值，则该数字被认为是出色的。”

示例：263 (2, 6, 3, 2*6 = 12, 6*3 = 18) 非常棒。

但是 236 (2, 3, 6 , 2*3 = 6 , 3*6 = 18) 并不出色。

我们只取子串，不取子序列。

我在想，由于重复的产品计算，我们可以在这里应用动态编程吗？我们还有什么其他的解决方案？（这不是作业问题。）

4

5 回答 5

6

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

假设我们有数字d 0 d 1 ... 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 2 )。

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 感兴趣的读者，我可以在这里推荐一些类似的问题/答案：

于 2012-08-24T18:59:18.150 回答
3

使用动态规划可能是要走的路：不是计算所有 O(n^2) 子串，然后使用 ~n 乘法命令来计算它们中的每一个，而是将先前计算的结果存储在矩阵 M 中，其中 M(i ,j) 是长度为 j 的子串的结果，从位置 i 开始。

（即，如果您的号码是 123456789，那么 M(1,5) 是 5！，而 M(1,6) 是 6！，只需将 M(1,5) 乘以 6 - 恒功）

这会将运行时间从 n 位的 O(n^3) 提高到 O(n^2)。

于 2012-08-24T18:42:37.067 回答
3

动态规划解决方案实际上是没有必要的，因为没有具有大量数字的出色数字（如果任何数字出现不止一次，则该数字不是出色的）。

这是每个出色数字的列表。共有 57,281 个。

这个文件在我的电脑上生成的时间不到一秒钟，即使没有使用动态编程:)

于 2012-08-27T18:10:43.520 回答
0

如果我们不将数字视为大字符串，那么散列会有所帮助；

 int brill(int A) {
    map<long long int,bool> m;
    vector<int> arr(10,0);
    int i=0;
    while(A){
        arr[i++]=A%10;
        A/=10;
    }

    for(int j=0;j<i;j++){

        long long int temp=1;

        for(int k=j;k>=0;k--){
            temp*=arr[k];

            if(m.find(temp)!=m.end()){
                return 0;
            }
            else{
                m[temp]=true;
            }
        }
    }
    return 1;

}
于 2015-08-19T19:12:29.773 回答
0

n 是包含数字的字符串。

由于在失败状态之前该数字不能大于 8 位，因此它的 O(1)。

function isBrill(n) {
  var set = {};
  set[parseInt(n.charAt(0))] = true;
  for(var i=0; i < n.length - 1; i++) {
    var a = parseInt(n.charAt(i));
    var b = parseInt(n.charAt(i+1));
    if(set[b] === true) { return false; }
    set[b] = true;
    if(set[a * b] === true) { return false; }
    set[a * b] = true;
  }
  return true;
}
isBrill("263"); // true
isBrill("236"); // false
于 2015-08-19T20:08:09.160 回答