4

我遇到了一个面试问题，要求您以升序但以最佳方式打印的值。例如3i * 7j

30 * 70 = 1
31 * 70 = 3
30 * 71 = 7
32 * 70 = 9
31 * 71 = 21
33 * 70 = 27

等等 ...

4

3 回答 3

3

你可以使用一个堆。首先插入最小值 ( 3^0 * 7^0)。在每一步，打印最小值（这将是你的堆的根），删除它，然后添加3 * minimum和7 * minimum到堆中。

这具有O(log n)时间复杂度。

于 2013-08-25T10:36:28.183 回答
0 
A(i,j)=3^i * 7^j
when i != 0 and j != 0:
    A(i,j)=A(i-1,j-1)*21
when i!=0 and j==0:
    A(i,0)=A(i-1,0)*3
when i==0 and j!=0:
    A(0,j)=A(0,j-1)*7
when i==0 and j==0:
    A(0,0)=1

您可以将它们存储到二维数组中，以便从中获取前一个值。

于 2013-08-25T10:37:58.613 回答
0

当您说最佳时，我唯一能想到的就是计算它并将值保存在表格中。然后只计算乘法

     long[] threePower = new long[10];
     long[] sevenPower = new long[10];

     threePower[0] = sevenPower[0] = 1;
     for (int i = 1; i < 10; i++)
     {
        threePower[i] = threePower[i - 1]*3;
        sevenPower[i] = sevenPower[i - 1] * 7;
     }

然后打印组合

于 2013-08-25T10:39:56.913 回答