每周完成一个 ARTS：

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

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

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

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

zgpeace 立个Flag：坚持ARTS 10年，今天是2020-05-04 ~ 2030-05-04，漏掉一次微信群发红包100大洋。



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

392. Is Subsequence

Given a string s and a string t, check if s is subsequence of t.



A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).



Follow up:

If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?



Credits:

Special thanks to @pbrother for adding this problem and creating all test cases.



Example 1:

Input: s = "abc", t = "ahbgdc"
Output: true



Example 2:

Input: s = "axc", t = "ahbgdc"
Output: false



Constraints:

1. 0 <= s.length <= 100

2. 0 <= t.length <= 10^4

3. Both strings consists only of lowercase characters.



来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/is-subsequence

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。



解决思路：笔者看这道题是二分查找的类型题，很自然就从二分查找，用左右两个坐标同时来匹配。短字符串s的左坐标为sleft, 右坐标为sright; 长字符串t的左坐标为tleft, 右坐标为tright.

1. 检查边界问题，比如短字符为空s == null || s.length() == 0， 则直接返回true；如果长字符为空t == null || t.length() == 0，则直接返回false；

2. 循环遍历条件为长字符串tleft <= tright , 在循环结束前tleft++; tright--;。

3. 如果短字符串的左边字符等于长字符串的左边字符串，则sleft++;；如果短字符串的右边字符等于长字符串的右边字符串，则sright--;。

4. 在结束前判断短字符串的sleft > sright，则返回true。 注意：笔者这里踩过坑，如果放到最前面判断，有可能，长字符串也结束了，导致结果还是false。



public boolean isSubsequence(String s, String t) {
    // check edge for s
    if (s == null || s.length() == 0) {
      return true;
    }
    // check edge for t
    if (t == null || t.length() == 0) {
      return false;
    }
    boolean result = false;
    int sleft = 0;
    int sright = s.length() - 1;
    int tleft = 0;
    int tright = t.length() - 1;
    while (tleft <= tright) {
      if (s.charAt(sleft) == t.charAt(tleft)) {
        sleft++;
      }
      if (s.charAt(sright) == t.charAt(tright)) {
        sright--;
      }
      
      if (sleft > sright) {
        return  true;
      }
      tleft++;
      tright--;
    }
    return result;
  }



笔者跑完以后，以为速度会是最快了，看了以后只能超过87%的提交。看了一下评论，发现还有更优解。

解题思路如下：

遍历短字符串的所有字符，比如遍历到短字符的c，如果长字符集能从前一个找到的字符的位置加一(第一个字符的初始值为-1)，能找到当前字符c，则返回第一次找到该字符的位置，则替换index为上一个找到的字符集；如果没有找到当前字符c，则结果是-1，如果是-1，则直接返回false。时间复杂度只有最短字符的长度，最快的情况下，如果第一个字符都没找到就直接退出。神来之笔。

public boolean isSubsequenceByIndexOfChar(String s, String t) {
    int index = -1;
    for (char c: s.toCharArray()) {
      index = t.indexOf(c, index + 1);
      if (index == -1) {
        return false;
      }
    }
    return true;
  }



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

怎么在Swift中应用接口protocol编程，swift中的protocol可以被class，struct，enum实现。但是只有类可以在继承一个类的基础上，继续实现别的接口protocol。因为接口可以方便拆解掉大的类，复用共同的功能，实现面向对象特性多态。这篇文章详细地讲解了protocol的属性必须要明确声明类型，和是只读类型，还是可读可写类型，并且有实际场景的应用。，



How to Master Protocols in Swift

https://medium.com/better-programming/protocols-from-zero-to-hero-72423dfdfe21



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

博客：

怎么查看iOS iPhone的Safari版本userAgent



# 问题

在iOS中的Setting，找不到Safari的版本信息，如下图。





# 曲线救国的方案

## 方法1. 访问地址：

https://spiderip.com/





可以看到这个网页的获取userAgent的代码如下：

 var k=this;   {var ia=k.navigator;if(ia){var ja=ia.userAgent;if(ja){w=ja;break a}}w=""}



## 方法2. 可以写一个网页，包含以下信息，也可以查询userAgent的信息。

 javascript:alert(this.navigator.userAgent)



# 参考

https://stackoverflow.com/questions/62320141/how-to-view-the-safari-version-in-setting-of-iphone-ios



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

极客大学架构师训练营 编程的本质与未来 第三课 听课总结

说明

编程的本质与未来



这一课的内容都是从Bob大叔（Robert C. Martin）的书《敏捷软件开发原则、模式与实践》借鉴而来。笔者也写过Bob大叔2016年的演讲，可以配合来看。【编程的未来 Java, C, Go, Swift, Dart? Uncle Bob Martin - The Future of Programming 】



