递归方法检查一行整数是否递减：return true/false

我必须在Java中编写一个递归方法，如果行是递减的，则返回true，否则返回false。递归方法检查一行整数是否递减：return true/false

这是我尝试过，但它不能正常工作：我觉得你有不必要的情况下，如果大小小于2，你只能假设真

ArrayList<Integer> getallen = new ArrayList(); 
     getallen.add(500); 
     getallen.add(400); 
     getallen.add(300); 
     getallen.add(200); 
     getallen.add(100); 
     getallen.add(0); 

     System.out.println(isDescending(getallen)); 
    } 

public static boolean isDescending(ArrayList<Integer> getallen) { 
    if (getallen.size() >= 2) { 
     if (getallen.get(0) < getallen.get(1)) { 
      return false; 
     } else if (getallen.size() > 0) { 
      getallen.remove(0); 
      return isDescending(getallen); 
     } else { 
      return true; 
     } 
    } else { 
     return false; 
    } 
}

来源

2015-09-12 MJM

什么不起作用？ –

您的问题与基本案例。什么是'isDescending'应该返回长度为1的列表？ – Tunaki

@Tunaki - 我不认为也有这个问题。他正在检查列表是递减的，并且大小列表不能被称为递减。因此否则块应该很好。 –

。

尝试：

public static boolean isDescending(ArrayList<Integer> getallen) { 
    if (getallen.size() >= 2) { 
     if (getallen.get(0) < getallen.get(1)) { 
      return false; 
     } else { 
      getallen.remove(0); 
      return isDescending(getallen); 
     } 
    } else { 
     return true; 
    } 
}

来源

2015-09-12 15:31:27 WillShackleford

谢谢！这帮了我。 – MJM

只是想添加几乎相同的解决方案:) 顺便说一句。当我使用List 集合时，调用'remove（0）'会抛出'UnsupprtedOperationException'（NetBeans 8.0.2，Java 8.0.45），所以我使用'subSet（）'传递参数以进一步递归。 – AndrewMcCoist

@AndrewMcCoist''ArrayList'永远不会在'remove'方法中抛出'UnsupportedOperationException'。你确定你没有使用'Arrays.asList（...）'返回的列表吗？ –

如果我不得不档次这一点，它会得到

一个大胖子X已经被欺骗性地问在计算器
是相当低效（试运行此在一百万个元素的列表上测试，然后意识到移除ArrayList中的元素0会导致所有元素向下移位）

而是考虑：

public static boolean isDescending(List<Integer> getallen) { 
    return isDescending(getallen, 0); 
} 

public static boolean isDescending(List<Integer> getallen, int from) { 
    return from >= getallen.size() - 1 
      || getallen.get(from) < getallen.get(from + 1) 
      && isDescending(getallen, from + 1); 
}

来源

2015-09-12 18:04:37 Arend

我知道删除ArrayList的第一个元素时，所有元素都向下移动，但我不明白为什么这个方法很重要。该方法的目的是检查元素是否按降序排列。你能解释一下吗？ – MJM

@MJM重要的不是功能，而是效率。在'ArrayList'中，向下移动的步骤与列表很长的步骤相同。所以你的算法具有二次时间复杂度（在列表长度中），而最好的算法（像我的）具有线性复杂度。当数据变大时，这一点非常重要。请注意''LinkedList'没有同样的缺点（删除需要一定的时间），所以这已经可以改善你的解决方案。 – Arend

@MJM修改列表作为该方法的副作用的另一个缺点是该列表可能是共享的。所有别名之后都会有一个空列表。 – Arend

如何用对数递归深度点点更有效的方法？就像练习一样。

public static void main(String[] args) { 
    List<Integer> getallen = new ArrayList<Integer>();   
    getallen.add(500); 
    getallen.add(400); 
    getallen.add(300); 
    getallen.add(200); 
    getallen.add(100); 
    getallen.add(0); 

    System.out.println(isDescending(getallen)); 
} 

public static boolean isDescending(List<Integer> getallen) { 
    return isDescending(getallen, 0, getallen.size()); 
} 

private static boolean isDescending(List<Integer> getallen, 
     int start, int end) { 
    if (end - start <= 1) 
     return true; 
    if (end - start == 2) { 
     return getallen.get(start) > getallen.get(start + 1); 
    } 
    int middle = (start + end - 1)/2 + 1; 
    return (getallen.get(middle - 1) > getallen.get(middle)) && 
      isDescending(getallen, start, middle) && 
      isDescending(getallen, middle, end); 
}

来源

2015-09-12 23:51:06 rsutormin

递归方法检查一行整数是否递减：return true/false

回答

相关问题