ARTS #42

Algorithm

本周选择的算法题是：Unique Paths II

规则如下：

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Note: m and n will be at most 100.

Example 1:

Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Solution

我实现的方案：

Runtime：40 ms，快过 91.22%。

Memory：12.9 MB，低于 100%。

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        if not obstacleGrid: return 0
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        current = [1] + [0] * (n - 1)
        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    current[j] = 0
                elif j > 0:
                    current[j] += current[j - 1]

        return current[-1]

这个解法和 Unique Paths I 的解法类似。其中 current 可以通过直接修改 obstacleGrid 来进一步优化掉：

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        if not obstacleGrid: return 0
        if not obstacleGrid[0]: return 1
        if obstacleGrid[0][0] == 1: return 0

        obstacleGrid[0][0] = 1
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        for i in range(1, n):
            obstacleGrid[0][i] = int(obstacleGrid[0][i] == 0 and obstacleGrid[0][i-1] == 1)
        
        for j in range(1, m):
            obstacleGrid[j][0] = int(obstacleGrid[j][0] == 0 and obstacleGrid[j-1][0] == 1)
        
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    obstacleGrid[i][j] = 0
                else:
                    obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]

        return obstacleGrid[-1][-1]

Review

Routing for iOS: universal navigation without rewriting the app

老实说 View 层的路由方案不太好做，内部要兼顾二方、三方库，保有高拓展性和灵活性，外部要抗住业务变化，社区有很多关于 View 层的路由解决方案，我总觉得一个好的路由应该是像后端系统那样，有各种各样的服务（服务注册、服务发现）加上一个完整的业务流程（编排），服务间可替换可拓展，流程可以根据不同的业务场景定制，适应性很强，类似的设计也越来越多了：

Coordinators Essential tutorial
微信支付跨平台软件架构 - 日期还很新鲜

Tip

Stop Using Square Bracket Notation to Get a Dictionary’s Value in Python

get 方法：

第一个参数为要检索的 key
第二个参数是指定的 key 不存在时的默认值，默认为 None

setdefault 方法和 get 很像，但使用场景完全不一样：

get 是只读，而 setdefault 会修改原有的数据结构

可以指定默认值

author = {
   "first_name": "Jonathan",
   "last_name": "Hsu",
   "username": "jhsu98"
}
print(author.setdefault('middle_initial',None)) # None
print(author)
"""
{
  'first_name': 'Jonathan',
  'last_name': 'Hsu',
  'username': 'jhsu98',
  'middle_initial': None
}
"""

苹果已经弃用了 UIWebView：

对新应用来说，苹果的 deadline 是2020年4月
对已有应用来说，苹果的 deadline 是2020年12月

从我们自己的代码中检测、移除 UIWebView 是相当容易的，但如果是一些第三方的依赖，比如通过 CocoaPods 或者 Framework 的库，可以采用以下方法：

针对源码依赖，直接用全文搜索整个目录：grep -r 'UIWebView' . 即可
针对 Framework 依赖，可以用 nm 读出符号表，再用 grep 搜索：
```
nm xxx.framework/xxx | grep -i UIWebView
```

Algorithm

Solution

Review

Tip

Share