【C++】 —— 笔试刷题day_22
一、添加字符标题解析
https://i-blog.csdnimg.cn/direct/ee108c27a1164812be8d0399754b59dc.png#pic_center
这道题，给定两个字符串A和B，字符串A的长度要小于B的长度；
现在我们要对A字符串添加字符，使得A字符串长度等于B字符串的长度，而且要求对应位置的字母尽量相等，然后求出来不相等的字符最少有多少位。
算法思绪
对于这道题而言，我们可以在A字符串的开头和结尾位置添加字符（那我们添加的字符肯定是和B字符串对应位置的字符相等的），以是我们就只必要在B字符串中找到一段区间（这个区间的长度等于A的长度，然后让这个区间内的字符尽可能和A字符串对应字符相等）。
看到这里，可能会想到滑动窗口、双指针算法来找更加高效的方法；
但这道题，B字符串的长度小于等于50，A字符串的长度小于等于B的长度，我们利用暴力解法即可。
暴力解法：
遍历B字符串，找以每一个位置为开始，长度等于A的长度的子串，然后找到不相等的字符最少的，记录一下结果即可。
代码实现
这里注意：假设A字符串的长度为n，B字符串的长度为m。
遍历B字符串时，我们要找i位置后面的n个字符，以是我们遍历到m-n位置即可
#include <iostream>
using namespace std;
int main() {
string str1, str2;
cin >> str1 >> str2;
int n = str1.size();
int m = str2.size();
int ret = m;
for (int i = 0; i < m - n + 1; i++) {//从0位置遍历到m-n位置
int tmp = 0;//记录以i位置开始
for (int j = 0; j < n; j++) {
if (str1 != str2)
tmp++;
}
ret = min(ret, tmp);
}
cout << ret << endl;
return 0;
}
二、数组变换
标题解析
https://i-blog.csdnimg.cn/direct/0d255ecc533d491b804e8b2f009eed7f.png#pic_center
标题给定一个数组，现在呢，我们要将数组中的全部数相等；
我们可以进行的操纵：将数组中的一个数改为这个数的两倍（说白了就是进行乘2操纵）
这个操纵没有次数限定，可以利用也可以不利用，让我们判断给定的数组能否通过乘2操纵将全部数变成一样的。
算法思绪
这道题，首先的标题就是：我们如何去判断给定的数组是否能够将全部数变成一样的。
首先，肯定就是，暴力枚举，枚举出来以是的两个数的组合，然后依次判断这两个数能否通过操纵变成一样的数。
这道题数据个数是小于50的，暴力枚举也可能可以通过；
但是我们进行一下优化：
[*]我们知道进行乘2操纵时，这个数是一直在变大的，以是如果整个数组中的全部数是可以变成一样的，那是不是可以明白为我们可以将全部数通过乘2操纵，变成最大的那一个数。（如果无法变成最大的那一个数，那无论多少次操纵都是不能变成同一个数的）。
[*]那我们就可以记录一下整个数组中最大的数num，然后遍历数组，判断每一个数能否通过乘2操纵变成最大的数即可
那现在我们的标题就来到了如何去判断一个数，能否通过乘2操纵变成别的一个数。
我们仔细想一下，如果x可以通过乘2操纵变成y，那是不是说y是x的2^n倍？
我们乘2操纵2,4,8,16,32......，这些都是2^n，这里如果x等于y，那y就是x的1(2^0)。
那也就是y/x是一个2^n。
那我们的标题就变成了判断一个数的2^n
这里暴力就是通过/2操纵判断y/x每次/2的商是否是2的倍数。
这里先容两种判断一个数是否是2^n次方的 方法：
[*]x - (x & -x)：如果x - (x & -x) == 0，那x就是2^n；否则就不是。
[*]x & (x - 1)：如果x & (x - 1) == 0，那x就是2^n；否则就不是。
https://i-blog.csdnimg.cn/direct/39239b5d86b14333a1aca57be2be133a.png#pic_center
代码实现
#include <iostream>
using namespace std;
const int N = 51;
int n;
int arr;
int num = 0;
bool fun()
{
//判断是否能转换
for(int i = 0;i<n;i++)
{
if(num % arr != 0)
return false;
int b = num/arr;
//判断b是否是2的n次方
//if(b - (b&-b)!=0)return false;
if(b & (b-1) !=0) return false;
}
return true;
}
int main() {
cin>>n;
for(int i = 0;i<n;i++)
{
cin>>arr;
num = max(num,arr);
}
if(fun()) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}
三、装箱标题
标题解析
https://i-blog.csdnimg.cn/direct/4463872e07c54cc782b802ee9b1eded6.png#pic_center
这道题，给一个箱子的容量v，和n个物品，和每一个物品的体积；
现在我们要在这n个物品中选择体积不高出v的物品，然后要求箱子的剩余空间最小。
算法思绪
有体系学习过动态规划，大概了解过01背包标题，相比已经想到这道题思绪了；
这道题就是01背包的一个应用。
标题要求我们箱子的剩余容量最小，我们反过来明白，就是我们在n个物品中选择体积不高出v的物品，然后要选择物品的总体积最大。
那这道题就简单了。思绪就是动态规划-01背包
状态表示： dp表示从n个物品中选择体积不高出j是物品，所选择物品总体积的最大值。
状态转移方程：
[*]对于i位置的物品，我们可以选择它，也可以不选择它；
[*]如果选择i位置的物品，dp = dp] + arr。（选择i物品，那就要从剩下的i-1位置中选择体积不高出j - arr的物品；这里还要注意能不能选择i位置的标题）
[*]如果不选择i位置的物品，dp = dp。（不选择i位置的物品，那就要从剩下的i-1位置中选择体积不高出j的物品）。
这里如果i位置物品的体积大于j，那一定是不能选择i位置的。
https://i-blog.csdnimg.cn/direct/13ab00b92e744119af9264fb95fa58fb.png#pic_center
代码实现
#include <iostream>
using namespace std;
const int N = 35;
const int M = 2e4+10;
int arr;
int dp;
int n,v;
int main()
{
cin>>v>>n;
for(int i = 1;i<=n;i++)
{
cin>>arr;
}
for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=v;j++)
{
dp = dp;
if(j>=arr)
dp = max(dp, dp] + arr);
}
}
cout<<(v - dp)<<endl;
return 0;
}
到这里本篇文章内容就竣事了
感谢各位的支持
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]