-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.java
More file actions
107 lines (81 loc) · 2.74 KB
/
Solution.java
File metadata and controls
107 lines (81 loc) · 2.74 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
package almostsorted;
import java.util.*;
public class Solution {
// Complete the almostSorted function below.
static void almostSorted(int[] arr) {
if (arr.length == 1) {
System.out.println("yes");
return;
}
int startIndex = 0;
int finishIndex = -1;
for (int i=1; i<arr.length; i++) {
if (arr[i] > arr[i-1] && finishIndex == -1) {
startIndex = i;
} else if (arr[i] < arr[i-1]) {
finishIndex = i;
}
}
if (finishIndex == -1) {
System.out.println("yes");
return;
}
if (
finishIndex - startIndex == 1 || //neighbours
(finishIndex - startIndex > 3 && arr[startIndex+1] < arr[startIndex+2]) // random swap
) {
swap(arr, startIndex, finishIndex);
if (isSorted(arr)) {
System.out.println("yes");
System.out.print("swap " + (startIndex + 1) + " " + (finishIndex + 1));
return;
} else {
System.out.println("no");
return;
}
}
reverse(arr, startIndex, finishIndex);
if (isSorted(arr)) {
System.out.println("yes");
System.out.print("reverse " + (startIndex + 1) + " " + (finishIndex + 1));
} else {
System.out.println("no");
}
}
static boolean isSorted(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
if (a[i] > a[i + 1]) {
return false;
}
}
return true;
}
private static void reverse(int[] arr, int startIndex, int finishIndex) {
int lenght = finishIndex - startIndex + 1;
for(int i = startIndex; i< startIndex + lenght/2; i++){
int temp = arr[i];
int endIndex = finishIndex - (i- startIndex);
arr[i] = arr[endIndex];
arr[endIndex] = temp;
}
}
private static void swap(int[] arr, int startIndex, int finishIndex) {
int tmp = arr[startIndex];
arr[startIndex] = arr[finishIndex];
arr[finishIndex] = tmp;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) {
int n = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
int[] arr = new int[n];
String[] arrItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int i = 0; i < n; i++) {
int arrItem = Integer.parseInt(arrItems[i]);
arr[i] = arrItem;
}
almostSorted(arr);
scanner.close();
}
}