panxin0718
BAN USERpublic TreeNode build(int[] val)
{
Stack<TreeNode> ns = new Stack<TreeNode>();
TreeNode root = new TreeNode(val[0]);
ns.push(root);
TreeNode last = null;
for(int i = 1; i < val.length; i++)
{
TreeNode n = new TreeNode(val[i]);
if(val[i] < ns.peek().val)
{
ns.peek().left = n;
}
else
{
for(last = ns.pop(); ns.size() > 0 && ns.peek().val <= val[i]; ns.pop());
if(ns.size() == 0)
{
last.right = n;
}
else
{
ns.peek().left = n;
}
ns.push(n);
}
}
return root;
}
public ArrayList<String> permutation(String[] num)
{
Arrays.sort(num);
Arrays.reverse(num);
ArrayList<String> res = new ArrayList<String>();
pHelper(0, num, res);
return res;
}
public void pHelper(int p, String[] num, ArrayList<String> res)
{
if(p == num.length)
{
String v = "";
for(int i = 0; i < num.length; i++)
v += num[i];
res.add(v);
return;
}
pHelper(p+1, num, res);
for(int i = p+1; i < num.length; i++)
{
swap(num, p, i);
pHelper(p+1, num, res);
swap(num, p, i);
}
}
public void swap(String[] num, int p, int i)
{
String h = num[i];
num[i] = num[p];
num[p] = h;
}
public ListNode insert(ListNode head, ListNode newNode)
{
if(head == null)
{
head = newNode;
head.next = head;
return head;
}
ListNode pre = head;
ListNode cur = head.next;
while(cur != head)
{
if(newNode.val <= cur.val && newNode.val >= pre.val)
{
pre.next = newNode;
newNode.next = cur;
return head;
}
pre = cur;
cur = cur.next;
}
pre.next = newNode;
newNode.next = cur;
if(preNode.val < cur)
return preNode;
else
return cur;
}
public String minArr(String s)
{
char min = 'Z';
for(int i = 0; i < s.length(); i++)
if(s.charAt(i) < min)
min = s.charAt(i);
ArrayList<Integer> pos = new ArrayList<Integer>();
for(int i = 0; i < s.length(); i++)
if(s.charAt(i) == min)
pos.add(i);
int p = getMinPos(pos, s);
return s.substring(p) + s.substring(0, p);
}
public int getMinPos(ArrayList<Integer> pos, String s)
{
int add = 1;
int len = s.length();
s += s;
while(pos.size() > 1 && add < len)
{
for(int i = 1; i < pos.size(); )
{
if(s.charAt(pos.get(i)+add) < s.charAt(pos.get(i-1)+add))
pos.remove(i-1);
else if(s.charAt(pos.get(i)+add) > s.charAt(pos.get(i-1)+add))
pos.remove(i);
else
i++;
}
add++;
}
return pos.get(0);
}
Nice solution
- panxin0718 January 27, 2013Isn't the lexicographically minimum permutation of 3,2,1,6,7,4,5 being 3,2,1,6,7,5,4?
- panxin0718 January 27, 2013public boolean arrange(int[] x, int[] y)
{
if(x.length != y.length)
return false;
else if(x.length == 0)
return true;
return arrHelper(x, y, 0);
}
public boolean arrHelper(int[] x, int[] y, int p)
{
if(p == x.length-1)
{
if(x[p] > y[p])
return true;
else
return false;
}
if(getEqual(x, y[p])
return arrHelper(x, y, p+1);
if(!getNext(x, y[p]))
return false;
Arrays.sort(p+1, x);
return true;
}
public boolean getEqual(int[] x, int[] y, int p)
{
for(int i = p; i < x.length; i++)
{
if(x[i] == y[p])
{
int h = x[i];
x[i] = x[p];
x[p] = h;
return true;
}
}
return false
}
public boolean getNext(int[] x, int[] y, int p)
{
int min = Integer.MAX_VALUE;
int j = p;
int i = p;
for(; i < x.length; i++)
{
if(x[i] > y[p] && x[i] < min)
{
j = i;
min = x[i];
}
}
if(i == x.length) return false;
int h = x[p];
x[p] = x[j];
x[j] = h;
return true;
}
public HashMap<Integer, Integer> verticalSum(TreeNode root)
{
HashMap<Integer, Integer> vs = new HashMap<Integer, Integer>();
verticalSumHelper(vs, root, 0);
return vs;
}
public void verticalSumHelper(HashMap<Integer, Integer> vs, TreeNode root, int pos)
{
if(root == null)
return;
if(vs.get(pos) == null)
vs.put(pos, root.val);
else
vs.put(pos, vs.get(pos)+root.val);
verticalSumHelper(root.left, pos-1);
verticalSumHelper(root.right, pos+1);
}
Cache the maps in memory.
- panxin0718 February 14, 2013Top level maps are replicated to at least one machine in a region.
Low level maps are partitioned to different machines.
Hot maps, such as new york city are replicated to more machines.
the placement can be based on hash partition on the map location value;
It can adopt Dynamo's architecture which you multicast query to several machines and return as lone as one machine returns.