面试+算法：罗马数字及Excel列名与数字互相转换

概述

算法是一个程序员的核心竞争力，也是面试最重要的考查环节。

试题

判断一个罗马数字是否有效

罗马数字包含七种字符：I，V，X，L，C，D和M，如下

字符	数值
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

规则：

1. 不能出现连续相同的4个及以上字符，但是IIII=4，MMMM=4000除外；
2. 不能存在特定组合，如DD，因为DD=M；
3. 小数字只能在大数字的右边，表示这些数字相加得到的数；
4. 但存在违反上述规则的特例：小数字在大数字的左边，表示大数减小数得到的数，只适用于以下六种情况：
   • I 可以放在 V(5) 和 X (10) 的左边，表示4和9；
   • X 可以放在 L(50) 和 C (100) 的左边，表示40和90
   • C 可以放在 D(500) 和 M (1000) 的左边，表示400和900

在线阿拉伯数字和罗马数字互相转换
https://www.onlineconversion.com/roman_numerals_advanced.htm

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

罗马数字最大只能表示到4999。

比如输入：LVIIID，系统提示：LVIIID is not a valid input

https://www.luomashuzi.com/

使用正则表达式来判断一个给定的字符串是不是合法的罗马数字字符串：

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})");
}

阿拉伯数字转罗马数字

将一个阿拉伯数字转换成罗马数字，显然需要考虑罗马数字的有效性问题。

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;
}/*** 重复多次*/
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();
}

罗马数字转数字

给定一个罗马数字表示的字符串，将其转换成数字，即阿拉伯数字。

注：可以假定给定的罗马数字字符串是合法的。

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;
}

数字转Excel列

给定一个数字将其转换成Excel里面的列。

背景知识：

• Excel的行是用阿拉伯数字表示，列则用大写英文字母表示；
• 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列转数字

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;
}

参考

• 检查罗马数字的有效性