abhishek08aug
BAN USERThen where is 'D'?
- abhishek08aug April 29, 2015package in.blogspot.randomcompiler;
class TreeNode {
int data;
TreeNode left;
TreeNode right;
}
public class CheckBST {
public static void main(String[] args) {
TreeNode n1 = new TreeNode();
n1.data = 100;
TreeNode n2 = new TreeNode();
n2.data = 75;
n1.left = n2;
TreeNode n3 = new TreeNode();
n3.data = 125;
n1.right = n3;
TreeNode n4 = new TreeNode();
n4.data = 50;
n2.left = n4;
TreeNode n5 = new TreeNode();
n5.data = 90;
n2.right = n5;
System.out.println(isBST(n1));
}
private static boolean isBST(TreeNode root) {
if(root == null) return true;
boolean isBSTLeft = isBST(root.left);
boolean isBSTRight = isBST(root.right);
boolean gtLeft = root.left == null? true : root.data >= root.left.data;
boolean ltRight = root.right == null? true : root.data < root.right.data;
return isBSTLeft && isBSTRight && gtLeft && ltRight;
}
}
Output:
true
I believe it could be solved using greedy strategy.
- abhishek08aug April 29, 2015package in.blogspot.randomcompiler;
class Node {
int data;
Node next;
}
public class ReversePairs {
public static void main(String[] args) {
Node node = new Node();
node.data = 1;
Node head = node;
for(int i=2; i<=101; i++) {
Node temp = new Node();
temp.data = i;
node.next = temp;
node=temp;
}
printNodes(head);
head = reversePairs(head);
printNodes(head);
}
private static Node reversePairs(Node head) {
if(head == null || head.next == null) {
return head;
}
Node headNextNext = head.next.next;
head.next.next = head;
Node newHeadNext = reversePairs(headNextNext);
Node newHead = head.next;
head.next = newHeadNext;
return newHead;
}
private static void printNodes(Node head) {
while(head != null) {
System.out.print(head.data + " -> ");
head = head.next;
}
System.out.print("null");
System.out.println();
}
}
Output:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 -> 18 -> 19 -> 20 -> 21 -> 22 -> 23 -> 24 -> 25 -> 26 -> 27 -> 28 -> 29 -> 30 -> 31 -> 32 -> 33 -> 34 -> 35 -> 36 -> 37 -> 38 -> 39 -> 40 -> 41 -> 42 -> 43 -> 44 -> 45 -> 46 -> 47 -> 48 -> 49 -> 50 -> 51 -> 52 -> 53 -> 54 -> 55 -> 56 -> 57 -> 58 -> 59 -> 60 -> 61 -> 62 -> 63 -> 64 -> 65 -> 66 -> 67 -> 68 -> 69 -> 70 -> 71 -> 72 -> 73 -> 74 -> 75 -> 76 -> 77 -> 78 -> 79 -> 80 -> 81 -> 82 -> 83 -> 84 -> 85 -> 86 -> 87 -> 88 -> 89 -> 90 -> 91 -> 92 -> 93 -> 94 -> 95 -> 96 -> 97 -> 98 -> 99 -> 100 -> 101 -> null
2 -> 1 -> 4 -> 3 -> 6 -> 5 -> 8 -> 7 -> 10 -> 9 -> 12 -> 11 -> 14 -> 13 -> 16 -> 15 -> 18 -> 17 -> 20 -> 19 -> 22 -> 21 -> 24 -> 23 -> 26 -> 25 -> 28 -> 27 -> 30 -> 29 -> 32 -> 31 -> 34 -> 33 -> 36 -> 35 -> 38 -> 37 -> 40 -> 39 -> 42 -> 41 -> 44 -> 43 -> 46 -> 45 -> 48 -> 47 -> 50 -> 49 -> 52 -> 51 -> 54 -> 53 -> 56 -> 55 -> 58 -> 57 -> 60 -> 59 -> 62 -> 61 -> 64 -> 63 -> 66 -> 65 -> 68 -> 67 -> 70 -> 69 -> 72 -> 71 -> 74 -> 73 -> 76 -> 75 -> 78 -> 77 -> 80 -> 79 -> 82 -> 81 -> 84 -> 83 -> 86 -> 85 -> 88 -> 87 -> 90 -> 89 -> 92 -> 91 -> 94 -> 93 -> 96 -> 95 -> 98 -> 97 -> 100 -> 99 -> 101 -> null
return Math.max(maxStep(currentStep, totalMoves, brokenStep, currentMove+1), maxStep(currentStep+currentMove, totalMoves, brokenStep, currentMove+1));
First part is for the case when no step is taken. Steps are not taken when
1) You end up stepping on the broken step.
2) Not taking some particular step could help you taking a later longer step
Here is the working code and output:
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
private int maxStep(int currentStep, int totalMoves, int brokenStep, int currentMove) {
if(totalMoves == 0) {
return currentStep;
}
if(currentMove > totalMoves) {
return currentStep;
}
if(currentStep + currentMove == brokenStep)
return maxStep(currentStep, totalMoves, brokenStep, currentMove+1);
else
return Math.max(maxStep(currentStep, totalMoves, brokenStep, currentMove+1), maxStep(currentStep+currentMove, totalMoves, brokenStep, currentMove+1));
}
public static void main (String[] args) throws java.lang.Exception {
Ideone one = new Ideone();
System.out.println(one.maxStep(0, 4, 10, 1));
System.out.println(one.maxStep(0, 3, 1, 1));
System.out.println(one.maxStep(0, 3, 2, 1));
}
}
Success time: 0.09 memory: 320320 signal:0
9
5
6
Consider the case with n=4 and k=10.
Your solution will give: 1+2+3+0=6.
However the correct solution is: 0+2+3+4=9.
Guys this is simple. Just keep a pointer to the internally transferred location in the actual token locations.
- abhishek08aug May 01, 2015