ARTS 打卡 (20.09.07-20.09.13)

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i][j - 2];
                    if (matches(s, p, i, j - 1)) {
                        f[i][j] = f[i][j] || f[i - 1][j];
                    }
                }
                else {
                    if (matches(s, p, i, j)) {
                        f[i][j] = f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }
    public boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }
}

class Solution {
    public String intToRoman(int num) {
        String result = "";
        Map<Integer, String> relation = new HashMap<>();
        relation.put(1, "I");
        relation.put(5, "V");
        relation.put(10, "X");
        relation.put(50, "L");
        relation.put(100, "C");
        relation.put(500, "D");
        relation.put(1000, "M");
        boolean b = true;
        int temp = 0;
        int times = 1;
        while (b) {
            temp = num % 10;
            num = num / 10;
            if (num == 0) {
                b = false;
            }
            for (int i = 1; i <= temp; i++) {
                if(temp == 4 || temp == 9) {
                    result = relation.get(times) + relation.get((temp + 1) * times) + result;
                    break;
                } else if (temp < 4) {
                    for (int j = 0; j < temp; j++) {
                        result = relation.get(times) + result;
                    }
                    break;
                } else if (temp == 5) {
                    result = relation.get(times * temp) + result;
                    break;
                } else if( temp > 5 && temp < 9) {
                    String tempResult = relation.get(5 * times);
                    for (int j = 5; j < temp; j++) {
                        tempResult = tempResult + relation.get(times);
                    }
                    result = tempResult + result;
                    break;
                }
            }
            times *= 10;
        }
        return result;
    }
}

public static String solution(int num) {
        int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] romans = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        StringBuilder stringBuilder = new StringBuilder();
        int index = 0;
        while (index < 13) {
            // 特别注意：这里是等号
            while (num >= nums[index]) {
                // 注意：这里是等于号，表示尽量使用大的"面值"
                stringBuilder.append(romans[index]);
                num -= nums[index];
            }
            index++;
        }
        return stringBuilder.toString();
    }

public class Elvis {
		private static final Elvis INSTANCE = new Elvis();
		private Elvis() { ... }
		public static Elvis getInstance() { return INSTANCE; }
		public void leaveTheBuilding() { ... }
}