Skip to content

Navigation Menu

Sign in

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit a774c1f

Browse filesBrowse files
darecoderdarecoder
committed
Crux update
1 parent d082105 commit a774c1f
Copy full SHA for a774c1f

21 files changed

+218
-272
lines changed

‎.idea/workspace.xml

Copy file name to clipboardExpand all lines: .idea/workspace.xml
+67-247Lines changed: 67 additions & 247 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎out/production/Crux/com/company/Lecture13/CheckParanthesis.class

Copy file name to clipboard
1.53 KB
Binary file not shown.

‎out/production/Crux/com/company/Lecture18/BST.class

Copy file name to clipboard
15 Bytes
Binary file not shown.

‎out/production/Crux/com/company/Lecture21/AdjListGraph.class

Copy file name to clipboard
-4 Bytes
Binary file not shown.

‎out/production/Crux/com/company/Lecture22/AdjMapGraph$Vertex.class

Copy file name to clipboard
0 Bytes
Binary file not shown.

‎out/production/Crux/com/company/Lecture22/AdjMapGraph.class

Copy file name to clipboard
0 Bytes
Binary file not shown.

‎out/production/Crux/com/company/Lecture22/AdjMapWeightGraph$1.class

Copy file name to clipboard
-1.56 KB
Binary file not shown.

‎out/production/Crux/com/company/Lecture22/AdjMapWeightGraph$2.class

Copy file name to clipboard
-1.54 KB
Binary file not shown.

‎out/production/Crux/com/company/Lecture22/AdjMapWeightGraph$DjPair.class

Copy file name to clipboard
1.41 KB
Binary file not shown.

‎out/production/Crux/com/company/Lecture22/AdjMapWeightGraph$Edge.class

Copy file name to clipboard
0 Bytes
Binary file not shown.

‎out/production/Crux/com/company/Lecture22/AdjMapWeightGraph$Vertex.class

Copy file name to clipboard
0 Bytes
Binary file not shown.

‎out/production/Crux/com/company/Lecture22/AdjMapWeightGraph.class

Copy file name to clipboard
2.24 KB
Binary file not shown.

‎out/production/Crux/com/company/Lecture8/RecursionExamples.class

Copy file name to clipboard
-22 Bytes
Binary file not shown.

‎out/production/Crux/com/company/Lecture9/SubSeq.class

Copy file name to clipboard
575 Bytes
Binary file not shown.

‎src/com/company/Lecture13/CheckParanthesis.java

Copy file name to clipboard
+41Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
package com.company.Lecture13;
2+
3+
import java.util.Stack;
4+
5+
public class CheckParanthesis {
6+
public static void main(String[] args) {
7+
String str = "{(){}[((])]}";
8+
System.out.println(isBalanced(str));
9+
}
10+
11+
public static boolean isBalanced(String str) {
12+
Stack<Character> stack = new Stack<>();
13+
for (int i = 0; i < str.length(); i++) {
14+
if (str.charAt(i) == '{' || str.charAt(i) == '[' || str.charAt(i) =='(') {
15+
stack.push(str.charAt(i));
16+
}else {
17+
char close = findOpen(str.charAt(i));
18+
if (stack.peek() == close) {
19+
stack.pop();
20+
} else {
21+
return false;
22+
}
23+
}
24+
}
25+
26+
if (stack.empty()) {
27+
return true;
28+
}
29+
return false;
30+
}
31+
32+
private static char findOpen(char ch) {
33+
if (ch == ')') {
34+
return '(';
35+
}else if(ch == '}') {
36+
return '{';
37+
} else {
38+
return '[';
39+
}
40+
}
41+
}

‎src/com/company/Lecture18/BST.java

Copy file name to clipboardExpand all lines: src/com/company/Lecture18/BST.java
+1-1Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -231,7 +231,7 @@ public LinkedListGeneric<T> makeSortedList(){
231231
return makeSortedList(this.root,list);
232232
}
233233

