【备战秋招】——算法题目训练和总结day3😎
- 前言🙌
- BC149简写单词
- 题解思路分析
- 代码分享：
- dd爱框框
- 题解思路分析
- 代码分享：
- 除2！
- 题解思路分析
- 代码分享：
- 总结撒花💞
😎博客昵称：博客小梦
😊最喜欢的座右铭：全神贯注的上吧！！！
😊作者简介：一名热爱C/C++，算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主！
😘博主小留言：哈喽！😄各位CSDN的uu们，我是你的博客好友小梦，希望我的文章可以给您带来一定的帮助，话不多说，文章推上！欢迎大家在评论区唠嗑指正，觉得好的话别忘了一键三连哦！😘
前言🙌
哈喽各位友友们😊，我今天又学到了很多有趣的知识，现在迫不及待的想和大家分享一下！😘都是精华内容，可不要错过哟！！！😍😍😍
BC149简写单词
链接: 149简写单词
题解思路分析
算法思想：模拟。
- 首先是认真审题，结合示例理解。
- 我们可以利用cin流提取的特点，巧妙的跳过空格。每一次读到一个单词，然后将首字母进行一个简单的判断，如果是大写字母就转小写。
代码分享：
#include <iostream>
using namespace std;
int main()
{
string s;
while(cin >> s)
{
if(s[0] >= 'a' && s[0] <= 'z') cout << (char)(s[0] - 32);
else cout << s[0];
}
return 0;
}
dd爱框框
链接: dd爱框框
题解思路分析
算法思想：同向双指针/滑动窗口
- 首先是认真审题，结合示例理解。
- 写出滑动窗口四部法则：进窗口、判断、出窗口、更新结果。注意什么时候要跟新结果，这个因题而异。这里的更新结果放到判断和出窗口之间的位置。
- 进窗口：sum += a[r];
- 判断：sum >= x
- 出窗口：sum -= a[l++];
- 更新结果：r - l + 1< mindis
- 根据四步，完成代码，并注意细节即可。
代码分享：
#include<iostream>
using namespace std;
const int N = 1e7 + 10;
int a[N];
int l = 0, r = 0, sum = 0;
int mindis = 0x3f3f3f3f;
int main()
{
int n , x;
int left,right;
cin >> n >> x;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
}
while(r <= n)
{
//进窗口
sum += a[r];
//判断
while(sum >= x)
{
//更新
if(r - l + 1< mindis)
{
left = l;
right = r;
mindis = r - l + 1;
}
//出窗口
sum -= a[l++];
}
r++;
}
cout << left << " " << right << endl;
return 0;
}
除2！
链接: 除2！
题解思路分析
算法思想：模拟 + 贪心 + 堆
- 首先是认真审题，结合示例理解。这里的数据个数和范围都比较大，如果累加，会有溢出情况的。因此我们定义的sum为long long 类型。博主就是因为没审清楚题，掉在坑里半天了。。。。
- 既然要使得最后数组之和最小，那很自然的我们就想到贪心的思想，即每一次操作都把最大的那个偶数进行减半。
- 我们借助堆数据结构，可以进行一个很好的控制，写起代码来也比较好控制。
代码分享：
#include<iostream>
#include<queue>
using namespace std;
int main()
{
int n,k;
cin >> n >> k;
long long sum = 0;
int a = 0;
priority_queue<int> heap;
for(int i = 0; i < n; i++)
{
cin >> a;
sum += a;
if(a % 2 == 0)
heap.push(a);
}
while(!heap.empty() && k--)
{
int t = heap.top() / 2;
heap.pop();
sum -= t;
if(t % 2 == 0)
heap.push(t);
}
cout << sum << endl;
return 0;
}
总结撒花💞
本篇文章旨在分享的是算法题目题解知识。希望大家通过阅读此文有所收获！
😘如果我写的有什么不好之处，请在文章下方给出你宝贵的意见😊。如果觉得我写的好的话请点个赞赞和关注哦~😘😘😘
