2022年复试题

常见算法整理：DFS、贪心、快速选择、摩尔投票与滑动窗口

在算法题中，有一些高频且实用的经典方法。本文结合几个典型问题，系统整理这些算法的核心思想与代码实现，适合作为复习与面试参考。

一、判断一个数是3的幂次方

#include<iostream> #include<cmath> 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; }

二、贪心算法——最优解快速求解

📌 问题：用最少张数凑金额

核心思想

• 每次优先使用最大面额

✅ 代码

#include<iostream>#include<vector>usingnamespacestd;intmain(){vector<int>denominations={100,50,20,10,5,1};vector<int>count(6,0);intamount;cin>>amount;for(inti=0;i<6;i++){count[i]=amount/denominations[i];amount%=denominations[i];}cout<<"最少张数方案："<<endl;for(inti=0;i<6;i++){cout<<denominations[i]<<"元: "<<count[i]<<"张"<<endl;}return0;}

🧠 总结

👉 贪心适合：标准货币系统（如人民币）

三、快速选择（QuickSelect）——找最大值

📌 问题：在无序数组中找最大值

核心思想

• 利用快排 partition
• 每次只递归一边（剪枝）

✅ 代码

intfindMax(inta[],intl,intr){if(l==r)returna[l];inti=l,j=r;intpivot=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]);returnfindMax(a,l,i);}

快排的代码

#include<iostream> 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(vector<int>&nums){intcandidate=0,count=0;for(intx:nums){if(count==0){candidate=x;count=1;}elseif(x==candidate){count++;}else{count--;}}count=0;for(intx:nums){if(x==candidate)count++;}returncount>nums.size()/2?candidate:-1;}

或者

#include<iostream> #include<unordered_map> using namespace std; int main(){ unordered_map<int, 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

✅ 代码

inti=1,j=1,sum=0;while(i<=n/2){if(sum<n){sum+=j++;}elseif(sum>n){sum-=i++;}else{for(intk=i;k<j;k++){cout<<k<<" ";}cout<<endl;sum-=i++;}}