AC4400
BAN USEROne solution: Every time, select the smallest number with front[] = 0.
e.g. height[] = {3, 1, 2, 4}, front[] = {0, 2, 1, 0}
1) Find the smallest number from height[] that has 0 in front[], in this case it is 3, then 3 is 1st element in the queue.
2) For rest of the elements i in height[], if it is smaller than 3, then front[i] - 1, otherwise keep front[i] the same.
Go back to 1)
This is pretty much like topological sorting; each time remove the node with indegree == 0.
Nice catch. Thanks.
Still recursion;
public static void printMove(int[] src, int[] tgt, int index){
Print(src); // Print move
if(index < src.length && src[index] != tgt[index]){
int numPos = findPos(src, tgt[index]);
int zeroPos = findPos(src, 0);
int temp = 0;
if(zeroPos != index){
temp = src[index];
src[index] = src[zeroPos];
src[zeroPos] = temp;
Print(src); // Print move
}
temp = src[index];
src[index] = src[numPos];
src[numPos] = temp;
printMove(src, tgt, index+1);
}
}
A simple recursion should be suffice:
1) Find the 0's index (pos_0) in src[]
2) If tgt[pos_0] == 0, stop recursion, otherwise swap 0 with tgt[pos_0], then recursion.
Time complexity is O(N^2), space is O(1).
public static void PrintSwap(int[] src, int[] tgt){
for(int n : src) System.out.print(s+" "); // Print every move
int pos_0 = findPosition(src, 0);
if(tgt[pos_0] != 0){
int pos_n = findPosition(tgt[pos_0]);
int temp = src[pos_0];
src[pos_0] = src[pos_n];
src[pos_n] = src[pos_0];
PrintSwap(src, tgt); // Recursion
}
}
private static int findPosition(int[] array, int key){
for(int i=0;i<array.length;i++)
if(array[i] == key)
return i;
return -1;
}
Dynamic programming, similar to Longest Common Subsequence:
public static String LPL(String str, int i, int j, String result){
if(i > j) return result;
if(i == j)
return result.substring(0, result.length()/2) + str.charAt(i) + result.substring(result.length()/2);
if(str.charAt(i) == str.charAt(j))
return LPL(str, i+1, j-1, result.substring(0, length()/2 + str.charAt(i) + str.charAt(j) + result.substring(result.length()/2));
String str1 = LPL(str, i+1, j, "");
String str2 = LPL(str, i, j-1, "");
return (str1.length() > str2.length()) ? str1 : str2;
}
This can be viewed as a BFS traversal of a graph.
public static int CalculateCn(int num){
int count = 0;
ArrayList<Integer> queue = new ArrayList<Integer>();
queue.add(0);
while(!queue.isEmpty()){
int sum = queue.remove(0);
if(sum == num)
count ++;
else
for(int i=1;i<=Math.min(3, num-sum);i++)
queue.add(sum+i);
}
return count;
}
- AC4400 September 19, 2013