力扣刷题日常(13-14)

第13题: 罗马数字转整数 (难度:简单)

原题:

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

1
2
3
4
5
6
7
8
字符          数值
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:

1
2
输入: s = "III"
输出: 3

示例 2:

1
2
输入: s = "IV"
输出: 4

示例 3:

1
2
输入: s = "IX"
输出: 9

示例 4:

1
2
3
输入: s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:

1
2
3
输入: s = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：

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

开始解题

那么这个题与昨天的12题十分相似,就是逆向操作

那么将罗马数字转换为整数,核心在于如何处理那六种特殊的"减法"情况 (如 IV 是 4, CM 是 900). 如果没有这些特殊情况, 我们只需要把每个罗马字符代表的数字加起来就行了.

一个非常巧妙且直观的思路是从右向左遍历这个罗马数字字符串. 为什么从右向左呢? 因为一个字符是应该被加还是被减, 取决于它右边的字符.

让我们来构思一下这个从右到左的逻辑:

  1. 建立映射: 首先, 我们需要一个能快速查询到每个罗马字符对应整数值的方法. 比如, 输入 ‘V’, 就能立刻得到 5. 在编程中, 这通常用一个哈希表 (Dictionary) 或一个 switch 语句来实现.

  2. 处理最后一个字符: 罗马数字最右边的那个字符, 它的右边没有其他字符了, 所以它永远代表的是加法. 我们可以用它的值作为我们计算的初始值.

  3. 从右向左遍历: 我们从字符串的倒数第二个字符开始, 一直遍历到第一个字符. 在每一步, 我们都将当前字符的值与它右边一个字符的值进行比较.

  4. 判断与操作: 假设我们当前遍历到的字符是 current, 它右边的字符是 right.

    • 如果 current 的值大于或等于 right 的值: 这说明是一个正常的, 从大到小的排列 (例如 VI 中的 ‘V’, XI 中的 ‘X’). 这种情况下, 我们就将 current 的值加上去.
    • 如果 current 的值小于 right 的值: 这就命中了我们的特殊"减法"规则 (例如 IV 中的 ‘I’, IX 中的 ‘I’). 这种情况下, 我们就将 current 的值减掉.

让我们用 “MCMXCIV” 这个例子来走一遍这个流程:

  • 输入: “MCMXCIV”
  • 1. 初始化: 先看最右边的 ‘V’. 它的值是 5. 我们的总和 result 初始化为 5.
  • 2. 向左移动: 看 ‘V’ 左边的 ‘I’.
    • ‘I’ 的值是 1. 它右边 ‘V’ 的值是 5.
    • 因为 1 < 5, 所以执行减法. result = 5 - 1 = 4.
  • 3. 向左移动: 看 ‘I’ 左边的 ‘C’.
    • ‘C’ 的值是 100. 它右边 ‘I’ 的值是 1.
    • 因为 100 > 1, 所以执行加法. result = 4 + 100 = 104.
  • 4. 向左移动: 看 ‘C’ 左边的 ‘X’.
    • ‘X’ 的值是 10. 它右边 ‘C’ 的值是 100.
    • 因为 10 < 100, 所以执行减法. result = 104 - 10 = 94.
  • 5. 向左移动: 看 ‘X’ 左边的 ‘M’.
    • ‘M’ 的值是 1000. 它右边 ‘X’ 的值是 10.
    • 因为 1000 > 10, 所以执行加法. result = 94 + 1000 = 1094.
  • 6. 向左移动: 看 ‘M’ 左边的 ‘C’.
    • ‘C’ 的值是 100. 它右边 ‘M’ 的值是 1000.
    • 因为 100 < 1000, 所以执行减法. result = 1094 - 100 = 994.
  • 7. 向左移动: 看 ‘C’ 左边的 ‘M’.
    • ‘M’ 的值是 1000. 它右边 ‘C’ 的值是 100.
    • 因为 1000 > 100, 所以执行加法. result = 994 + 1000 = 1994.
  • 8. 结束: 遍历完成, 最终结果是 1994.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class Solution {
    public int RomanToInt(string s) {
        // 1. 使用 Dictionary 建立字符到数值的映射
        Dictionary<char,int> rome = new Dictionary<char,int>
        {
            {'I', 1},
            {'V', 5},
            {'X', 10},
            {'L', 50},
            {'C', 100},
            {'D', 500},
            {'M', 1000}
        };
      
        int result = 0;
        // 2. 从右向左遍历, 先处理最右边的值
        char rightChar = s[s.Length - 1];
        int rightValue = rome[rightChar];
        result = rightValue;

        // 3. 从倒数第二个字符开始向左循环
        for(int i = s.Length - 2; i >= 0; i --)
        {
            char currentChar = s[i];
            int currentValue = rome[currentChar];

            // 4. 核心逻辑: 与右边的值比较
            if(currentValue < rightValue)
            {
                result -= currentValue; // 小于则减
            }
            else
            {
                result += currentValue; // 大于或等于则加
            }
            // 5. 更新 rightValue, 为下一次循环做准备
            rightValue = currentValue;
        }
        return result;
    }
}

