一、小乐乐改数字
题目解析
这道题，它们给定一个数，我们要对它进行修改；如果某一位是奇数，就把它变成1,；如果是偶数，就把它变成0；
让我们输出最后得到的数。
算法思路
这道题，总体来说是非常简单的啦，解法呢，就是模拟整个过程。
当然呢这里模拟，也不是去一次去这个数的某一位去操作，那太麻烦了。
我们可以直接按照字符串进行输出，然后遍历字符串，判断这一个数是奇数还是偶数，然后进行操作。
这里我们通过查看
ASSIC码可以发现，字符0到9数字0到9它的奇偶性是一样的，所以我们进行判断时就不用去-'0'了
最后呢我们需要取出前缀0，这里可以使用stoi函数，也可以自己实现去除前缀0。
代码实现
#include <iostream>
#include <string>
using namespace std;
string str;
int main() {
cin >> str;
for (int i = 0; i < str.size(); i++) {
if (str[i] % 2 == 0) str[i] = '0';
else str[i] = '1';
}
cout << stoi(str) << endl;
return 0;
}
二、十字爆破
题目解析
OK啊，这道题输入一个
n*m的二维数组，让我们求它每一个位置方格的得分情况，最后输出。得分规则：
arr[i][j]位置的得分等于第i行和第j列所有数的和。
算法思路
题目描述很简单，现在我们来看如何去解决这道问题；
首先暴力解法，当我们求某一个位置的得分时，去遍历它这一行和这一列所有的数，然后求和。（这里肯定会超时）
暴力解法不行，那我们来想一想有没有什么可以优化的：
我们在求
(i,j)位置时，要用到第i行所有数的和；在求(i,j-1)位置时，也要用到第i行所有数的和；那我们是不是可以预先将每一行/每一列所有数的和求出来，这样我们在求某一个位置的得分时就不用去遍历了。
**OK啊，这里我们的思路就出来了：**就是先将每一行/每一列所有数的和求出来，然后求
(i,j)位置的和直接用第i行的和加上第j列的和，再减去i,j位置的数就可以了。（这里第i行会计算一遍(i,j)位置，第j列也会计算(i,j)位置，所有要减去一个(i,j)位置的值）。
代码实现
#include<iostream>
using namespace std;
const int N = 1e6+10;
int n,m;
long long row[N];
long long col[N];
int main()
{
scanf("%ld %ld",&n,&m);
long long arr[n][m];
for(int i = 0;i < n;i++)
{
for(int j = 0;j < m;j++)
{
scanf("%ld",&arr[i][j]);
row[i]+=arr[i][j];
col[j]+=arr[i][j];
}
}
//记录完成以后输出
for(int i = 0;i<n;i++)
{
for(int j = 0;j<m;j++)
{
printf("%ld ",row[i]+col[j] - arr[i][j]);
}
printf("\n");
}
return 0;
}
三、比那名居的桃子
题目解析
题目描述：小红想要吃桃子，吃完桃子以后每天可以获得
ai的快乐值，获得bi个羞耻值，桃子效果可以持续k天。现在我们要求，小红在哪一天吃桃子可以获得尽可能多的快乐值；（如果快乐值相等，就让羞耻值尽可能小）。
算法思路
对于这道题，我们可以使用暴力解法，遍历数组，遍历到i位置时，求一下从i位置开始k天的快乐值和羞耻值。
对于暴力解法，我们就要进行优化：
滑动窗口：
我们在求从
i位置开始和从i+1位置开始时，这两个区间的差别就是i位置和i+k位置；所以我们在处理求
i+1位置开始时，只需要让i位置开始求出的值减去i位置，加上i+k位置即可。这里我们需要记录区间内快乐值的和
hSum，也要记录区间内羞耻值的和sSum；还要记录一下当前快乐值的最大值hMax和当前羞耻值的最小值sMin。
- 入窗口： 让
hSum加上right位置的快乐值，sSum加上right位置的羞耻值。- 判断： 当区间的长度大于
k时，进行出窗口操作（进行一次即可，这里我们要维持区间长度为k）- 出窗口： 让
hSum减去left位置的快乐值，sSum减去left位置的羞耻值；left++即可。- 更新结果：，当区间长度等于
k时，进行更新结果操作，这里我们更新不止是hSum > hMax时进行更新，当hSum == hMax && sSum < sMin时，我们也要更新结果。
当然对于这道题，我们还可以使用前缀和来解决：
通过暴力解法和优化的滑动窗口，我们可能发现，我们需要从i位置开始，k个数据的和；
那我们能不能先求出来这个和呢？
我们对于
h和s数组，分别创建一个对应的hSum和sSum数组，这两个数组中存放的就是每一个位置之前所有数的和。
hSum[i]：i位置之前h中所有数的和；
sSum[i]：i位置之前s中所有数的和；这里我们在遍历
i位置时，我们可以直接拿到从i位置开始k个数据的和numh（numh = hSum[i+k-1] - hSum[i-1]）和nums（nums = sSum[i+k-1] - sSum[i-1]）。这样我们遍历是时候，取到
numh和nums然后判断更新结果就好了。
这需要注意，我们在遍历i位置时，需要用到i-1位置和i+k-1位置，所以我们从1开始遍历，直到n-k（[1 , n-k+1])
这样对于大于n-k+1小于等于n的位置的数据，从这些位置开始，后面是没有k个数据的。
代码实现
滑动窗口：
#include<iostream>
using namespace std;
const int N = 1e5+10;
long long n,k;
long long h[N+1],s[N+1];
long long hSum[N+1],sSum[N+1];
int main()
{
//滑动窗口
cin>>n>>k;
for(int i = 1;i<=n;i++)
cin>>h[i];
for(int i = 1;i<=n;i++)
cin>>s[i];
int left = 1, right = 1;
long long hSum = 0,sSum = 0, hMax = 0, sMin = 0;
int ret = 0;
while(right<=n)
{
hSum+=h[right];
sSum+=s[right];
while(right - left + 1 > k)
{
hSum-=h[left];
sSum-=s[left];
left++;
}
if(right - left + 1 == k)
{
//更新结果
if((hSum > hMax)||(hSum == hMax && sSum < sMin))
{
ret = left;
hMax = hSum;
sMin = sSum;
}
}
right++;
}
cout<<ret<<endl;
return 0;
}
前缀和：
#include<iostream>
using namespace std;
const int N = 1e5+10;
long long n,k;
long long h[N+1],s[N+1];
long long hSum[N+1],sSum[N+1];
int main()
{
//前缀和
cin>>n>>k;
for(int i =1;i<=n;i++)
{
cin>>h[i];
hSum[i] = hSum[i-1]+h[i];
}
for(int i=1;i<=n;i++)
{
cin>>s[i];
sSum[i] = sSum[i-1]+s[i];
}
int ret = 0;
long long hMax = 0, sMin = 0;
for(int i = 1;i<=n-k+1;i++)
{
long long numh = hSum[i+k-1] - hSum[i-1];
long long nums = sSum[i+k-1] - sSum[i-1];
if((numh > hMax)||(numh == hMax && nums < sMin))
{
ret = i;
hMax = numh;
sMin = nums;
}
}
cout<<ret<<endl;
return 0;
}
到这里本篇文章就结束了，继续加油
我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws