Skip to content

Latest commit

 

History

History
302 lines (254 loc) · 15.5 KB

算法基础.md

File metadata and controls

302 lines (254 loc) · 15.5 KB
Raw

常见算法与思想

常见数据结构

树

树的部分定义
  • 完全二叉树：只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；
  • 满二叉树：除了叶结点外每一个结点都有左右子叶且叶结点都处在最底层的二叉树。
二叉树
  • 特殊的二叉树
    • 堆：堆（也叫优先队列），我们可以将堆看做是一棵完全二叉树，它的特点是父节点的值大于（小于）两个子节点的值（分别称为大顶堆和小顶堆）。使用数组来保存堆（堆的宽度优先遍历），可以快速的获取某一个元素的父和子元素（以节点i为例，i的父节点为int(i/2)；对应的左右子节点为2*i+1和2*i+2）。
      • 在堆中，数组的长度并不代表合法的堆中元素的个数，最小数组下标0所代表的元素不属于堆。
    • 红黑树：平衡树的一种（AVL、ABT等），统计性能较好，所以STL中很多部分（set、multiset、map、multimap）由红黑树的变种实现。

常见的算法思想

  • 分治法
    • 基本思想：将一个问题，分解为多个子问题，递归的去解决子问题，最终合并为问题的解
    • 适用情况：子问题与性质相同且更易求解
  • 动态规划
  • 贪心算法（贪心算法是动态规划算法的特例）
    • 思想：贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。（局部最优）
    • 基本思想：将问题分解为多个子问题（阶段），按顺序求解，前一个问题的解为后一个问题提供信息
    • 适用求解最优化问题
  • 回朔法
    • 基本思想：选优搜索法，走不通就退回重选，按照深度优先搜索的策略，从根节点出发，深度搜索解空间
  • 分支界限法

动态规划

动态规划的两个核心是状态与状态转移方程，在使用动态规划求解问题的时候我们需要一个初始状态，这个状态可以在求解之前用其他方法先准备好。

  • 可以考虑使用DP求解的时候
    • 求极值（特别是关于序列的），这个时候一般要维护一个极值序列。
    • 大问题可以拆分为小问题的问题都可以考虑动态规划。

简单

  • 爬楼梯：You are climbing a stair case. It takes n steps to reach to the top.Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

    可以使用递归与动态规划两种思想

  • 打家劫舍:You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

    维护一个一位数组sum，其中sum[i]表示到i位置时不相邻数能形成的最大和：sums[x] = max(sums[x-1],nums[x]+sums[x-2])。x-2的意义在于sums[x-1]可能包含了nums[x-1]，但sums[x-2]一定不包含nums[x-1]。

    int rob(vector<int>& nums) {
    if(nums.size() == 0)return 0;
    else if(nums.size() == 1)return nums[0];
    else if(nums.size()==2)return max(nums[0],nums[1]);
    else{
        vector<int> sums(nums.size(),0);
        sums[0] = nums[0];
        sums[1] = max(nums[0],nums[1]);
        for(int i = 2;i<nums.size();i++){
			//sums[i]可能包含nums[i]或不包含
            sums[i] = max(sums[i-1],nums[i]+sums[i-2]);
        }
        return sums[nums.size()-1];
    }
}

  • 一次性股票交易：Say you have an array for which the ith element is the price of a given stock on day i.If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock),design an algorithm to find the maximum profit.

    两种思想：①保存当前遇见的最小值使用当前值与最小值之差与已知最小值之差做对比②DP中的“局部极值与全局极值算法”

    int maxProfit(vector<int>& prices) {
    if(prices.size() == 0)return 0;
    else{
        int global = 0;
        int local = 0;
        for(int i = 0;i<prices.size()-1;i++){
			//local表示的是当前值与已知的最小值的差，如果当前值比已知最小值小则当前值成为最小值（故local成为0）
			//可以使用0~2π的正弦曲线模拟过程
            local = max(0,local+prices[i+1]-prices[i]);
            global = max(global,local);
        }
        return global;
    }
}

