全 1 子串算法求解、单元测试的必要性论述 John 易筋 ARTS 打卡 Week 32

John(易筋)

关注

发布于: 2020 年 12 月 28 日

1. Algorithm: 每周至少做一个 LeetCode 的算法题

笔者的文章：

算法：全一子串的数量或全零子串的数量 1513. Number of Substrings With Only 1s

LeetCode 全集请参考：LeetCode Github 大全

题目

1513. Number of Substrings With Only 1s

Given a binary string s (a string consisting only of '0' and '1's).

Return the number of substrings with all characters 1's.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: s = "0110111"Output: 9Explanation: There are 9 substring in total with only 1's characters."1" -> 5 times."11" -> 3 times."111" -> 1 time.

复制代码

Example 2:

Input: s = "101"Output: 2Explanation: Substring "1" is shown 2 times in s.

复制代码

Example 3:

Input: s = "111111"Output: 21Explanation: Each substring contains only 1's characters.

复制代码

Example 4:

Input: s = "000"Output: 0

复制代码

Constraints:

s[i] == '0' or s[i] == '1'1 <= s.length <= 10^5

复制代码

常规求和解法

分析：连续 1 的和，比如 3 个 1，111，

1 的选择是 3;
11 的选择是3-1=2；
11 的选择是2-1=1；

简单来说就是count * (count + 1) / 2 ;

public int numSub(String s) {    int len = s.length();    int[] onecount = new int[len+1];
    int sum = 0;    int count = 0;    final int MOD = (int)1e9 + 7;    //System.out.println(MOD + "  " + (MOD == 1_000_000_007));    for (char c: s.toCharArray()) {      if (c == '0') {        if (count != 0) {          sum = (sum + count * (count +1) / 2) % MOD;          count = 0;        }
        continue;      }
      count++;    }
    if (count > 0) {      sum = (sum + count * (count +1) / 2) % MOD;    }
    return sum;  }

复制代码

正常情况下count * (count +1) 不溢出就没有问题，偏偏 LeetCode 中就有溢出的 case。

累计求和解决溢出的问题

public int numSubWithConcise(String s) {    int sum = 0;    int count = 0;    final int MOD = (int)1e9 + 7;    //System.out.println(MOD + "  " + (MOD == 1_000_000_007));    for (char c: s.toCharArray()) {      count = c == '1' ? count + 1 : 0;      sum = (sum + count) % MOD;    }
    return sum;  }

复制代码

2. Review: 阅读并点评至少一篇英文技术文章

笔者文章：

翻译：Swift 5编写并发编程，并发解决方案和异步Operation

说明

异步操作允许执行长时间运行的任务，而不必阻塞调用线程，直到执行完成为止。这是建立关注点分离的好方法，特别是与在操作之间创建依赖项结合使用时。

如果您不熟悉操作，建议您先阅读博客文章 Swift中的Operations和OperationQueues入门。这篇文章可以帮助您入门并介绍基本知识。让我们开始研究异步操作，首先查看它们之间的区别及其同步的对立面。

异步与同步操作

看起来差别不大；实际上，它只是一个 A，但实际差异要大得多。同步操作更容易设置和使用，但是只要异步操作不阻塞调用线程就无法运行。

异步操作可以发挥最大的作用，从而充分利用 Swift 中的操作。由于可以运行长时间运行的异步任务，因此可以将它们用于任何任务。创建关注点分离或将操作用作应用程序基础的核心逻辑。

综上所述，异步操作使您能够：

运行长时间运行的任务
从操作中调度到另一个队列
手动开始操作，没有风险

我将在下一段中对最后一点做更多解释。

手动开始操作

同步和异步操作都可以手动启动。手动启动基本上可以归结为 start()手动调用方法，而不是使用 anOperationQueue 来管理执行。

同步操作始终阻塞调用线程，直到操作完成。因此，它们不太适合手动启动操作。使用异步任务时，阻塞调用线程的风险不太重要，因为它有可能分派到另一个线程。

不建议手动启动

即使现在尝试手动启动异步任务可能很诱人，但也不建议这样做。通过使用 an，OperationQueue您无需考虑执行多个操作时的执行顺序，并且可以从诸如优先任务等更多功能中受益。因此，建议始终通过将操作添加到中开始操作OperationQueue。

创建异步操作

创建异步操作都始于创建自定义子类并覆盖isAsynchronous属性。

