ARTS-Week 3

每周至少写一道算法题，阅读并点评至少一篇英文文章，学习至少一个技术技巧，分享一篇有观点和思考的技术文章。本周的算法主要是栈相关的算法。看了一些分布式相关的文章，还有学习了 TF 提供的模型。

Algorithm

20. Valid Parentheses

括号匹配，判断输入的字符串中的括号是否正确。

循环字符，如果是左括号（ [, {, ( ）就入栈，遇到右括号（ ], }, ) ）就取出栈顶元素来匹配，能匹配上就继续循环，如果没有匹配上就说明括号匹配失败，直接返回 False 。

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        char_map = {
            "}": "{",
            ")": "(",
            "]": "[",
        }
        for char in s:
            if char in char_map:
                if char_map[char] != stack.pop() if stack else '#':
                    return False
            else:
                stack.append(char)
        return not stack

这里也要注意，遍历完整个字符串后，栈中的元素理应全部都 pop 出来，如果里面还有元素，则表示匹配失败，其中还有多余的左括号未被匹配。

155. Min Stack

这个如果只是简单的 AC 题目的话，可以最接最简单的在获取最小值的时候每次都做判断获取最小值，不过这不是这题的本意，这题目是需要以空间换时间的方式，设置一个辅助栈来保存小的元素，在每次 push 值进来的时候，判断新的值是否比辅助栈的栈顶元素小，小的话就添加进栈顶，在值弹出的时候也要做判断，看弹出的元素是否和辅助栈栈顶元素相同，相同的话需要一起弹出。

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.handle = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.handle or x <= self.handle[-1]:
            self.handle.append(x)

    def pop(self) -> None:
        if self.stack.pop() == self.handle[-1]:
            self.handle.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.handle[-1]

在添加值的时候，先判断辅助栈中是否有元素，之后在判断栈顶元素和需要添加的值的大小。

844. Backspace String Compare

这题比较简单，就循环判断每个字符，遇到字母，就压入栈中，遇到 # 号的时候就从栈顶弹出一个数，对两个字符串（ S 和 T ）都这样操作，最后比较两者的值。

class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool:
        return self.get_result(S) == self.get_result(T)

    def get_result(self, char_str: str):
        stack = []
        for char in char_str:
            if char == '#':
                if stack:
                    stack.pop()
            else:
                stack.append(char)
        return stack

在从栈顶弹出一个元素的时候需要判断是否是空栈。

Review

• Fallacies of Distributed Computing Explained

Arnon Rotem-Gal-Oz 写的一篇文章，关于分布式系统的一些错误认识。

在1994年，彼得·多伊奇（Peter Deutsch）起草了7条关于分布式系统架构和设计的假设，虽然从长远来看证明是错误的，并且还引发了不少麻烦。后来在1997年 James Gosling 加多了一条，所形成的这八条错误的假设就成为了 “分布式系统的8条谬论”：

1. 网络是可靠的
2. 延迟为0
3. 网络带宽无限
4. 网络是安全的
5. 网络拓扑不会发生变化
6. 只有一个管理员
7. 传输成本为0
8. 网络是同质的（有相同的配置和拓扑）

Tip

• Tensorflow Object Detection API

前一段时间有要使用 Object Detection 的功能需求，并且时间紧急，没有时间造轮子，并且也没有机器来训练样本，也没有样本集，最终只能去找别人的模型来实现这个功能，虽然最后使用的是 阿里云的图像识别接口 ，里面有个图像打标，在公司需要紧急开发一些产品，或者不想话费时间经历去训练图像识别的功能的话，可以直接用这个接口。

最后回到正题，这个 Object Detection API 是 Tensorflow 官方提供的一个训练好的模型以及 API 接口的示例代码，是一个强大的工具集合，可以使得像没有太多开发经验的新人都能开发构建部署图像识别系统。

这份文档里面提供了详细的步骤，来一步步使用这个模型，有个 Demo 也详细的写了要怎么用，在这里记录一下在使用过程中的注意事项：

• 在使用的时候，如果需要自己训练图片可以使用 LabelImg 这个工具来打标。
• 文档中提供了很多模型来使用：Detection Model ，在挑选模型的时候需要注意自身的使用场景，看是否速度重要还是精度重要，来选择不同的模型来使用，其中每个模型都标明了自己的速度（Speed）和平均精度（mAP）。
• 一般返回的结果会将得分（score）按倒序排列，也就是排第一的就是得分最高的一项，有时候只需要判断图片中的一个物体的时候就可以直接取第一项就行。
• 因为使用的这个模型是 Tensorflow 的，所有返回的识别结果是英文，在使用的时候需要注意。如果需要中文的话要使用相应的一些简单的翻译工具，或者对数据集标签做一个Map。
• 在测试的时候，在日常使用的时候，对物体呈现的角度有很大影响，也就是这样会出现很多无理头的结果，这毕竟是免费的模型，有些识别错误是很正常的，所以要对识别的得分做一个判断，一般得分大于50的（满分100）才能比较准确的判断物体。

（下图识别出来的结果是：苹果(apple)！87%）

（鼠标(mouse)：67% | 杯子(cup)：83%）

Share

这周看完的文章有两篇想分享的。

• 中台之上（一）：重视业务架构，不要让“业务的归业务、技术的归技术”

这是个系列文章，就不全部贴出来了，主要是让我明白了除了前端，后端，现在还有一个中台的概念出来，文章以阿里的中台为例子，引出了中台的概念以及中台的地位。

未来，技术不仅仅是技术，业务也不再是简单的业务，一切都需要转变。

中台的概念不仅仅局限于技术，而延伸进业务和管理层面，构建共享业务单元，遵循高内聚，低耦合的特点划分。

这其中也是微服务和分布式的一个应用，也有可能是最近这一块火起来的原因。

• CAP 定理的含义

感觉分布式是未来很长一段时间热门的东西，也是我接下来的几年时间需要去学习进取的方向，就先从基本的含义一点点学起。

这篇是阮一峰大哥的文章，CAP指的是三个指标：一致性（Consistency）、可用性（Availability） 和 分区容错性（Partition tolerance），这个定理表明这三个指标是不可能同时满足的。

参阅：CAP原则(CAP定理)、BASE理论