Skip to content

Commit 1a053b2

Browse files
amangit1314amangit1314
committed
#Modification 116
1 parent d0c7669 commit 1a053b2

23 files changed

+1186
-565
lines changed

‎.idea/uiDesigner.xml‎

Lines changed: 124 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎README.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
# Java Placement Preparation DSA CRACKER SHEET 💻🦸‍♂️🐱‍👤[225/450]
1+
# Java Placement Preparation DSA CRACKER SHEET 💻🦸‍♂️🐱‍👤[238/450]
22

33
☄ This is a full fled-ged repository for learning Java Language & DSA for Placement Preparation.
44

‎dp/DP_Problem_10.java‎

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
package dp;
2+
3+
import java.util.Arrays;
4+
// Problem Title => Gold Mine Problem
5+
public class DP_Problem_10 {
6+
7+
static final int MAX = 100;
8+
9+
// Returns maximum amount of gold that can be collected when journey started from first column and moves allowed are right,
10+
// right-up and right-down
11+
static int getMaxGold(int[][] gold, int m, int n)
12+
{
13+
14+
// Create a table for storing intermediate results and initialize all cells to 0.
15+
// The first row of goldMineTable gives the maximum gold that the miner can collect when starts that row
16+
int[][] goldTable = new int[m][n];
17+
18+
for(int[] rows:goldTable)
19+
Arrays.fill(rows, 0);
20+
21+
for (int col = n-1; col >= 0; col--)
22+
{
23+
for (int row = 0; row < m; row++)
24+
{
25+
26+
// Gold collected on going to the cell on the right(->)
27+
int right = (col == n-1) ? 0
28+
: goldTable[row][col+1];
29+
30+
// Gold collected on going to the cell to right up (/)
31+
int right_up = (row == 0 ||
32+
col == n-1) ? 0 :
33+
goldTable[row-1][col+1];
34+
35+
// Gold collected on going to the cell to right down (\)
36+
int right_down = (row == m-1
37+
|| col == n-1) ? 0 :
38+
goldTable[row+1][col+1];
39+
40+
// Max gold collected from taking either of the above 3 paths
41+
goldTable[row][col] = gold[row][col] + Math.max(right, Math.max(right_up, right_down));
42+
}
43+
}
44+
45+
// The max amount of gold collected will be the max value in first column of all rows
46+
int res = goldTable[0][0];
47+
48+
for (int i = 1; i < m; i++)
49+
res = Math.max(res, goldTable[i][0]);
50+
51+
return res;
52+
}
53+
54+
//driver code
55+
public static void main(String[] arg)
56+
{
57+
int[][] gold= { {1, 3, 1, 5},
58+
{2, 2, 4, 1},
59+
{5, 0, 2, 3},
60+
{0, 6, 1, 2} };
61+
62+
int m = 4, n = 4;
63+
64+
System.out.print(getMaxGold(gold, m, n));
65+
}
66+
}

‎dp/DP_Problem_11.java‎

Lines changed: 1 addition & 49 deletions
Original file line numberDiff line numberDiff line change
@@ -1,56 +1,8 @@
11
package dp;
22
import java.util.*;
33

4-
// Problem Title => Gold Mine Problem
4+
// Problem Title =>
55
public class DP_Problem_11 {
6-
static final int MAX = 100;
7-
8-
// Returns maximum amount of gold that can be collected when journey started from first column and moves allowed are right,
9-
// right-up and right-down
10-
static int getMaxGold(int[][] gold, int m, int n) {
11-
12-
// Create a table for storing intermediate results and initialize all cells to 0.
13-
// The first row of goldMineTable gives the maximum gold that the miner can collect when starts that row
14-
int[][] goldTable = new int[m][n];
15-
16-
for(int[] rows:goldTable)
17-
Arrays.fill(rows, 0);
18-
19-
for (int col = n-1; col >= 0; col--) {
20-
for (int row = 0; row < m; row++) {
21-
// Gold collected on going to the cell on the right(->)
22-
int right = (col == n - 1) ? 0 : goldTable[row][col + 1];
23-
24-
// Gold collected on going to the cell to right up (/)
25-
int right_up = (row == 0 || col == n - 1) ? 0 : goldTable[row - 1][col + 1];
26-
27-
// Gold collected on going to the cell to right down (\)
28-
int right_down = (row == m - 1 || col == n - 1) ? 0 : goldTable[row + 1][col + 1];
29-
30-
// Max gold collected from taking either of the above 3 paths
31-
goldTable[row][col] = gold[row][col] + Math.max(right, Math.max(right_up, right_down));
32-
}
33-
}
34-
35-
// The max amount of gold collected will be the max value in first column of all rows
36-
int res = goldTable[0][0];
37-
38-
for (int i = 1; i < m; i++)
39-
res = Math.max(res, goldTable[i][0]);
40-
41-
return res;
42-
}
43-
44-
//driver code
456
public static void main(String[] arg) {
46-
int[][] gold= {
47-
{1, 3, 1, 5},
48-
{2, 2, 4, 1},
49-
{5, 0, 2, 3},
50-
{0, 6, 1, 2}
51-
};
52-
53-
int m = 4, n = 4;
54-
System.out.print(getMaxGold(gold, m, n));
557
}
568
}

‎dp/DP_Problem_23.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
package dp;
2-
// PROBLEM TITLE => Edd Dropping Problem
2+
// PROBLEM TITLE => Egg Dropping Problem
33
public class DP_Problem_23 {
44

55
/* Function to get minimum number of trials needed in worst case with n eggs and k floors */

‎graphics_lab/Transformation_Operation.java‎

Lines changed: 0 additions & 27 deletions
This file was deleted.

‎graphs/Graph_Problem_10.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
package graphs;
22
import java.util.*;
3-
3+
// Problem Title => making wired connections
44
public class Graph_Problem_10 {
55
// Function to visit the nodes of a graph
66
public static void DFS(HashMap<Integer, ArrayList<Integer> > adj, int node, boolean[] visited) {

‎graphs/Graph_Problem_11.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
package graphs;
22
import java.util.*;
33

4-
// Problem Title =>
4+
// Problem Title => Word ladder
55
public class Graph_Problem_11 {
66
// Returns length of the shortest chain to reach 'target' from 'start' using minimum number of adjacent moves. D is dictionary
77
static int shortestChainLen(String start, String target, Set<String> D) {

‎graphs/Graph_Problem_12.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
package graphs;
22
import java.util.*;
33

4-
// Problem Title => Dijkstra's Algorithm (Find Shortest Path)
4+
// Problem Title => Dijkstra's Algorithm (Find The Shortest Path)
55
public class Graph_Problem_12 {
66
// finding vertex with min distance,
77
// from set of non-included vertices in the shortest path tree

0 commit comments

Comments
 (0)