Skip to content

Instantly share code, notes, and snippets.

@inherithandle
Created October 18, 2019 05:47
Show Gist options
  • Save inherithandle/abe32f6a7d8bee117c7fe6581beca064 to your computer and use it in GitHub Desktop.
Save inherithandle/abe32f6a7d8bee117c7fe6581beca064 to your computer and use it in GitHub Desktop.
CodeWriting almost increasing
package com.jimmy.song.problem;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
public class CodeWriting {
public boolean almostIncreasingSequence(int[] sequence) {
boolean isIncreasingSequnece = isIncreasingSequenceWithoutRemoving(sequence);
if (isIncreasingSequnece) {
return true;
}
if (isAlmostIncreasingSequence(sequence)) {
return true;
}
return false;
}
private boolean isIncreasingSequenceWithoutRemoving(int[] sequence) {
for (int i = 0; i < sequence.length - 1; i++) {
if (sequence[i] > sequence[i + 1]) {
return false;
}
}
return true;
}
// [1,3,2,1]
// [1,3,2]
// [1,2]
private boolean isAlmostIncreasingSequence(int[] sequence) {
boolean isAlmostIncreased = true;
for (int i = 0; i < sequence.length; i++) {
List<Integer> removedArray = Arrays.stream(sequence).boxed().collect(Collectors.toList());
removedArray.remove(i);
boolean isIncreasingSequence = true;
for (int j = 0; j < removedArray.size() - 1; j++) {
if (removedArray.get(j) > removedArray.get(j+1)) {
isIncreasingSequence = false;
break;
}
}
if (isIncreasingSequence) {
return true;
}
}
return false;
}
// copied from StackOverflow, https://stackoverflow.com/questions/642897/removing-an-element-from-an-array-java
public void removeElement(Object[] arr, int removedIdx) {
System.arraycopy(arr, removedIdx + 1, arr, removedIdx, arr.length - 1 - removedIdx);
}
public static void main(String[] args) {
// [1,3,2,1]
// [1,3,2]
// [1,2]
int[] a = new int[] {1, 3, 2, 1};
int[] b = new int[] {1, 3, 2};
int[] c = new int[] {1, 2};
CodeWriting codeWriting = new CodeWriting();
System.out.println(codeWriting.almostIncreasingSequence(a));
System.out.println(codeWriting.almostIncreasingSequence(b));
System.out.println(codeWriting.almostIncreasingSequence(c));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment