每天一道算法题

LeetCode第12题：整数转罗马数字

这道题搞了个比较妖的解法，虽然妖路但是耗时还是击败了91.37%的用户，各位看看这种方式，也可以去看看官方的其他解法

/**
     * 提前一轮处理9，避免9被5除了不好处理
     * 4和其他情况直接当轮处理即可，比较简单
     */
    public static String intToRoman(int num) {
        int[] key = new int[]{1000, 500, 100, 50, 10, 5, 1};
        char[] value = new char[]{'M', 'D', 'C', 'L', 'X', 'V', 'I'};
        StringBuilder ans = new StringBuilder();
        int start = 0;
        while (num != 0) {
            for (int i = start; i < key.length; i++) {
                int last = num / key[i];
                if (last == 0) {
                    // 处理9
                    int k = key[i] / 10;
                    int rel = key[i] >= 10 ? num / k : num;
                    if (rel == 9 && key[i] / key[i+1] == 2) {
                        ans.append(value[i + 2]).append(value[i]);
                        num = num - 9 * key[i] / 10;
                        break;
                    }
                    start = i;
                } else {
                    // 处理4
                    if (last == 4){
                        ans.append(value[i]).append(value[i-1]);
                    }else {
                        for (int j = 0; j < last; j++) {
                            ans.append(value[i]);
                        }
                    }
                    num = num % (last * key[i]);
                    break;
                }
            }
        }
        return ans.toString();
    }