中等难度

  • 摆动序列：A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence.

    摆动的序列设涉及到两个状态：上升与下降，那就维护两个数组，表示当前以某一个状态结尾的最大值

    int wiggleMaxLength(vector<int>& nums) {
    if(nums.size() <= 1)return nums.size();
    else if(nums.size() == 2)return nums[0] == nums[1]?1:2;
    else{
	   //用up[i]和down[i]分别记录到第i个元素为止以上升沿和下降沿结束的最长“摆动”序列长度
       vector<int> up(nums.size(),1),down(nums.size(),1);
       for(int i = 1;i<nums.size();i++){
           if(nums[i] == nums[i-1]){
               up[i] = up[i-1];
               down[i] = down[i-1];
           }
           else if(nums[i]>nums[i-1]){
               up[i] = down[i-1]+1;
               down[i] = down[i-1];
           }
           else{
               down[i] = up[i-1]+1;
               up[i] = up[i-1];
           }
       }
        return max(up[nums.size()-1],down[nums.size()-1]);
    }
}

  • 最短路线（或two ways）：Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.Note: You can only move either down or right at any point in time.

    注意方向的约束；如果想到达某一格，上一步只有两种情况，这是准备过去情况的条件

    int minPathSum(vector<vector<int>>& grid) {
    if(grid.size() == 0 )return 0;
    else if(grid.size() == 1 && grid[0].size() == 1)return grid[0][0];
    else{
        auto min_steps(grid);
        for(int i = 1;i<grid[0].size();i++){
            min_steps[0][i]+=min_steps[0][i-1];
        }
        for(int i = 1;i<grid.size();i++){
            min_steps[i][0]+=min_steps[i-1][0];
        }
        for(int i = 1;i<grid.size();i++){
            for(int j = 1;j<grid[0].size();j++){
                min_steps[i][j] = min(min_steps[i-1][j],min_steps[i][j-1])+min_steps[i][j];
            }
        }
        return min_steps[grid.size()-1][grid[0].size()-1];
}

  • Path sum:three ways:The minimal path sum in the 5 by 5 matrix below, by starting in any cell in the left column and finishing in any cell in the right column, and only moving up, down, and right, is indicated in red and bold;

    动态规划或Dijkstra算法， 不是很理解

  • Coin Change：You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

    很典型的动态规划，只是多了些条件（top down）。如果是bottom up则可以减少判断，从而减少代码量：

    int coinChange(vector<int>& coins, int amount) {
    if(amount == 0)return 0;
    else if(coins.size()<=0 || amount<0 )return -1;
    //哪怕有面值为1的硬币，amount也用不到amount+1个硬币
    //所以可以用amount+1表示当前值是无法实现的
    vector<int> results(amount+1,amount+1);
    results[0] = 0;
    for(int i = 1;i<results.size();i++){
        for(int c:coins){
            if(c<=i)results[i] = min(results[i],results[i-c]+1);
        }
    }
    return results[amount]>=amount+1?-1:results[amount];
}

  • Perfect Squares：Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

    依旧是十分典型的动态规划，但可以使用数学的方法“四平方和定理”求解：

       int numSquares(int n) {
        while(n % 4 == 0)
            n /= 4;
        
        if (n % 8 == 7)
            return 4;
        
        for(int a = 0; a * a <= n; ++a) {
            int b = sqrt(n - a * a);
            if (a * a + b * b == n)
                return !!a + !!b;
        }
        
        return 3;
    }

背包问题

背包问题进阶参考1、参考2
0-1背包问题

  • 基本概念：有n种重量和价值分别为Wi和Vi的物品。从这些物品中挑选出总重量不超过w的物品，每种物品都只能挑选一件，求所有挑选方案中价值总和的最大值。

  • leetcode 474。假设我们已经知道了最佳的结果为R[m,n]（m个0，n个1，最多可以组成K 个字符串中的R[m,n]个字符串）。假设结果集中第R[m,n]-1（从0开始算起，即最后一个）个字符串中有mk个0，nk个1，那么R[m,n] = R[m-mk,n-nk]+1（可以用反证法证明）。这样我们就可以考虑使用动态规划来解决。因为mk，nk不固定，所以需要使用一个二维数组来辅助。这个二维数组所表示的是P(p<=K)个字符串的情况下x个0和y个1分别可以可以组成的最大字符串数（x∈[0,m],y∈[0,n]）。转移方程如下：

    R[m,n] = max(R[m,n],R[m-zeros,n-ones]+1)
完全背包问题
  • 基本概念：有n种重量和价值分别为Wi和Vi的物品。从这些物品中挑选出总重量不超过w的物品，每种物品都可以挑选多件，求所有挑选方案中价值总和的最大值。
部分背包问题
  • 基本概念：有n种重量和价值分别为Wi和Vi的物品。从这些物品中挑选出总重量不超过w的物品，第i种物品最多选mi个，求所有挑选方案中价值总和的最大值。

常见排序算法【参考】

  • 常见排序算法的比较与选择
  • 排序算法的概念
    • 内（外）部排序：内部排序指的是数据记录在内存中排序
    • 稳定排序：相同大小的元素其顺序与原始顺序相同

堆排序

堆排序有两个主要的过程：①构建堆②利用堆进行排序

代码如下：

#include<iostream>
#include<algorithm>

using namespace std;

//当前的递归函数可以使用迭代的形式实现
template<typename T>
void adjust_down (T*data, int k, int len)
{
    if (k * 2 > len) { return; }
    
    else
    {
        int max_child = 2 * k;
        
        if (max_child > len) { return; }
        
        if (2 * k + 1 < len && data[2 * k] < data[2 * k + 1]) { max_child++; }
        
        if (data[k] >= data[max_child]) { return; }
        
        else
        {
            swap (data[k], data[max_child]);
            adjust_down (data, max_child, len);
        }
    }
}

template<typename T>
void build_maxheap (T*data, int len)
{
    for (int i = len / 2 + 1; i >= 1; i--)
    {
        adjust_down (data, i, len);
    }
}

template<typename T>
void heap_sort (T*data, int len)
{
    build_maxheap (data, len);
    
    for (int i = len; i >= 1; i--)
    {
        swap (data[i], data[1]);
        adjust_down (data, 1, i - 1);
    }
}

int main()
{
    int data[] = {0, 1, 5, 1, 2, 7, 4, 9, 7, 3, 5, 6};
    heap_sort (data, 11);
	for_each (begin (data), end (data), [] (int a) {cout << a << " "; });
    system ("pause");
}

快速排序（分治思想）

快速排序（Quicksort）是对冒泡排序的一种改进。

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序中核心为int partition(begin,end)函数，将[begin,end]中的原始分为两段，并返回分段节点的下标。

归并排序

分治法的应用。核心思想是有序序列的合并速度比无序序列的合并要快。

if (first < last)  
{  
    int mid = (first + last) / 2;  
    mergesort(a, first, mid, temp);    //左边有序  
    mergesort(a, mid + 1, last, temp); //右边有序  
    mergearray(a, first, mid, last, temp); //再将二个有序数列合并  
}

桶排序/基数排序

插入排序

插入排序和整理扑克牌很类似。插入排序是稳定的，因为当遇见相等的元素时当前元素会放在相等元素的后面。

改进：折半插入排序

希尔排序

希尔排序又叫缩小增量排序。先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

选择排序

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

冒泡排序（交换排序）

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。

冒泡排序与选择排序最大的区别在于比较原始与当前元素的位置，前者为临近元素，后者在一次排序中是固定的。

常见排序算法对比