讲师：李智慧



架构设计回顾

上面这张图是上课的同学分类的，详细设计很多时候也是架构师的工作内容。笔者在阿里任职期间，实际上是要做开发设计的，比较符合阿里的分类。



李智慧老师从初级工程师到首席架构师的跃迁

李智慧老师，第一份工作是05年做日本的一个大型系统，那个时候前端是VB，服务端是用Java。刚开始的时候，一共也是几个人。最开始进去时候发现用VB调用Java Server，还没有办法直接调用。那个时候高手都到日本出差去了，李智慧老师给项目经理说了这个gap。项目经理也不懂技术，项目经理就说既然你提出这个问题，你就负责做这个组件吧。李智慧老师周末就看了Struts的架构，用两天时间画了一些组件图。周一就找项目经理评审，项目经理就协调了一些技术高手过来评审，觉得没什么大的问题。项目经理说现在项目还没开始，剩下的几个人就交给你分配任务，完成这个组件，并用一个业务做个Demo。最终组件就按照计划实现了，业务Demo也跑通了。后来大业务团队都从日本回来了，因为时间关系，大家就用了李智慧老师的框架，200多人的大团队都用了这个模块组件来进行前后端通信。高手们也提出一些改进计划，李智慧老师，后面就不断优化这个通信模块组件。整个团队都要李智慧老师培训，前端、后端如何用这个模块，包括后面入职新员工，都是由李智慧老师培训如何用该通信组件开发。李智慧老师从刚入职的低级新员工，到离开的时候就成了首席架构师。



第二份工作，李智慧老师跳槽到另一家日本公司，做的类似于Tomcat这种中间件，脱离了业务，专门去做技术架构。李智慧老师，觉得这两份工作经历为他后来的职业生涯提供了很大的帮助。



软件开发简史

从编程的历史看编程的本质和未来



请带着以下问题观看本节课的内容。

你还在用面向对象编程语言写面向过程的代码吗？



莱布尼兹的奇思怪想

莱布尼兹就是跟牛顿打了一辈子官司，谁是微积分的发明人。二进制就是莱布尼兹发明的。一切信息都可以用二进制表示。



计算机软件编程是个非常新兴的行业，程序员这一职业的出现不过半个多世纪，但是人类从事编程的探索却要久远的多，在计算机出现之前，甚至蒸汽机出现之前，人类就开始探索软件编程了。



最早开始编程探索的人是德国人莱布尼兹，早在1700年代，莱布尼兹就期望将各种事物都通过一种逻辑语言进行描述，然后用一种可执行演算规则的机器进行计算，就可以计算出事物的各种结果。这种思想其实和我们现代的软件编程与计算机已经差不多了，莱布尼兹为了实现这个想法，进行了大量的工作，获得了丰硕的成果，其中就包括了微积分和二进制。



莱布尼兹是计算机思想，后来科学家布尔，用Bool实现了逻辑编程。(就是Bool变量的这个布尔。)



人类第一位程序媛

莱布尼兹制造可编程计算机的梦想没有成功。又过了100年，法国人雅卡尔发明了一台可编程的织布机，这种织布机读取纸带上的打孔，进而控制织布机织出不同的图案。于是人们开始尝试将打孔纸带用于计算机编程，19世纪中叶，当英国人 Ada 利用打孔纸带写出人类第一个软件程序的时候，距离能够运行这个程序的计算机发明还有100年的时间，而这个程序已经包含了循环和子程序。 *Ada* 因此被认为是人类第一个程序员， 准确来说，是程序媛。科技发明受时代的限制，天才们的想象力和聪明才智却可以超过时代。



什么是计算机？什么是程序？

人类发明制造计算机器有非常悠久的历史，但是这些计算机器都是专门进行数值计算的，加减乘除、微分积分等等。而从莱布尼兹、Ada，到图灵、冯诺依曼，这些现代计算机的开创者们试图创造的是一种通用的计算机，这种计算机不是读取数值进行计算，而是读取数据进行计算，这些数据本身包含着计算的逻辑，这个数据就是程序。



现代计算机与现代的程序

当冯诺依曼在 ENIAC 计算机上输入第一个程序的时候，标志着现代计算机的诞生，也意味着软件编程这一新兴行业即将出现。



最早的计算机编程非常麻烦，程序员需要将电线编来编去，作为输入数据，以控制计算机的执行，这也是编程这个词的由来。不过很快人们就将打孔纸带应用到计算机上，编程的效率极大提升。



面向电线编程的时代。