FreeTymeKiyan
BAN USERpublic static List<Integer> steppingNo(int s, int e) {
ArrayList<Integer> res = new ArrayList<Integer>();
int i = 0;
while (s <= e) {
if (isStepping(s)) {
res.add(s);
}
s++;
}
return res;
}
private static boolean isStepping(int i) {
if (i >= 0 && i <= 9) return true;
while (i >= 10) {
if (Math.abs(i % 10 - (i / 10) % 10) != 1) { // compare last two digits
return false;
}
i = i / 10;
}
return true;
}
Java version of Kadane / max subarray:
public int[] indexRange(int[] array) {
int beginTemp = 0;
int begin = 0;
int end = 0;
int maxSoFar = array[0];
int maxEndingHere = array[0];
for (int i = 1; i < array.length; i++) {
if (maxEndingHere < 0) {
maxEndingHere = array[i];
beginTemp = i;
} else {
maxEndingHere += array[i];
}
// calculate maxSoFar
if(maxEndingHere >= maxSoFar) {
maxSoFar = maxEndingHere;
begin = beginTemp;
end = i;
}
}
return new int[]{begin, end, maxSoFar};
}
i don't think this would work given an all negative array
- FreeTymeKiyan October 12, 2013
Sorry about the efficiency. Your dfs is absolutely more efficient than the brute-force checking. I just wrote down my first idea.
- FreeTymeKiyan October 16, 2014