时间戳

首页 > 解决方案 > 对于任何输入，程序似乎总是返回 1

java - 对于任何输入，程序似乎总是返回 1

问题描述

我正在尝试解决这个名为 Thanos Sort 的竞争性编程问题。有关问题的一些详细信息，请单击此链接：https ://codeforces.com/problemset/problem/1145/A 本次比赛很久以前就结束了，因此允许讨论。这似乎是一个非常简单的问题。我尝试使用递归来解决这个问题（重复地将数组分成两半并检查它是否已排序，如果我发现其中一半已排序，则返回一半长度的值）。这是我的代码：

import java.util.*;
import java.io.*;
class Main {
 public static void main(String[] args) throws IOException{
   BufferedReader b1 = new BufferedReader(new InputStreamReader(System.in));
   int T = Integer.parseInt(b1.readLine());
   for(int i = 0; i<T; i++) {
     String vals [] = (b1.readLine()).split(" ");
     int nums [] = new int[vals.length];
     for(int j = 0; j<vals.length; j++) {
         nums[j] = Integer.parseInt(vals[j]);
     }
     System.out.println(solve(nums));
   }
 }
 public static int solve(int arr[]) {
   int temp1 [] = new int[arr.length/2];
   int temp2 [] = new int[arr.length/2];
   for(int i = 0; i<arr.length/2; i++) {
     temp1[i] = arr[i];
   }
   for(int i = arr.length/2; i<arr.length; i++) {
     temp2[i-(arr.length/2)] = arr[i];
   }
   if(isSorted(temp1) == true) {
     return temp1.length;
   }
    if(isSorted(temp2) == true) {
     return temp2.length;
   }
   solve(temp1);
   solve(temp2);
  return 1;
 } 
 public static boolean isSorted(int [] arr) {
   for(int i = 0; i<arr.length; i++) {
     if(arr.length == 1) {
       return true;
     }
     if(i < arr.length-2 && arr[i] < arr[i+1]) {
       continue;
     }
     else {
       return false;
     }
   }
   return true;
 }
}

在任何数组上测试时，我的代码似乎总是输出 1。我知道我的代码末尾有“return 1”语句（我需要有这个，因为其他返回语句在 if 语句中）。我相信错误是由我的“return 1”语句引起的。有什么建议么？

标签： javarecursionreturn

解决方案

当你递归时，你丢弃了递归返回的值。改变

solve(temp1);
solve(temp2);
return 1;

类似于

return Math.max(1, Math.max(solve(temp1), solve(temp2)));

此外，您的isSorted算法似乎被破坏了。迭代数组，检查每个值是否等于或大于前一个。喜欢，

public static boolean isSorted(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] < arr[i - 1]) {
            return false;
        }
    }
    return true;
}

推荐阅读