面试经典150题——数组/字符串（三）

1、罗马数字转整数

1.1 题目链接

点击跳转到题目位置

1.2 题目描述

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符    数值
I      1
V     5
X     10
L     50
C     100
D     500
M     1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

• I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
• X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
• C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。

提示：

• 1 <= s.length <= 15
• s 仅含字符 (‘I’, ‘V’, ‘X’, ‘L’, ‘C’, ‘D’, ‘M’)
• 题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内
• 题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
• IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
• 关于罗马数字的详尽书写规则，可以参考 罗马数字 - 百度百科。

1.3 解题代码

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

1.4 解题思路

1. 先用HashMap将罗马数字和阿拉伯数字映射起来。
2. 然后遍历字符串，如果是最后一位直接加上就行了，如果不是，获取当前一位数字num1和下一位数字num2，如果num1 > num2.则最后结果加上num1，继续遍历进行了，如果num1 小于 num2，则加上num2 - num1，跳过下一位继续进行计算。

2、整数转罗马数字

2.1 题目链接

点击跳转到题目位置

2.2 题目描述

七个不同的符号代表罗马数字，其值如下：

符号     值
I         1
V        5
X       10
L        50
C      100
D      500
M       1000
罗马数字是通过添加从最高到最低的小数位值的转换而形成的。将小数位值转换为罗马数字有以下规则：

• 如果该值不是以 4 或 9 开头，请选择可以从输入中减去的最大值的符号，将该符号附加到结果，减去其值，然后将其余部分转换为罗马数字。
• 如果该值以 4 或 9 开头，使用 减法形式，表示从以下符号中减去一个符号，例如 4 是 5 (V) 减 1 (I): IV ，9 是 10 (X) 减 1 (I)：IX。仅使用以下减法形式：4 (IV)，9 (IX)，40 (XL)，90 (XC)，400 (CD) 和 900 (CM)。
• 只有 10 的次方（I, X, C, M）最多可以连续附加 3 次以代表 10 的倍数。你不能多次附加 5 (V)，50 (L) 或 500 (D)。如果需要将符号附加4次，请使用 减法形式。

给定一个整数，将其转换为罗马数字。

提示：

• 1 <= num <= 3999

2.3 解题代码

class Solution {
    int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

    public String intToRoman(int num) {
        StringBuffer sb = new StringBuffer();
        int n = values.length;
        while(num > 0){
            for(int i = 0; i < n; ++i){
                if(num >= values[i]){
                    sb.append(symbols[i]);
                    num -= values[i];
                    break;
                } 
            }
        }
    return sb.toString();
    }
}

2.4 解题思路

1. 将罗马数字中的不停表示按从大到小进行排序。
2. 然后一直从左往右遍历，每次都添加最大的数的罗马形式。

3、最后一个单词的长度

3.1 题目链接

点击跳转到题目位置

3.2 题目描述

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。

单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

提示：

• 1 <= s.length <= 10⁴
• s 仅有英文字母和空格 ’ ’ 组成
• s 中至少存在一个单词

3.3 解题代码

class Solution {
    public int lengthOfLastWord(String s) {
        int ret = 0;
        int num = 0;
        for(int i = 0; i < s.length(); ++i){
            if(s.charAt(i) != ' '){
                num++;
            } else{
                if(num != 0){
                    ret = num;
                }
                num = 0;
            }
        }
        if(num != 0){
            ret = num;
        }
    return ret;
    }
}

3.4 解题思路

1. 一次遍历字符串。
2. 记录最后结果为ret，用num表示当前遍历的单词长度。
3. 如果碰到空字符串，如果num存在值，则将ret赋值为num，否则的话不赋值，最终num清空。
4. 如果遍历完了，需要再判断num是否为0，如果不为0则最后一个单词长度没有赋值给ret，需要给ret赋值一下。

4、最长公共前缀

4.1 题目链接

点击跳转到题目位置

4.2 题目描述

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

提示：

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] 仅由小写英文字母组成

4.3 解题代码

class Solution {
    public String longestCommonPrefix(String[] strs) {
        StringBuffer sb = new StringBuffer();
        int min_len = 300;
        for(int i = 0; i < strs.length; ++i){
            min_len = Math.min(min_len, strs[i].length());
        }
        for(int i = 0; i < min_len; ++i){
            char ch = strs[0].charAt(i);
            int flag = 0;
            for(int j = 1; j < strs.length; ++j){
                if(strs[j].charAt(i) != ch){
                    flag = 1;
                    break;
                }
            }
            if(flag == 1){
                break;
            }
            sb.append(ch);
        }
    return sb.toString();
    }
}

