如今不论是校招还是社招，大多数公司都会有笔试+面试的算法题，以此来考察候选人的数据结构和算法能力，因此我们面试前最好复习下算法，简单来说就是刷题呗！
以下是本人社招时在Leetcode和牛客网上的大厂的高频题，大概二三百道，此系列只列出最热门的一百来道，代码都是Leetcode上的，可以正常运行。大家可以根据下面推荐的题目来有选择的刷题，最好是进入Leetcode或牛客来刷，里面有许多优秀解法可以参考！
常见算法有背包、DFS、BFS、动态规划、数组、状态压缩、图优化、数学推导、字符串、链表二叉树、邻接表、图优化等等。
下面是正常的题目，大家可以参考一下：
1、比较版本号
https://leetcode-cn.com/problems/compare-version-numbers/
class Solution {
public:
void sub(string version1,vector &res){
while (!version1.empty()) {
int i = 0;
while (i < version1.size() && version1[i] != '.') {
i++;
}
string s1 = version1.substr(0, i);
res.push_back(s1);
if (i + 1 >= version1.size())
break;
version1 = version1.substr(i+1);
}
}
int compareVersion(string version1, string version2) {
vector res1;
vector res2;
sub(version1,res1);
sub(version2,res2);
int i = 0;
for(;ik2)return 1;
if(k1 >& cost) {
// write code here
for(int i = 0; i <= n; i++) p[i] = i;//初始化并查集
//排序
sort(cost.begin(),cost.begin() + m, [](vector& a, vector &b){return a[2] < b[2];});
int res = 0;
for(int i = 0; i < m; i++)
{
if(find(cost[i][0]) != find(cost[i][1]))//如果不是同一个集合，
{
res += cost[i][2];//加路
p[find(cost[i][0])] = find(cost[i][1]);//合并集合
}
}
return res;
}
};
3、栈和排序
class Solution {
public:
vector solve(int* a, int aLen) {
stacks;//定义一个栈用来存储数据
int n = aLen;
vectorres;//用来返回结果
vector vis(aLen + 10,0);//用来标记哪个数字出现过
for(int i = 0;i < aLen;i ++){//遍历数组
s.push(a[i]);//压入栈
vis[a[i]] = 1;//压入一个数就把对应的数字标记为1
while(n && vis[n]) n--;//检测现有栈中有多少个数出现了就是较大的哪些数出现了（从大到小）
while(!s.empty() && n <= s.top()){
//然后将栈中>=n的元素出栈
res.push_back(s.top());
s.pop();
}
}
//如果栈没为空就按照栈中原样直接出栈
while(!s.empty()){
int temp = s.top();
res.push_back(temp);
s.pop();
}
return res;
}
};
4、01背包
class Solution {
public:
int knapsack(int V, int n, vector >& vw) {
// write code here
vector dp(V+1,0);
for(auto it:vw){
for(int i = V;i>0;i--){
if(i >= it[0])
dp[i] = max(dp[i],dp[i-it[0]]+it[1]);
}
}
return dp[V];
}
};
5、最大公约数
class Solution {
public:
int gcd(int a, int b) {
if(a%b==0){return b;}
else{return gcd(b,a%b);}
}
};
6、数组中只出现一次的数（其它数出现k次）
public int foundonceNumber (int[] arr, int k) {
// 每个二进制位求和，如果某个二进制位不能被k整除，那么只出现一次的那个数字在这个二进制位上为1。
int[] binarySum = new int[32];
for(int i = 0; i< 32; i++){//求每个二进制位的和
int sum = 0;
for(int num : arr){
sum += (num >>i & 1);//依次右移num，同1相与，计算每一位上1的个数
}
binarySum[i] = sum;
}
int res = 0;
for (int i = 0; i< 32; i++){
if(binarySum[i]%k!=0){
res += 1< ans;
//把n个盘子从Left 借助 Mid，移动到Right柱子上
void Hanoi(int n,string Left,string Mid,string Right)
{
if(n==0){return;}
//把n-1个盘子从Left 借助 Right，移动到Mid柱子上
Hanoi(n-1,Left,Right,Mid);
//把剩下最大的那一个盘子从Left移动到 Right柱子上
string t = "move from " + Left + " to " + Right;
ans.push_back(t);
//把n-1个盘子从Mid 借助 Left，移动到,Right柱子上
Hanoi(n-1,Mid,Left,Right);
}
vector getSolution(int n) {
Hanoi(n,"left","mid","right");
return ans;
}
};
8、拼接所有的字符串产生字典序最小的字符串
class Solution {
public:
static bool cmp(const string a, const string b) {
return (a + b) < (b + a);
}
string minString(vector& strs) {
string ans;
sort(strs.begin(), strs.end(), cmp);
for (int i = 0; i < (int)strs.size(); ++i) ans += strs[i];
return ans;
}
};
//2021.06.14
9. 判断子序列
(1)
class Solution {
public:
bool isSubsequence(string s, string t) {
int n = s.length(), m = t.length();
int i = 0, j = 0;
while (i < n && j < m) {
if (s[i] == t[j]) {
i++;
}
j++;
}
return i == n;
}
};
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/is-subsequence/solution/pan-duan-zi-xu-lie-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
(2)
//dp解法
bool isSubsequence(string s, string t){
int n = s.length(),m = t.length();
//dp数组dp[i][j]表示字符串t以i位置开始第一次出现字符j的位置
vector> dp(m + 1,vector (26,0));
//初始化边界条件，dp[i][j] = m表示t中不存在字符j
for(int i=0;i<26;i++){
dp[m][i] = m;
}
//从后往前递推初始化dp数组
for(int i = m - 1;i>=0;i--) {
for(int j=0;j<26;j++){
if(t[i] == 'a' + j){
dp[i][j] = i;
}else {
dp[i][j] = dp[i + 1][j];
}
}
}
int add = 0;
for(int i = 0;i& removable) {
int ns = s.size();
int np = p.size();
int n = removable.size();
// 辅助函数，用来判断移除 k 个下标后 p 是否是 s_k 的子序列
auto check = [&](int k) -> bool {
vector state(ns, 1); // s 中每个字符的状态
for (int i = 0; i < k; ++i){
state[removable[i]] = 0;
}
// 匹配 s_k 与 p
int j = 0;
for (int i = 0; i < ns; ++i){
// s[i] 未被删除且与 p[j] 相等时，匹配成功，增加 j
if (state[i] && s[i] == p[j]){
++j;
if (j == np){
return true;
}
}
}
return false;
};
// 二分查找
int l = 0;
int r = n + 1;
while (l < r){
int mid = l + (r - l) / 2;
if (check(mid)){
l = mid + 1;
}
else{
r = mid;
}
}
return l - 1;
}
};
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/maximum-number-of-removable-characters/solution/ke-yi-chu-zi-fu-de-zui-da-shu-mu-by-leet-9ve9/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
