将int转换为正数和负数的字符串(不需要像数组、列表或解析之类的东西)的递归手动方法

Question

你好，我研究了一个递归方法，以完全手动的方式将int转换为string，我想知道这个递归方法是否有效，以及您是否可以帮助我改进代码。我是算法的新手，所以如果有些东西看起来很难看，不要责怪我。。。我在互联网上搜索过，但从未找到过这样的东西：

public class IntToString {
public static String intToString(int number) {
    return intToString(number, "", false);
}
private static String intToString(int number, String answer,
        boolean isNegative) {
    if (number < 0 && isNegative == false) {
        isNegative = true;
        number = -number;
    }
    if (number == 0)
        if (isNegative)
            return "-" + answer;
        else
            return answer;
    System.out.println(number);
    return intToString(number / 10, answer = number % 10 + answer,
            isNegative);
}
// test
public static void main(String[] args) {
    String ans = intToString(-324234);
    System.out.println(ans);
}

}

Answer 1

不，它不是很有效。尽管情况可能会更糟。至少它仍然是O（N），其中N是给定数字中的小数位数。

• CCD_ 1并不是真正需要的。你之所以使用它，是因为你将它附加到你向下传递递归的答案上，这将导致该数字反转。但至少还有两种其他方法可以做到这一点，这样它就不会倒置
• 若你们注意到，你们处理负数和正数的方式只有很小的差别。如果你记得处理负数和处理它的正反面是一样的，并且在处理完-后，你可以对它们运行相同的过程
• 没有理由对所有的标志进行否定和反转。这两项工作都是在顶级水平上完成的。因此，您可以在intToString(int number)函数中而不是在递归函数中执行这些操作，并节省大量的条件检查，当然还有replaceAll()调用
• 不需要传递answer。您可以根据递归调用返回的值来确定返回值。记住，对于1,2,3这样的数字，你会得到字符串'1'，'2'，'3'。因此，如果你有23，并且你传了2，你可以使用你得到的2来构建你的答案
• 您的算法没有返回0的正确答案。当你用递归术语思考时，这是正确的答案，但当你用main中的0调用它时，这不是正确的答案。至少有两种方法可以解决这个问题

还有一些风格建议：

• 始终正确缩进代码
• 您不需要将布尔值与true或invertInt0进行比较。如果有布尔变量x，则可以使用if (x)或if (!x)，而不是if (x==true)和if (x==false)。以一种更直观的方式命名布尔变量，如isNegative或needsInversion。读if (isNegative)是有意义的

---

更详细的信息，以防你找不到解决方案：

我们如何避免反转？基本上有两种方式。如果你坚持要把答案传下去，那么不要：

answer += num % 10;

用途：

answer = ( num % 10 ) + answer;

也就是说，把它附加在答案的左边，而不是右边。

我更喜欢的方法是使用较低级别的答案。假设你有123这个号码。所以你把12传下去，得到的答案是"12"。然后你可以使用

return answer + ( num % 10 );

这会给你"123"。这一次，它被附加在右边。

---

最后，这里是完整的解决方案：

public static String intToString( int n ) {
    if ( n == 0 ) {
        return "0";
    } else if ( n < 0 ) {
        return "-" + positiveIntToString( -n );
    } else {
        return positiveIntToString(n);
    }
}
private static String positiveIntToString( int n ) {
    if ( n == 0 ) {
        return "";
    } else {
        return positiveIntToString( n / 10 ) + ( n % 10 );
    }
}

你的公共职能就是你向世界展示的东西。递归函数是私有的，它只对正数调用。如果用零调用，它将返回一个空字符串，这有利于递归，但不是真正的解决方案。

因此，公共职能部门首先检查两个可能的问题。如果数字为零，则不应将其传递给私有函数，因为它不会返回正确的答案。相反，只需返回字符串"0"，因为这是正确的答案。

对于负数，我们所需要做的就是为它的对应项-n做工作，它是正数，因此对于私有函数来说是可以接受的。然后我们在前面加上"-"。

正整数的递归函数变得非常简单：如果它为零，则返回空字符串。对于其他任何事情，使用n/10调用自己，将n%10粘贴到结果的右侧，然后返回。

这里还有一个替代解决方案，没有私有方法：

public static String intToString( int n ) {
    if ( n == 0 ) {
        return "0";
    } else if ( n < 0 ) {
        return "-" + intToString( -n );
    } else if ( n < 10 ) {
        return "" + (n%10);
    } else {
        return intToString(n/10) + (n%10);
    }
}

实际上，我认为这是一个效率稍低的解决方案，因为我们在每个级别上还要进行两次检查。在最高级别，阴性检查只会为真一次。只有在调用函数时首先使用零的情况下，才会对零进行检查。对个位数的检查是当前递归的结束（因为我们不能在零处停止递归，否则我们总是在开始时得到一个额外的"0"）。