lokesh.kmr.mishra
BAN USERpublic static int getNumberOfSquareBySize(int size, int noHLine, List<Segment> brokenSegment, int count) {
for (int i = 1; i < noHLine; i++) {
for (int j = 1; j < noHLine; j++) {
boolean isUnbrokenSquare = false;
if (j + size-1 < noHLine && i + size-1 < noHLine) {
for (int k = 0; k < size; k++) {
// check for 1st horizontal line for length k
if (brokenSegment.contains(new Segment('H', i, j + k))) {
isUnbrokenSquare = true;
break;
}
if (brokenSegment.contains(new Segment('V', j, i + k))) {
isUnbrokenSquare = true;
break;
}
}
if (!isUnbrokenSquare) {
for (int k = 0; k < size; k++) {
if (brokenSegment.contains(new Segment('H', size + i, j + k))) {
isUnbrokenSquare = true;
break;
}
if (brokenSegment.contains(new Segment('V', j + size, i + k))) {
isUnbrokenSquare = true;
break;
}
}
}
if (!isUnbrokenSquare) {
count++;
}
}
}
}
return count;
}
static class Segment {
char segmentType;
int hLength;
int vLength;
public Segment(char segmentType, int hLength, int vLength) {
super();
this.segmentType = segmentType;
this.hLength = hLength;
this.vLength = vLength;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj instanceof Segment) {
Segment s = (Segment) obj;
if (this.segmentType == s.segmentType && this.hLength == s.hLength && this.vLength == s.vLength) {
return true;
}
}
return false;
}
}
public class FindMaxPathInTree {
public static class Node {
public Node left;
public Node right;
public int data;
public Node(int data) {
super();
this.data = data;
}
}
public static void main(String[] args) {
/*Node node = new Node(9);
node.left = new Node(-2);
node.right = new Node(7);
node.left.left = new Node(5);
node.left.right = new Node(3);
node.left.left.left = new Node(1);
node.left.left.right = new Node(4);
node.left.right = new Node(3);
node.right.left = new Node(2);
node.right.right = new Node(9);
node.right.right.left = new Node(7);
node.right.right.left.left = new Node(2);
node.right.right.left.right = new Node(9);
StringBuilder result = new StringBuilder();*/
Node node = new Node(-1);
node.left = new Node(-2);
node.right = new Node(3);
node.right.right = new Node(-1);
StringBuilder result = new StringBuilder();
findMaxPathInTree(node, new Sum(),result, new StringBuilder());
System.out.println(result.toString());
}
private static class Sum {
int sum;
}
public static int findMaxPathInTree(Node node, Sum sum, StringBuilder maxPath, StringBuilder currPath) {
int currentSum = 0;
if (node == null) {
return 0;
} else if (node.left == null && node.right == null) {
if (sum.sum < node.data) {
sum.sum = node.data;
maxPath.delete(0, maxPath.length());
maxPath.append("" + node.data);
}
currPath.delete(0, currPath.length());
currPath.append("" + node.data);
currentSum = node.data;
} else {
int leftSum = findMaxPathInTree(node.left, sum, maxPath, currPath);
String leftSumPath = currPath.toString();
currPath.delete(0, currPath.length());
int rightSum = findMaxPathInTree(node.right, sum, maxPath, currPath);
String rightSumPath = currPath.reverse().toString();
currPath.delete(0, currPath.length());
// find current sum including left subtree, right subtree, and current node
if (leftSum + node.data > node.data) {
int tempSum = node.data + leftSum;
if (node.data + rightSum > node.data) {
// append all three for finding tempSum
tempSum += rightSum;
if (tempSum > sum.sum) {
sum.sum = tempSum;
maxPath.delete(0, maxPath.length());
maxPath.append("" + leftSumPath + node.data + rightSumPath);
}
if (leftSum > rightSum) {
currPath.append(leftSumPath + node.data);
currentSum = leftSum + node.data;
} else {
currPath.append(rightSumPath + "" + node.data);
currentSum = rightSum + node.data;
}
} else {
currentSum = leftSum + node.data;
currPath.append("" + leftSumPath + "" + node.data);
}
}
else if (rightSum + node.data > node.data) {
int tempSum = node.data + rightSum;
if (node.data + leftSum > node.data) {
// append all three for finding tempSum
tempSum += leftSum;
if (tempSum > sum.sum) {
sum.sum = tempSum;
maxPath.delete(0, maxPath.length());
maxPath.append("" + leftSumPath + node.data + rightSumPath);
}
if (leftSum > rightSum) {
currPath.append(leftSumPath + node.data);
currentSum = leftSum + node.data;
} else {
currPath.append(rightSumPath + "" + node.data);
currentSum = rightSum + node.data;
}
} else {
currentSum = rightSum + node.data;
currPath.append("" + rightSumPath + "" + node.data);
}
} else {
if (node.data > sum.sum) {
maxPath.delete(0, maxPath.length());
maxPath.append("" + node.data);
currPath.append("" + node.data);
currentSum = node.data;
}
}
}
return currentSum;
}
}
- lokesh.kmr.mishra February 07, 2018