234-
private LinkedListGeneric<T> makeSortedList(Node node, LinkedListGeneric list) {
234+
private LinkedListGeneric<T> makeSortedList(Node node, LinkedListGeneric<T> list) {
235235
if(node == null){
236236
return list;
237237
}

‎src/com/company/Lecture21/AdjListGraph.java

Copy file name to clipboardExpand all lines: src/com/company/Lecture21/AdjListGraph.java
+1-4Lines changed: 1 addition & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -217,10 +217,7 @@ public boolean bipartiteGraph(){
217217

218218
public boolean isConnected(){
219219
List<LinkedList<E>> list = this.connectedComponent();
220-
if(list.size() == 1){
221-
return true;
222-
}
223-
return false;
220+
return list.size() < 2;
224221
}
225222

226223
public boolean isCyclic(E start){

‎src/com/company/Lecture22/AdjMapGraph.java

Copy file name to clipboardExpand all lines: src/com/company/Lecture22/AdjMapGraph.java
+1-2Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -2,8 +2,7 @@
22

33
import java.util.*;
44

5-
public class
6-
AdjMapGraph<E> {
5+
public class AdjMapGraph<E> {
76

87
private Map<E, Vertex> vertices = new HashMap<E, Vertex>();
98

‎src/com/company/Lecture22/AdjMapWeightGraph.java

Copy file name to clipboardExpand all lines: src/com/company/Lecture22/AdjMapWeightGraph.java
+86-13Lines changed: 86 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,8 @@
22

33
import java.util.*;
44

5+
import static java.util.Comparator.*;
6+
57
public class AdjMapWeightGraph<E> {
68

79
private Map<E, Vertex> vertices = new HashMap<E, Vertex>();
@@ -40,15 +42,17 @@ public Integer kruskal(){
4042
}
4143
}
4244

43-
Collections.sort(list, new Comparator<Edge>() {
44-
@Override
45-
public int compare(Edge o1, Edge o2) {
46-
return o1.weight - o2.weight;
47-
}
48-
});
45+
// Collections.sort(list, new Comparator<Edge>() {
46+
// @Override
47+
// public int compare(Edge o1, Edge o2) {
48+
// return o1.weight - o2.weight;
49+
// }
50+
// });
4951

5052
// Collections.sort(list, (o1, o2) -> o1.weight - o2.weight); Lambda Expressions
5153

54+
list.sort(comparingInt(o -> o.weight));
55+
5256
Map<Vertex, Vertex> parents = generateParents();
5357
int total = 0;
5458
for (Edge edge : list){
@@ -64,12 +68,7 @@ public int prims(){
6468
Vertex start = vertices.values().iterator().next();
6569
Set<Vertex> visited = new HashSet<Vertex>();
6670

67-
PriorityQueue<Edge> queue = new PriorityQueue<Edge>(new Comparator<Edge>() {
68-
@Override
69-
public int compare(Edge o1, Edge o2) {
70-
return o1.weight - o2.weight;
71-
}
72-
});
71+
PriorityQueue<Edge> queue = new PriorityQueue<Edge>(comparingInt(o -> o.weight));
7372

7473
visited.add(start);
7574
for (Vertex end : start.neighbours.keySet()){
@@ -145,7 +144,7 @@ private boolean Union(Vertex first,Vertex second, Map<Vertex, Vertex> parents){
145144
first = find(first, parents);
146145
second = find(second, parents);
147146

148-
if(first != second){
147+
if(first != second) {
149148
parents.put(first, second);
150149
return true;
151150
}
@@ -174,4 +173,78 @@ public void DFT(E value){
174173
}
175174
}
176175
}
176+
177+
public class DjPair implements Comparable<DjPair> {
178+
int cost;
179+
E connectingVertex;
180+
E endVertex;
181+
182+
DjPair(E endVertex, int cost, E acquirer) {
183+
this.connectingVertex = acquirer;
184+
this.endVertex = endVertex;
185+
this.cost = cost;
186+
}
187+
188+
@Override
189+
public int compareTo(DjPair o) {
190+
return this.cost - o.cost;
191+
}
192+
}
193+
194+
public void dijkstra(E source) {
195+
HashMap<E, DjPair> map = new HashMap<>();
196+
PriorityQueue<DjPair> minheap = new PriorityQueue<>();
197+
Set<E> allvertices = this.vertices.keySet();
198+
199+
/* Saare vertices pe traverse kar rhe hain and if it is the same
200+
as source toh usme cost 0 daal rehe hain nhi toh infinity */
201+
for (E vertex : allvertices) {
202+
DjPair d;
203+
if (vertex.equals(source)) {
204+
d = new DjPair(vertex, 0, null);
205+
} else {
206+
d = new DjPair(vertex, Integer.MAX_VALUE, null);
207+
}
208+
209+
//saare DjPair of vertices heap mein add kar de rhe hain
210+
minheap.add(d);
211+
map.put(vertex, d);
212+
}
213+
214+
//Heap mein traverse kar rhe hain
215+
while (!minheap.isEmpty()) {
216+
//Minimum DjPair on the basis of cost remove karenge
217+
DjPair current = minheap.remove();
218+
map.remove(current.endVertex);
219+
220+
/* Us pair ke 2nd vertex ya keh lo connected
221+
vertex ko aur uski cost ko print kar dia */
222+
System.out.println(current.endVertex +"->"+current.cost);
223+
224+
/* Ab jis vertex ko print kia uske saare neighbouring vertex
225+
ki cost jaake update kar do, means ki agar mai uski neighbouring
226+
vertex pe is vertex ke through jaaun toh kya cost hogi */
227+
Set<Vertex> neighbour = vertices.get(current.endVertex).neighbours.keySet();
228+
for (Vertex padosi : neighbour) {
229+
if (map.containsKey(padosi.value)) {
230+
DjPair pair = map.get(padosi.value);
231+
int oldcost = pair.cost;
232+
/* source se current vertex tak ka cost + current vertex se padosi tak jaane ka cost */
233+
int newcost = current.cost + vertices.get(current.endVertex).neighbours.get(padosi);
234+
if (newcost < oldcost) {
235+
/* Heap se pichla cost vala pair remove kar
236+
do kyunki naya cost jaada chhota hai ab */
237+
minheap.remove(map.get(padosi.value));
238+
239+
// Naya pair banao naye cost ke saath aur heap mein add kar do
240+
pair.cost = newcost;
241+
pair.connectingVertex = current.endVertex;
242+
map.put(padosi.value, pair);
243+
minheap.add(pair);
244+
}
245+
}
246+
}
247+
}
248+
249+
}
177250
}

‎src/com/company/Lecture8/RecursionExamples.java

Copy file name to clipboardExpand all lines: src/com/company/Lecture8/RecursionExamples.java
+1-4Lines changed: 1 addition & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -23,14 +23,11 @@ public static int power(int x,int n){
2323
}
2424

2525
public static int factorial(int n){
26-
2726
if(n == 0){
2827
return 1;
2928
}
3029

31-
int res = 1;
32-
res = n * factorial(n-1);
33-
return res;
30+
return n * factorial(n-1);
3431
}
3532

3633
public static int fibo(int n){

‎src/com/company/Lecture9/SubSeq.java

Copy file name to clipboardExpand all lines: src/com/company/Lecture9/SubSeq.java
+20-1Lines changed: 20 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,14 @@
11
package com.company.Lecture9;
22

33
import java.util.ArrayList;
4+
import java.util.List;
45

56
public class SubSeq {
67
public static void main(String[] args) {
78
String chars = "abc";
89
ArrayList<String> list = new ArrayList<String>();
9-
subseqList("", chars, list);
10+
// subseqList("", chars, list);
11+
System.out.println(subseqlist("", chars));
1012
System.out.println(list);
1113
// subseq("", chars);
1214
// subseq2("", chars);
@@ -57,6 +59,23 @@ public static void subseq2(String proc, String unproc){
5759
subseq2(proc, unproc);
5860
}
5961

62+
public static List<String> subseqlist(String proc, String unproc){
63+
if(unproc.isEmpty()){
64+
List<String> list = new ArrayList<>();
65+
list.add(proc);
66+
return list;
67+
}
68+
69+
List<String> res = new ArrayList<>();
70+
char ch = unproc.charAt(0);
71+
unproc = unproc.substring(1);
72+
73+
res.addAll(subseqlist(proc + ch, unproc));
74+
res.addAll(subseqlist(proc, unproc));
75+
76+
return res;
77+
}
78+
6079
public static int countsubseq2(String proc, String unproc){
6180
if(unproc.isEmpty()){
6281
return 1;

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.