4.4 解题思路

1. 首先求出所有字符串的最小长度
2. 接着两层循环，外层按长度遍历，内层遍历判断每一个字符串的当前位置的字符是否相等，如果不相等，则直接返回最终结果，否则就将该字符添加进结果字符串中。

5、反转字符串中的单词

5.1 题目链接

点击跳转到题目位置

5.2 题目描述

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意： 输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

提示：

• 1 <= s.length <= 10⁴
• s 包含英文大小写字母、数字和空格 ’ ’
• s 中 至少存在一个 单词

5.3 解题代码

class Solution {
     public String reverseWords(String s) {
        s = s.trim();
        int n = s.length();
        StringBuilder sub = new StringBuilder();
        StringBuilder ans = new StringBuilder();
        for(int i = 0; i < n; i++){
            if(s.charAt(i) != ' '){
                sub.append(s.charAt(i));
            }else if(sub.toString().length() > 0){
                ans.insert(0, sub.toString());
                ans.insert(0, ' ');
                sub.setLength(0);
            }
        }
        ans.insert(0,sub.toString());
        return ans.toString();
    }
}

5.4 解题思路

1. 首先先去除掉字符串的前后空格。
2. 接着遍历出字符串中的每个单词（遇到空格就将该字符串放到结果字符串ans的开头）。
3. 最后返回的结果就是逆序的。

6、Z 字形变换

6.1 题目链接

点击跳转到题目位置

6.2 题目描述

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“PAHNAPLSIIGYIR”。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

提示：

• 1 <= s.length <= 1000
• s 由英文字母（小写和大写）、‘,’ 和 ‘.’ 组成
• 1 <= numRows <= 1000

6.3 解题代码

class Solution {
    public String convert(String s, int numRows) {
        StringBuffer sb = new StringBuffer();
        int n = s.length();
        if(numRows <= 1){
            return s;
        }
        List<StringBuffer> rows = new ArrayList<StringBuffer>(); 
        for(int i = 0; i < numRows; i++){
            rows.add(new StringBuffer());
        }
        int flag = 0;
        int y = 0;
        for(int i = 0; i < n; ++i){
            rows.get(y).append(s.charAt(i));
            if(flag == 0){
                if(y == numRows - 1){
                    flag = 1;
                    y--;
                } else{
                    y++;
                }
            } else{
                if(y == 0){
                    flag = 0;
                    y++;
                } else{
                    y--;
                }
            }
        }
        for(int i = 0; i < numRows; ++i){
            sb.append(rows.get(i));
        }
    return sb.toString();
    }
}

6.4 解题思路

1. 模拟进行遍历，按照从上到下，再从下到上的顺序进行模拟，然后用flag来调控方向，flag等于0表示向下遍历，flag等于1表示向上遍历。
2. 最后在List rows = new ArrayList();中获取每一行的字符串。
3. 最后拼接成为逐行读取的字符串。

7、找出字符串中第一个匹配项的下标

7.1 题目链接

点击跳转到题目位置

7.2 题目描述

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

提示：

• 1 <= haystack.length, needle.length <= 10⁴
• haystack 和 needle 仅由小写英文字符组成

7.3 解题代码

class Solution {
    public int strStr(String haystack, String needle) {
        for(int i = 0; i < haystack.length(); ++i){
            int flag = 0;
            if(i + needle.length() > haystack.length()){
                break;
            }
            for(int j = 0; j < needle.length(); ++j){
                if(haystack.charAt(i + j) != needle.charAt(j)){
                    flag = -1;
                    break;
                }
            }
            if(flag == 0){
                return i;
            }
        }
    return -1;
    }
}

7.4 解题思路

1. KMP算法解决。

8、文本左右对齐

8.1 题目链接

点击跳转到题目位置

8.2 题目描述

给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ’ ’ 填充，使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐，且单词之间不插入额外的空格。

注意:

• 单词是指由非空格字符组成的字符序列。
• 每个单词的长度大于 0，小于等于 maxWidth。
• 输入单词数组 words 至少包含一个单词。

8.3 解题代码

8.4 解题思路