pablo.barrientos
BAN USERIs there any time constraint? If not, simply sort tha array and then look for the repeated elements -- O(n.log n).
- pablo.barrientos October 28, 2011public class Main {
public static void main(String[] args) {
combinations("hello", "", 3);
}
private static void combinations(String sourceString, String accum,
int limit) {
if (sourceString == null || sourceString.length() == 0
|| "".equals(sourceString) || limit == 0) {
System.out.println(accum);
} else {
for (char ch : sourceString.toCharArray()) {
combinations(sourceString, accum + ch, limit - 1);
}
}
}
}
Ups! I submitted the code and I was not logged in.
- pablo.barrientos October 27, 2011public class Point {
private double x;
private double y;
// getters, setters, constructors, etc.
public boolean includedInTriangle(Point p1, Point p2, Point p3) {
// based on triangles rotation
double direction = (p1.getX() - p3.getX()) * (p2.getY() - p3.getY())
- (p1.getY() - p3.getY()) * (p2.getX() - p3.getX());
double direction1 = (p1.getX() - this.getX())
* (p2.getY() - this.getY()) - (p1.getY() - this.getY())
* (p2.getX() - this.getX());
double direction2 = (p2.getX() - this.getX())
* (p3.getY() - this.getY()) - (p2.getY() - this.getY())
* (p3.getX() - this.getX());
double direction3 = (p3.getX() - this.getX())
* (p1.getY() - this.getY()) - (p3.getY() - this.getY())
* (p1.getX() - this.getX());
return (direction >= 0 && direction1 >= 0 && direction2 >= 0 && direction3 >= 0) ||
(direction < 0 && direction1 < 0 && direction2 < 0 && direction3 < 0);
}
public boolean isAnEdgeOfTriangle(Point p1, Point p2, Point p3) {
//y = xM + b and y value is included in the range;
return (this.getY() == p1.getM(p2) * this.getX() + p1.getB(p2) &&
this.getY() <= Math.max(p1.getY(), p2.getY()) && this.getY() >= Math.min(p1.getY(), p2.getY())) ||
(this.getY() == p1.getM(p3) * this.getX() + p1.getB(p3) &&
this.getY() <= Math.max(p1.getY(), p3.getY()) && this.getY() >= Math.min(p1.getY(), p3.getY())) ||
this.getY() == p2.getM(p3) * this.getX() + p2.getB(p3) &&
this.getY() <= Math.max(p2.getY(), p3.getY()) && this.getY() >= Math.min(p2.getY(), p3.getY());
}
public boolean isAVertexOfTriangle(Point p1, Point p2, Point p3){
//simple comparison of components
return (this.getX() == p1.getX() && this.getY() == p1.getY()) ||
(this.getX() == p2.getX() && this.getY() == p2.getY()) ||
(this.getX() == p3.getX() && this.getY() == p3.getY());
}
private double getM(Point other) {
return (this.getY() - other.getY()) / (this.getX() - other.getX());
}
private double getB(Point other) {
return this.getY() - this.getM(other) * this.getX();
}
}
Very easy using link from child to parent. Create the ordered list of ancestors for node q. Then check inclusion of any parent of p on the way up to the root. The first parent of p included in the list is the LCA.
- pablo.barrientos October 28, 2011public class Node {
private Node parent;
private Integer value;
public Node(Integer value) {// constructor for root
this.value = value;
}
public Node(Node parent, Integer value) {
this(value);
this.parent = parent;
}
public Node lcs(Node other) {
LinkedList<Node> parents = other.getParents();
return this.findLCA(parents);
}
private Node findLCA(List<Node> parents) {
Node parent = this.parent;
while (parent != null) {
if (parents.contains(parent)) {
return parent;
} else {
parent = parent.parent;
}
}
return parent;
}
private LinkedList<Node> getParents() {
if (parent == null) // / tree root
return new LinkedList<Node>();
else {
LinkedList<Node> parents = this.parent.getParents();
parents.addLast(this.parent);
return parents;
}
}
}
----
public class LCASample {
public static void main(String[] args) {
Node n1 = new Node(1);
Node n2 = new Node(n1, 2);
Node n3 = new Node(n1, 3);
Node n4 = new Node(n2, 4);
Node n5 = new Node(n2, 5);
Node n6 = new Node(n4, 6);
Node n7 = new Node(n5, 7);
Node n8 = new Node(n5, 8);
Node n9 = new Node(n8, 9);
System.out.println(n6.lcs(n9).getValue());
}
}