Difference between revisions of "Algorithms"
Jump to navigation
Jump to search
Line 366: | Line 366: | ||
} | } | ||
+ | } | ||
+ | ==Merge two lists== | ||
+ | import java.util.Stack; | ||
+ | /*This code merges two ordered lists into one keeping their increasing order | ||
+ | * the lists used for testing are in the main function*/ | ||
+ | public class MergeLists { | ||
+ | static class Node { | ||
+ | int data; | ||
+ | Node next; | ||
+ | Node(int z) { | ||
+ | this.data = z; | ||
+ | next = null; | ||
+ | } | ||
+ | } | ||
+ | |||
+ | /*This function reads the values of a list and loads them on a Stack, then reads from the stack*/ | ||
+ | public static void loadInStack(Node f) { | ||
+ | Stack<Integer> pack = new Stack<>(); | ||
+ | if (f == null) | ||
+ | return; | ||
+ | pack.push(f.data); | ||
+ | loadInStack(f.next); | ||
+ | System.out.println(pack); | ||
+ | } | ||
+ | |||
+ | /*This function duplicates the provided list into another one*/ | ||
+ | public static void duplicateList(Node m) { | ||
+ | Node hold = new Node(-1); | ||
+ | if (m == null) | ||
+ | return; | ||
+ | hold.data = m.data; | ||
+ | duplicateList(m.next); | ||
+ | System.out.println(hold.data); | ||
+ | } | ||
+ | |||
+ | /*This function reads from two lists picking the lesser of*/ | ||
+ | /*It takes in two lists as variables a and b*/ | ||
+ | public static void pickTwo(Node a, Node b) { | ||
+ | /*This is a dummy list initialized with -1*/ | ||
+ | Node dummyList = new Node(-1); | ||
+ | while (a != null && b != null) { | ||
+ | if (a.data <= b.data) { | ||
+ | /*populate the dummy list from a, if smaller*/ | ||
+ | dummyList.data = a.data; | ||
+ | /*Increment a*/ | ||
+ | a = a.next; | ||
+ | } else { | ||
+ | /*populate the dummy list from b, if smaller*/ | ||
+ | dummyList.data = b.data; | ||
+ | /*Increment b*/ | ||
+ | b = b.next; | ||
+ | } | ||
+ | /*Print when done*/ | ||
+ | System.out.print(dummyList.data + " -> "); | ||
+ | } | ||
+ | } | ||
+ | |||
+ | public static void main(String args[]) { | ||
+ | Node f = new Node(2); | ||
+ | Node g = new Node(7); | ||
+ | Node h = new Node(8); | ||
+ | Node i = new Node(11); | ||
+ | |||
+ | f.next = g; | ||
+ | g.next = h; | ||
+ | h.next = i; | ||
+ | |||
+ | //printNodes(f); | ||
+ | |||
+ | Node k = new Node(4); | ||
+ | Node l = new Node(6); | ||
+ | Node m = new Node(9); | ||
+ | Node n = new Node(10); | ||
+ | Node o = new Node(12); | ||
+ | |||
+ | k.next = l; | ||
+ | l.next = m; | ||
+ | m.next = n; | ||
+ | n.next = o; | ||
+ | |||
+ | //loadInStack(f); | ||
+ | //duplicateList(k); | ||
+ | pickTwo(f, k); | ||
+ | } | ||
} | } |
Revision as of 02:13, 22 October 2022
Contents
Java Graph Implementation with Search Methods
import java.util.HashMap; import java.util.LinkedList;
public class Chart {
static class Employee { int id; String firstName; String lastName; String jobTitle; boolean mapped;
Employee(int id, String fn, String ln, String jt) { this.id = id; this.jobTitle = jt; this.firstName = fn; this.lastName = ln; }
void map() { mapped = true; }
void unmap() { mapped = false; } }
private final HashMap<Employee, LinkedList<Employee>> assignment;
public Chart(boolean directed) { assignment = new HashMap<>(); }
public void addEdgeHelper(Employee a, Employee b) { LinkedList<Employee> e = assignment.get(a); if (e != null) { assignment.remove(b); } else e = new LinkedList<>(); e.add(b); assignment.put(a, e); }
public void addEdge(Employee boss, Employee subordinate) { if (!assignment.containsKey(boss)) assignment.put(boss, null); if (!assignment.containsKey(subordinate)) assignment.put(subordinate, null); addEdgeHelper(boss, subordinate); }
public void depthFirstSearch(Employee employee) { employee.map(); System.out.println(employee.firstName + " " + employee.lastName + " is a " + employee.jobTitle); LinkedList<Employee> neighbors = assignment.get(employee); if (neighbors == null) return; for (Employee e : neighbors) { if (!e.mapped) depthFirstSearch(e); } }
public void breadthFirstSearch(Employee employee) { /*Check if target item is null - if so quit*/ if (employee == null) return; /*Declare a queue using LinkedList and add the target item*/ LinkedList<Employee> queue = new LinkedList<>(); queue.add(employee); /*As long as the queue has data get the first in item .removeFirst*/ while (!queue.isEmpty()) { Employee currentFirst = queue.removeFirst(); /*If visited move on*/ if (currentFirst.mapped) { continue; } else { /*else visit it and print it*/ currentFirst.map(); System.out.println(currentFirst.id + ": " + currentFirst.firstName + " " + currentFirst.lastName + " - " + currentFirst.jobTitle); } /*Find neighbors of the current item*/ LinkedList<Employee> allNeighbors = assignment.get(currentFirst); /*If there are none move on*/ if (allNeighbors == null) continue; /*else if there are some and not visited, add them to the queue and the process starts over*/ for (Employee e : allNeighbors) { if (!e.mapped) queue.add(e); } } }
public void resetMapping() { for (Employee e : assignment.keySet()) { e.unmap(); } }
public static void main(String args[]) { Employee a = new Employee(38, "Jimbo", "Jones", "President"); Employee b = new Employee(39, "Mike", "McCobb", "VP"); Employee c = new Employee(43, "Elda", "Two", "VP"); Employee d = new Employee(48, "Simon", "Sneeth", "VP"); Employee e = new Employee(56, "Tim", "Scott", "Manager"); Employee f = new Employee(58, "Bob", "Tilman", "Manager"); Employee g = new Employee(78, "Andrew", "Cole", "Analyst"); Employee h = new Employee(83, "Matt", "Lemon", "Analyst"); Employee i = new Employee(88, "Chris", "Lock", "Analyst"); Employee j = new Employee(71, "Agnes", "White", "Accountant"); Employee k = new Employee(61, "George", "Mills", "Manager"); Employee l = new Employee(59, "Thomas", "Wells", "Manager"); Employee m = new Employee(63, "Zip", "Two", "Manager"); Employee n = new Employee(73, "Rasta", "Him", "Technician"); Employee o = new Employee(89, "Claire", "Collins", "Supervisor"); Employee p = new Employee(95, "Jim", "Four", "Receptionist"); Employee q = new Employee(104, "Tom", "Flat", "Receptionist"); Employee r = new Employee(64, "Grace", "Marks", "Manager"); Employee s = new Employee(68, "Dan", "Four", "Manager"); Employee t = new Employee(117, "Shad", "Fifty", "Security"); Employee u = new Employee(108, "Tall", "Nephew", "Legal"); Employee v = new Employee(109, "Short", "Nephew", "Legal");
Chart chart = new Chart(true); chart.addEdge(a, b); chart.addEdge(a, c); chart.addEdge(a, d); chart.addEdge(b, e); chart.addEdge(b, f); chart.addEdge(e, g); chart.addEdge(e, h); chart.addEdge(e, i); chart.addEdge(f, j); chart.addEdge(c, k); chart.addEdge(c, l); chart.addEdge(c, m); chart.addEdge(l, n); chart.addEdge(k, o); chart.addEdge(o, p); chart.addEdge(o, q); chart.addEdge(d, r); chart.addEdge(d, s); chart.addEdge(s, t); chart.addEdge(r, u); chart.addEdge(r, v); //System.out.println(a.firstName + " " + a.lastName + " " + a.jobTitle + " " + a.id); chart.resetMapping(); //chart.depthFirstSearch(k);
chart.resetMapping(); chart.breadthFirstSearch(a); }
}
Find missing number
//The missing number = a sum of the provided array subracted from a sum of indeces + 2 //example 1, 2, 4 missing is 3 = (1 +2 +3+4) - (1 +2+4)
import java.util.ArrayList; import java.util.Arrays; import java.util.List;
public class MissingNum {
public static int findMissing(List<Integer> l) { int tot_prov = 0; for (Integer integer : l) { tot_prov += integer; } List<Integer> k = new ArrayList<>(); int tot_req = 0; for (int i = 0; i < l.size() + 2; i++) { k.add(i); tot_req += k.get(i); } return tot_req - tot_prov; }
public static void main(String[] args) { List<Integer> g = Arrays.asList(8, 5, 3, 2, 4, 1, 7); System.out.println("The missing number is " + findMissing(g)); }
}
Mergesort
public class MergeSort {
private static Comparable[] aux;
public static void sort(Comparable[] a) { aux = new Comparable[a.length]; sort(a, 0, a.length - 1); }
private static void merge(Comparable[] a, int lo, int mid, int hi) { assert isSorted(a, lo, mid); assert isSorted(a, mid + 1, hi); //copy for [] a to [] aux for (int k = lo; k <= hi; k++) { aux[k] = a[k]; } // the merging process // i is the first index of the first half of the array // j is the first index of the second half of the array int i = lo, j = mid + 1;
// for every value of k - the indices of [] a for (int k = lo; k <= hi; k++) { /*Left half exhausted take from the right*/ if (i > mid) a[k] = aux[j++]; /*Right half exhausted take from the left*/ else if (j > hi) a[k] = aux[i++]; /*Current key on the right less than current key on the left take from the right*/ else if (less(aux[j], aux[i])) a[k] = aux[j++]; /*Current key on the right greater than current key on the left take from the left */ else a[k] = aux[i++]; } assert isSorted(a, lo, hi); }
private static void sort(Comparable[] a, int lo, int hi) { if (hi <= lo) return; int mid = lo + (hi - lo) / 2; sort(a, lo, mid); sort(a, mid + 1, hi); merge(a, lo, mid, hi); }
private static boolean less(Comparable v, Comparable w) { return v.compareTo(w) < 0; }
private static boolean isSorted(Comparable[] a, int lo, int hi) { for (int i = lo + 1; i <= hi; i++) if (less(a[i], a[i - 1])) return false; return true; }
public static void show(Comparable[] a) { for (int i = 0; i < a.length; i++) { //System.out.print(a[i]); System.out.println(a[i]); } }
public static void main(String args[]) { // Comparable[] a = {"E", "E", "G", "M", "R", "A", "C", "E", "R", "T"};
Comparable[] aa = {"A", "X", "G", "M", "R"}; Comparable[] bb = {"H", "D", "J", "Y", "Z"}; /*Merge the two comparable arrays*/ Comparable[] a = new Comparable[aa.length + bb.length]; System.arraycopy(aa, 0, a, 0, aa.length); System.arraycopy(bb, 0, a, aa.length, bb.length);
MergeSort.sort(a); show(a); }
}
Binary Search
public class BinarySearch { public static int binSearch(int[] fg, int t) {
int left = 0; int right = fg.length - 1;
while (left <= right) { int mid = left + (right - left); if (fg[mid] == t) return mid; if (fg[mid] < t) { left = mid + 1; } else { right = mid - 1; } } return -1; }
public static void main(String args[]) { int[] lsr = {1, 10, 20, 47, 59, 63, 75, 88, 99, 107, 120, 133, 155, 162, 176, 188, 199, 200, 210, 222, 223};
int t = 162;
System.out.println("The target is at position " + binSearch(lsr, t)); }
}
Binary Search Tree
public class BinarySearchTree {
static class Node { int value; Node left; Node right; Node(int value) { this.value = value; this.left = null; this.right = null; } } Node root; public BinarySearchTree() { root = null; } public boolean isbst(Node root, Node l, Node r) { if (root == null) return true; if (l != null && l.value > root.value) return false; if (r != null && r.value < root.value) return false; return isbst(root.left, l, root) && isbst(root.right, root, r); }
public static void main(String args[]) { BinarySearchTree bt = new BinarySearchTree(); bt.root = new Node(10); bt.root.left = new Node(5); bt.root.right = new Node(15); bt.root.left.left = new Node(4); bt.root.left.right = new Node(7); bt.root.right.left = new Node(13); bt.root.right.right = new Node(26); if (bt.isbst(bt.root, null, null)) System.out.println("Is a BST"); else System.out.println("Is not a BST"); }
}
Sum of two numbers
public class SumOfTwo {
public static void main(String args[]) { Set<Integer> set = new HashSet<>(); /*Populate this Set with target values*/ /*Array of target values*/ int[] g = {5, 6, 8, 39, 9, 11, 20, 59, 10, 1}; /*Insert the arrays values in the set*/ for (int i = 0; i < g.length; i++) { set.add(g[i]); } /*Set a target number to check for*/ int y = 20; /*If there are a set of numbers that would add up, increment this counter*/ int counter = 0; /*Pick up a number in the set by turns and assign it to x*/ for (int i = 0; i < g.length; i++) { int x = g[i]; /*Check to see if the set contains target minus found number.*/ if (set.contains(y - x)) { //if this is true /*If so, increment the counter by 1*/ counter += 1; } } if (counter > 0) { /*Some numbers add up*/ System.out.println("There are sets of numbers that add up to " + y); } else { /*No numbers add up*/ System.out.println("There are no sets of numbers that add up to " + y); }
}
}
Merge two lists
import java.util.Stack; /*This code merges two ordered lists into one keeping their increasing order
* the lists used for testing are in the main function*/
public class MergeLists {
static class Node { int data; Node next; Node(int z) { this.data = z; next = null; } }
/*This function reads the values of a list and loads them on a Stack, then reads from the stack*/ public static void loadInStack(Node f) { Stack<Integer> pack = new Stack<>(); if (f == null) return; pack.push(f.data); loadInStack(f.next); System.out.println(pack); }
/*This function duplicates the provided list into another one*/ public static void duplicateList(Node m) { Node hold = new Node(-1); if (m == null) return; hold.data = m.data; duplicateList(m.next); System.out.println(hold.data); }
/*This function reads from two lists picking the lesser of*/ /*It takes in two lists as variables a and b*/ public static void pickTwo(Node a, Node b) { /*This is a dummy list initialized with -1*/ Node dummyList = new Node(-1); while (a != null && b != null) { if (a.data <= b.data) { /*populate the dummy list from a, if smaller*/ dummyList.data = a.data; /*Increment a*/ a = a.next; } else { /*populate the dummy list from b, if smaller*/ dummyList.data = b.data; /*Increment b*/ b = b.next; } /*Print when done*/ System.out.print(dummyList.data + " -> "); } }
public static void main(String args[]) { Node f = new Node(2); Node g = new Node(7); Node h = new Node(8); Node i = new Node(11);
f.next = g; g.next = h; h.next = i;
//printNodes(f);
Node k = new Node(4); Node l = new Node(6); Node m = new Node(9); Node n = new Node(10); Node o = new Node(12);
k.next = l; l.next = m; m.next = n; n.next = o;
//loadInStack(f); //duplicateList(k); pickTwo(f, k); }
}