在科研中，其实主要用的是最大流开源库，没有自己写过。

为了在效率上优化，实际上maxflow/min-cut这个库写的还挺复杂，我曾看过一些，但只能做到在有代码的情况下弄懂。

最小生成树——Prim

Read More

排序是最基本的算法，面试中可能都不直接考，但经常涉及到排序算法的变种

我尝试了下自己手写，发现全部写对，困难不小。

头文件，习惯性将常用的头文件都加入进去

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <deque>
#include <map>
#include <stack>
#include <time.h>
#include <fstream>
using namespace std;
const int maxn=100000;

Read More

在微博上看到一篇文章，关于二分查找：当我写二分查找时，我想些什么

于是想到刚看过的《编程珠玑》上的一句话，“90%的人无法正确写出二分查找”

自己动手：

int BinarySearch(int A[], int n, int target)
{
    int left=0, right=n-1;
    while(left<=right)
    {
        int mid=(left+right)/2;
        if(A[mid] == target) return mid;
        if(target > A[mid]) left=mid+1;
        else right=mid-1;
    }
    return -1;
}

写完了后，去看这篇文章的答案，发现有很多问题，果然也属于那“90%”。

Read More

点集有很多特征，这里提到的有：最小凸包，最小外接矩形，最大内接三角形，最大内接四边形。

编程里面，如何求取点集的这些特征呢？

预处理知识

• 对于三个点，p0,p1,p2，如何判断以p0为中心，p0p1到p0p2是顺时针还是逆时针？

求向量p0p2与p0p1的叉积，若大于0,则说明是p0p2在p0p1的顺时针方向，若小于0，则说明p0p2在p0p1的逆时针方向。

Read More