1

23 没有对，因为 2 + 3 != 10

73 有 1 对，因为 7 + 3 = 10

783436 有 3 对，因为 7 + 3, 7 + 3, 6 + 4 = 10

我正在尝试使用递归来解决这个问题。这是我的基本情况：

  if n < 10:
        return 0
  if n >= 10 and n <= 99:
        if n % 10 + n // 10 == 10:
            return 1
        else:
            return 0

但是递归步骤让我望而却步。

4

5 回答 5

1

您会注意到其中一个解决方案给出了O(n 2 )复杂性解决方案。您实际上可以编写一个在O(n)中运行的算法。这是如何完成的：

(1)遍历数字并计算所有的 1、2、... 9。

int[] A = new int[] {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
String numStr = "783436";
for(char c: numStr.toCharArray())
    A[c - '0'] += 1;

(2)只有某些对相加才能得到 10、{1,9}、{2,8}、{3,7}、{4,6}、{5,5}。使用此信息总结对：

int pairs = A[1]*A[9] + A[2]*A[8] + A[3]*A[7] + A[4]*A[6] + A[5]*A[5];

（注意：您将计数相乘，因为如问题中所述，对不必是唯一的）

以 783436 为例（注意：这不是实际代码，我只是想说明）：

//The counts for digits 1 - 9
A = {0, 0, 2, 1, 0, 1, 1, 1, 0}

pairs = 0*0 + 0*1 + 2*1 + 1*1 + 0*0 = 3
于 2013-09-28T03:40:02.267 回答
0

使用下面的代码，它的顺序为 n（最佳）。

取一个全局变量，它将保存 0-9 的出现

private int[] countOfDigits = new int[10];

使用以下方法将返回可用对的总数。

int countPair(int num) {
    while (num > 0) {
        countOfDigits[num % 10]++;
        num /= 10;
    }

    return ((countOfDigits[1] * countOfDigits[9])
            + (countOfDigits[2] * countOfDigits[8])
            + (countOfDigits[3] * countOfDigits[7])
            + (countOfDigits[4] * countOfDigits[6]) + (countOfDigits[5]
        * (countOfDigits[5] - 1) / 2));
    }
于 2013-09-28T09:36:18.437 回答
0

如果您不关心您计算 7+3 两次（因为 3 在数字序列中出现两次），那么您可以执行以下操作（用 Java 编写）：

// a helper function that takes a number and returns an array of digits
static int[] numberToDigits(int number){
    char[] charNums = String.valueOf(number).toCharArray();
    int[] digits = new int[charNums.length];
    for(int i=0; i<charNums.length; i++){
        digits[i] = charNums[i]-48; // convert the char to int value
    }
    return digits;
}

// here's the algorithm that counts the pairs
static int count(int number){
    int[] digits = numberToDigits(number);
    int counter = 0;
    for(int i=0; i<digits.length; i++){
        for(int j=i+1; j<digits.length; j++){
            if(digits[i]+digits[j] == 10){
                counter += 1;
            }
        }
    }
    return counter;
}

public static void main(String...args){
    int tens = count(783436);
    System.out.println("tens = " + tens);
}

输出
十位 = 3

于 2013-09-28T03:10:06.130 回答
0

这是我没有回击的解决方案

在线编译器上的代码

public static void main (String[] args)
{
    // add user input
    int SUM = 10;
    // add user input
    String numStr = "783436";

    int length = numStr.length();

    int numArray[] = new int[length];
    int numArrayNeed[] = new int[length];

    int temp=Integer.parseInt(numStr);
    int i=0;

    do
    {

        numArray[i] = temp % 10;
        temp = temp /10;

        numArrayNeed[i] = SUM - numArray[i];

        i++;

    }while(temp>0);

    for(int j=0;j<length;j++)
    {
        if(numStr.contains( String.valueOf(numArrayNeed[j]) ))
        {
            System.out.println(": " + numArrayNeed[j] + " & " + (10-numArrayNeed[j]) );
        }
    }


}
于 2013-09-28T04:18:01.283 回答
0

如果您在 Python 中使用递归，这是一个很好的解决方案：

def ten_maker(some_number=str):

    # Base case
    if len(some_number) == 1:
        return

    # Comparing first item to the rest to see if it adds up to 10
    for var in some_number[1:]:
        if int(some_number[0]) + int(var) == 10:
            print(some_number[0], var)

    # Doing the same with the rest, and slowly finishing the string
    return ten_maker(some_number[1:])

if __name__ == '__main__':
    ten_maker("783436")
于 2013-09-28T05:23:48.037 回答