Algorithm

Leetcode 13： 罗马数字转整数

题目描述

例如， 罗马数字 2 写做II，即为两个并列的 1。12 写做XII，即为X+II。 27 写做XXVII, 即为XX+V+II。

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

思路

使用双指针遍历，比较当前数与前一位数的大小，若小为减， 大为加。

题解

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
func romanToInt(_ s: String) -> Int {
    guard !s.isEmpty else { return 0 }
    var res = 0
    let start = s.startIndex
    var preNum = valueFrom(s[start])
    var num = 0;
    for i in 1 ..< s.count {
        num = valueFrom(s[s.index(start, offsetBy: i)])
        if preNum < num {
            res -= preNum
        } else {
            res += preNum
        }
        preNum = num
    }
    res += preNum
    return res
}

func valueFrom(_ str: Character) -> Int {
    switch str {
    case "I":
        return 1
    case "V":
        return 5
    case "X":
        return 10
    case "L":
        return 50
    case "C":
        return 100
    case "D":
        return 500
    case "M":
        return 1000
    default:
        return 0
    }
}

Review

as, as?, and as!

一篇来自 Ole Begemann 的文章，讨论了 Swift 中 as、as?和as! 的区别：

as！和as?是运行时操作，而as是在编译期对类型进行转换。这也能够解释为何 4 as Double可以编译运行而4 as! Double会 crash，因为前者表达式中的 4 是 integer literal ，还没有具体类型，而后者表达式中的 4 已经是 Int 类型，而 Swift 中不允许数字类型间的隐式转换，导致了 crash 。

Tips

在上文的算法中需要用到String的index，其特点有：

  • 需要用String实例方法来生成String.Index实例
  • 使用的方法是startIndex + offset的方式，如：
1
2
3
let aString = "im a string"
let index = aString.index(aString.startIndex, offsetBy: 3)
let char = aString[index] // Character

这样设计的原因，首先是因为String的元素是不等长的，每个元素可能是由 1~4 个UTF8码位组成，这意味着无法通过数组的那种简单的起始地址 + index * 元素长度的方式取到对应元素，若简单实用 Int作为下标会使遍历的时间复杂度会比等长数组高一个数量级。

因此String通过Index来解决这个问题，内部记录对应元素的偏移量来复用查找下一个元素。

String.Index 的内存布局：

  • position aka encodedOffset: 一个 48 bit 值，用来记录码位偏移量
  • transcoded offset: 一个 2 bit 的值，用来记录字符使用的码位数量
  • grapheme cache: 一个 6 bit 的值，用来记录下一个字符的边界
  • reserved: 7 bit 的预留字段
  • scalar aligned: 一个 1 bit 的值，用来记录标量是否已经对齐过

Share

Rollout Swift Support – Under The Hood

Rollout 利用 SIL 来实现的 Swift 代码热修复，通过拦截 swiftc 编译出的文件，识别其中所有的方法并在方法之上封装一层，使方法可以执行一个从 Rollout 云下载的 JS 函数，当然也可以调用原函数，从而实现热修复的能力。