Talk

开新坑

刷一发存在感

好久没写博客了:D 学校里混了一年，实现是混不下去了，只好出来实习，结果发现自己offer烂的一笔。。。（果然学渣是没出路的吗。。）
今天就是标记，改天发发些干货~ ~

AlgoProblem►Basic

求最长等差数列

最长等差数列

最长连续子序列 longest consecutive sequence 问题的升级版
，大家一定很熟LCS问题的求解方法，甚至他的单调队列优化版本（栈优化）。

这里我们将讨论其变形版：给出一系列的随机的整数数列。要求在$O(n^2)$的时间复杂度内求解出一个最长的子序列并且为等差数列。

这里需要注意的是题目描述里并没有说明是输出等差数列的长度还是等差数列本身。

这其实也是一个被别人研究过的问题，我这里只是给出这一问题的简单总结

一个观点

方法一

一个比较简单粗暴的方法就是枚举每两个数列项，在哈希表中维护[num, d]状态的个数，记录所有可能出现的等差数列。

伪代码如下：

1
2
3
4
for i in range(n-1, 0)
	for j in range(i+1, n-1)
		d = num[j] - num[i] #数列差
		HASH[num[i], d] = HASH[num[j], d] + 1

显然下面的描述也是等效的：

1
2
3
4
for i in range(0, n-1)
	for j in range(i+1, n-1)
		d = num[j] - num[i] #数列差
		HASH[num[j], d] = HASH[num[i], d] + 1

C++实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int main(int argc, char const* argv[]) {
    unordered_map<pair<int, int>, int> HASH1;
    int N;
    int d;
    cin >> N;
    int num[N];
    for (int i = 0; i < N; i++) {
        cin >> num[i];
    }

    for (int i = N-1; i >= 0; i--) {
        for (int j = i+1; j < N; j++) {
            d = num[j] - num[i];
            HASH1[mp(num[i], d)] = HASH1[mp(num[j], d)] + 1;
        }
    }

    int MAX = INT_MIN;
    for (auto &a : HASH1) {
        DBN(a.second);
        if (MAX < a.second) {
            MAX = a.second;
        }
    }
    printf("%d\n", MAX+1);
    return 0;
}

当然如果是自己编写的哈希表效率会更好些。

方法二

这里给出另一个dp的解法，用dp(i,j)表示第i项与第j项构成的等差数列的数量。

C++实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#define MAX_N 10001

int main(int argc, char const* argv[]) {
    int N; int d; int pre;
    unordered_map<int, int> eleMap;
    int dp[MAX_N][MAX_N];
    cin >> N;
    int num[N];
    for (int i = 0; i < N; i++) {
        cin >> num[i];
        eleMap[num[i]] = i;   // 逆映射
    }

    int MAX = INT_MIN;
    for (int i = 0; i < N; i++) {
        for (int j = i+1; j < N; j++) {
            d = num[j] - num[i];
            pre = num[i] - d;
            auto it = eleMap.find(pre);
            if (it != eleMap.end()) {
                dp[i][j] = dp[it->second][i] + 1;
            }
            else {
                dp[i][j] = 2;
            }
            if (dp[i][j] > MAX) {
                MAX = dp[i][j];
            }
        }
    }
    printf("%d\n", MAX);

    return 0;
}

另一个观点

如果我们把问题条件改一下，输出不是子序列，而是一个子集，这个自己可以构成等差数列，那么这个问题怎么求解？其实我们只要先排序就好了。

Math►Combinatorics

n个球放到m个盒子里

很有意思的一类组合题

