整数转罗马数字

该题目可以用背包问题的方法解决（贪心）。为了方便理解，此处用递归的方式来解决问题。大概意思就是给出一个指定的数，然后在一堆数中找出合为该数的集合，再映射成为罗马字母即可。从大到小，第一次满足的集合就是最优解。

import java.util.*;
public class Solution {
    Map<Integer, String> map;
    String resr = "";
    public String ArabicToRoman (int n) {
        map = new HashMap<>();
        map.put(1, "I");
        map.put(4, "IV");
        map.put(5, "V");
        map.put(9, "IX");
        map.put(10, "X");
        map.put(40, "XL");
        map.put(50, "L");
        map.put(90, "XC");
        map.put(100, "C");
        map.put(400, "CD");
        map.put(500, "D");
        map.put(900, "CM");
        map.put(1000, "M");
        int arry[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        func("", n, arry, 0);
        return resr;
    }
    void func(String res, int num, int[] array, int index) {
        if(resr != "")return;//加这个判断是为了防止重复计算
        if(index >= array.length)return;
        if(num == 0) {
            resr = res;
            return;
        }
        for(int i = index; i < array.length; ++i) {
            if(num - array[i] < 0) continue;
            else func(res + map.get(array[i]), num - array[i], array, i);
        }
    }
}

public String ArabicToRoman (int n) {
        // write code here
        int[] nums = new int[]{1000,900,500,400,100,90,50,40,10,9,5,4,1};
        String[] strs = new String[]{"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        StringBuilder sb = new StringBuilder("");
        int i=0;
        while(n!=0){
            while(i<nums.length && n<nums[i]){
                i++;
            }
            sb.append(strs[i]);
            n-=nums[i];
        }
        return sb.toString();
    }

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型
# @return string字符串
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/7649cde9711f42da81209819b790a640?tpId=196&tqId=40451&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    参考：
        大神：牛客849220173号
    算法：
        1. 建立哈希表，键：数字，值：数字对应的罗马数字，总共有13种关键数字，使用nums存储这13种数字，按照从大到小顺讯
        2. 遍历nums：
            若n == num，刚好解析完成；
            否则，若n > num，进行整除和取余操作，累加结果
    复杂度：
        时间复杂度：O(1)
        空间复杂度：O(1)
    """

    def ArabicToRoman(self, n):
        # write code here
        hashMap = {1000: "M", 900: "CM", 500: "D", 400: "CD", 100: "C", 90: "XC", 50: "L", 40: "XL", 10: "X", 9: "IX",
                   5: "V", 4: "IV", 1: "I", }
        nums = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]

        res = ""
        for num in nums:
            if n == num:
                res += hashMap[n]
                break
            elif n > num:
                count = n / num
                res += hashMap[num] * count
                n %= num

        return res


if __name__ == "__main__":
    sol = Solution()

    # n = 5

    # n = 6

    # n = 3049

    n = 3999

    res = sol.ArabicToRoman(n)

    print res