devball
BAN USERThis is an example of dynamic programming:
Here is the code for this
import java.util.Scanner;
public class FindMaxSubSeq
{
int arraySize;
int arr[];
int sarr[];
public FindMaxSubSeq()
{
Scanner s = new Scanner(System.in);
System.out.println("Enter array size : ");
arraySize = s.nextInt();
System.out.println("Enter the elements : ");
int i=0;
sarr = new int[arraySize];
arr = new int[arraySize];
while(i<arraySize)
{
arr[i] = s.nextInt();
i++;
}
}
public void findTheSequence()
{
int i=0;
while(i < arraySize)
{
if(i==0)
{
sarr[0] = arr[0];
}
else
{
sarr[i] = Math.max(arr[i], sarr[i-1] + arr[i]);
}
i++;
}
//Now evaluate the max we just found
int k=0; int max = sarr[k];int max_index = 0;
while(k<arraySize)
{
if(sarr[k] > max)
{
max = sarr[k];
max_index = k;
}
k++;
}
//we found the max, just traverse backwards
int z = max_index;
int start = max_index;
int end = max_index;
int sumTillNow = 0;
while (z >= 0)
{
sumTillNow = sumTillNow + arr[z];
if(sumTillNow == max)
{
System.out.println(" The start index : " +end+ " The end index : " +start+ " The sum is : " + max);
return;
}
z--;
end--;
}
}
public static void main(String args[])
{
FindMaxSubSeq s = new FindMaxSubSeq();
s.findTheSequence();
}
}
Do BFS and keep track of the queue continuously, to figure out if the Target has now been available in the queue. If yes, then find the parent of the target in the queue by continuously dequeing so that the right sibling where ever it is (under same parent of target or different parent) is achieved. Level needs to be tracked because if the target is right most sibling, then the right sibling of it wont exist
public class Node {
int value;
public Node left;
public Node right;
public Node(int value) {
this.value = value;
left = null;
right = null;
}
}
import java.util.Scanner;
public class BinaryTree
{
Node root;
BinaryTree()
{
root = null;
}
void insert(int value,int id)
{
Node n = new Node(value);
if(root == null)
{
root = n;
return;
}
Node parent = this.find(root,id/2);
if(id%2==0)
{
parent.left = n;
}
else
parent.right = n;
return;
}
public Node find(Node root, int parent)
{
if (parent==1)
return root;
int level = 1;
int arr[] = new int[100];
int i= parent;
arr[level] = i;
level++;
while(i>;1){
i = i/2;
arr[level] = i;
level++;
}
arr[level] = 10101010;
Node temp = root;
for (int j=level-2;j>;0;j--)
{
if(arr[j]%2 == 0)
{
//take a left
temp = temp.left;
}
else
{
//take a right;
temp = temp.right;
}
}
return temp;
}
public void buildBinaryTree()
{
System.out.println("Enter the number of nodes");
Scanner s = new Scanner(System.in);
int number = s.nextInt();
for(int i=0;i<number;i++)
{
System.out.println("Enter Node Value");
int value = s.nextInt();
System.out.println("Enter Node ID");
int id = s.nextInt();
insert(value,id);
}
}
public Node findInorder(Node root, int value)
{
Node temp = root;
if(temp == null)
return null;
if(temp.value == value)
{
return temp;
}
Node s = findInorder(temp.left,value);
if(s!=null)
return s;
Node t = findInorder(temp.right,value);
if(t !=null)
return t;
// TODO Auto-generated method stub
return null;
}
public void performInorderTraversal(Node temp)
{
if(temp == null)
return;
performInorderTraversal(temp.left);
System.out.println(temp.value);
performInorderTraversal(temp.right);
}
}
public class QNode
{
int value;
int level;
QNode next;
QNode(int value)
{
this.value = value;
this.next = null;
this.level = 0;
}
}
public class Queue
{
QNode front;
QNode rear;
Queue()
{
front = null;
rear = null;
}
public void enqueue(QNode n)
{
if(front == null)
{
front = rear = n;
return;
}
n.next = front;
front = n;
}
public QNode dequeue()
{
if(front == rear)
{
QNode temp = front;
front = null;
rear = null;
return temp;
}
QNode temp = front;
while(temp != null && temp.next!=rear)
{
temp = temp.next;
}
QNode rtemp = rear;
rear = temp;
rear.next = null;
return rtemp;
}
public boolean elementPresent(int val)
{
QNode temp = front;
while(temp != null)
{
if(temp.value == val)
return true;
temp = temp.next;
}
// TODO Auto-generated method stub
return false;
}
public boolean elementAtFront(int val)
{
if(front.value == val)
return true;
return false;
}
}
import java.util.Scanner;
public class BTreeMain {
public static void main(String[] args)
{
// TODO Auto-generated method stub
BinaryTree b = new BinaryTree();
b.buildBinaryTree();
b.performInorderTraversal(b.root);;
Scanner s = new Scanner(System.in);
System.out.println("Enter the sibling value");
int sibValue = s.nextInt();
Node sibling = b.findInorder(b.root, sibValue);
int x = findNextSibling(b,sibling);
System.out.println("The sibling is : " + x);
}
private static int findNextSibling(BinaryTree b, Node sibling)
{
// TODO Auto-generated method stub
//Perform Breadth first traversal
if(sibling == b.root)
{
System.out.println("No sibling for the root");
return -1;
}
Queue q = new Queue();
QNode r = new QNode(b.root.value);
q.enqueue(r);
r.level = 1;
while(q.front != null)
{
QNode y = q.dequeue();
//find using inorder traversal
Node y1 = b.findInorder(b.root,y.value);
Node left = y1.left;
Node right = y1.right;
QNode qleft = null;
QNode qright = null;
if(left != null)
qleft = new QNode(left.value);
if(right != null)
qright = new QNode(right.value);
if(qleft != null)
{
q.enqueue(qleft);
qleft.level = y.level + 1;
}
if(qright != null)
{
q.enqueue(qright);
qright.level = y.level+1;
}
if(q.elementPresent(sibling.value) && !q.elementAtFront(sibling.value))
{
// This implies the sibling is somewhere in the queue
//now keep dequeing the queue to remove x + 1 element
QNode dequeued = null;
while(q.front != null)
{
//keep doing this
dequeued = q.dequeue();
if(dequeued.value == sibling.value)
{
break;
}
}
int l = dequeued.level;
QNode rightSib = q.dequeue();
if(rightSib.level == l)
{
return rightSib.value;
}
else
{
System.out.println("Node is at extreme right cant have sibling");
}
}
}
System.out.println("No sibling exists");
return -1;
}
}
CONSOLE OUTPUTS:
===================
Enter the number of nodes
3
Enter Node Value
1
1Enter Node ID
Enter Node Value
2
Enter Node ID
2
Enter Node Value
3
Enter Node ID
3
2
1
3
Enter the sibling value
3
No sibling exists
The sibling is : -1
==================
Enter the number of nodes
9
Enter Node Value
1
Enter Node ID
1
Enter Node Value
2
Enter Node ID
2
Enter Node Value
4
Enter Node ID
4
Enter Node Value
8
Enter Node ID
8
Enter Node Value
17
Enter Node ID
17
Enter Node Value
3
Enter Node ID
3
Enter Node Value
7
Enter Node ID
7
Enter Node Value
14
Enter Node ID
14
Enter Node Value
29
Enter Node ID
29
8
17
4
2
1
3
14
29
7
Enter the sibling value
8
The sibling is : 14
public class Matgame {
public static void main(String[] args)
{
// TODO Auto-generated method stub
Matrix matrix = new Matrix();
matrix.printTheMatrixValues();
matrix.findThePath(matrix.mat[0][0]);
matrix.printSuccessPath();
}
}
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;
public class Matrix
{
int rows;
int columns;
ArrayList<Node>successPath = new ArrayList<Node>();
Node mat[][];
void enterRowsAndColumns()
{
Scanner input = new Scanner(System.in);
System.out.println("Enter the rows of the matrix : \n");
this.rows = input.nextInt();
System.out.println("Enter the columns of the matrix : \n");
this.columns = input.nextInt();
}
Matrix()
{
enterRowsAndColumns();
this.mat = new Node[this.rows][this.columns];
buildMatrixWithUserInput();
}
public void printSuccessPath(){
int i=0;
System.out.println("\nSuccess path is:");
while(i < this.successPath.size())
{
System.out.println(this.successPath.get(i).id);
i++;
}
}
private void buildMatrixWithUserInput()
{
System.out.println("Enter the values in the matrix\n");
// TODO Auto-generated method stub
Scanner input = new Scanner(System.in);
for(int i=0;i<this.rows;i++)
for(int j=0;j<this.columns;j++)
{
int num = input.nextInt();
mat[i][j] = new Node(num, i*rows + j, i, j, false);
}
}
void printTheMatrixValues()
{
System.out.println("\n");
for(int i=0;i<this.rows;i++)
{
System.out.println("\n");
for(int j=0;j<this.columns;j++)
{
System.out.print(this.mat[i][j].value + " ");
}
}
}
void printTheMatrixIDs()
{
System.out.println("\n");
for(int i=0;i<this.rows;i++)
{
System.out.println("\n");
for(int j=0;j<this.columns;j++)
{
System.out.print(this.mat[i][j].id + " ");
}
}
}
public boolean findThePath(Node n) {
// TODO Auto-generated method stub
//Perform the first node check
if(n.x==0 && n.y==0)
{
//this is the first node, check if we can start from here
if(n.value==0)
{
this.successPath.add(n);
}
else
{
System.out.println("No path exists");
return false;
}
}
//Perform the last node check
if(n.x==rows-1 && n.y==columns-1)
{
//This is the last node
if(n.value == 0)
{
boolean flag = false;
//check if the success path contains 2
int i=0;
while(i != this.successPath.size()-1)
{
if(this.successPath.get(i).value == 2)
{
flag = true;
break;
}
i++;
}
if(flag)
return true;
else
return false;
}
}
//Get the node's neighbours
ArrayList<Node> neighbours = new ArrayList<Node>();
neighbours = getNeighboursWith0or2(n);
if (neighbours.size()==0)
{
//System.out.println("Hi: n id : " + n.id);
if(n.id == 0)
{
System.out.println("No success path");
}
return false;
}
for(Node k: neighbours)
{
if(this.successPath.contains(k))
{
continue;
}
this.successPath.add(k);
boolean success = findThePath(k);
if(success)
return true;
else
{
this.successPath.remove(k);
}
}
return false;
}
private ArrayList<Node> getNeighboursWith0or2(Node n)
{
// TODO Auto-generated method stub
ArrayList<Node> neighbours = new ArrayList<Node>();
if(n.id > this.columns)
{
Node up = getNodeWithId(n.id - this.columns);
if(up.value ==0 || up.value == 2)
{
neighbours.add(up);
//System.out.println("ADDED UPPER");
}
}
if(n.id <= (this.rows*this.columns-1) - this.columns)
{
Node down = getNodeWithId(n.id + this.columns);
if(down.value ==0 || down.value == 2)
{
neighbours.add(down);
//System.out.println("ADDED DOWN");
}
}
if(n.id % this.columns != 0)
{
Node left = getNodeWithId(n.id - 1);
if(left.value == 0 || left.value == 2)
{
neighbours.add(left);
//System.out.println("ADDED LEFT");
}
}
if((n.id+1) % this.columns != 0)
{
Node right = getNodeWithId(n.id + 1);
if(right.value ==0 || right.value == 2)
{
neighbours.add(right);
//System.out.println("ADDED RIGHT");
}
}
//System.out.println(neighbours.size());
return neighbours;
}
private Node getNodeWithId(int id)
{
int col = id % (this.columns);
int row = id / this.columns;
return this.mat[row][col];
}
}
public class Node
{
int value;
int id;
int x;
int y;
boolean visited;
Node(int value, int id, int x, int y, boolean visited)
{
this.value = value;
this.id = id;
this.x = x;
this.y = y;
this.visited = visited;
}
}
CONSOLE:
Enter the rows of the matrix :
6
Enter the columns of the matrix :
6
Enter the values in the matrix
0
0
2
1
1
1
1
1
0
1
1
1
1
1
0
1
1
1
1
0
0
1
1
1
1
0
1
1
0
0
1
0
0
0
0
0
0 0 2 1 1 1
1 1 0 1 1 1
1 1 0 1 1 1
1 0 0 1 1 1
1 0 1 1 0 0
1 0 0 0 0 0
Success path is:
0
1
2
8
14
20
19
25
31
32
33
34
28
29
35
RepNinaHedge, Android Engineer at ABC TECH SUPPORT
Hello, I am a Book writer who uses their content creation and verbal skills to produce articles, blogs or professional ...
Reprrobertgregory, Nursing aide at Road Runner Lawn Services
I am working as a Nursing Assistant . My duties include helping patients to bathe and get dressed, repositioning wheelchairs etc ...
Repaaronfreunda, Human resources coordinator at Prestiga-Biz
Aaron , My work is to facilitate daily HR functions like track of employees records and supporting the interview process. I ...
RepEileenBaker, Applications Developer at ABC TECH SUPPORT
I am an experienced and dedicated professional with a track record of effective mentorship. Nowaday most people search for Ambani ...
Repmorganswitzer8475, Android test engineer at ABC TECH SUPPORT
Hey, I'm Morgan switzer and i am a sociologist. I also like to read some interesting books like get ...
Reproseljannet75, Financial Software Developer at Abs india pvt. ltd.
Je suis jannet , une conseillère en voyages qui conseille les clients sur les options de voyage et les voyages organisés ...
RepDavidTBevins, Apple Phone Number available 24/7 for our Customers at AMD
Hi am working as a writer and i wrote many books.Mostly i write books related to Magic and my ...
Repmargaratlonger, Talent Acquisition at Huawei
Hello, I am Margaret . I have been working with the company of Heilig-Meyers for the last 7 year. I guide ...
RepRafaelLisa, Librarian at Cut Above
I am a librarian . responsible for selecting, organizing, and delivering information materials in a variety of formats such as electronic ...
RepNoelleBurgess, Ticket clerk at Handyman
As a Ticket Clerk with a penchant for the exhilarating world of cricket, my professional journey harmoniously blends the meticulousness ...
O(nlogn)
Sort first, then swap elements from 1...n-2 [a(0-n-1)] array
CONSOLE:
- devball December 24, 2013=========
Enter the size
20
Enter values
2
5
4
3
1
8
7
9
34
56
71
12
28
90
76
43
31
98
67
76
The less great sort array is :
1
3
2
5
4
8
7
12
9
31
28
43
34
67
56
76
71
90
76
98