[LeetCode] ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

Result: PQHNAPLSIIGYIR

If we think of the above as 2D matrix of letters, the key here is to figure out for each character of the string, what will be its row index and column index in the matrix? Once we have the 2D matrix, we can just go through it row by row to construct the output string.

In the above example, the number of row is 3. Then there will be 3-2=1 element between each multiple-element column. So if the string length is 4, 4/(3+(3-2))=1, there will be 1*(3-2+1) = 2 columns. If the string length is 5, 6, 7, there will be 1*(3-2+1) + 1 = 3 columns, if string length is 8, there will be 2*(3-2+1) = 4 columns.

Got the math?

And here is the code:




	public String convert(String s, int numRows) {
	if(s==null || s.isEmpty() || s.length() == 1 || numRows <= 1)
	return s;
	int len = s.length();
	int numCols = getNumCols(len, numRows);
	char[][] matrix = new char[numRows][numCols];
	for(int i=0; i<len; i++){
	matrix[getNumRows(i+1, numRows)-1][getNumCols(i+1, numRows)-1] = s.charAt(i);
	}
	StringBuilder sb = new StringBuilder();
	for(int r=0; r<numRows; r++){
	for(int c=0; c<numCols; c++){
	if(matrix[r][c]!='\0')
	sb.append(matrix[r][c]);
	}
	}
	return sb.toString();
	}
	public int getNumRows(int len, int numRows){
	int t = len%(numRows-2+numRows);
	if(t==0)
	return 2;
	else if(t>numRows)
	return 2+numRows-2+numRows-t;
	else
	return t;
	}
	public int getNumCols(int len, int numRows){
	int t1 = len/(numRows-2+numRows);
	int t2 = len%(numRows-2+numRows);
	if(t2==0)
	return t1*(numRows-1);
	else if(t2>numRows)
	return t1*(numRows-1) + t2 - numRows + 1;
	else
	return t1*(numRows-1) + 1;
	}

view raw zigzag.java hosted with ❤ by GitHub

Three ice water buckets challenge

This problem is found here: http://learningandtheadolescentmind.org/resources_02_bucket.html

I called it three "Ice Bucket Challenge" for fun. ;) Here is the problem description.

There are an 8-liter bucket filled with ice water and empty 3-liter and 5-liter buckets. You solve the puzzle by using the three buckets to divide the 8 liters of water into two equal parts of 4 liters. Try to solve the puzzle in the fewest number of moves.

Although to find a fewest number of moves is not easy, but I can design depth first search to find the necessary moves to distribute the waters.
Here is the code

	public static boolean threeBuckets(Integer[] curr, Integer[] max, List<List<Integer>> visited){
	//skip the ones we already try
	if(visited.contains(Arrays.asList(curr)))
	return false;
	visited.add(Arrays.asList(curr));
	if(isDone(curr)){
	//print out the solution
	System.out.println(visited);
	return true;
	}
	for(int i = 0; i<3; i++){
	if(curr[i]>0){
	//transfer water to other buckets
	for(int j = 0; j<3; j++){
	//skip itself and the bucket is already full
	if(j==i || curr[j] == max[j])
	continue;
	//we are going to dump as much water as we can
	//make a copy of the buckets so we can retry later on
	Integer[] copy = Arrays.copyOf(curr, 3);
	if(copy[i] + copy[j] <= max[j]){
	copy[j] = copy[i] + copy[j];
	copy[i] = 0;
	}else{
	int t = copy[i] + copy[j];
	copy[j] = max[j];
	copy[i] = t - copy[j];
	}
	if(threeBuckets(copy, max, visited))
	return true;
	}
	}
	}
	return false;
	}
	private static boolean isDone(Integer[] curr){
	return curr[0] == 4 || curr[1] == 4 || curr[2] == 4;
	}

view raw 3buckets.java hosted with ❤ by GitHub

The idea here is to for each possible case, we find the all possible cases which can be derived from it. For example, from 8, 0, 0, it could be 5, 0, 3 or 3, 5, 0. And we use a list keep track of the cases we already visited. Think of all possible cases as a graph, we essentially do a depth first search until we find the case contains 4. A potential solution to find the fewest moves is to use the breath first search. We can use a Queue to contain the list of cases we already visited, then generate the queue of next level based on that, also keep track of the parent case for each case in the queue until we find the case.