快速排序

class Solution {
public:
    const int N = 1e6+10;
    void quickS(int l, int r, vector &v) {
        if(l >= r) return;
        int mid = v[l], i = l - 1, j = r + 1;
        while(i < j) {
            do i++; while(v[i] < mid);
            do j--; while(v[j] > mid);
            if(i < j) std::swap(v[i], v[j]);
        }
        quickS(l, j, v);
        quickS(j+1, r, v);
    }
    vector sortArray(vector& nums) {
        quickS(0, nums.size() - 1, nums);
        return nums;
    }
};

归并排序

    void merge(int l, int r, vector& v) {
        if(l >= r) return;
        int mid = (l + r ) / 2;
        merge(l, mid, v);
        merge(mid+1, r, v);
        vector tmp(r - l + 1);
        int c = 0;
        for(int i = l, j = mid + 1; i <= mid || j <= r;++c) {
            if(i > mid || j <= r && v[i] > v[j]) tmp[c] = v[j++];
            else tmp[c] = v[i++];
        }
        for(int i = 0, j = l; i < c; ++i, ++j) v[j] = tmp[i];
    }

KL散度

KL散度不能作为距离，因为不满足距离的对称性。

字母大小写转换的方法：

统一转成大写：ch & 0b11011111 简写：ch & 0xDF 统一转成小写：ch | 0b00100000 简写：ch | 0x20

并查集

int f[1001];
void init() {
    for(int i = 0; i < 1001; f[i]=i++);
}
void find(int u) {
    while(u != f[u]) u = f[u];
    return u;
}
void union(int a, int b) {
    fa[find(v)] = find(u);
}

优化1：路径压缩：

void findx(int u) {
    if(u != f[u]) {
        f[u] = findx(f[u]);
    }
    return f[u];
}

找零问题

最小方案数目

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int INF = amount + 1;
        vector<int> dp(amount + 1, INF);
        dp[0] = 0;
        for(int i = 0; i < coins.size(); ++i) {
            for(int j = coins[i]; j <= amount; ++j) {
                dp[j] = std::min(dp[j], dp[j-coins[i]] + 1);
            }
        }
        return dp[amount] < INF ? dp[amount]: -1;
    }
};

滑动窗口

leetcode 567:https://leetcode-cn.com/problems/permutation-in-string/

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        vector<int> v1(26); vector<int> v2(26);
        int l1 = s1.length(), l2 = s2.length();
        for(char s:s1) ++v1[s - 'a'];
        for(int i = 0; i < l2; ++i) {
            if(i >= l1) {
                --v2[s2[i - l1] - 'a'];
            }
            ++v2[s2[i] - 'a'];
            if(v1 == v2) return true;
        }
        return false;
    }
};

求根号

二分法

#include<iostream>
#include<cmath>
using namespace std;
double MySqrt(double n)
{
    double _max = n; //此处一定为浮点数，不要用整数
    double _min = 0.0;
    double p = 1e-5; //此处为精度，当满足该精度时，返回该近似值
    double  mid = (_max + _min) / 2.0;
    while(fabs(mid * mid - n) > p)//此处是浮点数之差的绝对值与精度进行比较
    {
        if(mid * mid < n)
            _min = mid;
        else if(mid * mid > n)
            _max = mid;
        else
            return mid;
        mid = (_max + _min) / 2.0;
    }
    return mid;
}
int main()
{
    cout<<MySqrt(80)<<endl;
}

牛顿法

#include<iostream>
#include<cmath>
using namespace std;
double MySqrt(double n)
{
    double x = 1.0;//设置初值
    double p = 1e-5;//设置精度
    while(fabs(x*x - n) > p)
    {
        x = (x + n / x) / 2.0;
    }
    return x;
}
int main()
{
    cout<<MySqrt(82)<<endl;
}

编辑距离

记忆化搜索

class Solution {
public:
    vector<vector<int>> d;
    int minDistance(string word1, string word2) {
        int l1 = word1.length();
        int l2 = word2.length();
        d = vector<vector<int>>(l1 + 1, vector<int>(l2 + 1, -1));
        return dp(word1, word2, l1, l2);

    }
    int dp(string s1, string s2, int l1, int l2) {
        if (!l1) return l2;
        if(!l2) return l1;
        if (d[l1][l2] >= 0) return d[l1][l2];
        if(s1[l1 - 1] == s2[l2 - 1]) return dp(s1, s2, l1-1, l2-1);
        d[l1][l2] = std::min(dp(s1, s2, l1, l2-1),
                             std::min(dp(s1, s2, l1 - 1, l2), dp(s1, s2, l1 - 1, l2 - 1))) + 1;
        return d[l1][l2];
    }
};

循环

class Solution {
public:
    int minDistance(string word1, string word2) {
        int l1 = word1.length(), l2 = word2.length();
        vector<vector<int>> dp(l1 + 1, vector<int>(l2 + 1, 0));
        for(int i = 0; i <= l1; ++i)
            dp[i][0] = i;
        for(int j = 0; j <= l2; ++j)
            dp[0][j] = j;

        for(int i = 1; i <= l1; ++i) {
            for(int j = 1; j <= l2; ++j) {
                int c = (word1[i-1] == word2[j-1]) ? 0 : 1;
                dp[i][j] = min(dp[i - 1][j - 1] + c,
                               min(dp[i][j - 1], dp[i-1][j]) + 1);

            }
        }
        return dp[l1][l2];
    }
};

基于Priority优化的dijkstra

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        vector<int> dis(N+1,-1);
        dis[K]=0;
        using Pair=pair<int,int>;//first是距离，second是目标点
        priority_queue<Pair,vector<Pair>,greater<Pair>> pq;
        pq.emplace(0,K);//起点先入队

        while(!pq.empty()){
            auto e=pq.top();pq.pop();//e为连接visited和unvisited的最小边
            if(e.first>dis[e.second]) continue;//如果e的权比K到e.second还大，就不可能缩短路径了
            for(int i=0;i<times.size();i++){
                if(times[i][0]==e.second){//遍历一遍所有以e.second为起点的边，做relax，并将relax之后的点入队
                    int v=times[i][1];
                    int w=e.first+times[i][2];
                    if(dis[v]==-1||dis[v]>w){
                        dis[v]=w;
                        pq.emplace(w,v);
                    }
                }
            }

        }

        int ans=0;
        for(int i=1;i<=N;i++){
            if(dis[i]==-1) return -1;
            ans=max(ans,dis[i]);
        }
        return ans;
    }
};

树状数组

class FenwickTree {    
public:
    FenwickTree(int n): sums_(n + 1, 0) {}

    void update(int i, int delta) {
        while (i < sums_.size()) {
            sums_[i] += delta;
            i += lowbit(i);
        }
    }

    int query(int i) const {        //query(8) 表示的是前8个元素的和
        int sum = 0;
        while (i > 0) {
            sum += sums_[i];
            i -= lowbit(i);
        }
        return sum;
    }
private:
    static inline int lowbit(int x) { 
        return x & (-x); 
    }
    vector<int> sums_;
};