arviman
BAN USERTested in C# and works fine:
private static void solve(Node head)
{
Stack<int> lst = new Stack<int>();
for(Node cur = head; cur!=null; cur=cur.Next)
{
if (cur.Data == 0) continue;
Stack<int> tmp = new Stack<int>();
int sum = cur.Data;
while ((cur.Data < 0 ? sum < 0 : sum > 0) && lst.Count > 0)
{
var puttotmp = lst.Pop();
tmp.Push(puttotmp);
sum += puttotmp;
}
if (sum != 0)
{
while (tmp.Count > 0)
lst.Push(tmp.Pop());
lst.Push(cur.Data);
}
}
Stack<int> revlst = new Stack<int>();
while (lst.Count > 0)
revlst.Push(lst.Pop());
while (revlst.Count > 0)
Console.Write(revlst.Pop() + " ");
}
Haven't tested this:
public ArrayList<String> eliminateAnagram(String[] inputArray){
int n = inputArray.length;
Map<String,Boolean> isAnagram = new HasMap<String,Boolean>();
Set<String> candidates = new Set<String>();
Set<String> ret = new Set<String>();
ArrayList<String> ret = new ArrayList<String>();
for(String str : inputArray) {
char[] ca = str.toCharArray();
Arrays.sort(ca);
String sorted = new String(ca);
if(seen.contains(sorted)) {
isAnagram[str] = true;
}
else { seen.add(sorted); candidates.add(str); }
}
for(String candidate : candidates) {
if(!isAnagram[candidate])
ret.add(candidate);
}
return ret;
}
Use technique similar to connected components. Mark all vertices as cc = -1. (not part of a component).
When you get an add, check if either vertex is connected. If only one is connected, mark other with the cc. If both are having a cc that are different, mark second one's cc as same as first one's cc for all vertices having second one's cc.
If both are unconnected mark both with the same new new cc number.
Checking if two points i and j are connected is an O(1) operation as you will just check the cc[i] and cc[j] are same.
You just need to construct the tree. No need to do an LCA.
Use an adjacency list as shown in anon's code and build a binary tree or adjacency map to represent the relationships. Former is preferred since the graph is very sparse (max three edges per node - 2 for child, 1 for parent).
You could also use an array representation to represent the tree such that 2*i and 2*i+1 are children of i item. However, it would waste space when the graph is linear like a list.
This is simple. Compute from bottom-right all the way to the top - left.
int[,] best = new int[R, C];
Arrays.fill(best[R], Integer.MAX_VALUE);
for(int i =0; i < R; ++i)
best[i, C] = Integer.MAX_VALUE;
for(row = R-1; row >= 0; row--)
{
for(col = C-1; col >= col; col--)
{
best[row][col] = min (best[row+1][col], best[row][col+1], best[row+1][col+1]);
}
}
return best[0][0];
static class butter {
public void solve(int testNumber, Scanner in, PrintWriter out) {
Node nd = null;
if (in.hasNext())
nd = new Node(Integer.parseInt(in.next()));
int cnt = 1;
while (in.hasNext()) {
int num = Integer.parseInt(in.next());
nd.add(num);
++cnt;
}
Node gimme = interleave(nd, out, cnt);
gimme.print(out);
out.close();
}
private Node interleave(Node nd, PrintWriter out, int n) {
Node rev = nd.clone().reverse();
Node nl = new Node(nd.data);
int cnt = 1;
Node s1 = nd.next;
Node r1 = rev;
while (r1.next != null) {
nl.add(r1.data);
if (++cnt == n) break;
nl.add(s1.data);
if (++cnt == n) break;
r1 = r1.next;
s1 = s1.next;
}
return nl;
}
class Node {
int data;
Node next;
Node(int d) {
data = d;
}
void print(PrintWriter pw) {
Node cur = this;
while (cur != null) {
pw.print(cur.data + " ");
cur = cur.next;
}
}
void add(int n) {
Node newnode = new Node(n);
Node cur = this;
while (cur.next != null) {
cur = cur.next;
}
cur.next = newnode;
}
protected Node clone() {
Node nd = new Node(this.data);
Node cur = this;
while (cur.next != null) {
cur = cur.next;
nd.add(cur.data);
}
return nd;
}
public Node reverse() {
Node prev = null;
Node cur = this;
Node nxt;
while (cur.next != null) {
nxt = cur.next;
cur.next = prev;
prev = cur;
cur = nxt;
}
cur.next = prev;
return cur;
}
}
}
just deal with numbers <=10 since only +ve numbers are incoming.
- arviman September 30, 2016