直接扫描的做法

1
2
3
4
5
6
7
8
9
10
11

vector<bool> camelMatch(vector<string>& qs, string pattern, vector<bool> res = {}) {
  for (auto i = 0, j = 0, p = 0; i < qs.size(); ++i) {
    for (j = 0, p = 0; j < qs[i].size(); ++j) {
      if (p < pattern.size() && qs[i][j] == pattern[p]) ++p;
      else if (!islower(qs[i][j])) break;
    }
    res.push_back(j == qs[i].size() && p == pattern.size());
  }
  return res;
}

优秀的程序员会告诉你打根基的重要性，会劝你在厚积薄发前要隐忍。

优秀的码农会告诉你学啥底层、啥啥啥一拖就好了，学了python还要啥自行车啊，数据结构排序函数二分搜索这不都内置了吗？工作中永远用不到，学算法有啥用啊？成为高手有很多种方法汇编是个屁啊？

+++基础的分割线+++

列举几个我认为比较重要的根基并附入门书

编程语言，《程序设计语言-实践之路》《concepts of programming languages》

计算机通用知识，《csapp》

算法、数据结构，《算法导论》

程序设计、结构，没有书推荐

软件工程，这个词大家理解不同，我以为，《人月》《代码大全》《the pragmatic programmer》《sicp》、讲测试讲重构的都是软件工程，其实上面设计模式也是软件工程，哈哈

这些书，初时读来感觉全无作用，而且要读多次才能体会其中意味，所以叫它根基也是十分合适，你根基越深才能爬得越高嘛。

+++方向的分割线+++

啥是优秀程序员？

记者和很多网民说熊猫烧香作者是高手

公司里你出什么bug他都能告诉你原因用什么软件有问题他都能回答你的你就觉得是高手

有人说徒手做产品的全栈才是高手

各语言的作者都是高手

有不写代码，扔出一个restful论文的

还有人说高德纳是神，他如果是神，那他那些代码一定是在考验我们，嗯

。。。。

上面这些的确都算是高手，我琢磨着前两年被开掉的moto公司员工里肯定也有做功能机的高手和写廉价板驱动的高手

你想自己选自己的方向还是被人忽悠方向？

我的想法是自己都尝试玩玩，然后做自己喜欢的方向。当然，程序员的生态金字塔是上面做工具、基础设施给下面人用来给普通人编程序，所以你选方向可以参考一下这个金字塔模型

+++爬坑的分割线+++

方向定下，然后就是做事了，一大误区就是 【追求最好的东西】，于是非得弄清楚：

php是最好的语言吗？
OpenGL比directx差吗？
程序员要先学数学吗？
最好的c语言书是谭浩强写的吗？
放屁要先脱裤子吗？
linux发行版那么多该选哪个？
某大牛说IDE不如编辑器
听说黑客都是用记事本写程序的
C#是升调记号应该读csharp而java不应念 [加wa（轻声）]
。。。

如果你是一个*nix世界的玩家的话，你应该知道有一个jargon来上面的毛病，叫yak-shaving，我以前提过几次yak-shaving，但是很多人看不懂，它的字面意思是Any seemingly pointless activity which is actually necessary to solve a problem which solves a problem which, several levels of recursion later, solves the real problem you’re working on.

但一般都引申其意使用它，我这里举例一下：

你本来要打开软件写一个helloworld，软件提示你升级，你点了升级，提示你xx库不够新，然后你更新xx库，提示你要升级yy驱动，然后你升级yy驱动，系统告诉你要编译这个驱动，你必须下载s.f版本的编译器和库，你更新编译器，系统说s.f版本编译器必须在e.n系统上运行，然后你就升级系统了，几个小时过去，你发现系统升级导致了几个软件损坏，然后你更新那些软件，去找解决问题的方法，不知不觉到了半夜，你累成了狗，却发现问题还有一大堆，而helloworld也没写成。。。。

这些问题我都遇到过，我的建议是挑一本大牛说的书就是了，看会了其他也会了。当然，如果你不幸不认识大牛（都上知乎了只要会搜索这种事情不可能发生），或者单纯好奇——就像我当年那样的话，那就每种都试试，不过有的答案你自己知道就好，像是编辑器emacs比vim更好，写程序ide比编辑器更好这种话，你是不应该乱说出来的。

对了，像是不同范式的编程语言、不同的开发环境是应该尝试体验一下的，不过这种建议书上都写了，我这里说显得有些废话了。

所以说，不能被无关的东西弄偏了目标，要专注，坚持。

等你学深了一门语言，就算是学另一们其他范式的语言也不会太难，你学会了opengl，dx也就看看就能写了。

