保研秋招实习机试准备——C++算法题（三）
·
上一篇：
提示：后续对于新加入的力扣题目（主要是hot100），我会同时给出力扣格式代码和带有输入输出的完整代码
六、排序相关问题
排序这一块，对应机试题目需要使用的排序的建议直接使用sort函数（可自定义排序方式），但对于经典的排序算法原理还是要学一下的，企业面试时会考察。
这里推荐一个排序算法题文章和模板代码文章
必刷算法题之排序篇（题目及代码）---C++_c++冒泡排序题目-CSDN博客
C++模板实现十大排序算法_c++十大排序算法模板代码-CSDN博客
此外对于sort的自定义比较函数，C++官方技术文档是这样解释的：二元函数，接受范围内的两个元素作为参数，并返回一个可转换为bool的值。返回值指示作为第一个参数传递的元素是否按照其定义的特定严格弱排序优先于第二个参数。（我觉得没有什么不这个更清晰的解释了）
（6-1）P1059 [NOIP 2006 普及组] 明明的随机数
对 \( N \) 个 1 到 1000 间的随机整数，去除重复数后从小到大排序，输出不同数的个数及排序结果。
去重也可以使用stl中的unique
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,tmp;
cin >> n;
set<int> s;
for(int i = 0;i<n;i++){
cin >> tmp;
s.insert(tmp);
}
cout << s.size()<<endl;
for(auto&i:s){
cout<< i<<" ";
}
cout << endl;
return 0;
}
//去重也可以使用stl中的unique
/*
set集合是c++ stl库中自带的一个容器，set具有以下两个特点：
1、set中的元素都是排好序的
2、set集合中没有重复的元素
常用操作：
begin() 返回set容器的第一个元素的地址
end() 返回set容器的最后一个元素地址
clear() 删除set容器中的所有的元素
empty() 判断set容器是否为空
max_size() 返回set容器可能包含的元素最大个数
size() 返回当前set容器中的元素个数
erase(it) 删除迭代器指针it处元素
insert(a) 插入某个元素*/（6-2）P1068 [NOIP 2009 普及组] 分数线划定
根据报名选手的笔试成绩，按计划录取人数的150%（向下取整）划定面试分数线，输出分数线、进入面试的人数，以及这些选手的报名号和成绩（成绩高到低，同分时报名号小的在前）。
//结构体或者下标数组
#include<bits/stdc++.h>
using namespace std;
struct scoreline{
int k,s;
}nums[5001]; //a存储结构体
//比较函数:
/*C++技术文档解释：二元函数，接受范围内的两个元素作为参数，并返回一个可转换为bool的值。返回值指示作为第一个参数传递的元素是否按照其定义的特定严格弱排序优先于第二个参数。*/
bool cmp(scoreline a,scoreline b){
if(a.s!=b.s) return a.s>b.s;
return a.k < b.k;
}
//主函数
int main(){
int n,m;
cin >> n>>m;
for(int i=0 ;i<n;i++){
cin >> nums[i].k >> nums[i].s;
}
sort(nums,nums+n,cmp);
int t = m*1.5; //面试线人数 int 自动向下转型
//考虑与分数线重分的
while(t<n){
if(nums[t].s == nums[t-1].s) t++;
else break;
}
cout <<nums[t-1].s<<' '<<t<<endl;
for(int i =0;i<t;i++){
cout << nums[i].k <<' '<< nums[i].s <<endl;
}
return 0;
}（6-3）P1051 [NOIP 2005 提高组] 谁拿了最多奖学金
给定若干学生的期末成绩、班级评议成绩等信息，依据五种奖学金的不同条件，计算出获奖金最多的学生姓名、该学生奖金总数，以及所有学生的奖金总数。
#include<bits/stdc++.h>
using namespace std;
struct stu{
string name;
int s,sc,p,m; //s期末平均成绩 sc班级评议成绩 p论文数 m奖金
char x,y ; // x是否是学生干部 y是否是西部省份学生
}nums[101];
//比较函数
bool cmp(stu a ,stu b){
return a.m > b.m;
}
int main(){
int n,sum=0;
cin >> n;
for(int i = 0;i<n;i++){
int tmp_m=0; //奖金临时储存
cin >> nums[i].name>>nums[i].s>>nums[i].sc>>nums[i].x>>nums[i].y>>nums[i].p;
if(nums[i].s > 80 && nums[i].p >= 1) tmp_m += 8000;
if(nums[i].s>85&& nums[i].sc>80) tmp_m+= 4000;
if (nums[i].s > 90) tmp_m += 2000;
if (nums[i].s > 85 && nums[i].y == 'Y') tmp_m += 1000;
if (nums[i].sc > 80 && nums[i].x == 'Y') tmp_m += 850;
nums[i].m = tmp_m;//奖奖可兼得
sum += tmp_m;
}
// sort(nums,nums+n,cmp); 不全对 使用stable_sort 保持相等值相对顺序不变
stable_sort(nums,nums+n,cmp);
cout <<nums[0].name <<"\n"<<nums[0].m<<"\n"<<sum;
return 0;
}
//普通模拟
/*#include<bits/stdc++.h>
using namespace std;
int n, a, b, e, sum, Sum, mx;
string s, ans;
int main () {
cin >> n;
for (char c, d; n--; Sum+=sum) {
cin >> s >> a >> b >> c >> d >> e;
sum=(a>80&&e)*8000+
(a>85&&b>80)*4000+
(a>90)*2000+
(a>85&&d=='Y')*1000+
(b>80&&c=='Y')*850;
if (sum>mx)
mx=sum,
ans=s;
}
cout << ans << '\n' << mx << '\n' << Sum;
return 0;
}
*/（6-4）P1908 逆序对
给定一段正整数序列，统计其中逆序对（满足 \(a_i > a_j\) 且 \(i < j\) 的有序对）的数量。
思路：在归并排序合并两个有序子数组时，当取右子数组元素时，左子数组中剩余的元素都能与该右子数组元素构成逆序对，从而累加得到逆序对总数。
//归并排序的核心思想是 “分治”：先将大区间拆分为小区间，排序后再合并。
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>a,tmp;//a存储原始序列
//tmp归并排序的临时数组（用于合并阶段避免原数组操作覆盖）
long long res=0;
void merge(int l,int r){
//对区间[l, r]内的元素进行归并排序，并统计逆序对数量。
if(l==r)return;
int m = l+(r-l)/2,i=l,j=m+1,k=l;
//i左区间的起始指针,k临时数组c的起始指针
merge(l,m);//递归排序左半区间
merge(m+1,r);
while(i<=m&&j<=r){//当左右区间都还有元素时，比较并合并
if(a[i]<=a[j]) tmp[k++] =a[i++];
else{
tmp[k++] = a[j++];
res += m-i+1;//由于递归,左右区间已排序,故i后的所有元素都与ap[j]构成逆序对
}
}
//有一方区间为空,直接将剩余的添在合并的后面
while(i<=m) tmp[k++] = a[i++];
while(j<=r) tmp[k++] = a[j++];
for(int i=l;i<=r;i++) a[i] = tmp[i];//复制回原数组
}
int main(){
cin >> n;
//不调整a,tmp会导致越界访问，vector动态大小是通过push_back等方法自动扩大容量
//而未预先分配了任意位置的访问权限，刚定义的 vector<int>a，其size()是0
a.resize(n+1);
tmp.resize(n+1);
for(int i=1;i<=n;i++) cin >> a[i];
merge(1,n);
cout << res;
return 0;
}（6-5）215. 数组中的第K个最大元素
题意：给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
TopK 问题，典型的解法有「快排思想」和「堆排思想」。
维护一个大小为 k 的最小堆；
遍历数组，当堆的大小小于 k 时，直接加入堆；
堆满时，比较当前元素与堆顶元素：如果大于堆顶，弹出堆顶并加入当前元素，否则跳过；最后堆顶元素就是第 k 大的元素。
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, k; // n:数组元素个数，k:要查找的第k个最大元素
cin >> n >> k;
vector<int> nums(n); // 存储输入的数组
for (int i = 0; i < n; ++i) {
cin >> nums[i];
}
// 定义小顶堆（优先队列），堆顶元素为当前堆中最小的元素
// greater<int> 表示使用升序排序，使队列顶部始终是最小元素
priority_queue<int, vector<int>, greater<int>> pq;
// 先将数组的前k个元素放入堆中
for (int i = 0; i < k; ++i) {
pq.push(nums[i]);
}
// 遍历数组中剩余的元素
for (int i = k; i < n; ++i) {
// 若当前元素比堆顶元素大，说明堆顶元素不可能是第k大元素
// 弹出堆顶的小元素，将当前大元素入堆
if (nums[i] > pq.top()) {
pq.pop(); // 移除堆中最小元素
pq.push(nums[i]);// 加入当前更大的元素
}
}
// 经过上述操作，堆中保留的是数组中最大的k个元素
// 堆顶元素即为这k个元素中最小的，也就是整个数组的第k个最大元素
cout << pq.top() << endl;
return 0;
}
----------------------------------------------------------
//leetcode格式代码
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
// 小顶堆，堆顶是当前堆中最小元素
priority_queue<int, vector<int>, greater<int>>pq;
// 先将前k个元素入堆
for (int i = 0; i < k; ++i) {
pq.push(nums[i]);
}
int n = nums.size();
// 遍历剩余元素
for (int i = k; i < n; ++i) {
// 若当前元素比堆顶大，替换堆顶
if (nums[i] > pq.top()) {
pq.pop();
pq.push(nums[i]);
}
}
// 堆顶即为第k大元素
return pq.top();
}
};快速排序方法：
- 利用快速排序的分区操作，每次确定一个基准元素的位置
- 若基准位置等于目标位置（第 k 大对应升序的
nums.size()-k），直接返回该元素
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
// 目标位置：第k大元素在升序排列中对应的索引
int target = nums.size() - k;
int l = 0, r = nums.size() - 1;
// 循环查找，直到找到目标位置
while (true) {
int p = partition(nums, l, r); // 分区后基准元素的位置
if (p == target) {
return nums[p]; // 找到第k大元素
} else if (p < target) {
l = p + 1; // 目标在右侧区间
} else {
r = p - 1; // 目标在左侧区间
}
}
}
private:
// 分区函数：将小于等于基准的元素放左侧，大于基准的放右侧
int partition(vector<int>& nums, int l, int r) {
int pivot = nums[r]; // 选最右侧元素作为基准
int i = l; // i标记小于等于基准区域的右边界
// 遍历区间内元素，进行分区
for (int j = l; j < r; j++) {
if (nums[j] <= pivot) {
swap(nums[i], nums[j]); // 将小于等于基准的元素移到左侧
i++; // 扩大左侧区域
}
}
swap(nums[i], nums[r]); // 将基准元素放到最终位置
return i; // 返回基准元素的索引
}
};
（6-6）347. 前 K 个高频元素
整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。
常见关于堆的面试：1. 实现一个堆数据结构（插入，删除） 2. 求 top k 3. 求中位数 4. k 路归并……
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, k; // n：数组元素数量，k：需要返回的高频元素个数
cin >> n >> k;
vector<int> nums(n); // 存储输入的数组
for (int i = 0; i < n; ++i) {
cin >> nums[i];
}
map<int, int> mp;// 统计每个元素出现次数，键为元素值，值为次数
for (int num : nums) {
mp[num]++; // 对应元素的计数加1
}
// 大顶堆，存储<出现次数, 元素值>，默认按默认按出现次数从大到小排序
priority_queue<pair<int, int>> pq;
for (auto& entry : mp) {
// 将次数和元素值存入堆中，次数作为排序依据
pq.emplace(entry.second, entry.first);
}
// 存储结果的向量，将前k个高频元素按顺序存入
vector<int> res;
while (k--) {
// 堆顶是当前出现次数最多的元素，取其元素值存入结果
res.emplace_back(pq.top().second);
pq.pop(); // 弹出堆顶元素，继续处理下一个高频元素
}
// 输出结果，元素间用空格分隔
for (size_t i = 0; i < res.size(); ++i) {
if (i > 0) {
cout << " ";
}
cout << res[i];
}
cout << endl;
return 0;
}
----------------------------------------------------------
//leetcode格式代码
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
map<int,int> mp;//<值，次数>
priority_queue<pair<int,int>> pq;//默认大顶堆
for(int i:nums){
mp[i]++;
}
for(auto a:mp){
pq.emplace(a.second,a.first);//<次数，值>
}
vector<int> res;
while(k--){
res.emplace_back(pq.top().second);
pq.pop();
}
return res;
}
};桶排序：将待排序的序列分到若干个桶中，每个桶内的元素再进行个别排序。
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
int n=0;//用于确定桶数量
map<int,int>mp;
for(auto&num: nums){
mp[num]++;//计数
n = max(n,mp[num]);
}
//把出现次数相同的元素放同一个桶中
vector<vector<int>>buckets(n+1);
//pair的第一个为元素 第二个为次数
for(auto& pair:mp) buckets[pair.second].push_back(pair.first);
//倒序遍历buckets,前k个大的元素为结果
vector<int>res;
for(int i = n;i>=0&&res.size()<k;i--){
for(auto x:buckets[i]){
res.push_back(x);
}
}
return res;
}
};（6-7）148. 排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
纯链表类的题洛谷见的比较少，就不提供输入输出格式了，代码太长
思路：分治 归并排序
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
//分治 归并排序
class Solution {
public:
ListNode* middleNode(ListNode* head){
ListNode* pre = head; //记录s的前一个节点（用来断开）
ListNode* s = head;//慢指针
ListNode* f = head;//快指针
while(f&&f->next){
pre = s;
s = s->next;
f= f->next->next;
}
pre->next = nullptr; //断开中间节点与前一个节点
return s;
}
ListNode* mergeTwoLists(ListNode* list1,ListNode* list2){
ListNode dum ;//对象
ListNode* cur = &dum; //指向dum地址
while(list1&&list2){
if(list1->val < list2->val){
cur->next = list1;
list1 = list1->next;
}else{
cur->next = list2;
list2 = list2->next;
}
cur = cur->next;
}
cur->next = list1?list1:list2;
return dum.next;
}
ListNode* sortList(ListNode* head) {
if (head == nullptr || head->next == nullptr ){
return head;
}
ListNode* head2 = middleNode(head);
//递归 分治
head = sortList(head);
head2 = sortList(head2);
return mergeTwoLists(head,head2);
}
};七、二分问题
对于二分有一个@liweiwei1419的题解写的分成非常好，有深度，强烈推荐观看：二分法模板
（7-1）P1024 [NOIP 2001 提高组] 一元三次方程求解
给定一元三次方程 \( ax^3 + bx^2 + cx + d = 0 \) 的系数 \( a,b,c,d \)，已知方程有三个不同实根（范围在 \(-100\) 到 \(100\) 之间，且根间距≥1），从小到大输出这三个实根，精确到小数点后2位。
小数位数 使用scanf 和printf
暴力解法，可ak
#include<iostream>
#include<cstdio>
using namespace std;
double a,b,c,d;// 题目要的数据是小数点后2位所以定义首先用double
int num;// num用来记录解的个数 因为一元三次方程只有三个解 解达到三个以后就break掉 减少多余循环
int main()
{
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);// double类型用 lf 输入
for(double i=-100.00;i<=100.00;i+=0.001)// 最后结果保存两位数 所以这里i每次加0.001（n只有100所以暴不了）
{
double j=i+0.001;
double y1 = a*i*i*i+b*i*i+c*i+d;
double y2 = a*j*j*j+b*j*j+c*j+d;
if(y1>=0&&y2<=0||y1<=0&&y2>=0)// 若存在两个数x1，x2且x1<x2，f（x1）*f（x2）<0 则方程解肯定在x1~x2范围内 基本数学原理
printf("%.2f ",i),num++;// 小数点后两位输出
if(num==3) break;// 解达到三个break掉
}
return 0;
}
//小数位数 使用scanf 和printf二分解法（注意浮点数二分的细微差异）
//二分解法
#include<bits/stdc++.h>
using namespace std;
double a,b,c,d;
int num=0;
double fc(double x){
return a*x*x*x+b*x*x+c*x+d;//三次方程
}
int main(){
double l,r,mid,x1,x2;
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);// double类型用 lf 输入
for(int i=-100;i<100;i++){//两个根的差的绝对值>=1,每个大小为1的区间至多1个解
//所以枚举步长为1，在每个长度1的区间内进行二分查找
l=i,r = i+1;
x1 = fc(l),x2 = fc(r);
if(!x1){//左端点是0直接输出
printf("%.2lf",l);
num++;
}
if(x1*x2<0){
//用 l=mid+1 或 r=mid-1 这类整数二分的更新方式并不适用于浮点数二分
while(r-l>=0.001){
mid = (r+l)/2;//由于while(r-l>=0.001)，所以l,r都用mid更新不会死循环
if(fc(mid)*fc(r)<0) l=mid;// 根在[mid, r]
else r = mid;// 根在[l, mid]
}
printf("%.2lf",r);
num ++;
}
if(num==3) break;
}
return 0;
}（7-2）287. 寻找重复数
题意：给定长度为 \(n + 1\)、元素在 \([1, n]\) 范围内的数组，其中只有一个重复整数，要求不修改数组且用 \(O(1)\) 额外空间找出这个重复数。
可以利用二分查找思想，通过统计特定范围内的数字个数判断重复数位置，当然本题也可使用哈希表set或快慢指针 （参考力扣142题 环形链表）做
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> nums(n + 1); // 题目中数组长度为n+1
for (int i = 0; i <= n; i++) {
cin >> nums[i];
}
// 二分查找寻找重复数
int min = 1, max = n;
while (min < max) {
int mid = (min + max) / 2;
int cnt = 0; // 统计[min, mid]范围内的数字个数
for (int num : nums) {
if (num >= min && num <= mid) {
cnt++;
}
}
// 若个数超过区间长度，说明重复数在左区间
if (cnt > mid - min + 1) {
max = mid;
} else {
// 否则在右区间
min = mid + 1;
}
}
cout << min << endl;
return 0;
}
------------------------------------------
//leetcode格式代码：
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int min = 1;
int max = nums.size();
while(min< max){
int mid = (min+max) / 2;
int cut = 0;
for(int n:nums){
if(n>=min && n<=mid) cut++;
}
if(cut > mid-min+1){ //存在
max = mid;
}else{
min = mid+1; //加 1 是为了跳过 mid（因为 mid 所在的左侧区间已被排除），避免重复检查。
}
}
return min;
}
};
（7-3）34. 在排序数组中查找元素的第一个和最后一个位置
给定非递减排序数组和目标值，用 \(O(\log n)\) 时间找目标值在数组里的起始和结束位置，不存在则返回 \([-1,-1]\)。
对于二分时选择开区间还是闭区间推荐看灵神的视频二分查找 红蓝染色法【基础算法精讲 04】
- 自定义
lower_bound函数，使用开区间二分法查找第一个≥目标值的位置 - 起始位置
start为第一个≥target的位置 - 结束位置通过查找第一个≥
target+1的位置再减 1 得到
#include<bits/stdc++.h>
using namespace std;
// 查找第一个大于等于target的位置（开区间二分）
int lower_bound(vector<int>& nums, int target) {
int l = -1, r = nums.size();
while (l + 1 < r) {
int mid = l + (r - l) / 2; // 防溢出
if (nums[mid] >= target) {
r = mid;
} else {
l = mid;
}
}
return r;
}
int main() {
int n, target;
cin >> n >> target;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
int start = lower_bound(nums, target);
// 检查目标值是否存在
if (start == n || nums[start] != target) {
cout << "-1 -1" << endl;
} else {
// 查找target+1的起始位置，减1即为target的结束位置
int end = lower_bound(nums, target + 1) - 1;
cout << start << " " << end << endl;
}
return 0;
}
----------------------------------------
//leetcode格式代码
//开区间二分
class Solution {
int lower_bound(vector<int>&nums,int target){
int l = -1,r = nums.size();
while(l+1<r){
int mid = l+(r-l)/2; //防溢出
if(nums[mid]>=target){
r = mid;
}
else{
l = mid;
}
}
return r;
}
public:
vector<int> searchRange(vector<int>& nums, int target) {
int start = lower_bound(nums,target);
if(start == nums.size()||nums[start]!=target){
return {-1,-1};
}
int end = lower_bound(nums,target+1)-1;
return{start,end};
}
};
（7-4）33. 搜索旋转排序数组
给一个升序且元素互不相同的旋转数组（原数组在未知下标左旋转得到）和目标值，用 \(O(\log n)\) 时间找目标值下标，不存在返回 \(-1\)。（数组分两段递增）
但凡是从有序序列中找某个数，我们第一反应应该是「二分」。
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, target; // n:数组长度，target:待查找的目标值
cin >> n >> target;
vector<int> nums(n); // 存储旋转后的升序数组
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
int l = 0; // 左边界
int r = nums.size() - 1; // 右边界
int mid; // 中间位置
// 核心逻辑：利用旋转数组的局部有序性缩小查找范围
while (l <= r) {
mid = l + (r - l) / 2; // 计算中间位置，避免(l + r)溢出
if (nums[mid] == target) {
// 找到目标值，直接返回下标
cout << mid << endl;
return 0;
}
// 左侧区间[l, mid]是连续递增的（未旋转部分）
if (nums[l] <= nums[mid]) {
// 目标值在左侧区间内，缩小右边界
if (nums[l] <= target && target < nums[mid]) {
r = mid - 1;
} else {
// 目标值不在左侧，缩小左边界到右侧区间
l = mid + 1;
}
} else {
// 右侧区间[mid, r]是连续递增的（未旋转部分）
// 目标值在右侧区间内，缩小左边界
if (nums[mid] < target && target <= nums[r]) {
l = mid + 1;
} else {
// 目标值不在右侧，缩小右边界到左侧区间
r = mid - 1;
}
}
}
// 循环结束仍未找到，说明目标值不存在
cout << -1 << endl;
return 0;
}
--------------------------------------
//leetcode格式
class Solution {
public:
int search(vector<int>& nums, int target) {
//但凡是从有序序列中找某个数，我们第一反应应该是「二分」。
int l = 0;
int r= nums.size()-1;
int mid =0;
while(l<=r){
mid = l +(r-l)/2 ;
if(nums[mid]==target) return mid;
if(nums[l]<=nums[mid]){//左侧区间 [left,mid]连续递增
// target 位于左侧 在左侧 [left,mid) 查找
if(nums[l] <=target&& target<nums[mid]) r = mid-1;
else l = mid+1;//否则在右侧区间查找
}else{// [mid,right] 连续递增, 加等号，因为 right 可能是 target
if(nums[mid] <target&& target<=nums[r]) l = mid+1;
else r = mid-1;
}
}
return -1;
}
};更多推荐
29
0- 0
已为社区贡献4条内容
所有评论(0)