max
BAN USERpublic final class OptimalJump {
public OptimalJump(int[] arr) {
super();
this.arr = arr;
}
public Jump determineJump(){
return findMinJump(0, 0);
}
//==== NESTED ====
public static class Jump implements Comparable<Jump> {
@Override
public int compareTo(Jump other) {
int size1 = elements.size();
int size2 = other.elements.size();
if( size1 > size2 ){
return 1;
}
else if( size1 < size2 ){
return -1;
}
return 0;
}
@Override
public String toString(){
return elements.toString();
}
private List<Integer> elements = new ArrayList<Integer>();
}
private static final class JumpKey {
JumpKey(int index, int offset) {
super();
this.index = index;
this.offset = offset;
}
int index;
int offset;
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + index;
result = prime * result + offset;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
JumpKey other = (JumpKey) obj;
if (index != other.index)
return false;
if (offset != other.offset)
return false;
return true;
}
}
//==== PRIVATE ====
private final int[] arr;
private final Map<JumpKey, Jump> cache = new HashMap<JumpKey, Jump>();
private Jump findMinJump( int index, int offset ){
final JumpKey key = new JumpKey(index, offset);
Jump memJump = cache.get( key );
if( memJump != null ){
return memJump;
}
index = index + offset;
final int value = arr[index];
Jump minJump = null;
for( int i = 1; i < value+1 && index+i < arr.length; i++ ){
Jump jump = findMinJump(index, i);
if( minJump == null || jump.compareTo(minJump) < 0 ){
minJump = jump;
}
}
if( minJump == null ){
minJump = new Jump();
}
minJump.elements.add(0, index);
cache.put(key, minJump);
return minJump;
}
}
private List<Pair> findSum( final int[] arr , int sum ){
final Map<Integer, Integer> elems = new HashMap<Integer, Integer>();
// O(N)
for( int value : arr ){
Integer counter = elems.get(value);
if( counter == null ){
counter = Integer.valueOf(1);
}
else {
counter += 1;
}
elems.put( value, counter );
}
final List<Pair> pairs = new ArrayList<Pair>();
// O(N)
for( int value : arr ){
Integer curCounter = elems.get(value);
elems.put( value, curCounter-1 );
int neededValue = sum - value;
Integer neededCounter = elems.get(neededValue);
if( neededCounter != null && neededCounter > 0 ){
pairs.add( new Pair(value, neededValue) );
elems.put(neededValue, neededCounter-1);
}
}
return pairs;
}
// Rabin-Karp algorithm
/**
* Write a function that takes an input string and a pattern string and returns a collection
* of indices of occurences of pattern within the input string.
*
* N - 'base' string length
* M - 'pattern' string length
*
*/
public final class RabinKarpStringMatcher {
public RabinKarpStringMatcher(String base, String pattern) {
if( base == null || pattern == null ){
throw new IllegalArgumentException("NULL 'base' or 'pattern' string passed: base = '" + base + "', pattern = '" + pattern + "'");
}
this.base = base;
this.pattern = pattern;
this.patternLength = pattern.length();
this.baseLength = base.length();
this.patternHash = calculateHash(pattern, 0, patternLength-1);
}
/**
* Time: O(N+M)
*/
public List<Integer> findMatches(){
if( matchedIndexes == null ){
matchedIndexes = new ArrayList<Integer>();
final int lastIndex = baseLength - patternLength + 1;
BigInteger baseValue = null;
int baseHash = 0;
for( int i = 0; i < lastIndex; i++ ){
if( i == 0 ){
baseValue = calculateValue(base, 0, patternLength-1);
}
else {
baseValue = recalculateValue(base, baseValue, i-1, i+patternLength-1);
}
baseHash = baseValue.mod( BigInteger.valueOf(MODULO) ).intValue();
if( baseHash == patternHash && isBaseEqualToPattern(i) ){
matchedIndexes.add(i);
}
}
}
return matchedIndexes;
}
//==== PRIVATE ====
private final String base;
private final String pattern;
private final int patternLength;
private final int baseLength;
private final int patternHash;
private static final int MODULO = 307;
private static final int BASE = 32;
private static final int BASE_SHIFT = 5; // pow(2, BASE_SHIFT) = BASE
private List<Integer> matchedIndexes;
/**
* Time: O(M)
*/
private boolean isBaseEqualToPattern(int from){
for(int j = 0; j < patternLength; j++ ){
if( base.charAt(from+j) != pattern.charAt(j) ){
return false;
}
}
return true;
}
/**
* Time: O(M)
*/
private BigInteger calculateValue(String str, int from ,int to){
BigInteger value = BigInteger.valueOf(0);
for( int i = from; i < to+1; i++ ){
value = value.multiply( BigInteger.valueOf(BASE) ).add( BigInteger.valueOf(str.charAt(i)) );
}
return value;
}
/**
* Time: O(M)
*/
private int calculateHash(String str, int from ,int to){
int hash = 0;
for( int i = from; i < to+1; i++ ){
hash = ( hash * BASE + str.charAt(i) ) % MODULO;
}
return hash;
}
/**
* Time: O(1)
*/
private BigInteger recalculateValue(String str, BigInteger hash, int from ,int to){
final int h = 1 << ( BASE_SHIFT * (to-from-1));
BigInteger newHash = hash.subtract( BigInteger.valueOf(str.charAt(from)).multiply( BigInteger.valueOf(h) ) );
newHash = newHash.multiply( BigInteger.valueOf(BASE) );
newHash = newHash.add( BigInteger.valueOf(str.charAt(to)) );
return newHash;
}
}
- max November 03, 2016