你看看武侠小说里，段誉就是一个傻逼，仗着有时发出有时发不出的脉冲波和绕圈圈就能快跑直线的bug技就加上一门佛学能独步武林最终迎娶了白富美，出任了CEO，走向了人生巅峰，乔峰永远是一招降龙十八掌，更夸张。而慕容复文武双才，基本精通天下武学，每天读书4时辰练功4时辰，论用功谁能和他比啊。。。可到了30多岁还是一事无成，pk连段誉这种新手都搞不过，最后被人抢了老婆，就是因为方向不对，而且太不专注了。

所以求多不如求专，深度到了，再花20%的时间去扩展一下广度即可。

+++重要的分割线+++

以上东西你都做好了，要花个2年时间的样子，对于学生来说，如果你有一个好的学校背景，人生可以就此扬帆起步了

但这不是终点，俗话说人靠衣装，美靠包装。包装是门学问，这里的包装不是让你西装领带亮皮鞋黑丝套裙白衬衫整一个营销狗hr的造型，是说专业技能上的包装。

为什么这是最重要的部分呢？因为别人一般不和你说这么多，尤其是懂得包装的人，更不会传你这些不传之秘啦。。。。。

包装自己的第一步是提高实力

没有实力的包装那是空中楼阁，只能靠每天日常搞外包的忽悠架构大数据云计算过活，明眼人也能看出来，所以纯属作秀，没有意义。

在某个领域（编译器、虚拟机、开发架构、前端。。。）成为专家（专家的定义嘛，，我的理解是能在简历里写精通）后，包装的实力就算具备了。

包装的第二步是定位

提到美国会有一大堆人跳出来说是人类的希望民主的大救星，提到google就是最纯的技术公司不作恶、软件业的翘楚开发界的标杆、心美人美白莲花。。。哪怕你列举google卖假药、恶意打压yelp、挟持web标准等等等等这些事，他们也会说百度更差（咦这不5角钱常用的语句吗怎么被民主进步人士盗取了？。。。），可我根本没提到百度好吗。。。

这全是包装造成的，所以包装的巨大威力，以此可窥之。

google是搜索引擎，百度难道也说自己是搜索引擎？不，百度说自己是最懂中文的搜索引擎。。。哈哈哈，你别笑，这的确很管用，就像google说自己不作恶是好女孩一样。

程序员的包装定位，无非稀缺和独特这两点。物以稀为贵，稀缺就是要做到不可替代，这很好理解，比如你知道世界第一高峰是珠穆朗玛峰，如果没看过禅师精选集你很难知道第二高峰是乔戈里峰，但文青特别偏好乞力马扎罗山，不爬不跟你结婚，为啥？独特性嘛。。。我不跟你比高，我和你比文化底蕴，于是就赢了。

由于你有实力，所以你应该尽量把自己的实力包装成稀缺属性，你是专家嘛。。然后你实力多，应该把独特的实力包装出来，避免和他人共同曝光，以免被人压在身下。

我说一个我朋友包装自己的故事，他进公司接手了一个项目，已经是被隔壁组开发了3，4个月的一个软件，其实这软件2个月也能做好的，但是隔壁人忙而且也不上心，不熟悉这个技术，加上又不是自己的老板，所以做事拖沓了那么久才做好。他接手后一刻没闲，晚上带回家也做，做到半夜，10天做成，然后整个公司的人都知道他的名字了，他也就立稳脚跟了。

这个包装的主题是，技术实力强，开发速度快。

包装的第三步是推广

推广就是让人知道你做得好，强化你的个人品牌，可以用博客、知乎、mailing-list、github等，通过写文章、参加线下聚会演讲、回答问题、帮助他人等方法。这个用好了是门学问，用不好就是装逼，不展开了。。。

记住不要匿名，匿名你基本啥也得不到

有人明明技术实力强，但是由于没有包装好，或被埋没了才能，或被贴上了各种不应该有的标签，或被人偏见看待。比如 赵劼 的c#和 vczh 的微软标签

有人明明实力一般，但是善于鼓动小白，包装得好，所以有一批忠实粉丝，这种人我都不太敢说名字了，呵呵。。

所以优秀的程序员应该善用包装啊

一、基础规范
（1）必须使用InnoDB存储引擎
解读：支持事务、行级锁、并发性能更好、CPU及内存缓存页优化使得资源利用率更高

（2）必须使用UTF8字符集
解读：万国码，无需转码，无乱码风险，节省空间

（3）数据表、数据字段必须加入中文注释
解读：N年后谁tm知道这个r1,r2,r3字段是干嘛的

