maverick
BAN USERimport java.util.*;
import java.lang.Math;
public class EditDistance
{
// This problem is also called the Levenshtein distance problem
// To edit the strings, basic operations needed are < 1. Insert; 2. Delete 3. Replace >
// Lets define E(x[1...i], y[1...j]) as the matrix which keeps track of the
// number of opertation that needs to be performed to make the change
// Base cases:
// 1. E(0,0) = 0 ( nothing changed)
// 2. E(1,0) = 1 ( replace or delete a character in x, nothing changes in y)
// So, if the same operating is done for 'k' indexes, edit distance would be 'k'. E(k,0) = k or E(0,k) = k
// E(i,j) : defined as edit distance to make all values from x[1...i] to look like y[1...j] or vice-versa
// E(i,j) = mininum {
// (1+ E(i-1,j)),
// (1+ E(i, j-1)),
// ( s + E(i-1,j-1) ) if x(i) == y(j) s =0: s=1
// }
public static int computeEditDistance(String s1, String s2)
{
int n = s1.length() + 1;
int m = s2.length() + 1;
int [][] e = new int[n][m];
for(int i=0; i<n; i++)
{
e[i][0] = i;
}
for(int j=0; j<m; j++)
{
e[0][j]=j;
}
for( int i=1; i<n; i++){
for(int j=1; j<m; j++)
{
e[i][j] = computeMin( 1 + e[i-1][j] , 1 + e[i][j-1],
e[i-1][j-1] + (s1.charAt(i-1) == s2.charAt(j-1)? 0:1) );
}
}
return e[n-1][m-1];
}
public static int computeMin(int a, int b, int c)
{
return Math.min(Math.min(a,b),c);
}
public static void main(String[] args)
{
// Test cases1
String s1 = "cats";
String s2 = "cat";
int result = computeEditDistance(s1,s2);
System.out.println("Edit Distance:" + result);
// Test Case2
s1 = "cats";
s2 = "cats";
result = computeEditDistance(s1,s2);
System.out.println("Edit Distance:" + result);
//Test Case3
s1 = "cat";
s2 = "networks";
result = computeEditDistance(s1,s2);
System.out.println("Edit Distance:" + result);
}
}
import java.util.*;
import java.lang.Math;
public class EditDistance
{
// This problem is also called the Levenshtein distance problem
// To edit the strings, basic operations needed are < 1. Insert; 2. Delete 3. Replace >
// Lets define E(x[1...i], y[1...j]) as the matrix which keeps track of the
// number of opertation that needs to be performed to make the change
// Base cases:
// 1. E(0,0) = 0 ( nothing changed)
// 2. E(1,0) = 1 ( replace or delete a character in x, nothing changes in y)
// So, if the same operating is done for 'k' indexes, edit distance would be 'k'. E(k,0) = k or E(0,k) = k
// E(i,j) : defined as edit distance to make all values from x[1...i] to look like y[1...j] or vice-versa
// E(i,j) = mininum {
// (1+ E(i-1,j)),
// (1+ E(i, j-1)),
// ( s + E(i-1,j-1) ) if x(i) == y(j) s =0: s=1
// }
public static int computeEditDistance(String s1, String s2)
{
int n = s1.length() + 1;
int m = s2.length() + 1;
int [][] e = new int[n][m];
for(int i=0; i<n; i++)
{
e[i][0] = i;
}
for(int j=0; j<m; j++)
{
e[0][j]=j;
}
for( int i=1; i<n; i++){
for(int j=1; j<m; j++)
{
e[i][j] = computeMin( 1 + e[i-1][j] , 1 + e[i][j-1],
e[i-1][j-1] + (s1.charAt(i-1) == s2.charAt(j-1)? 0:1) );
}
}
return e[n-1][m-1];
}
public static int computeMin(int a, int b, int c)
{
return Math.min(Math.min(a,b),c);
}
public static void main(String[] args)
{
// Test cases1
String s1 = "cats";
String s2 = "cat";
int result = computeEditDistance(s1,s2);
System.out.println("Edit Distance:" + result);
// Test Case2
s1 = "cats";
s2 = "cats";
result = computeEditDistance(s1,s2);
System.out.println("Edit Distance:" + result);
//Test Case3
s1 = "cat";
s2 = "networks";
result = computeEditDistance(s1,s2);
System.out.println("Edit Distance:" + result);
}
}
import java.util.*;
import java.lang.Math;
public class EditDistance
{
// This problem is also called the Levenshtein distance problem
// To edit the strings, basic operations needed are < 1. Insert; 2. Delete 3. Replace >
// Lets define E(x[1...i], y[1...j]) as the matrix which keeps track of the
// number of opertation that needs to be performed to make the change
// Base cases:
// 1. E(0,0) = 0 ( nothing changed)
// 2. E(1,0) = 1 ( replace or delete a character in x, nothing changes in y)
// So, if the same operating is done for 'k' indexes, edit distance would be 'k'. E(k,0) = k or E(0,k) = k
// E(i,j) : defined as edit distance to make all values from x[1...i] to look like y[1...j] or vice-versa
// E(i,j) = mininum {
// (1+ E(i-1,j)),
// (1+ E(i, j-1)),
// ( s + E(i-1,j-1) ) if x(i) == y(j) s =0: s=1
// }
public static int computeEditDistance(String s1, String s2)
{
int n = s1.length() + 1;
int m = s2.length() + 1;
int [][] e = new int[n][m];
for(int i=0; i<n; i++)
{
e[i][0] = i;
}
for(int j=0; j<m; j++)
{
e[0][j]=j;
}
for( int i=1; i<n; i++){
for(int j=1; j<m; j++)
{
e[i][j] = computeMin( 1 + e[i-1][j] , 1 + e[i][j-1],
e[i-1][j-1] + (s1.charAt(i-1) == s2.charAt(j-1)? 0:1) );
}
}
return e[n-1][m-1];
}
public static int computeMin(int a, int b, int c)
{
return Math.min(Math.min(a,b),c);
}
public static void main(String[] args)
{
// Test cases1
String s1 = "cats";
String s2 = "cat";
int result = computeEditDistance(s1,s2);
System.out.println("Edit Distance:" + result);
// Test Case2
s1 = "cats";
s2 = "cats";
result = computeEditDistance(s1,s2);
System.out.println("Edit Distance:" + result);
//Test Case3
s1 = "cat";
s2 = "networks";
result = computeEditDistance(s1,s2);
System.out.println("Edit Distance:" + result);
}
}
import java.util.*;
class Triangle
{
public HashMap<Integer, LinkedList<Integer>> maplist = new HashMap<Integer, LinkedList<Integer>>();
public Map<Integer, Boolean> visited = new HashMap<Integer, Boolean>();
public void createList()
{
maplist.put(0, new LinkedList<Integer>());
LinkedList<Integer> l = maplist.get(0);
l.add(1); l.add(2);
maplist.put(2, new LinkedList<Integer>());
l = maplist.get(2);
l.add(1); l.add(3);
maplist.put(4, new LinkedList<Integer>());
l = maplist.get(4);
l.add(1);
maplist.put(1, new LinkedList<Integer>());
l = maplist.get(1);
l.add(3);
}
public void displayAdjList()
{
Iterator itr = maplist.entrySet().iterator();
while(itr.hasNext())
{
Map.Entry pairs = (Map.Entry)itr.next();
System.out.println("Node:" + pairs.getKey() + "List:" + pairs.getValue());
}
}
public int numberOfTriangles()
{
int count = 0 ;
for(int key: maplist.keySet())
{
LinkedList<Integer> l = maplist.get(key);
for(int item: l)
{
if(!visited.containsKey(item))
visited.put(item, true);
else if (visited.containsKey(key) && visited.get(item)) // finding out the common nodes
{
count++;
}
}
}
return count;
}
public static void main(String[] args)
{
Triangle t = new Triangle();
t.createList();
t.displayAdjList();
int num = t.numberOfTriangles();
System.out.println(num);
}
}
import java.util.*;
class CircularLinkedList
{
public Node root = null;
public class Node
{
Node next = null;
int item;
public Node(int data)
{
item = data;
}
}
public Node sortedInsert(Node root, int data)
{
Node current = root;
Node newItem = new Node(data);
// Case1: LinkedList is none
if( current == null) { current = newItem; current.next = current; root = current;} // self loop, since its the only item
// Case2: inserting before the head node
if( current.item > data ){ newItem.next = current; current.next = newItem; root = newItem;}
// Case 3: inbetween
if(newItem.item > current.item)
{
while(current !=null){
if(current.next != null && current.next.item > newItem.item)
{
Node temp = current.next;
current.next = newItem;
current.next.next = temp;
break;
}
if(newItem.item > current.item && current.next.item == root.item) // is the last element
{
current.next = newItem;
current.next.next = root;
break;
}
current = current.next;
}
}
return root;
}
public void display(Node n)
{
Node current = n;
while(current != null)
{
System.out.println(current.item);
current = current.next;
if( current.item == n.item) break;
}
}
public static void main(String[] args)
{
CircularLinkedList cr = new CircularLinkedList();
System.out.println("After inserting 2");
cr.root = cr.sortedInsert(cr.root, 2);
cr.display(cr.root);
System.out.println("After inserting 1");
cr.root = cr.sortedInsert(cr.root, 1);
cr.display(cr.root);
System.out.println("After inserting 4");
cr.root = cr.sortedInsert(cr.root, 4);
cr.display(cr.root);
System.out.println("After inserting 3");
cr.root = cr.sortedInsert(cr.root, 3);
cr.display(cr.root);
System.out.println("After inserting 5");
cr.root = cr.sortedInsert(cr.root, 5);
cr.display(cr.root);
}
}
Replushililly, Area Sales Manager at ASAPInfosystemsPvtLtd
I am Graphic designer from Watertown. a professional within the graphic design and graphic arts industry assembles together images, typography ...
The logic to the solution given by Jack,
- maverick December 15, 2014Since we know that we are looking at 2 additional values
diff A - B will give the sum of 2 additional numbers ( x + y)
diff of A^2- B^2 will give x^2 + y^2
we also know that (x+y)^2 = x^2 + y^2 + 2*x*y, so x*y can be computed
We are trying to find x-y , using the property (x-y)^2 = (x+y)^2 - 4x*y
Then we can solve (x+y) and (x-y) to get x and y.
I hope this helps.