需要帮助来解决黑客挑战
我正在尝试解决hackerrank中的一个“几乎已排序”的挑战。问题是:
给定一个包含元素的数组，可以只使用以下操作之一按升序对该数组进行排序吗？
交换两个元素。反转一个子段。
输入格式 第一行包含一个整数，指示数组的大小。
下一行包含以空格分隔的整数。
样本输入#1
2 4 2
示例输出 #1
是< br >交换1 2
示例输入 #2
3
3 1 2
样品输出#2
不
示例输入 #3
6
1 5 4 3 2 6
示例输出 #3
是的。
反向2 5
我试图解决挑战，我的代码正在工作，但对于大数组来说似乎很慢。
请你帮我为提到的问题找到更好的解决办法。
下面是我的代码：
import java.util.*;
public class Solution
{
private static int[] arr;
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int N = in.nextInt();
arr = new int[N];
for (int i = 0; i < N; i++)
{
arr[i] = in.nextInt();
}
if (IsSorted(arr))
{
System.out.println("yes");
return;
}
if(CheckSingleSwap(arr))
return;
if(CheckSingleReverse(arr))
return;
System.out.println("no");
}
private static boolean CheckSingleReverse(int[] arr)
{
int length = arr.length;
int limit = length - 2;
int current = 1;
List<Integer> indexes = new ArrayList<Integer>();
while (current < limit)
{
for (int i = 0; i < length; i++)
{
int temp = current + i;
for (int j = i; j <= temp && temp < length; j++)
{
indexes.add(j);
}
if (IsSorted(ReverseArrayPart(arr, indexes)))
{
System.out.println("yes");
System.out.println("reverse " + (indexes.get(0) + 1) + " " + (indexes.get(indexes.size() - 1) + 1));
return true;
}
indexes.clear();
}
current++;
}
return false;
}
private static int[] ReverseArrayPart(int[] arr, List<Integer> indexes)
{
int[] result = new int[arr.length];
int[] arrayPart = new int[indexes.size()];
int j = 0;
for (int i = 0; i < arr.length; i++)
{
if (indexes.contains(i))
{
arrayPart[j] = arr[i];
j++;
}
result[i] = arr[i];
}
for(int i = 0; i < arrayPart.length / 2; i++)
{
int temp = arrayPart[i];
arrayPart[i] = arrayPart[arrayPart.length - i - 1];
arrayPart[arrayPart.length - i - 1] = temp;
}
j = 0;
for (int i = 0; i < result.length; i++)
{
if (indexes.contains(i))
{
result[i] = arrayPart[j];
j++;
}
}
return result;
}
private static boolean CheckSingleSwap(int[] arr)
{
int count = 0;
int[] B = Arrays.copyOf(arr, arr.length);
Arrays.sort(B);
List<Integer> indexes = new ArrayList<Integer>();
for(int i = 0; i < arr.length; i++)
{
if(arr[i] != B[i])
{
count++;
indexes.add(i+1);
}
}
if(count > 2)
return false;
System.out.println("yes");
System.out.println("swap " + indexes.get(0) + " " + indexes.get(1));
return true;
}
private static boolean IsSorted(int[] arr)
{
int length = arr.length;
for (int i = 0; i < length - 1; i++)
{
if (arr[i] > arr[i + 1])
{
return false;
}
}
return true;
}
}
共有1个答案
对于下面的代码，传入< code>A作为原始数组，传入< code>B作为排序后的数组。
CheckSingleSwap：
不要将索引添加到另一个列表中，而是存储您遇到的第一个交换，并继续下去；如果你找到相应的其他交换，然后存储它并记录发现；如果发现不同的交换，用false退出。最后，如果你已经记录了发现，打印相应的索引。
private static boolean CheckSingleSwap(int[] A, int[] B)
{
int L = A.length;
int firstSwap = -1, secondSwap = -1;
for(int i = 0; i < L; i++)
{
if(A[i] != B[i])
{
if (firstSwap == -1)
firstSwap = i;
else if (secondSwap == -1 && A[i] == B[firstSwap] && A[firstSwap] == B[i])
secondSwap = i;
else
return false;
}
}
if (firstSwap != -1 && secondSwap != -1)
{
System.out.println("yes");
System.out.println("swap " + (firstSwap + 1) + " " + (secondSwap + 1));
return true;
}
System.out.println("array is already sorted!");
return false; // or whatever you decide to do; maybe even an exception or enumerated type
}
检查单反转：
你在这里做得太多了！乍一看，你似乎对每一个可能的案例都很残忍。
相反，你可以做的是找到所有数字都不同的区域。如果这些元素中有两个以上，或者两个被多个元素分隔，则立即返回false。
上面“不止一个”的原因是因为奇数长度的区域——中间的元素是相同的。如果找到这两个区域，请将它们视为一个。然后，您可以继续查找该区域是否反转。
private static boolean CheckSingleReverse(int[] A, int[] B)
{
// find region
int L = A.length;
int diffStart = -1, diffEnd = -1; boolean mid = false, found = false;
for (int i = 0; i < L; i++)
{
if (A[i] != B[i])
{
if (found)
{
if (i - diffEnd == 2 && !mid)
{
mid = true;
found = false;
diffEnd = -1;
}
else
return false;
}
else if (diffStart == -1)
diffStart = i;
}
else
if (diffStart != -1 && diffEnd == -1)
{
found = true;
diffEnd = i - 1;
}
}
if (diffEnd == -1)
{
if (A[L - 1] != B[L - 1])
diffEnd = L - 1;
else if (!found)
{
System.out.println("array is already sorted!");
return false;
}
}
// find out if it's reversed
int count = (diffEnd - diffStart + 1) / 2;
for (int i = 0; i < count; i++)
{
int oneEnd = diffStart + i, otherEnd = diffEnd - i;
if (!(A[oneEnd] == B[otherEnd] && A[otherEnd] == B[oneEnd]))
return false;
}
System.out.println("yes");
System.out.println("reverse " + (diffStart + 1) + " " + (diffEnd + 1));
return true;
}
只是为了让您了解性能提升，在数组长度为 150 的 ideone.com 上，CheckSingleReverse 的原始实现需要 1.83 秒，而新的实现只需要 0.1 秒。长度为 250，原始版本实际上超过了计算时间限制（5 秒），而新的仍然只需要 0.12 秒。
由此看来，你的实现需要指数时间，而我的是线性时间(忽略排序)。
有趣的是，对于300万的数组大小，我仍然得到大约0.26秒的时间(< code>ideone的执行时间也有一点波动，可能是由于需求的原因)
-
我遇到了这个问题，给定一个整数数组，判断整数序列是从左、右还是死端退出数组。您从左侧输入数组并沿指定方向移动N个索引（其中N是整数的值）（正是右，负是左） 我想到的一个解决方案是，若所有整数的值都是正的，那个么就向右退出或向左退出。但是，此解决方案并不涵盖所有场景。我需要帮助来解决这个问题。
-
我正在使用android Studio学习应用程序开发。 在build.gradle页面上，我遇到了一个错误，即 “编译'com.android.support:appcompat-v7:25.2.0'”
-
首先，如果我搞砸了我的描述，我是新手，基本上我在正确使用node上遇到了麻烦，我跟随了youtube教程，直到老师告诉我们重新运行我们的代码，当我尝试使用他做的代码时，我得到了这个错误。 我搜索了错误中提到的，但找不到文件夹，我认为它是问题的一部分。 我尝试了很多方法，例如使用，这导致了这个cmd日志； 我还尝试删除我的和，但没有结果。 任何帮助都是感激的，并提前表示感谢：） 编辑：这里是pack
-
我使用ACR122读卡器已经有一段时间了，它在读取Mifare 1K或Mifare Ultralight NFC卡时都没有问题。 将读卡器升级到最新版本（ACR1251）后，我的程序无法读取Mifare 1K卡的UID。 这是我用来阅读的片段： 使用新版rad阅读器： ResponseAPDU.getSW1（）函数返回98 而getSW2（）返回130 我试着在网上和读卡器文档中搜索响应代码的解释
-
问题内容： 我有一小段代码在包含SWING控件的applet中运行，用于将信息写入某个端口上的套接字，然后侦听响应。这可以正常工作，但是有问题。端口侦听器实际上处于循环状态，直到服务器接收到null。我希望用户能够在等待服务器响应的同时在applet实例化的GUI中执行其他操作（这可能需要几分钟的时间）。我还需要担心服务器与客户端之间的连接断开。但是在编写代码的方式中，小程序似乎冻结（实际上是在循
-
我试图写一个代码为每个股票价值是75美元或更多添加一个"*"在STK_FLAG列。 ORA-06550：第15行，第21列：PLS-00201：标识符“STK\U FLG”必须声明ORA-06550：第15行，第5列：PL/SQL:SQL语句忽略ORA-06550：第23行，第7列：PL/SQL:ORA-00904：“STK\U FLG”：无效标识符ORA-06550：第17行，第5列：PL/SQ