还有比二分查找更快的算法,面向接口编程 Protocol,John 易筋 ARTS 打卡 Week 05

发布于: 6 小时前

每周完成一个 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 计算机上输入第一个程序的时候,标志着现代计算机的诞生,也意味着软件编程这一新兴行业即将出现。

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

面向电线编程的时代。

发布于: 6 小时前 阅读数: 9
用户头像

John(易筋)

关注

问渠那得清如许?为有源头活水来 2018.07.17 加入

前阿里巴巴资深无线开发,目前汇丰银行专家。客户端架构师,全栈工程师。擅长算法、数据结构、设计模式、iOS、Java、 Spring Boot、Spring Cloud、Docker

评论

发布
暂无评论
还有比二分查找更快的算法,面向接口编程Protocol,John 易筋 ARTS 打卡 Week 05