Project 1
Project 1:
EQUILIBRIUM POINT
package equilibriumpoint;
public class EquilibriumPoint {
int equilibrium(int arr[], int n)
{
int i, j;
int leftsum, rightsum;
for (i = 0; i < n; ++i) {
leftsum = 0;
for (j = 0; j < i; j++)
leftsum += arr[j];
rightsum = 0;
for (j = i + 1; j < n; j++)
rightsum += arr[j];
if (leftsum == rightsum)
return i;
}
return 1;
}
public static void main(String[] args)
{
EquilibriumPoint equi = new EquilibriumPoint();
int arr[] = { 1,3,5,2,2 };
int arr_size = arr.length;
System.out.println(equi.equilibrium(arr, arr_size));
}
}
2)package equilibriumpoint;
public class EquilibriumPoint {
int equilibrium(int arr[], int n)
{
int i, j;
int leftsum, rightsum;
for (i = 0; i < n; ++i) {
leftsum = 0;
for (j = 0; j < i; j++)
leftsum += arr[j];
rightsum = 0;
for (j = i + 1; j < n; j++)
rightsum += arr[j];
if (leftsum == rightsum)
return i;
}
return 1;
}
public static void main(String[] args)
{
EquilibriumPoint equi = new EquilibriumPoint();
int arr[] = {1};
int arr_size = arr.length;
System.out.println(equi.equilibrium(arr, arr_size));
}
}
LEADERS IN AN ARRAY
package leaderinarray;
public class LeadersInArray {
void printLeaders(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
int j;
for (j = i + 1; j < size; j++)
{
if (arr[i] <=arr[j])
break;
}
if (j == size)
System.out.print(arr[i] + " ");
}
}
public static void main(String[] args)
{
LeadersInArray lead = new LeadersInArray();
int arr[] = new int[]{16, 17, 4, 3, 5, 2};
int n = arr.length;
lead.printLeaders(arr, n);
}
}
2)package leaderinarray;
public class LeadersInArray {
void printLeaders(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
int j;
for (j = i + 1; j < size; j++)
{
if (arr[i] <=arr[j])
break;
}
if (j == size)
System.out.print(arr[i] + " ");
}
}
public static void main(String[] args)
{
LeadersInArray lead = new LeadersInArray();
int arr[] = new int[]{1, 2,3, 4, 0};
int n = arr.length;
lead.printLeaders(arr, n);
}
}
REVERSE WORDS IN A GIVEN STRING
public class REVERSEWORDSINAGIVENSTRING {
static void reverse(char str[], int start, int end)
{
char temp;
while (start <= end) {
temp = str[start];
str[start] = str[end];
str[end] = temp;
start++;
end--;
}
}
static char[] reverseWords(char[] s)
{
int start = 0;
for (int end = 0; end < s.length; end++) {
if (s[end] == ' ') {
reverse(s, start, end);
start = end + 1;
}
}
reverse(s, start, s.length - 1);
reverse(s, 0, s.length - 1);
return s;
}
public static void main(String[] args)
{
String s = "i like this program very much ";
char[] p = reverseWords(s.toCharArray());
System.out.print(p);
}
}
2)public class REVERSEWORDSINAGIVENSTRING {
static void reverse(char str[], int start, int end)
{
char temp;
while (start <= end) {
temp = str[start];
str[start] = str[end];
str[end] = temp;
start++;
end--;
}
}
static char[] reverseWords(char[] s)
{
int start = 0;
for (int end = 0; end < s.length; end++) {
if (s[end] == ' ') {
reverse(s, start, end);
start = end + 1;
}
}
reverse(s, start, s.length - 1);
reverse(s, 0, s.length - 1);
return s;
}
public static void main(String[] args)
{
String s = "pqr.mno ";
char[] p = reverseWords(s.toCharArray());
System.out.print(p);
}
}
REMOVE DUPLICATES
package removeduplicates;
import java.util.Arrays;
public class RemoveDuplicates {
static String removeDuplicate(char str[], int n)
{
int index = 0;
for (int i = 0; i < n; i++)
{
int j;
for (j = 0; j < i; j++)
{
if (str[i] == str[j])
{
break;
}
}
if (j == i)
{
str[index++] = str[i];
}
}
return String.valueOf(Arrays.copyOf(str, index));
}
public static void main(String[] args)
{
char str[]="skilllync".toCharArray();
int n = str.length;
System.out.println(removeDuplicate(str, n));
}
}
2)package removeduplicates;
import java.util.Arrays;
public class RemoveDuplicates {
static String removeDuplicate(char str[], int n)
{
int index = 0;
for (int i = 0; i < n; i++)
{
int j;
for (j = 0; j < i; j++)
{
if (str[i] == str[j])
{
break;
}
}
if (j == i)
{
str[index++] = str[i];
}
}
return String.valueOf(Arrays.copyOf(str, index));
}
public static void main(String[] args)
{
char str[]="skill lync course".toCharArray();
int n = str.length;
System.out.println(removeDuplicate(str, n));
}
}
REVERSE A LINKED LIST
public class LinkedList {
static Node head;
static class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
Node reverse(Node node)
{
Node prev = null;
Node current = node;
Node next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
node = prev;
return node;
}
void printList(Node node)
{
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
public static void main(String[] args)
{
LinkedList list = new LinkedList();
LinkedList.head = new Node(6);
LinkedList.head.next = new Node(5);
LinkedList.head.next.next = new Node(4);
LinkedList.head.next.next.next = new Node(3);
LinkedList.head.next.next.next = new Node(2);
LinkedList.head.next.next.next = new Node(1);
System.out.println("Given linked list");
list.printList(head);
head = list.reverse(head);
System.out.println("");
System.out.println("Reversed linked list ");
list.printList(head);
}
}
PAIRWISE SWAP ELEMENTS OF A LINKED LIST
package pairwiseswap;
public class PairwiseSwap {
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
void pairWiseSwap()
{
Node head = null;
Node temp = head;
while (temp != null && temp.next != null) {
int k = temp.data;
temp.data = temp.next.data;
temp.next.data = k;
temp = temp.next.next;
}
}
public void push(int new_data)
{
Node new_node = new Node(new_data);
Node head = null;
new_node.next = head;
head = new_node;
}
void printList()
{
Node head = null;
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
public static void main(String args[])
{
PairwiseSwap llist = new PairwiseSwap();
llist.push(1);
llist.push(2);
llist.push(2);
llist.push(4);
llist.push(5);
llist.push(6);
llist.push(7);
llist.push(8);
System.out.println("Linked List before calling pairWiseSwap() ");
llist.printList();
llist.pairWiseSwap();
System.out.println("Linked List after calling pairWiseSwap() ");
llist.printList();
}
}
ADD TWO NUMBERS REPRESENTED BY LINKED LISTS
public class AddTwoList {
static Node head1, head2;
static class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
void addTwoLists(Node first, Node second) {
Node start1 = new Node(0);
start1.next = first;
Node start2 = new Node(0);
start2.next = second;
addPrecedingZeros(start1, start2);
Node result = new Node(0);
if (sumTwoNodes(start1.next, start2.next, result) == 1) {
Node node = new Node(1);
node.next = result.next;
result.next = node;
}
printList(result.next);
}
private int sumTwoNodes(Node first, Node second, Node result) {
if (first == null) {
return 0;
}
int number = first.data + second.data + sumTwoNodes(first.next, second.next, result);
Node node = new Node(number % 10);
node.next = result.next;
result.next = node;
return number / 10;
}
private void addPrecedingZeros(Node start1, Node start2) {
Node next1 = start1.next;
Node next2 = start2.next;
while (next1 != null && next2 != null) {
next1 = next1.next;
next2 = next2.next;
}
if (next1 == null && next2 != null) {
while (next2 != null) {
Node node = new Node(0);
node.next = start1.next;
start1.next = node;
next2 = next2.next;
}
} else if (next2 == null && next1 != null) {
while (next1 != null) {
Node node = new Node(0);
node.next = start2.next;
start2.next = node;
next1 = next1.next;
}
}
}
void printList(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
System.out.println("");
}
public static void main(String[] args) {
AddTwoList list = new AddTwoList();
list.head1 = new Node(6);
list.head1.next = new Node(3);
System.out.print("First list is ");
list.printList(head1);
list.head1.next.next = new Node(7);
System.out.print("Second list is ");
list.printList(head2);
System.out.print("Resultant list is ");
list.addTwoLists(head1, head2);
}
}
BINARY TREE TO DLL
public class Binary {
int data;
Node left, right;
public void Node(int data)
{
this.data = data;
left = right = null;
}
}
class BinaryTree
{
BinaryTree root;
BinaryTree head;
private BinaryTree left;
private BinaryTree right;
private String data;
static BinaryTree prev = null;
public BinaryTree(int i) {
}
void BinaryTree2DoubleLinkedList(BinaryTree root2)
{
if (root2 == null)
return;
BinaryTree2DoubleLinkedList(root2.left);
if (prev == null)
head = root2;
else
{
root2.left = prev;
prev.right = root2;
}
prev = root2;
BinaryTree2DoubleLinkedList(root2.right);
}
void printList(BinaryTree head2)
{
while (head2 != null)
{
System.out.print(head2.data + " ");
head2 = head2.right;
}
}
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree(10);
tree.root = new BinaryTree(12);
tree.root.left = new BinaryTree(25);
tree.root.right = new BinaryTree(30);
tree.root.left.left = new BinaryTree(15);
tree.root.left.right = new BinaryTree(36);
tree.BinaryTree2DoubleLinkedList(tree.root);
tree.printList(tree.head);
}
}
BELLMAN FORD ALGORITHM
public class GFG1 {
static void BellmanFord(int graph[][], int V, int E,
int src)
{
int []dis = new int[V];
for (int i = 0; i < V; i++)
dis[i] = Integer.MAX_VALUE;
dis[src] = 0;
for (int i = 0; i < V - 1; i++)
{
for (int j = 0; j < E; j++)
{
if (dis[graph[j][0]] != Integer.MAX_VALUE && dis[graph[j][0]] + graph[j][2] <
dis[graph[j][1]])
dis[graph[j][1]] =
dis[graph[j][0]] + graph[j][2];
}
}
for (int i = 0; i < E; i++)
{
int x = graph[i][0];
int y = graph[i][1];
int weight = graph[i][2];
if (dis[x] != Integer.MAX_VALUE &&
dis[x] + weight < dis[y])
System.out.println("Graph contains negative"
+" weight cycle");
}
System.out.println("Vertex Distance from Source");
for (int i = 0; i < V; i++)
System.out.println(i + "\t\t" + dis[i]);
}
public static void main(String[] args)
{
int V = 5;
int E = 8;
int graph[][] = { { 0, 1, -1 }, { 0, 2, 4 },
{ 1, 2, 3 }, { 1, 3, 2 },
{ 1, 4, 2 }, { 3, 2, 5 },
{ 3, 1, 1 }, { 4, 3, -3 } };
BellmanFord(graph, V, E, 0);
}
}
MINIMUM SWAPS TO SORT
package swaps;
import java.io.*;
import java.util.*;
public class Swaps {
public static int minSwaps(int[] nums)
{
int len = nums.length;
HashMap
for (int i = 0; i < len; i++)
map.put(nums[i], i);
Arrays.sort(nums);
boolean[] visited = new boolean[len];
Arrays.fill(visited, false);
int ans = 0;
for (int i = 0; i < len; i++) {
if (visited[i] || map.get(nums[i]) == i)
continue;
int j = i, cycle_size = 0;
while (!visited[j]) {
visited[j] = true;
j = map.get(nums[j]);
cycle_size++;
}
if (cycle_size > 0) {
ans += (cycle_size - 1);
}
}
return ans;
}
}
class MinSwaps {
public static void main(String[] args)
{
int[] a = { 8, 9, 16, 12 };
Swaps g = new Swaps();
System.out.println(g.minSwaps(a));
}
}
2)package swaps;
import java.io.*;
import java.util.*;
public class Swaps {
public static int minSwaps(int[] nums)
{
int len = nums.length;
HashMap
for (int i = 0; i < len; i++)
map.put(nums[i], i);
Arrays.sort(nums);
boolean[] visited = new boolean[len];
Arrays.fill(visited, false);
int ans = 0;
for (int i = 0; i < len; i++) {
if (visited[i] || map.get(nums[i]) == i)
continue;
int j = i, cycle_size = 0;
while (!visited[j]) {
visited[j] = true;
j = map.get(nums[j]);
cycle_size++;
}
if (cycle_size > 0) {
ans += (cycle_size - 1);
}
}
return ans;
}
}
class MinSwaps {
public static void main(String[] args)
{
int[] a = { 1,5,4,3,2 };
Swaps g = new Swaps();
System.out.println(g.minSwaps(a));
}
}
GET MINIMUM ELEMENT FROM STACK
package MyStack;
import java.util.*;
public class MyStack {
Main s;
Integer minEle;
MyStack() { Main s = new Main(); }
void getMin()
{
MyStack s = null;
if (s.isEmpty())
System.out.println("Stack is empty");
else
System.out.println("Minimum Element in the "
+ " stack is: " + minEle);
}
Integer peek()
{
MyStack s = null;
if (s.isEmpty()) {
System.out.println("Stack is empty ");
return minEle;
}
Integer t = s.peek(); // Top element.
System.out.print("Top Most Element is: ");
if (t < minEle)
System.out.println(minEle);
else
System.out.println(t);
return t;
}
Integer pop()
{
MyStack s = null;
if (s.isEmpty()) {
System.out.println("Stack is empty");
return minEle;
}
System.out.print("Top Most Element Removed: ");
Integer t = s.pop();
if (t < minEle) {
System.out.println(minEle);
minEle = 2 * minEle - t;
}
else
System.out.println(t);
return t;
}
void push(Integer x)
{
MyStack s = null;
if (s.isEmpty()) {
minEle = x;
s.push(x);
System.out.println("Number Inserted: " + x);
return;
}
if (x < minEle) {
s.push(2 * x - minEle);
minEle = x;
}
else
s.push(x);
System.out.println("Number Inserted: " + x);
}
private boolean isEmpty() {
return false;
}
};
public class Main {
public static void main(String[] args)
{
MyStack s = new MyStack();
s.push(2);
s.push(3);
s.getMin();
s.push(1);
s.getMin();
s.pop();
s.getMin();
s.pop();
s.peek();
}
}