dev.yeison
BAN USERThe space can be improved a small bit, but this is a practical solution.
public class Roman {
private static Map<Character, Integer> lookupMap = new HashMap<>();
static {
lookupMap.put('I', 1);
lookupMap.put('V', 5);
lookupMap.put('X', 10);
lookupMap.put('L', 50);
lookupMap.put('C', 100);
lookupMap.put('D', 500);
lookupMap.put('M', 1000);
}
public static void main(String[] args){
String[] tests = new String[]{
"IV",
"XII",
"XL",
"XX",
"LXXX",
"LXL"
};
for(String s : tests){
out.println(s);
out.println(getInteger(s));
out.println(getRoman(getInteger(s)));
System.out.println();
}
}
private static int getInteger(String roman){
int sum = 0;
int previous = 0;
for(int i = roman.length()-1; i >= 0; i--){
char c = roman.charAt(i);
int value = lookupMap.get(c);
if(previous > value){
sum -= value;
} else {
sum += value;
}
previous = value;
}
return sum;
}
private static int[] values = new int[]{1000, 500, 100, 50, 10, 5, 1};
private static char[] romans = new char[]{'M', 'D', 'C', 'L', 'X', 'V', 'I'};
private static String getRoman(int integer){
StringBuilder sb = new StringBuilder();
int[] romanCount = new int[romans.length];
for(int i = 0; i < values.length; i++) {
int val = values[i];
char roman = romans[i];
int quotient = integer / val;
for (int j = 0; j < quotient; j++) {
romanCount[i]++;
}
integer -= quotient * val;
}
out.println(Arrays.toString(romanCount));
for(int i = 0; i < romanCount[0]; i++){
sb.append(romans[i]);
}
for(int i = 0; i < romanCount.length; i++){
int count = romanCount[i];
if(count == 4){
sb.append(romans[i]);
sb.append(romans[i-1]);
} else {
for(int j = 0; j < romanCount[i]; j++){
sb.append(romans[i]);
}
}
}
return sb.toString();
}
}
@jerryyue1908 - Yes it is possible to optimize with DP. The optimization will be to memoize the result of decode on a substring (e.g. "123" in "121123"). This way, whenever decode("123") is called, the previous result can be retrieved instead of doing the computation over again.
- dev.yeison January 23, 2015The runtime complexity is O(2N) which is O(N)
The space complexity is O(1)
/** Created by yeison on 1/19/2015. */
public class ReverseInPlace {
public static void main(String[] args){
char[] s1 = "I am floating in a tin can.".toCharArray();
// The result will be "can. tin a in floating am I"
reverseSentence(s1);
System.out.println(s1);
}
/** Reverses the order of the words in a sentence in place
* so that a sentence such as: "This is an example" will end up
* as "example an is This" . */
public static void reverseSentence(char[] sentence){
// First reverse the whole string
reverseString(sentence, 0, sentence.length);
// Then reverse each word
for (int i = 0, start = 0; i < sentence.length; i++) {
if(sentence[i] == ' '){
reverseString(sentence, start, i);
start = i+1;
}
}
}
public static void reverseString(char[] string, int start, int end){
for (int i = start, j = end-1; i < start + (end-start)/2; i++, j--) {
swap(string, i,j);
}
}
private static void swap(char[] string, int i, int j) {
char temp = string[i];
string[i] = string[j];
string[j] = temp;
}
}
- dev.yeison March 18, 2018