liuben10
BAN USERSorry, career cup is breaking down on me and it's super frustrating; I've been having difficulty editing my comment. Here's the corrected version of my comment:
You can solve this problem by breaking down your input string into subproblems based on the first two characters of your input string. The resultant count is the number of leaves in your recursion.
For instance.
You break up the solution to "123" into these subproblems:
solution("123")
-> "1" + solution("23")
-> "1" + "2" + solution("3") => "1,2,3"
-> "1" + "23" + solution("") => "1", "23"
-> "12" + solution("3") => "12", "3"
To capture this, here's some simple Java code which shows this idea and also prints out each possible solution so you can easily confirm that the solution is correct.
public static int findHowManyStrings(String soFar, String numberString, String rest) {
final String ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
if (rest.length() == 0) {
System.out.println(soFar + "=" + numberString);
return 1;
} else if (rest.length() == 1) {
System.out.println(soFar + ALPHABET.charAt(Integer.parseInt(rest)-1) + "=" + numberString + rest);
return 1;
} else {
int sum = findHowManyStrings(soFar + ALPHABET.charAt(Integer.parseInt(rest.substring(0, 1))-1) + ",", numberString + rest.substring(0, 1) + ",", rest.substring(1));
String firstTwo = rest.substring(0, 2);
if (Integer.parseInt(firstTwo) <= 26) {
sum += findHowManyStrings(soFar + ALPHABET.charAt(Integer.parseInt(firstTwo)-1) + ",", numberString + rest.substring(0,2) + ",", rest.substring(2));
}
return sum;
}
}
Here's the log(n) binary search solution. I chose 0.000001 as an arbitrary precision.
public class Sqrt {
public static void main(String...args) {
System.out.println(findSquareRoot(4));
}
public static double findSquareRoot(double value) {
double low = 0;
double high = value;
double mid = (low + high) / 2;
while (Math.abs(value - mid * mid) > 0.000001) {
if (mid * mid == value) {
return mid;
}
if (mid * mid > value) {
high = mid;
} else {
low = mid;
}
mid = (low + high) / 2;
}
return mid;
}
}
What this will do is just go through each character in the string; adding each value to the result. If it is bigger than the previous character, it will subtract 2 * the previous result because you added it once already when you were looking at the previous result.
import java.util.HashMap;
import java.util.Map;
public class RomanNumber {
final static Map<Character, Integer> romanNumberMap = new HashMap<Character, Integer>() {
{
this.put('I', 1);
this.put('V', 5);
this.put('X', 10);
this.put('L', 50);
this.put('C', 100);
this.put('D', 500);
this.put('M', 1000);
}
};
public static void main(String...args) {
System.out.println("I=" + romanNumber("I"));
System.out.println("III=" + romanNumber("III"));
System.out.println("VI=" + romanNumber("VI"));
System.out.println("XVI=" + romanNumber("XVI"));
System.out.println("IV=" + romanNumber("IV"));
System.out.println("IX=" + romanNumber("IX"));
System.out.println("XIV=" + romanNumber("XIV"));
System.out.println("LXIV=" + romanNumber("LXIV"));
}
public static int romanNumber(String roman) {
int result = 0;
char[] romanChars = roman.toCharArray();
char prevChar = '\0';
for (Character c : romanChars) {
if (!romanNumberMap.containsKey(c)) {
throw new IllegalArgumentException("Not a valid roman number");
}
result += romanNumberMap.get(c);
if (prevChar != '\0' && romanNumberMap.get(prevChar) < romanNumberMap.get(c)) {
result -= romanNumberMap.get(prevChar) * 2;
}
prevChar = c;
}
return result;
}
}
I think this is pretty much just the problem where you are given a list of intervals, and a single interval and you just want to merge the interval into this list of intervals. You just have to loop through each interval in your iterator and then add the amount covered to your running total.
The only trick is to keep the running total space covered which isn't really too bad.
In other words, the pseudocode is something like
The java 8 implementation using a priority queue to handle sorting:
- liuben10 October 31, 2017