Java:编写递归函数，检查一位数为偶数，另一位数为非偶数

Question

我正在努力做一项练习。我需要写一个递归函数来检查一个数字是奇数，另一个是偶数，它需要在任意数字中切换。

例如,

• 123为真(3为奇数，2为偶数，1为奇数)
• 1234也是true
• 12354为假(4为偶数，5为奇数，3为奇数)

数字必须在偶数和奇数之间交替。

如果数字只有1位，则返回true。

下面是我写的函数，我找不到我的错误在哪里:/

//Assumption : num > 0
//this function will return if true or not if number is alternating
public static boolean isAlternatingNumber(int num) {
boolean flag;
if(num < 10) {
return true;
}
else {
flag =  isAlternatingNumber(num/10);
int n = num% 10;
if(num%10 % 2 == 0 && flag) {
return true;
}else {
return false;
}
}
}

Answer 1

假设原始函数签名public static boolean isAlternatingNumber(int num)不能更改，您可以通过使用recursive helper function向递归函数添加额外的参数来解决此问题。

下面是一个使用recursive helper function;

来解决这个问题的例子

class Main {  
public static void main(String args[]) { 
System.out.println("123: " + isAlternatingNumber(123)); // true
System.out.println("1234: " + isAlternatingNumber(1234)); // true
System.out.println("12354: " + isAlternatingNumber(12354)); // false
}

// Original function with unmodified signature
public static boolean isAlternatingNumber(int num) {
// Base case, returns true if num is only 1 digit
if (num < 10) {
return true;
}

/*
+ First argument; num with its first digit "sliced" (if num is 123, num / 10 is 12)
+ Second argument; Whether or not if the first digit of num is even (if num is 123,
(num % 10) % 2 == 0 is false, as (num % 10) gives 3, and 3 % 2 is 1, as 3 is an odd number)
*/
return findIfAlternating((num / 10), (num % 10) % 2 == 0);
}
/**
* Recursive helper function to find if a given number is alternating
* between odd and even (or vice versa) digits
* @param num number to be checked, without its first digit
* @param isCurrentDigitEven whether or not if the first digit of the number to be checked is even
*/
public static boolean findIfAlternating(int num, boolean isCurrentDigitEven) {
boolean isNextDigitEven = (num % 10) % 2 == 0;

// Base case, returns true if the digits are alternating between odd and even
if (num < 10) {
return (isCurrentDigitEven ^ isNextDigitEven); // ^ is the XOR operator in Java, returns true if either one of the variables are true, and returns false if both variables are false or true
}  

return (isCurrentDigitEven ^ isNextDigitEven) && findIfAlternating((num / 10), isNextDigitEven);
}
}

Answer 2

这个问题实际上可以视为(并标记?)算法。这会吸引更多的注意力、有趣的实现、反应、建议等。

由于OP提供了非常接近正确的解，任何1的修正都会导致算法工作。我只是发布了对op想法的可能评估。

public static boolean isAlter(int num, boolean isPrevEven) 
{
int next = (num - num % 10) / 10;
boolean isCurrEven = num % 2 == 0;
boolean isOk = (isCurrEven && !isPrevEven) || (!isCurrEven && isPrevEven);
if (isOk) 
return next == 0 || isAlter(next, isCurrEven);
else return false;
}

在这个问题上更有趣的是对于被接受的算法有什么要求？ 例如时间限制，内存使用限制，数据大小或mb任何大0复杂度限制。

递归算法通常可以以迭代的方式重写，这也经常导致时间/内存消耗的改善。然而，递归是优雅的，如果它不违背需求或效率，那就没什么不好的。只要记住使用正确的基例，这样递归就不会趋于无穷大，从而导致StackOverflow错误。

PS:如果方法只接受一个参数，那肯定不是问题:

public boolean isAlternatingNumber(int num) 
{
boolean isEven = num % 2 == 0;
return isAlter(num, !isEven);
}

Answer 3

正则表达式:

public static boolean isAlternatingNumber(int num) {
return !("" + num).matches(".*([02468]{2}|[13579]{2}).*");
}

Answer 4

我写的函数，我找不到我的错误在哪里

flag =  isAlternatingNumber(num/10);

方法isAlternatingNumber一直调用自己，直到num小于10(10)。

例如，如果我们最初使用号码123调用方法isAlternatingNumber，那么将有三次调用该方法，如下所示:

isAlternatingNumber(123);
isAlternatingNumber(12);
isAlternatingNumber(1);

最后一次调用将返回true。
然后，在最后第二个调用中，该方法将继续，即执行以下行:

if(num%10 % 2 == 0 && flag)

注意，局部变量n从未被使用过，所以这一行实际上并不影响isAlternatingNumber方法返回的值:

int n = num % 10;

只要num是奇数，方法isAlternatingNumber将返回false。然后每次递归调用都会返回false。

对于偶数/奇数交替出现的数的后两位，要么该数为偶数，要么该数除以10为奇数，反之亦然(除非该数小于10被认为是"真")，即

(num % 2 == 0 && (num / 10) % 2 == 1) || (num % 2 == 1 && (num / 10) % 2 == 0) || num < 10

如果上述表达式返回true(且num大于10)，则对num / 10重复此操作。

public static boolean isAlternatingNumber(int num) {
if (num < 10) {
return true;
}
else {
int rem1 = num % 2;
int rem2 = (num / 10) % 2;
boolean flag = ((rem1 == 0 && rem2 == 1) || (rem1 == 1 && rem2 == 0));
return flag && isAlternatingNumber(num / 10);
}
}

如果rem1和rem2做not

flag为真具有相同的值

return flag && isAlternatingNumber(num / 10);

如果flag为false, Java将不会[递归地]调用isAlternatingNumber方法。

Answer 5

对于递归解决方案，使用true/falseets递归检查最后一位数字就足够了。每次递归时，去掉值的最后一位。

public static boolean isAlternatingNumber(int num) {
boolean lastDigitEven = num % 10 % 2 == 0;
return isAlternatingNumber(num, lastDigitEven);
}
private static boolean isAlternatingNumber(int num, boolean expectedLastDigitEven) {
if (num == 0)
return true;
boolean lastDigitEven = num % 10 % 2 == 0;
if (lastDigitEven == expectedLastDigitEven)
return isAlternatingNumber(num / 10, !lastDigitEven);
return false;
}