（4）禁止使用存储过程、视图、触发器、Event
解读：高并发大数据的互联网业务，架构设计思路是“解放数据库CPU，将计算转移到服务层”，并发量大的情况下，这些功能很可能将数据库拖死，业务逻辑放到服务层具备更好的扩展性，能够轻易实现“增机器就加性能”。数据库擅长存储与索引，CPU计算还是上移吧

（5）禁止存储大文件或者大照片
解读：为何要让数据库做它不擅长的事情？大文件和照片存储在文件系统，数据库里存URI多好

二、命名规范
（6）只允许使用内网域名，而不是ip连接数据库

（7）线上环境、开发环境、测试环境数据库内网域名遵循命名规范
业务名称：xxx
线上环境：dj.xxx.db
开发环境：dj.xxx.rdb
测试环境：dj.xxx.tdb
从库在名称后加-s标识，备库在名称后加-ss标识
线上从库：dj.xxx-s.db
线上备库：dj.xxx-sss.db

（8）库名、表名、字段名：小写，下划线风格，不超过32个字符，必须见名知意，禁止拼音英文混用

（9）表名t_xxx，非唯一索引名idx_xxx，唯一索引名uniq_xxx

三、表设计规范
（10）单实例表数目必须小于500

（11）单表列数目必须小于30

（12）表必须有主键，例如自增主键
解读：
a）主键递增，数据行写入可以提高插入性能，可以避免page分裂，减少表碎片提升空间和内存的使用
b）主键要选择较短的数据类型， Innodb引擎普通索引都会保存主键的值，较短的数据类型可以有效的减少索引的磁盘空间，提高索引的缓存效率
c） 无主键的表删除，在row模式的主从架构，会导致备库夯住

（13）禁止使用外键，如果有外键完整性约束，需要应用程序控制
解读：外键会导致表与表之间耦合，update与delete操作都会涉及相关联的表，十分影响sql 的性能，甚至会造成死锁。高并发情况下容易造成数据库性能，大数据高并发业务场景数据库使用以性能优先

四、字段设计规范
（14）必须把字段定义为NOT NULL并且提供默认值
解读：
a）null的列使索引/索引统计/值比较都更加复杂，对MySQL来说更难优化
b）null 这种类型MySQL内部需要进行特殊处理，增加数据库处理记录的复杂性；同等条件下，表中有较多空字段的时候，数据库的处理性能会降低很多
c）null值需要更多的存储空，无论是表还是索引中每行中的null的列都需要额外的空间来标识
d）对null 的处理时候，只能采用is null或is not null，而不能采用=、in、<、<>、!=、not in这些操作符号。如：where name!=’shenjian’，如果存在name为null值的记录，查询结果就不会包含name为null值的记录

（15）禁止使用TEXT、BLOB类型
解读：会浪费更多的磁盘和内存空间，非必要的大量的大字段查询会淘汰掉热数据，导致内存命中率急剧降低，影响数据库性能

（16）禁止使用小数存储货币
解读：使用整数吧，小数容易导致钱对不上

（17）必须使用varchar(20)存储手机号
解读：
a）涉及到区号或者国家代号，可能出现+-()
b）手机号会去做数学运算么？
c）varchar可以支持模糊查询，例如：like“138%”

（18）禁止使用ENUM，可使用TINYINT代替
解读：
a）增加新的ENUM值要做DDL操作
b）ENUM的内部实际存储就是整数，你以为自己定义的是字符串？

五、索引设计规范
（19）单表索引建议控制在5个以内

（20）单索引字段数不允许超过5个
解读：字段超过5个时，实际已经起不到有效过滤数据的作用了

（21）禁止在更新十分频繁、区分度不高的属性上建立索引
解读：
a）更新会变更B+树，更新频繁的字段建立索引会大大降低数据库性能
b）“性别”这种区分度不大的属性，建立索引是没有什么意义的，不能有效过滤数据，性能与全表扫描类似

（22）建立组合索引，必须把区分度高的字段放在前面
解读：能够更加有效的过滤数据

六、SQL使用规范
（23）禁止使用SELECT ，只获取必要的字段，需要显示说明列属性
解读：
a）读取不需要的列会增加CPU、IO、NET消耗
b）不能有效的利用覆盖索引
c）使用SELECT 容易在增加或者删除字段后出现程序BUG
（24）禁止使用INSERT INTO t_xxx VALUES(xxx)，必须显示指定插入的列属性
解读：容易在增加或者删除字段后出现程序BUG

（25）禁止使用属性隐式转换
解读：SELECT uid FROM t_user WHERE phone=13812345678 会导致全表扫描，而不能命中phone索引，猜猜为什么？（这个线上问题不止出现过一次）

（26）禁止在WHERE条件的属性上使用函数或者表达式
解读：SELECT uid FROM t_user WHERE from_unixtime(day)>=’2017-02-15’ 会导致全表扫描
正确的写法是：SELECT uid FROM t_user WHERE day>= unix_timestamp(‘2017-02-15 00:00:00’)

（27）禁止负向查询，以及%开头的模糊查询
解读：
a）负向查询条件：NOT、!=、<>、!<、!>、NOT IN、NOT LIKE等，会导致全表扫描
b）%开头的模糊查询，会导致全表扫描

（28）禁止大表使用JOIN查询，禁止大表使用子查询
解读：会产生临时表，消耗较多内存与CPU，极大影响数据库性能

（29）禁止使用OR条件，必须改为IN查询
解读：旧版本Mysql的OR查询是不能命中索引的，即使能命中索引，为何要让数据库耗费更多的CPU帮助实施查询优化呢？

（30）应用程序必须捕获SQL异常，并有相应处理

计数初步

归纳 递归 归简

遍历

分解 合并 解决

贪心有理

复杂依赖

dijkstra

匹配 切割 流量

困难问题及其稀释

一、应对高并发的基本思路
1、加快单机的速度，例如使用Redis，提高数据访问频率；增加CPU的内核数，增大内存；

2、增加服务器的数量，利用集群。

二、分布式系统的设计

1、无状态
应用本身没有状态，状态全部通过配置文件或者集群的服务端提供并与之同步。比如不同的机房需要读取不同的数据源，那么他们直接通过配置文件或者中心来指定。

进一步，在分布式集群中，如果数据请求的节点可以做到没有状态，意味着任意节点都可以被请求，结合去中心化，就能有效避免单节点的访问瓶颈。

2、拆分
系统设计初期，不要按功能模块来进行拆分，只需要尽快保证每个开发的单元能独立运行，即按照多进程模式可以运行。例如搜索引擎的业务会分为地理信息、类别、文本等多个搜索，在初期所有搜索可以继承开发在一个http请求的响应处理模块里，初期就按照业务进行拆分，会带来极大的工作量，各个模块能独立并行运行即可。

系统拆分原则：

功能及业务：例如搜索模块、地图模块、用户信息模块

子功能拆分：例如搜索模块里，图数据库与文本搜索可以分开

读写分离：根据读写的特性在进行拆分，例如淘宝的商品浏览与编辑，编辑是一个纯写的功能，流量是一个纯读的功能，因此可以对读写的实现进行拆分，一个集群实现商品读取的功能，而另一个规模小的多的集群提供商品写入的功能。

代码模块：一般情况，与上图类似，一个系统可以按照Web、Service及DAO来划分，有专门负责Web请求的，有提供进一步数据服务的模块，以及专门的数据库HA管理模块。

3、负载均衡
如果单机不行，需要考虑使用集群，使用集群就意味着一个负载均衡服务提供在最前端。

负载均衡算法：

（1）轮询：以轮询的方式把请求发到上游服务器，配合weight配置实现基于权重的轮询

（2）IP hash：根据客户的IP做负载均衡，使得胸痛IP均衡到同一个upstream server。

（3）hash key：对客户端的一个key进行hash，建议使用一致性Hash实现负载均衡。普通Hash算法，当添加或删除服务器的时候，很多key都会被重新分配到不同的服务器，使用一致性hash，使得只有极少数的key会被重新分配服务器。

（4）least connection：把最新的请求负载均衡到活跃连接最少的服务器，依然可以与权重相结合。

一致性hash：

一致哈希将每个对象映射到圆环边上的一个点，系统再将可用的节点机器映射到圆环的不同位置。查找某个对象对应的机器时，需要用一致哈希算法计算得到对象对应圆环边上位置，沿着圆环边上查找直到遇到某个节点机器这台机器即为对象应该保存的位置。当删除一台节点机器时，这台机器保存的所有对象都要移动到下一台机器。添加一台机器到圆环边上的某个点时，这个点的下一台机器需要将这个节点前对应的对象移动到新机器上。更改对象在节点机器上的分布可以通过调整节点机器的位置来实现。

一致性hash的平衡性：

通过增加虚拟节点，使得节点的分布及hash算法能实现平衡。

4、服务化

当服务器集群设计为主从架构的时候，意味着需要有多个主服务器提供备份和容灾，这样就要考虑使用服务的自动注册和发现，比如使用ZooKeeper。

消息队列：