class AsyncOperation: Operation {    override var isAsynchronous: Bool {        return true    }
    override func main() {        /// Use a dispatch after to mimic the scenario of a long-running task.        DispatchQueue.global().asyncAfter(deadline: DispatchTime.now() + DispatchTimeInterval.seconds(1), execute: {            print("Executing")        })    }}

复制代码

这还不足以使任务异步，因为在执行 print 语句后，任务仍然直接进入完成状态。通过执行以下代码段可以证明这一点：

let operation = AsyncOperation()let queue = OperationQueue()queue.addOperations([operation], waitUntilFinished: true)print("Operations finished")
// Prints:// Operations finished// Executing

复制代码

换句话说，在异步任务仍在执行时，该任务已经标记为完成，这可能导致意外行为。我们需要自己开始管理状态，以使操作异步进行。

管理异步操作的状态

为了正确管理状态，我们需要使用多线程和 KVO 支持覆盖 isFinishedandisExecuting 属性。该 isExecuting 属性如下所示：

private var _isExecuting: Bool = falseoverride private(set) var isExecuting: Bool {    get {        return lockQueue.sync { () -> Bool in            return _isExecuting        }    }    set {        willChangeValue(forKey: "isExecuting")        lockQueue.sync(flags: [.barrier]) {            _isExecuting = newValue        }        didChangeValue(forKey: "isExecuting")    }}

复制代码

我们在仅同步访问的私有属性中跟踪执行状态。正如您在博客文章Concurrency in Swift中所了解的那样，您知道我们需要使用锁队列来进行线程安全的写和读访问。我们使用willChangeValue(forKey:)和didChangeValue(forKey:)来添加KVO支持，以确保OperationQueue正确更新获取的内容。

我们还需要覆盖start()更新状态的方法。重要的是要注意，super.start()因为我们现在正在自己处理状态，所以您永远不要调用此方法。

最后，我们添加了一个finish()方法，该方法允许我们在异步任务完成后将状态设置为完成。

将所有这些加在一起，我们得到一个看起来像这样的子类：

class AsyncOperation: Operation {    private let lockQueue = DispatchQueue(label: "com.swiftlee.asyncoperation", attributes: .concurrent)
    override var isAsynchronous: Bool {        return true    }
    private var _isExecuting: Bool = false    override private(set) var isExecuting: Bool {        get {            return lockQueue.sync { () -> Bool in                return _isExecuting            }        }        set {            willChangeValue(forKey: "isExecuting")            lockQueue.sync(flags: [.barrier]) {                _isExecuting = newValue            }            didChangeValue(forKey: "isExecuting")        }    }
    private var _isFinished: Bool = false    override private(set) var isFinished: Bool {        get {            return lockQueue.sync { () -> Bool in                return _isFinished            }        }        set {            willChangeValue(forKey: "isFinished")            lockQueue.sync(flags: [.barrier]) {                _isFinished = newValue            }            didChangeValue(forKey: "isFinished")        }    }
    override func start() {        print("Starting")        isFinished = false        isExecuting = true        main()    }
    override func main() {        /// Use a dispatch after to mimic the scenario of a long-running task.        DispatchQueue.global().asyncAfter(deadline: DispatchTime.now() + DispatchTimeInterval.seconds(1), execute: {            print("Executing")            self.finish()        })    }
    func finish() {        isExecuting = false        isFinished = true    }}

复制代码

为了确保我们的任务确实有效，我们将执行与之前相同的代码：

let operation = AsyncOperation()let queue = OperationQueue()queue.addOperations([operation], waitUntilFinished: true)print("Operations finished")
// Prints:// Starting// Executing// Operations finished

复制代码

这很棒，正是我们想要的！唯一缺少的是取消。

添加取消支持

由于操作可以随时取消，因此在开始执行时需要考虑到这一点。可能是在任务开始之前操作已被取消。

我们可以通过在start()方法内部简单地添加一个防护来做到这一点：

override func start() {    print("Starting")    guard !isCancelled else { return }
    isFinished = false    isExecuting = true    main()}

复制代码

尽管isFinishedandisExecuting属性此时包含正确的值，但是我们仍然需要根据文档进行更新：

具体来说，您必须更改 finished to YES 返回的值和executing to 返回的值 NO。即使开始执行操作之前取消了操作，也必须进行这些更改。

因此，我们finish()从start()防护内部的方法中调用该方法，使最终方法如下所示：

override func start() {    print("Starting")    guard !isCancelled else {        finish()        return    }
    isFinished = false    isExecuting = true    main()}

复制代码

利用异步任务

在为长时间运行的任务创建子类之后，是时候从中受益了。最终的异步操作类如下所示：

class AsyncOperation: Operation {    private let lockQueue = DispatchQueue(label: "com.swiftlee.asyncoperation", attributes: .concurrent)
    override var isAsynchronous: Bool {        return true    }
    private var _isExecuting: Bool = false    override private(set) var isExecuting: Bool {        get {            return lockQueue.sync { () -> Bool in                return _isExecuting            }        }        set {            willChangeValue(forKey: "isExecuting")            lockQueue.sync(flags: [.barrier]) {                _isExecuting = newValue            }            didChangeValue(forKey: "isExecuting")        }    }
    private var _isFinished: Bool = false    override private(set) var isFinished: Bool {        get {            return lockQueue.sync { () -> Bool in                return _isFinished            }        }        set {            willChangeValue(forKey: "isFinished")            lockQueue.sync(flags: [.barrier]) {                _isFinished = newValue            }            didChangeValue(forKey: "isFinished")        }    }
    override func start() {        print("Starting")        guard !isCancelled else {            finish()            return        }
        isFinished = false        isExecuting = true        main()    }
    override func main() {        fatalError("Subclasses must implement `main` without overriding super.")    }
    func finish() {        isExecuting = false        isFinished = true    }}

复制代码

当main()方法由子类执行时，我们将触发致命错误。

例如，您要上传带有的文件FileUploadOperation：

final class FileUploadOperation: AsyncOperation {
    private let fileURL: URL    private let targetUploadURL: URL    private var uploadTask: URLSessionTask?
    init(fileURL: URL, targetUploadURL: URL) {        self.fileURL = fileURL        self.targetUploadURL = targetUploadURL    }
    override func main() {        uploadTask = URLSession.shared.uploadTask(with: URLRequest(url: targetUploadURL), fromFile: fileURL) { (data, response, error) in            // Handle the response            // ...            // Call finish            self.finish()        }    }
    override func cancel() {        uploadTask?.cancel()        super.cancel()    }}

复制代码

请注意，我们正在保存数据任务，因此可以根据需要取消它。

这只是一个非常基本的例子。在 Collect by WeTransfer应用程序中，我们经常使用以下操作：

Content creation 内容创作
Content receiving 内容接收
Content uploading 内容上传
Content enriching 内容丰富

还有更多。很棒的事情是，您可以将这些操作链接在一起，如上一篇有关操作入门的文章所述。

结论

而已！我们创建了异步操作，您可以在项目中直接使用它。希望它可以使您以更好的性能将关注点与代码更好地分离。

这篇文章是系列文章的一部分：

Swift中的Operations和OperationQueues入门
在 Swift 中编写并发解决方案的异步操作(本文)
通过使用泛型进行高级异步操作

也可以以 Swift Playground 的形式找到：https://github.com/AvdLee/AsyncOperations

如果您想进一步提高 Swift 知识，请查看 Swift 类别页面。随意与我联系或鸣叫我在 Twitter 的，如果您有任何额外的提示或反馈。

谢谢！

参考

https://www.avanderlee.com/swift/asynchronous-operations/

3. Tips: 学习至少一个技术技巧

笔者的文章：

翻译：where在Swift中的用法

说明

Swift 中强大的关键字 where 可以轻松过滤出值。它可以用于许多不同的变体中，本文中列出了其中的大多数变体。

enum 中的用法

考虑具有以下枚举：

enum Action {    case createUser(age: Int)    case createPost    case logout}

复制代码

使用，where 您可以轻松过滤特定年龄范围的案件：

func printAction(action: Action) {    switch action {    case .createUser(let age) where age < 21:        print("Young and wild!")    case .createUser:        print("Older and wise!")    case .createPost:        print("Creating a post")    case .logout:        print("Logout")    }}
printAction(action: Action.createUser(age: 18)) // Young and wildprintAction(action: Action.createUser(age: 25)) // Older and wise

复制代码

for 循环中的用法

使用 for 循环打印偶数。

let numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for number in numbers where number % 2 == 0 {    print(number) // 0, 2, 4, 6, 8, 10}

复制代码

extension 协议扩展中的用法

Array 根据其元素扩展类型。

extension Array where Element == Int {    func printAverageAge() {        let total = reduce(0, +)        let average = total / count        print("Average age is \(average)")    }}
let ages = [20, 26, 40, 60, 84]ages.printAverageAge() // Average age is 46

复制代码

first 使用

根据条件获取第一个元素。

let names = ["Henk", "John", "Jack"]let firstJname = names.first(where: { (name) -> Bool in    return name.first == "J"}) // Returns John

复制代码

contains 中的用法

确定数组是否包含条件匹配元素。

let fruits = ["Banana", "Apple", "Kiwi"]let containsBanana = fruits.contains(where: { (fruit) in    return fruit == "Banana"}) // Returns true

复制代码

参考

https://www.avanderlee.com/swift/where-using-swift/

4. Share: 分享一篇有观点和思考的技术文章

笔者的文章：

单元测试的必要性从费用成本和时间成本综合考虑

单元测试与新飞机的质量

⾸先不可避免要回答的⼀个问题是，“为何要做单元测试？”，我个⼈的回答是：“这是保证——你写的代码是你想要的结果——的最有效办法！”，当然如果你有更好的办法，请不吝赐教。

没有完备的单元测试的代码所构成的⼀个系统，就像组装⼀架飞机，各个配件没有分别经过严格检验，只在最后组装好后，再通过试飞来检验飞机是否正常⼀样。

尽管软件开发可以“开着飞机换引擎”，但万⼀引发了线上事故，影响了绩效，减少了发量，这样的成本还是太⾼了。所以优秀的工程师总会想尽⼀切办法保证⾃⼰的出品没有质量问题，而单元测试就是⼀个有⼒的武器，可以⼤幅降低⼤家上线时的紧张指数。

单元测试的重要性

单元测试对我们的产品质量是非常重要的。
单元测试是所有测试中最底层的一类测试，是第一个环节，也是最重要的一个环节，是唯一一次有保证能够代码覆盖率达到 100%的测试，是整个软件测试过程的基础和前提，单元测试防止了开发的后期因 bug 过多而失控，单元测试的性价比是最好的。
据统计，大约有 80%的错误是在软件设计阶段引入的，并且修正一个软件错误所需的费用将随着软件生命期的进展而上升。错误发现的越晚，修复它的费用就越高，而且呈指数增长的趋势。作为编码人员，也是单元测试的主要执行者，是唯一能够做到生产出无缺陷程序这一点的人，其他任何人都无法做到这一点
代码规范、优化，可测试性的代码
放心重构
自动化执行 three-thousand times

时间成本指标

微软的统计数据：bug 在单元测试阶段被发现，平均耗时 3.25 小时，如果漏到系统测试阶段，要花费 11.5 小时。

测试中出现 bug 的阶段

下面这张图，旨在说明两个问题：85%的缺陷都在代码设计阶段产生，而发现 bug 的阶段越靠后，耗费成本就越高，指数级别的增高。所以，在早期的单元测试就能发现 bug，省时省力，一劳永逸，何乐而不为呢

单元测试的艺术

在《单元测试的艺术》这本书提到一个案例：找了开发能力相近的两个团队，同时开发相近的需求。进行单测的团队在编码阶段时长增长了一倍，从 7 天到 14 天，但是，这个团队在集成测试阶段的表现非常顺畅，bug 量小，定位 bug 迅速等。最终的效果，整体交付时间和缺陷数，均是单测团队最少。

单元测试演进过程

在金字塔模型之前，流行的是冰淇淋模型。包含了大量的手工测试、端到端的自动化测试及少量的单元测试。造成的后果是，随着产品壮大，手工回归测试时间越来越长，质量很难把控；自动化 case 频频失败，每一个失败对应着一个长长的函数调用，到底哪里出了问题？单元测试少的可怜，基本没作用。

Mike Cohn 在他的着作《Succeeding with Agile》一书中提出了“测试金字塔”这个概念。这个比喻非常形象，它让你一眼就知道测试是需要分层的。它还告诉你每一层需要写多少测试。测试金字塔本身是一条很好的经验法则，我们最好记住 Cohn 在金字塔模型中提到的两件事：

编写不同粒度的测试
层次越高，你写的测试应该越少

同时，我们对金字塔的理解绝不能止步于此，要进一步理解：我把金字塔模型理解为——冰激凌融化了。就是指，最顶部的“手工测试”理论上全部要自动化，向下融化，优先全部考虑融化成单元测试，单元测试覆盖不了的放在中间层（分层测试），再覆盖不了的才会放到 UI 层。

因此，UI 层的 case，能没有就不要有，跑的慢还不稳定。按照乔帮主的说法，我不分单元测试还是分层测试，统一都叫自动化测试，那就应该把所有的自动化 case 看做一个整体，case 不要冗余，单元测试能覆盖，就要把这个 case 从分层或 ui 中去掉。

越是底层的测试，牵扯到相关内容越少，而高层测试则涉及面更广。比如单元测试，它的关注点只有一个单元，而没有其它任何东西。所以，只要一个单元写好了，测试就是可以通过的；而集成测试则要把好几个单元组装到一起才能测试，测试通过的前提条件是，所有这些单元都写好了，这个周期就明显比单元测试要长；系统测试则要把整个系统的各个模块都连在一起，各种数据都准备好，才可能通过。

另外，因为涉及到的模块过多，任何一个模块做了调整，都有可能破坏高层测试，所以，高层测试通常是相对比较脆弱的，在实际的工作中，有些高层测试会牵扯到外部系统，这样一来，复杂度又在不断地提升。