概述

算法是一個(gè)程序員的核心競(jìng)爭(zhēng)力，也是面試最重要的考查環(huán)節(jié)。

試題

判斷一個(gè)羅馬數(shù)字是否有效

羅馬數(shù)字包含七種字符：I，V，X，L，C，D和M，如下

字符	數(shù)值
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

規(guī)則：

1. 不能出現(xiàn)連續(xù)相同的4個(gè)及以上字符，但是IIII=4，MMMM=4000除外；
2. 不能存在特定組合，如DD，因?yàn)镈D=M；
3. 小數(shù)字只能在大數(shù)字的右邊，表示這些數(shù)字相加得到的數(shù)；
4. 但存在違反上述規(guī)則的特例：小數(shù)字在大數(shù)字的左邊，表示大數(shù)減小數(shù)得到的數(shù)，只適用于以下六種情況：
   • I 可以放在 V(5) 和 X (10) 的左邊，表示4和9；
   • X 可以放在 L(50) 和 C (100) 的左邊，表示40和90
   • C 可以放在 D(500) 和 M (1000) 的左邊，表示400和900

在線阿拉伯?dāng)?shù)字和羅馬數(shù)字互相轉(zhuǎn)換
https://www.onlineconversion.com/roman_numerals_advanced.htm

The input must be in the range of 1 - 4999, or I to MMMMCMXCIX.

羅馬數(shù)字最大只能表示到4999。

比如輸入：LVIIID，系統(tǒng)提示：LVIIID is not a valid input

https://www.luomashuzi.com/

使用正則表達(dá)式來判斷一個(gè)給定的字符串是不是合法的羅馬數(shù)字字符串：

public static boolean isRoman(String s) {return !s.isEmpty()&& s.matches("M{0,4}(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})");
}

阿拉伯?dāng)?shù)字轉(zhuǎn)羅馬數(shù)字

將一個(gè)阿拉伯?dāng)?shù)字轉(zhuǎn)換成羅馬數(shù)字，顯然需要考慮羅馬數(shù)字的有效性問題。

public static String convertToRoman(int num) {if (num >= 5000) {return "";}String result = "";if (num >= 1000) {result = repeat("M", (int) Math.floor(1.0 * num / 1000));num %= 1000;}if (num >= 100) {result += geneBase((int) Math.floor(1.0 * num / 100), new String[]{"C", "D", "M"});num %= 100;}if (num >= 10) {result += geneBase((int) Math.floor(1.0 * num / 10), new String[]{"X", "L", "C"});num %= 10;}if (num >= 1) {result += geneBase((int) Math.floor(num), new String[]{"I", "V", "X"});}return result;
}private static String geneBase(int num, String[] arr) {String result = "";if (num >= 1 && num <= 3) {result = repeat(arr[0], num);}if (num == 4) {result = arr[0] + "" + arr[1];}if (num >= 5 && num <= 8) {result = arr[1] + "" + repeat(arr[0], num - 5);}if (num == 9) {result = arr[0] + "" + arr[2];}return result;
}/*** 重復(fù)多次*/
private static String repeat(String str, int count) {StringBuilder result = new StringBuilder();for (int i = 0; i < count; i++) {result.append(str);}return result.toString();
}

羅馬數(shù)字轉(zhuǎn)數(shù)字

給定一個(gè)羅馬數(shù)字表示的字符串，將其轉(zhuǎn)換成數(shù)字，即阿拉伯?dāng)?shù)字。

注：可以假定給定的羅馬數(shù)字字符串是合法的。

public static int romanToInt(String s) {int n = 0;for (int i = 0; i < s.length(); ) {char c = s.charAt(i);if (c == 'I') {if (i + 1 < s.length()) {if (s.charAt(i + 1) == 'V') {n += 4;i += 2;} else if (s.charAt(i + 1) == 'X') {n += 9;i += 2;} else {n += 1;i++;}} else {n += 1;i++;}} else if (c == 'X') {if (i + 1 < s.length()) {if (s.charAt(i + 1) == 'L') {n += 40;i += 2;} else if (s.charAt(i + 1) == 'C') {n += 90;i += 2;} else {n += 10;i++;}} else {n += 10;i++;}} else if (c == 'C') {if (i + 1 < s.length()) {if (s.charAt(i + 1) == 'D') {n += 400;i += 2;} else if (s.charAt(i + 1) == 'M') {n += 900;i += 2;} else {n += 100;i++;}} else {n += 100;i++;}} else if (c == 'V') {n += 5;i++;} else if (c == 'L') {n += 50;i++;} else if (c == 'D') {n += 500;i++;} else if (c == 'M') {n += 1000;i++;}}return n;
}

數(shù)字轉(zhuǎn)Excel列

給定一個(gè)數(shù)字將其轉(zhuǎn)換成Excel里面的列。

背景知識(shí)：

• Excel的行是用阿拉伯?dāng)?shù)字表示，列則用大寫英文字母表示；
• Excel 2003最多有65536行，256列；
• Excel 2007、2010最多有1048576行，16384列；
• 列用A到Z表示，第27列是AA，第53列是BA，第26 + 26 * 26 + 1列是AAA，以此類推……最后一列是XFD
  

public static String convertToTitle(int n) {if (n <= 0) {return "";}StringBuilder sb = new StringBuilder();while (n > 0) {n--;sb.append((char) (n % 26 + 'A'));n = n / 26;}return sb.reverse().toString();
}

Excel列轉(zhuǎn)數(shù)字

public static int excelColumnNameToNumber(String columnName) {int sum = 0;if (columnName.equals("")) {return sum;}for (int i = 0; i < columnName.length(); i++) {sum *= 26;sum += (columnName.charAt(i) - 'A' + 1);}return sum;
}

參考

• 檢查羅馬數(shù)字的有效性