消息队列用来解耦一些不需要同步调用的服务或者订阅一些通知以及系统的变化。使用消息队列可以实现服务解耦、异步处理、流量缓冲等。案例：

5、databus架构

我们可以通过databus来实现MySQL数据与redis的更新操作，把MySQL的数据变化同步到redis。

6、数据异构

把一些联合查询的数据，直接组合成一张结果表，这样在读取的时候能更快速地取回结果。通常这样的表会比较大，因此需要按照主键做分库分表来增加读取的性能，带来的问题：

（1）数据同步

（2）某一项服务的终止导致整体服务的终止

（3）聚合查询

数据异构的实现：

（1）通过MQ机制接收数据变更，然后原子化存储

（2）在任务队列里，聚合数据源并更新

（3）聚合的数据，根据类型、实例进行分割，分割的数据还可以考虑分片

7、缓存：
缓存不仅仅存在于服务端，它可以被用在从最前端的任意节点，只要缓存被命中，对应的数据查询就可以得到量级的提升。

（1）客户端缓存：浏览器的cookie、storage，APP的本地数据存储

（2）网络层：CDN、镜像服务器、P2P技术等

（3）服务前端：接入层的缓存，应用层缓存

（4）分布式缓存：利用redis数据库实现分布式的缓存系统

（5）数据库缓存：当所有结果都没命中的情况下，可以依赖数据库的缓存提高检索排序效率

8、并发：

9、隔离：

1.保护资源，以防被其他资源拖垮

2.把不同的数据资源隔开

当海量请求发送到前端的时候，单机的故障率会极大提高，此时一旦一台服务器出故障停止响应，前端反向代理会把请求发送到集群的其他节点，导致整体负载的进一步提升，使得所有的服务请求都被拖累，使得服务器节点如雪崩一样纷纷过载从而导致服务不够用。

因此需要考虑从以下几个维度对访问进行隔离：

（1）资源的隔离：比如js、CSS这类访问量极大的文件放在CDN上

（2）热点的隔离：一些高频的请求和低频的请求分开

（3）读写分离：分布式系统总必用的一点（保证系统高可用很重要的一点）

10、读写分离

MySQL中的存储引擎InnoDB：行级锁，事务（原子性），写快

MySQL中的存储引擎myisam：标记锁，纯读性能高

11、分库分表：

对于NoSQL的数据库，往往天然支持分布式部署，例如HBASE、MongoDB，因此直接可以用集群，通过分片及复制来提高响应能力

对于RDBMS，不能进行分片，所以当容量增长的时候，需要考虑分表，把旧的内容独立出来，新建一张表存储；当业务增长很快，可以进一步考虑把旧的历史数据存储到单独的服务器上的一个数据库，由应用层根据请求来判断到那个库上读取数据，这样能使得热点数据的总量以及总访问量是一定的

分库分表的策略：

（1）取模：按照主键取模后做分库分表，缺点是按照非主键查询的时候需要跨库跨表的查询，扩容需要建立新的集群并进行数据迁移

（2）分区：例如2B的系统，每个大的客户一张表，每个客户下的分店可以考虑分表；根据时间或地区，进行表或数据库的切割

12、限流：

HTTP的请求全部发送到任务队列中，当队列满的时候，直接返回服务器超时；队列的大小按照并发处理能力来设置，使得进入队列的请求都能在一定时间内响应

13、降级：

降级是指在服务并发突然增大的时候，启动限制性措施，降低服务提供的能力从而保护系统性能。降级一般是在系统的接口之间，设置降级开关，在特定的时候启用。例如前面讲到为限流而做的任务缓冲队列，可以通过降级来启动或停用：平峰或低估期请求通过代理层直达后端；高峰期通过降级，请求都进入到队列，由worker从队列获取数据来请求。

降级措施还包括针对服务级别的，例如在高峰情况下只读缓存，缓存失效的情况下直接返回失败，使得热点的访问能被响应，而非热点数据请求被拒绝；微博打开个人主页的时候，还回出现热点推荐、广告等，如果出现流量暴涨，可以关闭这些功能的服务接口。

降级的启动方式：

（1）超时：数据库、HTTP服务或者远程调用超时后，可以自动触发降级。例如淘宝的商品主页会异步加载价格、评论、推荐，而抢购活动时，评论和推荐都可以临时不展示，通过超时来自动降级

（2）统计失败次数：调用外部服务，例如数据来源于图数据库的情况，失败次数达到一定次数的时候自动降级

（3）故障：远程服务出错，可以直接降级并报警

（4）限流：流量监控，超过峰值后自动开启降级，把所有请求排队