【C++】 —— 笔试刷题day_22
一、添加字符
题目解析
这道题，给定两个字符串
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[j] != str2[i + j])tmp++;}ret = min(ret, tmp);}cout << ret << endl;return 0;
}
二、数组变换
题目解析
题目给定一个数组，现在呢，我们要将数组中的所有数相等；
我们可以进行的操作：将数组中的一个数改为这个数的两倍（说白了就是进行乘
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；否则就不是。
代码实现
#include <iostream>
using namespace std;
const int N = 51;
int n;
int arr[N];
int num = 0;
bool fun()
{//判断是否能转换for(int i = 0;i<n;i++){if(num % arr[i] != 0)return false;int b = num/arr[i];//判断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[i];num = max(num,arr[i]);}if(fun()) cout<<"YES"<<endl;else cout<<"NO"<<endl;return 0;
}
三、装箱问题
题目解析
这道题，给一个箱子的容量
v，和n个物品，和每一个物品的体积；现在我们要在这
n个物品中选择体积不超过v的物品，然后要求箱子的剩余空间最小。
算法思路
有系统学习过动态规划，或者了解过01背包问题，相比已经想到这道题思路了；
这道题就是01背包的一个应用。
题目要求我们箱子的剩余容量最小，我们反过来理解，就是我们在
n个物品中选择体积不超过v的物品，然后要选择物品的总体积最大。
那这道题就简单了。思路就是动态规划-01背包
状态表示：
dp[i][j]表示从n个物品中选择体积不超过j是物品，所选择物品总体积的最大值。状态转移方程：
- 对于
i位置的物品，我们可以选择它，也可以不选择它；- 如果选择
i位置的物品，dp[i][j] = dp[i-1][j-arr[i]] + arr[i]。（选择i物品，那就要从剩下的i-1位置中选择体积不超过j - arr[i]的物品；这里还要注意能不能选择i位置的问题）- 如果不选择
i位置的物品，dp[i][j] = dp[i-1][j]。（不选择i位置的物品，那就要从剩下的i-1位置中选择体积不超过j的物品）。这里如果
i位置物品的体积大于j，那一定是不能选择i位置的。
代码实现
#include <iostream>
using namespace std;
const int N = 35;
const int M = 2e4+10;
int arr[N];
int dp[N][M];
int n,v;
int main()
{cin>>v>>n;for(int i = 1;i<=n;i++){cin>>arr[i];}for(int i = 1;i<=n;i++){for(int j = 1;j<=v;j++){dp[i][j] = dp[i-1][j];if(j>=arr[i])dp[i][j] = max(dp[i][j], dp[i-1][j-arr[i]] + arr[i]);}}cout<<(v - dp[n][v])<<endl;return 0;
}
到这里本篇文章内容就结束了
感谢各位的支持