可能的实际应用:

  1. Dictionary / switch (键值映射):
    • 输入系统: 在Unity中, 我们可以使用 Dictionary<KeyCode, System.Action> 来构建一个灵活的按键绑定系统, 按下某个键时, 执行对应的委托(Action).
    • 本地化: 游戏需要支持多国语言时, 可以用 Dictionary<string, string> 来存储文本的键(如 “MENU_START”)和对应语言的值(如 “开始游戏”).
    • 对象池: 使用 Dictionary<string, Queue<GameObject>> 来管理不同种类的预制体对象池, 通过预制体的名字(string)来获取对应的对象队列.
  2. 循环逻辑 (从右到左 vs. 向前看):
    • UI布局: 在实现一个从右向左排列的UI元素列表(比如阿拉伯语国家的UI)时, 我们就需要使用反向循环来计算每个元素的位置.
    • 状态效果结算: 在一个回合制游戏中, 结算玩家身上的Buff/Debuff时, 某些效果的计算可能依赖于它后面的效果(比如一个"伤害加深"的debuff需要先于伤害技能结算). 这时就需要精心设计遍历和结算的顺序.
  3. 代码权衡 (可读性 vs. 效率):
    • Shader编写: 在写Shader时, 这是一个非常经典的权衡. 我们可以使用一些数学技巧让光照计算更快, 但这会让Shader代码非常难懂.
    • ECS (Entity Component System): 在Unity的DOTS中, 我们写的System代码非常注重性能, 因为它会处理成千上万个实体. 在这种场景下, 性能的优先级会高于常规代码的可读性. 但即便如此, 良好的命名和注释依然至关重要.

第14题: 最长公共前缀 (难度:简单)

原题:

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

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

示例 1：

1
2
输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：

1
2
3
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

提示：

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] 如果非空，则仅由小写英文字母组成

开始解题:

算法实现逻辑: 纵向扫描

这个方法非常直观, 就像我们用眼睛逐列对比文本一样. 它的核心思想是:

  1. 选定一个基准: 我们不需要两两比较所有字符串, 这样太复杂了. 我们可以直接选择数组中的第一个字符串 (例如 strs[0]) 作为我们的 “基准” 或者 “模板”. 最终的最长公共前缀, 长度绝对不可能超过这个基准字符串的长度.

  2. 逐个字符进行纵向对比: 我们从基准字符串的第一个字符开始 (索引为0), 然后拿着这个字符去和数组中 所有其他 字符串在 相同位置 的字符做比较.

    • 如果所有字符串在当前位置的字符都和基准字符相同, 那么说明这个字符是公共前缀的一部分. 我们就继续去检查下一个位置的字符.
    • 如果在这个过程中, 遇到了任何一个字符串在当前位置的字符与基准字符不同, 或者某个字符串的长度已经不够长了(比如我们要检查第5个字符, 但某个字符串总共只有4个字符), 那么比较就此终止.

  3. 确定最终结果:

    • 一旦比较终止, 那么最长公共前缀就是基准字符串从开头到 上一个 成功比较的位置的子串.
    • 如果整个基准字符串的所有字符都被成功比较完了, 那么说明整个基准字符串本身就是最长公共前缀.

让我们用示例 ["flower", "flow", "flight"] 来走一遍流程:

  1. 选择基准: 我们选择 "flower" 作为基准.

  2. 开始纵向扫描:

    • 第1列 (索引 0):

      • 基准字符是 'f'.
      • 检查 "flow" 的第1个字符, 是 'f'. 匹配.
      • 检查 "flight" 的第1个字符, 是 'f'. 匹配.
      • 结论: 所有字符串的第一列都是 'f', 'f' 是公共前缀的一部分. 继续.

    • 第2列 (索引 1):

      • 基准字符是 'l'.
      • 检查 "flow" 的第2个字符, 是 'l'. 匹配.
      • 检查 "flight" 的第2个字符, 是 'l'. 匹配.
      • 结论: 所有字符串的第二列都是 'l', 'l' 是公共前缀的一部分. 继续.

    • 第3列 (索引 2):

      • 基准字符是 'o'.
      • 检查 "flow" 的第3个字符, 是 'o'. 匹配.
      • 检查 "flight" 的第3个字符, 是 'i'. 不匹配!

  3. 得出结果:

    • 我们在索引为 2 的位置发现了不匹配. 这意味着最长公共前缀的长度就是 2.
    • 我们截取基准字符串 "flower" 从索引 0 开始, 长度为 2 的部分.
    • 结果就是 "fl".

这个方法的优点是, 一旦发现不匹配, 算法会立刻终止并返回结果, 在公共前缀很短的情况下效率非常高.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
    public string LongestCommonPrefix(string[] strs) {
        // 1. 处理边界情况: 如果数组为null或为空, 直接返回空字符串.实际上题目的条件已经给出范围了.
        if (strs == null || strs.Length == 0) {
            return "";
        }
        // 2. 外层循环遍历第一个字符串(基准)的每一个字符.
        // i 代表当前正在比较的字符列的索引.
        for (int i = 0; i < strs[0].Length; i++) {
            // 3. 取出基准字符串在当前列的字符.
            char c = strs[0][i];

            // 4. 内层循环遍历数组中剩余的字符串(从第二个开始).
            // j 代表当前正在比较的字符串的索引.
            for (int j = 1; j < strs.Length; j++) {
                // 5. 检查两种失败情况:
                // a) 当前比较的字符串长度已经不够了 (i == strs[j].Length).
                // b) 当前列的字符不匹配 (strs[j][i] != c).
                if (i == strs[j].Length || strs[j][i] != c) {
                    // 6. 一旦失败, 说明公共前缀到此为止.
                    // 截取基准字符串从0到i的部分并返回.
                    return strs[0].Substring(0, i);
                }
            }
        }
        // 7. 如果所有循环都正常结束, 说明第一个字符串本身就是最长公共前缀.
        return strs[0];
    }
}