本期日常：浪完了逛吃躺吃的中秋国庆小长假，我肥来了！肥归工作的第一天元气满满，决定填坑一篇～

“众里寻他千百度，蓦然回首，那人却在、灯火阑珊处。”
“那人”是不是在难说，不过今天我们要聊的字符串搜索之Boyer-Moore算法确是能借助回溯寻到“那串字符”。

来自Boyer-Moore的回眸

Boyer-Moore是Robert S. Boyer和J Strother Moore在1977年发明的算法。前文介绍的KMP是从前往后一次遍历文本（Text）进行搜索，并且采用了DFA来避免回溯操作。换个角度，若是每次使用目标字符串（Pattern）从后往前比较，我们反而能更快排除不符合的情况，及时止损，提高效率。

本期日常：
上午去上海WAIC溜达了一圈，惊叹于谷歌艺术计划里AI与艺术品擦出的火花。逛到Art Camera展区真的心生感激，任何藏品不可避免的自然老化过程，即使再如何减缓也无法彻底阻止，尽可能用技术高保真存留艺术品的原貌，也许是我们能为这些从古至今遗留的珍宝们做的最好的事情。

还是回到本篇笔记主题——字符串搜索来。
相比于艺术品欣赏这等阳春白雪，字符串搜索可谓大家日常使用最频繁的操作之一了。

稍微正式的定义一下字符串搜索：给定一串长度为N的文本（text）和一个长度为M的字符串（pattern），找到这个字符串在文本中出现的位置。

字符串搜索的几个算法都挺经典的，比如KMP，至少我在真正接触之前就久闻大名了。接下来，我们就逐个击破～

平时只用过最简单的git merge，还一般都是在GUI上点点按钮就结束了，今天正好遇到了一个比较不一样的操作，趁着记忆还新鲜，就顺便聊聊git merge与git rebase那些事吧～

简化版故事背景是这样的：

1. dev是主要开发分支
2. master一般不动，只在release时把dev的代码merge过来

结果，今天正好在dev改了些代码，而且又正好要往mastermerge，结果发现上一次merge到master的代码改动又出现在了这次的提交中，检查master发现代码确实已经过去了，但是git在对比时的时候还是会识别出提交过的代码，很奇怪。

又是一番检查，发现问题就出在这条命令上：

1

$ git merge --squash

无论是解决网络流量或是交通流量，最大流问题都是网络流问题中最基本的问题之一。

什么是网络流？很简单：

1. 给定一个有向图G=(V, E)，它的每条边的容量为c(v,w)，对于任意一条边(v, w)最多有c(v, w)个单位的“流”可以通过；
2. 它有两个顶点，一个是s，称为源点(source)，一个是t，称为汇点(sink)，从s发出的流必须等于流入t的流。

最大流问题就是确定从s到t可以通过的最大流量。

上图是一个简单的网络流图及其最大流的例子，斜杠左边代表经过一条边的流，右边代表边的容量。不难看出，图中最大流为5。

前面写了一篇笔记介绍Hystrix中用到的设计模式，今天我们就一起看一下Hystrix是如何应用command来实现它的功能的。

Hystrix到底是什么呢？

简单讲，Hystrix是个提供延迟和容错机制的库，通过隔离分布式环境中对各种服务的依赖的方式，提高整个系统的健壮性。

这句话里提到的分布式一词，就是Hystrix针对的主要场景了。在分布式系统中，一个服务通常依赖于多个其他服务，其他服务又依赖于更多的服务。各个服务之间的依赖关系很可能是错综复杂的，如果不能恰当处理服务之间的依赖关系，那么很可能某一个服务挂了，就会导致任何依赖于它的服务都挂，这样的系统是十分脆弱的。

Hystrix就是为了解决这个问题而出现的~

上一篇笔记里提到了快速排序，顺便翻了翻书复习了一遍，关于算法的实现和优化其实有不少需要留意的细节，写篇笔记巩固一下。

快速排序这个名字也是非常直白了，它的平均运行时间为O(NlogN)，当然了，最坏的情况也可能达到O(N^2)，不过使用一些小技巧就可以极大避免这种极端情况的出现，比如上一篇笔记里提到的“洗牌”。

快速排序本质上属于一种分治的递归算法，将数组S排序的基本算法由以下几步组成：

1. 如果S中元素个数是0或1，返回；
2. 取S中任一元素v作为pivot；
3. 将S中除v以外的元素划分为两个不相交集合：大于等于v(S1)和小于等于v的(S2)；
4. 分别S1和S2进行快速排序得到S1'，S2'，返回S1'接上v接上S2'。

看起来很简单，实现也不难，但是很有可能一不小心就导致算法出错或者性能很差哦。下面我们就来看看有哪些需要注意的地方吧～

问题：给定一个数组，找出这个数组中第k大的元素。

这是一道非常经典的算法题，总结一下几种典型解法。

将数组排序，取第k个

最容易想到的解法，关键在排序算法的选择。
在Java中可以偷懒直接调Arrays.sort方法，时间复杂度是O(NlgN)，空间复杂度是O(1)

1
2
3
4
5

public int findKthLargest(int[] nums, int k) {
    int n = nums.length;
    Arrays.sort(nums);
    return nums[n-k];
}

在跑Code Scan的时候报了一个关于equals()的问题：

父类重写了equals，子类继承了父类并添加了新的属性，却没有重写equals。

印象中equals的重写是个比较难处理好的问题。首先我们先回顾一下Java中默认的Object类的默认equals实现。

Object.equals

Java中最顶层的Object类中默认的equals实现很简单，就是比较两个对象的引用，如果指向同一个地址则相同，反之则不同。

1
2
3
4
5

public class Object {
    public boolean equals(Object obj) {
        return (this == obj);
    }
}

问题：给定一个数组,找到一个连续的子数组,使得这个子数组的和最大。
举个例子，[1, -3, 2, 1, -1]的最大子数组是[2, 1]，其和为3。

Brute-force Solution

最容易想到的就是暴力解法，遍历所有可能的子数组，时间复杂度为O(n^2)。

最近在看Hystrix的应用，整个HystrixCommand的概念都是基于Command Pattern（命令模式），正好对我来说是一个比较陌生的设计模式，借此机会深入了解一下。

命令模式的定义和动机

• 定义

  Encapsulate a request as an object, thereby letting you parameterize clients with
  different requests, queue or log requests, and support undoable operations.
  将一个请求封装成对象，使得你可以为客户定制化不同的请求，把请求纳入队列或记录请求日志，以及支持可撤销的操作。