面试时候需要做的准备(持续更新~)

快速排序

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;
    }
};

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];
    }
};

这篇文章是否对您有帮助?

请您为我打分吧!

平均分数 / 5. 投票数量:

发表评论

电子邮件地址不会被公开。 必填项已用*标注