分类 算法笔记 下的文章

《算法》读书笔记 - 排序

1. 选择排序

思想就是 从数组的第一个元素开始,找出从该元素开始到数组结束中的最小元素,与当前元素交换。

vector<int> selection_sort(vector<int> v) {
    int len = v.size();
    for(int i=0;i<len;i++) {
        int min_index = i;
        for(int j=i+1;j<len;j++) {
            if( v[j] < v[min_index] ) {
                min_index = j;
            }
        }
        //将 v[i]~v[len-1] 中的最小值与 v[i] 交换
        int tmp = v[i];
        v[i] = v[min_index];
        v[min_index] = tmp;
    }
    return v;
}

2. 插入排序

插入排序的整体思想就是将每个元素之前的部分视为已经排序好的,然后该元素插入到其中的适当位置。

vector<int> insertion_sort(vector<int> v) {
    int len = v.size();
    for(int i = 1; i < len; i++ ) {
        int j=i;
        //不断将元素前移,直到该元素大于等于当前位置的迁移元素,
        //即满足大于等于左侧元素,同时小于等于右侧元素,即移到了适当位置
        while(j>0 && v[j]<v[j-1]) {
            int tmp = v[j];
            v[j] = v[j-1];
            v[j-1] = tmp;
            j--;
        }
    }
    return v;
}

3. 希尔排序

希尔排序是插入排序的一个变种,解决了插入排序中交换元素操作过多的问题。希尔排序首先选定一个步进,按该步进将数组分为若干组。
例如一个长度为 10 的数组a[],若按步进为 3 分组,则 a[0],a[3],a[6],a[9]为一组,a[1],a[4],a[7]为一组,a[2],a[5],a[8]为一组,然后对这几个子分组分别进行插入排序,排序完成后,缩短步进,重复上面的操作,直到步进为 1 的分组排序结束。
《算法》中选择 1,4,13,40... 这个序列来改变步进,而似乎选择 1,2,4,8,16 这个序列来改变步进更方便

vector<int> shell_sort( vector<int> v ) {
    int len = v.size();
    for(int gap=len>>1;gap>0;gap>>=1) {
        for(int i = gap; i<len; i++) {
            int j = i;
            while(j-gap>=0 && v[j]<v[j-gap]) {
                int tmp = v[j-gap];
                v[j-gap] = v[j];
                v[j] = tmp;
                j-=gap;
            }
        }
    }
    return v;
}

ACM笔记-并查集

以POJ 1611 为例

Description

Severe acute respiratory syndrome (SARS), an atypical pneumonia of unknown aetiology, was recognized as a global threat in mid-March 2003. To minimize transmission to others, the best strategy is to separate the suspects from others.

In the Not-Spreading-Your-Sickness University (NSYSU), there are many student groups. Students in the same group intercommunicate with each other frequently, and a student may join several groups. To prevent the possible transmissions of SARS, the NSYSU collects the member lists of all student groups, and makes the following rule in their standard operation procedure (SOP).

- 阅读剩余部分 -

Manhattan距离和Chebyshev距离

以HDU 4311和HDU 4312为例

img

如图所示,Manhattan距离是指 1-2,2-4,3-4,4-1之间距离都为1,而对角线路线不可达状态下的两点距离

Chebyshev距离是指除曼哈顿距离外,对角线路线可达且距离为1的情况下(即 1-4,2-3之间距离为1),两点之间的距离

平面上两点间的 Manhattan 距离为 |x1-x2| + |y1-y2|,平面上两点间的 Chebyshev距离为 max(|x1-x2|, |y1-y2|)。

- 阅读剩余部分 -

ACM笔记-动态规划求Levenshtein distance

以HDU 4323为例

首先介绍一下什么叫做Levenshtein distance

编辑距离,又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字>符替换成另一个字符,插入一个字符,删除一个字符。
sitten (k→s)

sittin (e→i)

sitting (→g)

俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。

from Wikipedia


- 阅读剩余部分 -