Skip to content

Commit a80f00e

Browse files
tifa64tifa64
authored
Merge branch 'master' into ReadMeUpdate
2 parents ba301ef + b69548e commit a80f00e

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

49 files changed

+1912
-87
lines changed

‎Conversions/AnyBaseToAnyBase.java‎

Lines changed: 130 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,130 @@
1+
import java.util.Arrays;
2+
import java.util.HashSet;
3+
import java.util.InputMismatchException;
4+
import java.util.Scanner;
5+
6+
/**
7+
* Class for converting from "any" base to "any" other base, when "any" means from 2-36.
8+
* Works by going from base 1 to decimal to base 2. Includes auxiliary method for
9+
* determining whether a number is valid for a given base.
10+
*
11+
* @author Michael Rolland
12+
* @version 2017.10.10
13+
*
14+
*/
15+
public class AnyBaseToAnyBase {
16+
17+
// Smallest and largest base you want to accept as valid input
18+
static final int MINIMUM_BASE = 2;
19+
static final int MAXIMUM_BASE = 36;
20+
21+
// Driver
22+
public static void main(String[] args) {
23+
Scanner in = new Scanner(System.in);
24+
String n;
25+
int b1=0,b2=0;
26+
while (true) {
27+
try {
28+
System.out.print("Enter number: ");
29+
n = in.next();
30+
System.out.print("Enter beginning base (between "+MINIMUM_BASE+" and "+MAXIMUM_BASE+"): ");
31+
b1 = in.nextInt();
32+
if (b1 > MAXIMUM_BASE || b1 < MINIMUM_BASE) {
33+
System.out.println("Invalid base!");
34+
continue;
35+
}
36+
if (!validForBase(n, b1)) {
37+
System.out.println("The number is invalid for this base!");
38+
continue;
39+
}
40+
System.out.print("Enter end base (between "+MINIMUM_BASE+" and "+MAXIMUM_BASE+"): ");
41+
b2 = in.nextInt();
42+
if (b2 > MAXIMUM_BASE || b2 < MINIMUM_BASE) {
43+
System.out.println("Invalid base!");
44+
continue;
45+
}
46+
break;
47+
} catch (InputMismatchException e) {
48+
System.out.println("Invalid input.");
49+
in.next();
50+
}
51+
}
52+
System.out.println(base2base(n, b1, b2));
53+
}
54+
55+
/**
56+
* Checks if a number (as a String) is valid for a given base.
57+
*/
58+
public static boolean validForBase(String n, int base) {
59+
char[] validDigits = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E',
60+
'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V',
61+
'W', 'X', 'Y', 'Z'};
62+
// digitsForBase contains all the valid digits for the base given
63+
char[] digitsForBase = Arrays.copyOfRange(validDigits, 0, base);
64+
65+
// Convert character array into set for convenience of contains() method
66+
HashSet<Character> digitsList = new HashSet();
67+
for (int i=0; i<digitsForBase.length; i++)
68+
digitsList.add(digitsForBase[i]);
69+
70+
// Check that every digit in n is within the list of valid digits for that base.
71+
for (char c : n.toCharArray())
72+
if (!digitsList.contains(c))
73+
return false;
74+
75+
return true;
76+
}
77+
78+
/**
79+
* Method to convert any integer from base b1 to base b2. Works by converting from b1 to decimal,
80+
* then decimal to b2.
81+
* @param n The integer to be converted.
82+
* @param b1 Beginning base.
83+
* @param b2 End base.
84+
* @return n in base b2.
85+
*/
86+
public static String base2base(String n, int b1, int b2) {
87+
// Declare variables: decimal value of n,
88+
// character of base b1, character of base b2,
89+
// and the string that will be returned.
90+
int decimalValue = 0, charB2;
91+
char charB1;
92+
String output="";
93+
// Go through every character of n
94+
for (int i=0; i<n.length(); i++) {
95+
// store the character in charB1
96+
charB1 = n.charAt(i);
97+
// if it is a non-number, convert it to a decimal value >9 and store it in charB2
98+
if (charB1 >= 'A' && charB1 <= 'Z')
99+
charB2 = 10 + (charB1 - 'A');
100+
// Else, store the integer value in charB2
101+
else
102+
charB2 = charB1 - '0';
103+
// Convert the digit to decimal and add it to the
104+
// decimalValue of n
105+
decimalValue = decimalValue * b1 + charB2;
106+
}
107+
108+
// Converting the decimal value to base b2:
109+
// A number is converted from decimal to another base
110+
// by continuously dividing by the base and recording
111+
// the remainder until the quotient is zero. The number in the
112+
// new base is the remainders, with the last remainder
113+
// being the left-most digit.
114+
115+
// While the quotient is NOT zero:
116+
while (decimalValue != 0) {
117+
// If the remainder is a digit < 10, simply add it to
118+
// the left side of the new number.
119+
if (decimalValue % b2 < 10)
120+
output = Integer.toString(decimalValue % b2) + output;
121+
// If the remainder is >= 10, add a character with the
122+
// corresponding value to the new number. (A = 10, B = 11, C = 12, ...)
123+
else
124+
output = (char)((decimalValue % b2)+55) + output;
125+
// Divide by the new base again
126+
decimalValue /= b2;
127+
}
128+
return output;
129+
}
130+
}

