【C++】 —— 笔试刷题day_17
一、小乐乐改数字
题目解析
这道题，它们给定一个数，我们要对它进行修改；如果某一位是奇数，就把它变成1,；如果是偶数，就把它变成0；
让我们输出最后得到的数。
算法思路
这道题，总体来说是非常简单的啦，解法呢，就是模拟整个过程。
当然呢这里模拟，也不是去一次去这个数的某一位去操作，那太麻烦了。
我们可以直接按照字符串进行输出，然后遍历字符串，判断这一个数是奇数还是偶数，然后进行操作。
这里我们通过查看ASSIC码可以发现，字符0到9数字0到9它的奇偶性是一样的，所以我们进行判断时就不用去-'0'了
最后呢我们需要取出前缀0，这里可以使用stoi函数，也可以自己实现去除前缀0。
代码实现
#include<iostream>#include<string>usingnamespace std; string str;intmain(){ 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;return0;}二、十字爆破
题目解析
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>usingnamespace std;constint N =1e6+10;int n,m;longlong row[N];longlong col[N];intmain(){scanf("%ld %ld",&n,&m);longlong 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");}return0;}三、比那名居的桃子
题目解析
题目描述：小红想要吃桃子，吃完桃子以后每天可以获得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>usingnamespace std;constint N =1e5+10;longlong n,k;longlong h[N+1],s[N+1];longlong hSum[N+1],sSum[N+1];intmain(){//滑动窗口 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;longlong 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;return0;}前缀和：
#include<iostream>usingnamespace std;constint N =1e5+10;longlong n,k;longlong h[N+1],s[N+1];longlong hSum[N+1],sSum[N+1];intmain(){//前缀和 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;longlong hMax =0, sMin =0;for(int i =1;i<=n-k+1;i++){longlong numh = hSum[i+k-1]- hSum[i-1];longlong nums = sSum[i+k-1]- sSum[i-1];if((numh > hMax)||(numh == hMax && nums < sMin)){ ret = i; hMax = numh; sMin = nums;}} cout<<ret<<endl;return0;}到这里本篇文章就结束了，继续加油
我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws
