Merge branch 'master' of https://github.com/TheAlgorithms/Java into node-find-fix

mpokryva · mpokryva · commit edc51cb1e997 · 2017-09-29T11:27:27.000-04:00
diff --git a/Dynamic Programming/LongestIncreasingSubsequence.java b/Dynamic Programming/LongestIncreasingSubsequence.java
@@ -0,0 +1,62 @@
+import java.util.Scanner;
+
+/**
+ *
+ * @author Afrizal Fikri (https://github.com/icalF)
+ *
+ */
+public class LongestIncreasingSubsequence {
+    public static void main(String[] args) throws Exception {
+
+        Scanner sc = new Scanner(System.in);
+        int n = sc.nextInt();
+
+        int ar[] = new int[n];
+        for (int i = 0; i < n; i++) {
+            ar[i] = sc.nextInt();
+        }
+
+        System.out.println(LIS(ar));
+    }
+
+    private static int upperBound(int[] ar, int l, int r, int key) {
+        while (l < r-1) {
+            int m = (l + r) / 2;
+            if (ar[m] >= key)
+                r = m;
+            else
+                l = m;
+        }
+
+        return r;
+    }
+
+    public static int LIS(int[] array) {
+        int N = array.length;
+        if (N == 0)
+            return 0;
+ 
+        int[] tail = new int[N];
+        int length = 1; // always points empty slot in tail
+     
+        tail[0] = array[0];
+        for (int i = 1; i < N; i++) {
+
+            // new smallest value
+            if (array[i] < tail[0])
+                tail[0] = array[i];
+
+            // array[i] extends largest subsequence
+            else if (array[i] > tail[length-1])
+                tail[length++] = array[i];
+
+            // array[i] will become end candidate of an existing subsequence or
+            // Throw away larger elements in all LIS, to make room for upcoming grater elements than array[i]
+            // (and also, array[i] would have already appeared in one of LIS, identify the location and replace it)
+            else
+                tail[upperBound(tail, -1, length-1, array[i])] = array[i];
+        }
+     
+        return length;
+    }
+}
diff --git a/Misc/LowestBasePalindrome.java b/Misc/LowestBasePalindrome.java
@@ -0,0 +1,144 @@
+import java.util.InputMismatchException;
+import java.util.Scanner;
+
+/**
+ * Class for finding the lowest base in which a given integer is a palindrome.
+ * Includes auxiliary methods for converting between bases and reversing strings.
+ * 
+ * NOTE: There is potential for error, see note at line 63.
+ * 
+ * @author RollandMichael
+ * @version 2017.09.28
+ *
+ */
+public class LowestBasePalindrome {
+	
+	public static void main(String[] args) {
+		Scanner in = new Scanner(System.in);
+		int n=0;
+		while (true) {
+			try {
+				System.out.print("Enter number: ");
+				n = in.nextInt();
+				break;
+			} catch (InputMismatchException e) {
+				System.out.println("Invalid input!");
+				in.next();
+			}
+		}
+		System.out.println(n+" is a palindrome in base "+lowestBasePalindrome(n));
+		System.out.println(base2base(Integer.toString(n),10, lowestBasePalindrome(n)));
+	}
+	
+	/**
+	 * Given a number in base 10, returns the lowest base in which the
+	 * number is represented by a palindrome (read the same left-to-right
+	 * and right-to-left).
+	 * @param num A number in base 10.
+	 * @return The lowest base in which num is a palindrome.
+	 */
+	public static int lowestBasePalindrome(int num) {
+		int base, num2=num;
+		int digit;
+		char digitC;
+		boolean foundBase=false;
+		String newNum = "";
+		String digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
+		
+		while (!foundBase) {
+			// Try from bases 2 to num (any number n in base n is 1)
+			for (base=2; base<num2; base++) {
+				newNum="";
+				while(num>0) {
+					// Obtain the first digit of n in the current base,
+					// which is equivalent to the integer remainder of (n/base).
+					// The next digit is obtained by dividing n by the base and
+					// continuing the process of getting the remainder. This is done
+					// until n is <=0 and the number in the new base is obtained.
+					digit = (num % base);
+					num/=base;
+					// If the digit isn't in the set of [0-9][A-Z] (beyond base 36), its character
+					// form is just its value in ASCII.
+					
+					// NOTE: This may cause problems, as the capital letters are ASCII values
+					// 65-90. It may cause false positives when one digit is, for instance 10 and assigned
+					// 'A' from the character array and the other is 65 and also assigned 'A'.
+					
+					// Regardless, the character is added to the representation of n
+					// in the current base.
+					if (digit>=digits.length()) {
+						digitC=(char)(digit);
+						newNum+=digitC;
+						continue;
+					}
+					newNum+=digits.charAt(digit);
+				}
+				// Num is assigned back its original value for the next iteration.
+				num=num2;
+				// Auxiliary method reverses the number.
+				String reverse = reverse(newNum);
+				// If the number is read the same as its reverse, then it is a palindrome.
+				// The current base is returned.
+				if (reverse.equals(newNum)) {
+					foundBase=true;
+					return base;
+				}
+			}
+		}
+		// If all else fails, n is always a palindrome in base n-1. ("11")
+		return num-1;
+	}
+	
+	private static String reverse(String str) {
+	    String reverse = "";
+	    for(int i=str.length()-1; i>=0; i--) {
+	       reverse += str.charAt(i);
+	    }
+	    return reverse;
+	}
+	
+	private static String base2base(String n, int b1, int b2) {
+		// Declare variables: decimal value of n, 
+		// character of base b1, character of base b2,
+		// and the string that will be returned.
+		int decimalValue = 0, charB2;
+		char charB1;
+		String output="";
+		// Go through every character of n
+		for (int i=0; i<n.length(); i++) {
+			// store the character in charB1
+			charB1 = n.charAt(i);
+			// if it is a non-number, convert it to a decimal value >9 and store it in charB2
+			if (charB1 >= 'A' && charB1 <= 'Z') 
+				charB2 = 10 + (charB1 - 'A');
+			// Else, store the integer value in charB2
+			else 
+				charB2 = charB1 - '0';
+			// Convert the digit to decimal and add it to the
+			// decimalValue of n
+			decimalValue = decimalValue * b1 + charB2;
+		}
+		
+		// Converting the decimal value to base b2:
+		// A number is converted from decimal to another base
+		// by continuously dividing by the base and recording 
+		// the remainder until the quotient is zero. The number in the
+		// new base is the remainders, with the last remainder
+		// being the left-most digit.
+		
+		// While the quotient is NOT zero:
+		while (decimalValue != 0) {
+			// If the remainder is a digit < 10, simply add it to
+			// the left side of the new number.
+			if (decimalValue % b2 < 10) 
+				output = Integer.toString(decimalValue % b2) + output;
+			// If the remainder is >= 10, add a character with the
+			// corresponding value to the new number. (A = 10, B = 11, C = 12, ...)
+			else
+				output = (char)((decimalValue % b2)+55) + output;
+			// Divide by the new base again
+			decimalValue /= b2;
+		}
+		return output;
+	}
+}