‎Dynamic Programming/Fibonacci.java‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,7 @@
1111

1212
public class Fibonacci {
1313

14-
public static Map<Integer,Integer> map = new HashMap<Integer,Integer>();
14+
private static Map<Integer,Integer> map = new HashMap<Integer,Integer>();
1515

1616
public static void main(String[] args) throws Exception {
1717

@@ -29,7 +29,7 @@ public static void main(String[] args) throws Exception {
2929
* Outputs the nth fibonacci number
3030
**/
3131

32-
public static int fibMemo(int n) {
32+
private static int fibMemo(int n) {
3333
if (map.containsKey(n)) {
3434
return map.get(n);
3535
}
@@ -54,7 +54,7 @@ public static int fibMemo(int n) {
5454
* Outputs the nth fibonacci number
5555
**/
5656

57-
public static int fibBotUp(int n) {
57+
private static int fibBotUp(int n) {
5858

5959
Map<Integer,Integer> fib = new HashMap<Integer,Integer>();
6060

‎Dynamic Programming/Levenshtein_distance.java‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
*/
88

99
public class Levenshtein_distance{
10-
private int minimum(int a, int b, int c){
10+
private static int minimum(int a, int b, int c){
1111
if(a < b && a < c){
1212
return a;
1313
}else if(b < a && b < c){
@@ -16,7 +16,7 @@ private int minimum(int a, int b, int c){
1616
return c;
1717
}
1818
}
19-
public int calculate_distance(String a, String b){
19+
private static int calculate_distance(String a, String b){
2020
len_a = a.length() + 1;
2121
len_b = b.length() + 1;
2222
int [][] distance_mat = new int[len_a][len_b];

‎Dynamic Programming/LongestCommonSubsequence.java‎

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
class LongestCommonSubsequence {
2+
3+
public static String getLCS(String str1, String str2) {
4+
5+
//At least one string is null
6+
if(str1 == null || str2 == null)
7+
return null;
8+
9+
//At least one string is empty
10+
if(str1.length() == 0 || str2.length() == 0)
11+
return "";
12+
13+
String[] arr1 = str1.split("");
14+
String[] arr2 = str2.split("");
15+
16+
//lcsMatrix[i][j] = LCS of first i elements of arr1 and first j characters of arr2
17+
int[][] lcsMatrix = new int[arr1.length + 1][arr2.length + 1];
18+
19+
for(int i = 0; i < arr1.length + 1; i++)
20+
lcsMatrix[i][0] = 0;
21+
for(int j = 1; j < arr2.length + 1; j++)
22+
lcsMatrix[0][j] = 0;
23+
for(int i = 1; i < arr1.length + 1; i++) {
24+
for(int j = 1; j < arr2.length + 1; j++) {
25+
if(arr1[i-1].equals(arr2[j-1])) {
26+
lcsMatrix[i][j] = lcsMatrix[i-1][j-1] + 1;
27+
} else {
28+
lcsMatrix[i][j] = lcsMatrix[i-1][j] > lcsMatrix[i][j-1] ? lcsMatrix[i-1][j] : lcsMatrix[i][j-1];
29+
}
30+
}
31+
}
32+
return lcsString(str1, str2, lcsMatrix);
33+
}
34+
35+
public static String lcsString (String str1, String str2, int[][] lcsMatrix) {
36+
StringBuilder lcs = new StringBuilder();
37+
int i = str1.length(),
38+
j = str2.length();
39+
while(i > 0 && j > 0) {
40+
if(str1.charAt(i-1) == str2.charAt(j-1)) {
41+
lcs.append(str1.charAt(i-1));
42+
i--;
43+
j--;
44+
} else if(lcsMatrix[i-1][j] > lcsMatrix[i][j-1]) {
45+
i--;
46+
} else {
47+
j--;
48+
}
49+
}
50+
return lcs.reverse().toString();
51+
}
52+
53+
public static void main(String[] args) {
54+
String str1 = "DSGSHSRGSRHTRD";
55+
String str2 = "DATRGAGTSHS";
56+
String lcs = getLCS(str1, str2);
57+
58+
//Print LCS
59+
if(lcs != null) {
60+
System.out.println("String 1: " + str1);
61+
System.out.println("String 2: " + str2);
62+
System.out.println("LCS: " + lcs);
63+
System.out.println("LCS length: " + lcs.length());
64+
}
65+
}
66+
}

‎Dynamic Programming/LongestIncreasingSubsequence.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -31,7 +31,7 @@ private static int upperBound(int[] ar, int l, int r, int key) {
3131
return r;
3232
}
3333

34-
public static int LIS(int[] array) {
34+
private static int LIS(int[] array) {
3535
int N = array.length;
3636
if (N == 0)
3737
return 0;

Misc/Abecedarian.java renamed to Others/Abecedarian.java

File renamed without changes.

Misc/CountChar.java renamed to Others/CountChar.java

File renamed without changes.

Misc/Dijkshtra.java renamed to Others/Dijkshtra.java

File renamed without changes.

Misc/Factorial.java renamed to Others/Factorial.java

File renamed without changes.

Misc/FibToN.java renamed to Others/FibToN.java

File renamed without changes.

0 commit comments

Comments
 (0)