Dave
BAN USERTime O(n), Space O(n)
public static int[] IncArray(int[] arr) {
int carryOver = 0;
for(int i = arr.length - 1; i >= 0; i--) {
arr[i]++;
arr[i] += carryOver;
carryOver = 0;
if(arr[i] >= 10) {
carryOver = 1;
arr[i] %= 10;
} else {
break;
}
}
int[] result = arr;
if(carryOver == 1) {
result = new int[arr.length + 1];
result[0] = 1;
System.arraycopy(arr, 0, result, 1, arr.length);
}
return result;
}
O(n) implementation:
public static String ReducePath(String input, String sep) {
if(input == null || sep == null) {
return null;
}
// Tokenize by specified seperator
String[] parts = input.split(sep);
List<String> finalParts = new ArrayList<String>();
boolean skipNext = false;
// Go through path in reverse order
for(int i = parts.length - 1; i >= 0; i--) {
// Skipping as result of a ".."
if(skipNext == true) {
skipNext = false;
continue;
}
// Skipping as result of "//"
if(parts[i].isEmpty()) {
continue;
}
// Skipping ".." and setting marker for next iteration
if(parts[i].equals("..")) {
skipNext = true;
continue;
}
// Ignoring...
if(parts[i].equals(".")) {
continue;
}
// Ok, hold on to this
finalParts.add(parts[i]);
}
// Reverse the list
Collections.reverse(finalParts);
// Join the reversed list and prepend it with sep
return String.format("%s%s", sep, String.join(sep, finalParts));
}
I think your idea is on point. But for this:
I don't see where parent is declared. Also, once you exit the first while loop and you're just iterating over the remaining items in one branch or the other, there is no need to keep adding items to the set.
- Dave July 31, 2015