算法学习日记10.27

第一章 基础算法（一）

上课：理解算法主要思想

课后：理解代码模板并且能够快速默写 用题目检验 重复3-5次就能很好的提升熟练度

排序

快速排序

基于分治思想

1. 确定分界点： q[l] q[l + r >> 1] q[r] 随机

   快速排序这道题目的数据已加强，划分中点取左端点或右端点时会超时，改成取中点或者随机值即可

2. 调整区间：满足x左边的元素都小于等于x，右边的元素都大于等于x（等于x不影响），所以x不一定在中间位置

   初始情况，指针i在最左边的左边一个，指针j在最右边的右边一个的位置

   从左向右移动指针i，直到遇到第一个大于x的数，停下来；从右向左移动指针j，直到遇到第一个小于x的数停下来。

   交换此时指针i和指针j指向的数

   在继续移动指针i和j，直到i和j相遇为止

   指针j前面的数都是小于等于x的，指针i后面的数都是大于等于x的

3. 递归处理：递归的形式处理左右两段

   两个区间：l – j j+1 – r

易错点：

1. quick_sort() 函数里面传入的是 q[] , 因此在swap内也要使用 q[]；
2. do – while 循环步进条件 要区分 q[i] 和 q[j]；
3. 递归处理的时间前面的右边界为j ， 后面的左边界为 j+1。

快速排序算法模板

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

归并排序

基于分治思想

1. 确定分界点，mid = l + r >> 1，（快速排序取的是数值，归并排序里面确定的是位置）

2. 递归排序左边和右边，两边就变成了一个有序的数组

3. 归并——将两个有序数组合二为一

   双指针法处理两个数列，i指向a数组的0，j指向b数组的0

   如果a[i] < a[j] 将a[i] 放入新的数组，i++

   如果a[j] < a[i] 将a[j] 放入新的数组，j++

   到最后一定是有一个数组已经全部处理完成，还有一个数组没有处理完

   将未处理完的数组全部接到新数组的后面

易错点：

1. 两个区间 [l, mid] [mid + 1, r] i = l, j = mid + 1
2. 最后将tmp放入q的时候要注意条件是 i = l, i <= r

归并排序算法模板

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

二分

整数二分

有单调性就一定可以二分，但是不具有单调性的题目也一定可以二分，二分的本质不是单调性

在区间上定义了某种性质，该性质在左半边满足，在右半边不满足，左右半边不能相交（整数二分）

二分可以寻找性质的边界，既可以选择不满足的边界，也可以选择满足的边界

时刻保证答案在区间内部

1. 找中间值mid： mid = l + r >> 1

2. 先写一个 check() 函数，然后判断如何更新，如果是 l = mid ，就要把 mid 改成 l + r >> 1

3. 每次看更新区间是 l = mid ( 补上 +1 ) 还是 r = mid

4. 找左区间的右边界

   1. if( check( mid ) == true )

      那么mid就在满足性质的区间里面 ， 那么边界答案在 [mid, r] 里面 （包含mid）

      更新：l = mid

   2. if( check( mid ) == false )

      那么边界答案在 [ l , mid – 1 ] 里面

      更新：r = mid – 1

5. 找右区间的左边界

   1. if( check( mid ) == true )

      那么边界答案在 [ l , mid ]

      更新：r = mid

   2. if( check( mid ) == false )

      那么边界答案在 [ l , mid ]

      更新：l = mid + 1

注意点：

1. 每次选择下一个答案所在的区间

2. 二分是否有解和题目有关，和二分模板无关，二分是一定有解的，只需要最后判断二分得到的答案和题目要求的答案是否相同即可

给定数列，求元素的起始位置和终止位置

判断元素的起始位置，mid满足条件，说明起始位置在mid前面，r = mid

判断元素的终止位置，mid满足条件，说明终止位置在mid后面，l = mid

整数二分算法模板

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}
//边界答案都存在l指向的位置

浮点数二分

四位小数用 1e-6

六位小数用 1e-8

因为是浮点数二分，不需要考虑边界问题

浮点数二分算法模板

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;	
        else l = mid;
    }
    return l;
}

原文地址：http://www.cnblogs.com/xushengxiang/p/16833248.html