【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;
}

到这里本篇文章内容就结束了
感谢各位的支持