2022年复试题

常见算法整理DFS、贪心、快速选择、摩尔投票与滑动窗口在算法题中有一些高频且实用的经典方法。本文结合几个典型问题系统整理这些算法的核心思想与代码实现适合作为复习与面试参考。一、判断一个数是3的幂次方#includeiostream #includecmath using namespace std; int main(){ int n; cin n; if(n 0){ cout 不是3的幂次方 endl; return 0; } while(n % 3 0){ n / 3; } if(n 1){ cout 是3的幂次方 endl; return 0; } cout 不是3的幂次方 endl; return 0; }二、贪心算法——最优解快速求解 问题用最少张数凑金额核心思想每次优先使用最大面额✅ 代码#includeiostream#includevectorusingnamespacestd;intmain(){vectorintdenominations{100,50,20,10,5,1};vectorintcount(6,0);intamount;cinamount;for(inti0;i6;i){count[i]amount/denominations[i];amount%denominations[i];}cout最少张数方案endl;for(inti0;i6;i){coutdenominations[i]元: count[i]张endl;}return0;} 总结 贪心适合标准货币系统如人民币三、快速选择QuickSelect——找最大值 问题在无序数组中找最大值核心思想利用快排 partition每次只递归一边剪枝✅ 代码intfindMax(inta[],intl,intr){if(lr)returna[l];intil,jr;intpivota[l];while(ij){while(ija[j]pivot)j--;while(ija[i]pivot)i;if(ij)swap(a[i],a[j]);}swap(a[l],a[i]);returnfindMax(a,l,i);}快排的代码#includeiostream using namespace std; void quickSort(int a[], int l, int r){ if(l r) return; int i l, j r; int pivot a[l]; while(i j){ while(i j a[j] pivot) j--; while(i j a[i] pivot) i; if(i j) swap(a[i], a[j]); } swap(a[l], a[i]); quickSort(a, l, i - 1); quickSort(a, i 1, r); } int main(){ int n; cin n; int a[n]; for(int i 0; i n; i){ cin a[i]; } quickSort(a, 0, n - 1); for(int i 0; i n; i){ cout a[i] ; } return 0; } 总结 本质快排 剪枝 快速选择四、摩尔投票法——多数元素问题 问题找出现次数 n/2 的元素✅ 代码intmajorityElement(vectorintnums){intcandidate0,count0;for(intx:nums){if(count0){candidatex;count1;}elseif(xcandidate){count;}else{count--;}}count0;for(intx:nums){if(xcandidate)count;}returncountnums.size()/2?candidate:-1;}或者#includeiostream #includeunordered_map using namespace std; int main(){ unordered_mapint, int cnt; int n; cin n; for(int i 0; i n; i){ int x; cin x; cnt[x]; } for(auto c : cnt){ if(c.second n / 2){ cout c.first endl; } } return 0; } 核心思想相同1不同-1最终剩下的就是候选人五、滑动窗口——连续子数组问题 问题找所有连续正整数使和为 n✅ 代码inti1,j1,sum0;while(in/2){if(sumn){sumj;}elseif(sumn){sum-i;}else{for(intki;kj;k){coutk ;}coutendl;sum-i;}}