ARTS #60

Algorithm

本周选择的算法题是：Implement strStr()

规则如下：

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().

Constraints:

haystack and needle consist only of lowercase English characters.

Solution

KMP 算法的二维数组版：

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        m = len(needle)
        if m == 0: return 0
        
        # 构建状态表
        dp = [[0] * (ord('z') - ord('a') + 1) for _ in range(m)]
        dp[0][ord(needle[0]) - ord('a')] = 1
        x = 0
        for j in range(1, m):
            for c in range(ord('z') - ord('a')):
                if needle[j] == chr(ord('a') + c):
                    dp[j][c] = j + 1
                else:
                    dp[j][c] = dp[x][c]
            x = dp[x][ord(needle[j]) - ord('a')]

        # 开始状态推进
        j = 0
        for i, s in enumerate(haystack):
            j = dp[j][ord(s) - ord('a')]
            if j == m: return i - m + 1
        return -1

相比传统的 KMP 算法：

该版本需要更多的空间，但近似空间复杂度是一样的：O(26M)=O(M)
比一维数组更好理解状态的变化
时间复杂度都是 O(n)

传统的 KMP 算法：

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n, m = len(haystack), len(needle)
        if m == 0: return 0
        if n == 0: return -1

        # 构建状态回退表
        dp = [0] * m
        j = 0
        for i in range(1, m):
            if j > 0 and needle[i] != needle[j]:
                j = dp[j-1]
            
            if needle[i] == needle[j]:
                j += 1
                dp[i] = j
        
        # 开始匹配
        i, j = 0, 0
        while i < n:
            while j > 0 and haystack[i] != needle[j]:
                j = dp[j-1]
            
            if haystack[i] == needle[j]:
                j += 1
            i += 1
            if j == m: return i - j
            
        return -1

状态的变化过程不太容易理解。

双指针暴力解法：

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n, m = len(haystack), len(needle)
        if m == 0: return 0
        if n == 0: return -1

        p1, p2, curr_len = 0, 0, 0
        while p1 < n and p2 < m:
            if haystack[p1] == needle[p2]:
                curr_len += 1
                p1 += 1
                p2 += 1
            else:
                p1 = p1 - curr_len + 1
                p2, curr_len = 0, 0
            if curr_len == m: return p1-p2
        return -1

Review

iOS 14: What is new for WKWebView 苹果还在持续不断地改进 WKWebView，这次在 iOS 14 中：

增加了 JavaScript 沙盒模式的代码注入，隔离了宿主的执行环境
增加了新的原生调用 JS 的 API: callAsyncJavaScript
增加了全文检索 API: findString
支持将网页导出成 PDF
支持在原生控制页面的缩放

Tip

Behind the scene of ETag caching 偶然发现 OSS 服务器对部分资源没有返回 ETag 响应头，在网上找到了这篇文章。

打算再找机会看看 ETag 的计算逻辑，主要需要了解：

为什么设置了 Accept-Encoding: gzip, deflate, br 后会返回Transfer-Encoding: chunk
为什么导致了 ETag 没有被计算

在探索 Swift ARC 的过程中对 SIL 做了一些了解，发现 SIL 是很容易的理解的，比如以下源码：

class aClass{
    var value = 1
}

func main() {
    var c1 = aClass()
    var c2 = aClass()

    var fSpec = { 
        [unowned c1, weak c2] in
        c1.value = 42
        if let c2o = c2 {
            c2o.value = 42
        }
    }

    fSpec()
}

main()

关注到这一行：

var c1 = aClass()

它对应的 SIL 语句为：

%0 = alloc_stack $aClass, var, name "c1"        // users: %5, %52, %51, %14
%1 = metatype $@thick aClass.Type               // user: %3
// function_ref aClass.__allocating_init()
%2 = function_ref @test.aClass.__allocating_init() -> test.aClass : $@convention(method) (@thick aClass.Type) -> @owned aClass // user: %3
%3 = apply %2(%1) : $@convention(method) (@thick aClass.Type) -> @owned aClass // users: %20, %16, %5, %4
strong_retain %3 : $aClass                      // id: %4
store %3 to %0 : $*aClass                       // id: %5
...
strong_release %3 : $aClass                     // id: %20
...
destroy_addr %0 : $*aClass                      // id: %51
dealloc_stack %0 : $*aClass                     // id: %52

苹果提供了一分 SIL 指令文档，查询后可知：

alloc_stack - 在栈上分配一段未初始化的内存，也就是 %0
strong_retain - 增加了对象的 strong count
store - 将 %3 存放内存 %0，也就是之前分配的栈的地址
strong_release - 减少对象的 strong count，当 strong count 和 unowned count 都为0时，清理对象内存
destroy_addr - 清理对象内存
dealloc_stack - 回收之前通过 alloc_stack 分配的内存，在调用这个指令前，内存必须是未初始化或清除的状态

通过这种方式可以对 Swift 编译器背后针对 ARC 的实现有一个清晰的了解。

Algorithm

Solution

Review

Tip

Share