Richard
BAN USERThe following code may avoid repetitions:
public static void printAll(int[] data)
{
if(data == null) return;
if(data.length == 0) return;
int numOne = 0;
for(int i = 0; i < data.length; ++i)
{
numOne += data[i];
}
int numZero = data.length - numOne;
String str = "";
printHelper(numZero, numOne, 0, str, 0, 0);
}
private static void printHelper(int numZero, int numOne, int level, String str, int numZeroUsed, int numOneUsed)
{
if(level == numZero + numOne)
{
System.out.println(str);
return;
}
if(numZeroUsed < numZero)
{
String strNew = str;
strNew += "0";
printHelper(numZero, numOne, level+1, strNew , numZeroUsed+1, numOneUsed);
}
if(numOneUsed < numOne)
{
String strNew = str;
strNew += "1";
printHelper(numZero, numOne, level+1, strNew, numZeroUsed, numOneUsed+1);
}
}
For example you have a matrix, each row is sorted:
{5, 10, 15, 20}
{10, 13, 16, 19}
{2, 19, 26, 40}
{18, 22, 23, 24}
Then you need to sort the entire matrix and output a 4*4=16 dimensional vector:
{2, 5, 10, 10, 13, 15, 16, 18, 19, 19, 20, 22, 23, 24, 26, 40}.
Hope this helps.
I don't think this code can handle the following case:
Given String str = "123", output "123.0.0.0", "12.3.0.0", "12.30.0.0", etc.
Actually I doubt the example given in the question is correctly answered. For str = "25525511135", there are four possible valid IP addresses:
255.255.111.35
255.255.110.135
255.255.101.135
255.255.11.135
Suppose one end of the tunnel is at 0 point, and the other end is at L point. Suppose the particle come from 0 to L. Then obviously the total distance of the particle is s = Lv/2V. Since s may be larger than L, this means the particle may reach the L point and go back towards 0, and then reach 0 point and go to L again...
So, if s/L (integer division) is odd, it means the particle is going from L to 0 when the two trains meet. Therefore, the position of the particle should be L - s % L. Otherwise, the position is s % L.
Please correct me if I'm wrong.
So we can use ArrayList list to store the number of elements in each subarray (here by subarray I mean the subarray that contains consecutive numbers).
Also, we can use Hashtable table to store each element in array. The KEY is array[i], while VALUE is the index of subarray it belongs in.
Then, we traverse the array. For example: {4,5,34,33,32,11,10,31}
1. Put <4, 0> in table, and let list[0] = 1; (4 belongs to the 0-th subarray, so the 0-th subarray has 1 element)
2. Put<5, 0> in the table, and let list[0] = 2; (we know 5 belongs to the 0-th subarray because we check if array[i]-1 or array[i]+1 has been put into the table)
3. Put<34, 1> in the table, and let list[1] = 1; (this is because neither 33 nor 35 has been put int the table, so we think 34 belongs to a new subarray).
4. We keep this procedure until the last element in array.
5. Then list.size represents the number of subarray, while list[m] represents the number of elements in the m-th subarray.
===============
I just found this method cannot correctly deal with the array {4, 5, 8, 7, 6}. The above method will build two subarrays: {4, 5}, {8, 7, 6}. I think can be revised as follows:
For array[i] (say array[4] = 6), we check array[i]-1 AND array[i]+1. If both are in the table but with different subarray index (say {4, 5} is the 0-th subarray, {8, 7} is the 1st subarray), we merge them by changing the subarray index of {8, 7} to 0, and put<6, 0> into the table. Of course list[0] += list[1] and list.remove(1) should be done.
Use hashtable to achieve O(n) complexity. Please let me know if there is any mistake.
public static int[] find(int[] array)
{
// Contains the number of elements of each subarray
ArrayList<Integer> list = new ArrayList<Integer>();
// Key: the element in the int array, e.g. array[i].
// Value: the index of the element in "list" that saves
// the number of elements of the subarray that array[i] belongs in.
Hashtable<Integer, Integer> table = new Hashtable<Integer, Integer>();
int seqIndex = 0; // The number of subarrays so far.
for(int i = 0; i < array.length; ++i)
{
if(table.containsKey(array[i]-1))
{
table.put(array[i], table.get(array[i]-1)); // array[i] and array[i-1] belong to the same subarray
list.set(table.get(array[i]-1),list.get(table.get(array[i]-1))+1); // Increase the number of elements of the subarray by 1
}
else if(table.containsKey(array[i]+1))
{
table.put(array[i], table.get(array[i]+1));
list.set(table.get(array[i]+1),list.get(table.get(array[i]+1))+1);
}
else if(table.containsKey(array[i]))
{
list.set(table.get(array[i]),list.get(table.get(array[i]))+1);
}
else
{
table.put(array[i], seqIndex++); // array[i] does not belong to any subarray.
list.add(1); // The new array contains only array[i], so it has only 1 element.
}
}
// Find the subarray that contains maximum number of elements.
int max = 0;
for(int i = 0; i < list.size(); ++i)
{
if(max < list.get(i))
{
max = list.get(i);
}
}
int[] result = new int[max];
int resultIndex = 0;
for(int i = 0; i < array.length; ++i)
{
if(list.get(table.get(array[i])) == max)
{
result[resultIndex++] = array[i];
}
}
return result;
}
A very ugly brute force solution:
================================
class WaysBobDie
{
private int m;
private int n;
private int N;
private double die;
private double live;
public WaysBobDie(int m, int n, int N)
{
this.m = m;
this.n = n;
this.N = N;
die = 0;
live = 0;
}
public void calculate(int x, int y)
{
calculateHelper(x, y, 0);
System.out.println("Probability of alive: " + live/(live+die));
}
private void calculateHelper(int x, int y, int numSteps)
{
if(isLive(x, y) && numSteps != N)
{
calculateHelper(x+1, y, numSteps+1);
calculateHelper(x-1, y, numSteps+1);
calculateHelper(x, y+1, numSteps+1);
calculateHelper(x, y-1, numSteps+1);
}
else if(isLive(x, y) && numSteps == N)
{
++live;
return;
}
else if(!isLive(x, y))
{
++die;
return;
}
}
private boolean isLive(int X, int Y)
{
if(X < 0 || Y < 0 || X >= m || Y >= n)
{
return false;
}
else
{
return true;
}
}
}
I guess the time complexity is O(4^N), which is incredibly ugly. Looking forward to better solution.
As the other anonymous guy said, this process can be modeled as a two-dimensional random walk (thus Markov Chain) with equal probability in each direction. The probability transition matrix M of this process will be of size m*n-by-m*n, and it involves the calculation of M^N (multiply M by itself N times). Since the time complexity of matrix multiplication is O((m*n)^3) (well, you can make it a little faster), it is a polynomial time algorithm now (even though still not very fast).
I'm thinking of a similar algorithm to yours. First, find the level of p and q by continuously performing p = p.parent, q = q.parent until they hit the root (I assume we are given the pointers to p and q). So we can get the level of p & q (say Lp, Lq) in O(logn) time.
Then, if Lp > Lq, perform p = p.parent Lp-Lq times to make p and q at the same level (similarly if Lq > Lp). After this, we can set a while loop and let p = p.parent and q = q.parent "simultaneously" in each iteration, until they hit the same node, which is the lca.
The time complexity will be O(logn) without no extra space used. Do you think this algorithm is gonna work?
=========
Note that p and q must locate at the two different branches of the lca, so for BST, we just do the following:
Node n = root;
if(p.value > n.value && q.value > n.value) // assume distinct elements
n = n.right;
else if (p.value < n.value && q.value < n.value)
n = n.left;
else
return n;
public static boolean isColorful(int num)
{
ArrayList<Integer> list = new ArrayList<Integer>(); // contains each digit in num
int key = 0; // key value for the hashtable
Hashtable<Integer, Integer> table = new Hashtable<Integer, Integer>();
while(num != 0)
{
list.add(num%10);
if(table.contains(num%10))
{
return false;
}
else
{
table.put(key++, num%10);
System.out.println(num%10);
num /= 10;
}
}
int listSize = list.size();
int[] array = new int[listSize]; // contains the products of each substring
for(int i = 0; i < listSize; ++i)
{
array[i] = list.get(i);
}
int start = 1;
while(start < listSize - 1) // calculate the product of all substrings, O(n^2) where n is the number of digits
{
int j = 0;
for(int i = start; i < listSize; ++i)
{
array[j] = array[j] * list.get(i);
if(table.contains(array[j]))
{
return false;
}
else
{
table.put(key++, array[j]);
System.out.println(array[j]);
++j;
}
}
++start;
}
return true;
}
I found the while loop is not right. Taking 263 as an example. So the first loop push 3 in the list. The second loop push 6*3 in the list. The third loop push 2*3 and 2*6*3 in the list. However, as stated in the problem, 2*3 should not be considered, since it is not a substring.
Correct me if I'm wrong.
My understanding of the problem is, given an array a[1], ..., a[n], only a[i] and a[j] are the same number, while other elements are all distinct. However we don't know the index i, j. The only thing we know is j \in (i, i + arr_size/2]. We need to find both i and j.
I'm thinking of a method using a hash table which may work. For each element in a[i], if there is the same element in the hash table, then we have found this duplicated element, otherwise put a[i] into the hash table. Time complexity should be O(n). This algorithm should work, right?
One problem is that it did not take advantage of the information that the duplicated number must appear in the range (i, i + arr_size/2]. Also, since the range of the number is unknown, the size of hash table could be large if the largest number is very large and the hash function is not well chosen. Hope to see better method.
Artist, what I meant was that, it is straightforward to first search the given element and then seek for its successor. The method given above is definitely much better, and I have no clue how did Duke87 come up with it. That's why I ask.
- Richard November 06, 2012