n个球放到m个盒子里，根据球和盒子是否有区别以及是否允许有空盒有${ 2 } ^{ 3 }=8$种放球问题：求如下问题的放球方案数

  • 1) n个球有区别，m个盒子有区别，允许有空盒
  • ${ m }^{ n }$
  • 2) n个球有区别，m个盒子有区别，不允许有空盒
  • $m!S(n,m)$
  • 3) n个球有区别，m个盒子无区别，允许有空盒
  • $ \begin{cases} S(n,1)+S(n,2)+…+S(n,m),\quad m\le n ; \ S(n,1)+S(n,2)+…+S(n,n),\quad m>n \end{cases} $
  • 4) n个球有区别，m个盒子无区别，不允许有空盒
  • $S(n,m)$
  • 5) n个球无区别，m个盒子有区别，允许有空盒
  • $C(n+m-1,n)$
  • 6) n个球无区别，m个盒子有区别，不允许有空盒
  • $C(n-1,m-1)$
  • 7) n个球无区别，m个盒子无区别，允许有空盒
  • $G(x)=\frac { 1 }{ (1-x)(1-{ x }^{ 2 })…(1-{ x }^{ m }) } $的$x^n$项的系数
  • 8) n个球无区别，m个盒子无区别，不允许有空盒
  • $G(x)=\frac { x^m }{ (1-x)(1-{ x }^{ 2 })…(1-{ x }^{ m }) } $的$x^n$项的系数

注：

S(n,m)为第二类斯特林数
G(x)为母函数
C(n+m-1,n)为多重组合

Math►Geometry

Minkouski距离

最近看书的时候注意到了一个问题：Minkouski距离

$ d(i, j) = \sqrt [ p ]{ { ({ x }_{ i1 }-{ x }_{ j1 }) }^{ p }+{ ({ x }_{ i2 }-{ x }_{ j2 }) }^{ p }+…+{ ({ x }_{ il }-{ x }_{ jl }) }^{ p } } $

其有三个属性：

  • Positivity : 必然为正数
  • Symmetry 对称性 : $p_1$与$p_2$相互距离相等
  • Triangle Inequality : 对于任意$p_i$、$p_j$、$p_k$，$d(i,j)\le d(i,k)+d(k,j)$

Minkouski ditance还可以分为：

  • p = 1 , Manhattan (or city block) distance 曼哈顿距离
    • E.g. the Hamming distance: 可以使用奇偶剪枝
      $ d(i, j) = { \left| { x }_ { i1 }-{ x }_ { j1 } \right| +\left| { x }_ { i2 }-{ x }_ { j2 } \right| +…+\left| { x }_ { i3 }-{ x }_ { j3 } \right| } $

  • p = 2 , Euclidean distance 欧几里得距离
    $ d(i, j) = \sqrt{ { ({ x }_{ i1 }-{ x }_{ j1 }) }^{ 2 }+{ ({ x }_{ i2 }-{ x }_{ j2 }) }^{ 2 }+…+{ ({ x }_{ il }-{ x }_{ jl }) }^{ 2 } } $

  • p->oo , supremum distance 切比雪夫距离（两点各座标数值差绝对值的最大值）
    $d(i,j)={ max(\left| { x }_ { i1 }-{ x }_ { j1 } \right| ,\left| { x }_ { i2 }-{ x }_ { j2 } \right| ,…,\left| { x }_ { i3 }-{ x }_ { j3 } \right| })$

距离的定义可以直接影响一些问题：

  • 比如A*和IDA*启发函数的设计。。
  • 比如描述两组数据的相似度，或者说是两组状态的相似度。。
  • 比如k-means算法中距离的衡量的标准。。
  • 比如knn算法中距离。。
  • 。。。。。。
C++►etc.

Homebrew滚动更新的问题

最近遇到一个很郁闷的事情，就是本来能运行的项目突然就crash了，郁闷之余发现是一个软件的版本太高了（囧）。那为啥以前就没事呢？再思考一下估计是自己写的滚动更新的脚本的毛病，本来是想省事的却反而弄巧成茁。。。

具体点今天的问题就是opencv的libopencv_highgui.2.4.dylib，所依赖的libImath-2_1.11.dylib找不到了，那libImath是啥呢？一查居然是一个叫做ilmbase的软件的动态库文件。。。

那既然知道了问题所在，解决方法就有了，很简单就是指定版本重装ilmbase。

这里再给个brew的小技巧:
brew pin ilmbase
brew pin openexr
上面两个命令的意思就是说固定软件版本，很简单易用吧~~

homebrew的ruby包: