基本算法

题目汇总

面试中常用到机试题

常用函数

x的y次幂 pow(x，y)

语句area = pow(4.0，2)与以下代数表达式是等效的：

学习算法的可视化网站

大神总结

【LeetCode】代码模板，刷题必会

算法复杂度

算法的时间与空间复杂度

倒置链表

二分查找

二分查找法在算法家族大类中属于“分治法”，分治法基本都可以用递归来实现的，二分查找法的递归实现如下：

int bsearch(int array[], int low, int high, int target)
{
    if (low > high) return -1;
    
    int mid = (low + high)/2;
    if (array[mid]> target)
        return    binarysearch(array, low, mid -1, target);
    if (array[mid]< target)
        return    binarysearch(array, mid+1, high, target);
    
    //if (midValue == target)
        return mid;
}

二分查找法的实现和应用汇总

求根号double mysqrt(unsigned int n)

使用二分查找求之，夹逼之。

注意：浮点数比较不能直接用等于，只能判断落在某个区间内

double dpi = 0.0000000001;  // 精度

void fun(const double a, const double b, const double n, double& result)
{
    if (a < 1 || b < 1) {
        return;
    }

    double mid = (a + b) / 2;

    double tmp = mid * mid;
    double tmp1 = tmp - dpi;
    double tmp2 = tmp + dpi;
    if (n >= tmp1 && n <= tmp2) {
        result = mid;
        return;
    }
    else if (tmp < n) {
        fun(mid + dpi, b, n, result);
    }
    else {
        fun(a, mid - dpi, n, result);
    }   
}

double mysqrt(unsigned int n)
{
    if (n == 1 || n == 0) {
        return n;
    }
    double result = 0;
    double b = (double)n / 2.0;
    fun(1, b, (double)n, result);

    return result;
}

堆

215. 数组中的第K个最大元素

使用大顶堆求之。

大顶堆

#include <queue>
priority_queue<int, vector<int>, less<int>> big_stack;

小顶堆

#include <queue>
//                                       这里有可能要有空格，不然成了右移运算符
priority_queue<int, vector<int>, greater<int> > small_stack;

最大公约数

最大公约数（最大公因数）就是几个数公有的因数中最大的一个。
例：12与18 的最大最大公约数
12的因数有1，12，2，6，3，4
18的因数有1，18，2，9，6，3
公有的因数有1，2，3，6， 所以6就是12与18的最大公约数.
浅析求两个数的最大公约数的三种算法

素数

质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数。
素数判决和素数序列生成
埃拉托斯尼特筛选法

快速排序

912. 排序数组

基本思路：快速排序每一次都排定一个元素（这个元素呆在了它最终应该呆的位置），然后递归地去排它左边的部分和右边的部分，依次进行下去，直到数组有序；

void swap(vector<int>& arr, int i, int j)
{
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

void randBase(vector<int>& arr, int left, int right)
{ 
    int i = rand() % (right - left + 1) + left; // 随机选一个作为我们的主元
    //int i = rand() % arr.size() + left;   // 不能使用整个数组长度，因为这是一个递归的过程
    swap(arr, left, i);
}

// 一趟分割。严蔚敏《数据结构》标准分割函数
int partition(vector<int>& arr, int left, int right)
{
    randBase(arr, left, right);

    int tmpl = left;
    int tmp2 = right;
    int base = arr[left];
    while (left < right) {
        while (left < right && arr[right] >= base) {
            right--;
        }
        arr[left] = arr[right];

        while (left < right && arr[left] < base) {
            left++;
        }
        arr[right] = arr[left];
    }
    arr[left] = base;

    return left;
}

// 一趟分割。优化：快慢双指针
int partition2(vector<int>& arr, int left, int right)
{
    randBase(arr, left, right);

    int base = arr[left];
    int i = left;
    int j = i + 1;

    // 以base分割[low+1, right] => [... base ...]
    while (j <= right) {
        if (arr[j] < base) {
            // 找到小于base的数，往前放
            swap(arr, j, ++i);
        }
        j++;
    }
    // i指向了前半段的最后一个位置
    swap(arr, left, i);

    return i;
}

// 快速排序：
void quickSort(vector<int>& arr, int left, int right)
{
    if (left >= right) {
        return;
    }

    // 一趟分割，把数据分成 [.小. base .大..]
    int pivot = partition1(arr, left, right);

    // 递归左半边、右半边
    quickSort(arr, left, pivot - 1);
    quickSort(arr, pivot + 1, right);
}

vector<int> sortArray(vector<int>& nums) {
    srand((unsigned)time(NULL));
    quickSort(nums, 0, nums.size() - 1);
    return nums;
}

算法分析：1.当分区选取的基准元素为待排序元素中的最大或最小值时，为最坏的情况，时间复杂度和直接插入排序的一样，移动次数达到最大值
Cmax = 1+2+...+(n-1) = n*(n-1)/2 = O(n2) 此时最好时间复杂为O(n2)
2.当分区选取的基准元素为待排序元素中的"中值"，为最好的情况，时间复杂度为O(nlog2n)。
3.快速排序的空间复杂度为O(log2n).
4.当待排序元素类似[6,1,3,7,3]且基准元素为6时，经过分区，形成[1,3,3,6,7],两个3的相对位置发生了改变，所是快速排序是一种不稳定排序。

归并排序

基本思路：借助额外空间，合并两个有序数组，得到更长的有序数组。
归并排序是用分治思想，分治模式在每一层递归上有三个步骤：
分解（Divide）：将n个元素分成个含n/2个元素的子序列。
解决（Conquer）：用合并排序法对两个子序列递归的排序。
合并（Combine）：合并两个已排序的子序列已得到排序结果。
归并排序动图演示
图解排序算法(四)之归并排序
实现：

// 归并排序
void mergeSort(vector<int>& arr, int left, int right, vector<int>& temp) {
    if (left >= right) {
        return;
    }
        
    int mid = (left + right) / 2;
    mergeSort(arr, left, mid, temp);        // 左边归并排序，使得左子序列有序
    mergeSort(arr, mid + 1, right, temp);   // 右边归并排序，使得右子序列有序

    merge(arr, left, mid, right, temp);     // 将两个有序子数组合并操作     
}
    
// 将两个有序子数组合并 <left, mid> + <mid+1, right>
// temp数组作为临时存放空间，从外部传入避免频繁申请空间
void merge(vector<int>& arr, int left, int mid, int right, vector<int>& temp) {
    int i = left;
    int j = mid + 1;
    int k = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {            
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }

    k = 0;
    // 重点：将temp中的元素全部拷贝到原数组中
    while (left <= right) {
        arr[left++] = temp[k++];
    }
}