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

快速排序

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

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

请您为我打分吧!

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

发表评论

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