20190530 leetcode day2

[xinrong2019]

Roman to Integer

Description Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9. X can be placed before L (50) and C (100) to make 40 and 90. C can be placed before D (500) and M (1000) to make 400 and 900. Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: "III" Output: 3

Example 2:

Input: "IV" Output: 4

Example 3:

Input: "IX" Output: 9

Example 4:

Input: "LVIII" Output: 58 Explanation: C = 100, L = 50, XXX = 30 and III = 3.

Example 5:

Input: "MCMXCIV" Output: 1994 Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Tags: Math, String

leetcode

思路

题意是罗马数字转整型数，范围从 1 到 3999，查看下百度百科的罗马数字介绍如下：

• 相同的数字连写，所表示的数等于这些数字相加得到的数，如 Ⅲ=3；

• 小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数，如 Ⅷ=8、Ⅻ=12；

• 小的数字（限于 Ⅰ、X 和 C）在大的数字的左边，所表示的数等于大数减小数得到的数，如 Ⅳ=4、Ⅸ=9。

那么我们可以利用 map 来完成罗马数字的 7 个数字符号：I、V、X、L、C、D、M 和整数的映射关系，然后根据上面的解释来模拟完成即可。

class Solution {
    public int romanToInt(String s) {
        Map<Character, Integer> map = new HashMap<>();
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);
        int len = s.length();
        int sum = map.get(s.charAt(len - 1));
        for (int i = len - 2; i >= 0; --i) {
            if (map.get(s.charAt(i)) < map.get(s.charAt(i + 1))) {
                sum -= map.get(s.charAt(i));
            } else {
                sum += map.get(s.charAt(i));
            }
        }
        return sum;
    }
}

代码分析：

1、维护一个罗马数字到阿拉伯数字的映射关系

2、从右往左，获取右边第一位罗马数字对应的阿拉伯数字

3、从右边第二位开始，逐个遍历，直到最左边

4、每次遍历，比较当前字母对应的阿拉伯数字和其后面一位的数字大小，如果小于后面，就用累加值减当前数字，否则用累加值加当前数字

思路1：

class Solution {
    public int romanToInt(String s) {
        int sum=0;
        int len = s.length();
    int result = 0;
    for (int i = len - 1; i >= 0; i--) {
      switch (s.charAt(i)) {
        case 'I':
          result += 1;
          break;

        case 'V':
          result += 5;
          if (i != 0 && s.charAt(i - 1) == 'I') {
            result -= 1;
            i--;
          }
          break;

        case 'X':
          result += 10;
          if (i != 0 && s.charAt(i - 1) == 'I') {
            result -= 1;
            i--;
          }
          break;
        case 'L':
          result += 50;
              if (i != 0 && s.charAt(i - 1) == 'X') {
            result -= 10;
            i--;
          }
          break;
        case 'C':
          result += 100;
              if (i != 0 && s.charAt(i - 1) == 'X') {
            result -= 10;
            i--;
          }
          break;

        case 'D':
          result += 500;
              if (i != 0 && s.charAt(i - 1) == 'C') {
            result -= 100;
            i--;
          }
          break;

        case 'M':
          result += 1000;
              if (i != 0 && s.charAt(i - 1) == 'C') {
            result -= 100;
            i--;
          }
          break;

        default:
          break;
      }
    }
    return result;
    }
}

思路2：

class Solution {

    private static final Map<Character, Integer> symbols = new HashMap<>();
    static {
        symbols.put('I', 1);
        symbols.put('V', 5);
        symbols.put('X', 10);
        symbols.put('L', 50);
        symbols.put('C', 100);
        symbols.put('D', 500);
        symbols.put('M', 1000);
    }
    public int romanToInt(String s) {
        if (s == null) {
            return 0;
        }

        int sum = 0;
        char[] chars = s.toCharArray();

        // 倒序可以减少访问map的次数
        int i = s.length() - 1;
        int thisInt;
        int last = 0;
        while (i >= 0) {
            thisInt = symbols.get(chars[i]);
            if (thisInt < last) {
                sum -= thisInt;
            } else {
                sum += thisInt;
            }
            last = thisInt;
            i--;
        }
        return sum;
    }
}

[xinrong2019]

Longest Common Prefix

Description

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: ["flower","flow","flight"] Output: "fl"

Example 2:

Input: ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

Tags: String

思路

题意是让你从字符串数组中找出公共前缀，我的想法是找出最短的那个字符串的长度 minLen，然后在 0...minLen 的范围比较所有字符串，如果比较到有不同的字符，那么直接返回当前索引长度的字符串即可，否则最后返回最短的字符串即可。

class Solution {
    public String longestCommonPrefix(String[] strs) {
        int len = strs.length;
        if (len == 0) return "";
        int minLen = 0x7fffffff;
        for (String str : strs) minLen = Math.min(minLen, str.length());
        for (int j = 0; j < minLen; ++j)
            for (int i = 1; i < len; ++i)
                if (strs[0].charAt(j) != strs[i].charAt(j))
                    return strs[0].substring(0, j);
        return strs[0].substring(0, minLen);
    }
}

小结：

1、计算整数的最小值最大值，可以直接借助Math.min和Math.max函数

2、外层循环控制循环多少位，内层循环遍历字符串数组，拿字符串数组的第一位和后面的比较，只要有不想等的就直接返回一个初始位置到遍历位置的截取字符

官网给了好几种解法，可以学一下不同的思路

[xinrong2019]

Valid Parentheses

Description

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Note that an empty string is also considered valid.

Example 1:

Input: "()" Output: true

Example 2:

Input: "()[]{}" Output: true

Example 3:

Input: "(]" Output: false

Example 4:

Input: "([)]" Output: false

Example 5:

Input: "{[]}" Output: true

Tags: Stack, String

思路

题意是判断括号匹配是否正确，很明显，我们可以用栈来解决这个问题，当出现左括号的时候入栈，当遇到右括号时，判断栈顶的左括号是否和其匹配，不匹配的话直接返回 false 即可，最终判断是否空栈即可，这里我们可以用数组模拟栈的操作使其操作更快，有个细节注意下 top = 1;，从而省去了之后判空的操作和 top - 1 导致数组越界的错误。

class Solution {
    public boolean isValid(String s) {
        char[] stack = new char[s.length() + 1];
        int top = 1;
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack[top++] = c; 
            } else if (c == ')' && stack[--top] != '(') {
                return false;
            } else if (c == ']' && stack[--top] != '[') {
                return false;
            } else if (c == '}' && stack[--top] != '{') {
                return false;
            }
        }
        return top == 1;
    }
}

[xinrong2019]

回顾：

1、上午有人提交了一个IDEA文件，导致所有人pull失败，花了很长时间解决冲突，最后在我本地，使用tortosegit 执行delete(keep local)，然后将文件的删除状态推送到远端仓库，大家可以pull了

2、下午给gpis替换flash插件，插件在用户使用的时候不定期失效，要手动开启，换成了h5的插件

3、晚上下班回来，打了会球，然后回来洗澡，吃饭，吃饭的时候，老婆快到了，我去接她。吃过了玩游戏，做leetcode题。