Adi
BAN USERpublic ArrayList<Integer> serialize(Pair head)
{
ArrayList<Integer> al = new ArrayList<Integer>();
if(head==null)
{
al.add(null);
return al;
}
Stack<Pair> s = new Stack<Pair>();
s.push(head);
while(!s.empty())
{
Pair node = ( Pair) s.pop();
if(node==null)
{
al.add(null);
}
else
{
s.push(node.second);
s.push(node.first);
al.add(node.val);
}
}
return al;
}
public Pair cons_tree(Iterator<Integer> al)
{
Pair p = new Pair(null, null , 0);
Integer i = al.next();
if(i == null)
{
p = null;
return p;
}
p.val = i;
p.first = cons_tree(al);
p.second = cons_tree(al);
return p;
}
Move right when at top or bottom edge. move down when at left edge or right.
following is the code. Order of conditional statements should be reserved.
public void traverse_zigzag(int size)
{
traverse_recurse(size-1, 0,0, true);
}
private void traverse_recurse(int limit, int i, int j, boolean flag) {
int val = (i*(limit+1))+(j+1);
System.out.println(val);
if(val == (limit+1)*(limit+1))
{
return;
}
if(i==0 & flag)
{
traverse_recurse(limit, i, j+1, !flag);
}
else if(i==limit & !flag)
{
traverse_recurse(limit, i, j+1, !flag);
}
else if(j==0 & !flag)
{
traverse_recurse(limit, i+1, j, !flag);
}
else if(j==limit & flag)
{
traverse_recurse(limit, i+1, j, !flag);
}
else if(flag)
{
traverse_recurse(limit, i-1, j+1, flag);
}
else if(!flag)
{
traverse_recurse(limit, i+1, j-1, flag);
}
}
My runtime should be O(k * log j), where j is the maximum times a number repeats in n or m
My python solution basically looks for the largest number that be chosen from either of the arrays provided there are enough items left to fulfill remaining k after that number is chosen from either array.
I keep a running count of how many items can be chosen from n or m using nLeft or mLeft.
nArray is an array of lenght 10 where every index say i, contains a position p and array 'a'. 'a' is the indexes where i appeared in n. p is the index in a which is the smallest index of i in n which we can consider next. similarly mArray.
for every k i consider numbers from 9 to 1 in each array and check if i can choose it.
my code:
- Adi April 03, 2016