【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位置即可

1. #include <iostream>
2. using namespace std;
4. int main() {
5.     string str1, str2;
6.     cin >> str1 >> str2;
7.     int n = str1.size();
8.     int m = str2.size();
9.     int ret = m;
10.     for (int i = 0; i < m - n + 1; i++) {//从0位置遍历到m-n位置
11.         int tmp = 0;//记录以i位置开始
12.         for (int j = 0; j < n; j++) {
13.             if (str1[j] != str2[i + j])
14.                 tmp++;
15.         }
16.         ret = min(ret, tmp);
17.     }
18.     cout << ret << endl;
19.     return 0;
20. }

复制代码

二、数组变换

标题解析

   标题给定一个数组，现在呢，我们要将数组中的全部数相等；
  我们可以进行的操纵：将数组中的一个数改为这个数的两倍（说白了就是进行乘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；否则就不是。
  

  

代码实现

1. #include <iostream>
2. using namespace std;
3. const int N = 51;
4. int n;
5. int arr[N];
6. int num = 0;
7. bool fun()
8. {
9.     //判断是否能转换
10.     for(int i = 0;i<n;i++)
11.     {
12.         if(num % arr[i] != 0)
13.             return false;
14.         int b = num/arr[i];
15.         //判断b是否是2的n次方
16.         //if(b - (b&-b)!=0)  return false;
17.         if(b & (b-1) !=0)   return false;
18.     }
19.     return true;
20. }
21. int main() {
22.     cin>>n;
23.     for(int i = 0;i<n;i++)
24.     {
25.         cin>>arr[i];
26.         num = max(num,arr[i]);
27.     }
28.     if(fun()) cout<<"YES"<<endl;
29.     else cout<<"NO"<<endl;
30.     return 0;
31. }

复制代码

三、装箱标题

标题解析

   这道题，给一个箱子的容量v，和n个物品，和每一个物品的体积；
  现在我们要在这n个物品中选择体积不高出v的物品，然后要求箱子的剩余空间最小。
  算法思绪

有体系学习过动态规划，大概了解过01背包标题，相比已经想到这道题思绪了；
这道题就是01背包的一个应用。
   标题要求我们箱子的剩余容量最小，我们反过来明白，就是我们在n个物品中选择体积不高出v的物品，然后要选择物品的总体积最大。
  那这道题就简单了。思绪就是动态规划-01背包
   状态表示： dp[j]表示从n个物品中选择体积不高出j是物品，所选择物品总体积的最大值。
  状态转移方程：
  

• 对于i位置的物品，我们可以选择它，也可以不选择它；
  
• 如果选择i位置的物品，dp[j] = dp[i-1][j-arr] + arr。（选择i物品，那就要从剩下的i-1位置中选择体积不高出j - arr的物品；这里还要注意能不能选择i位置的标题）
  
• 如果不选择i位置的物品，dp[j] = dp[i-1][j]。（不选择i位置的物品，那就要从剩下的i-1位置中选择体积不高出j的物品）。
  

  这里如果i位置物品的体积大于j，那一定是不能选择i位置的。
  

代码实现

1. #include <iostream>
2. using namespace std;
3. const int N = 35;
4. const int M = 2e4+10;
5. int arr[N];
6. int dp[N][M];
7. int n,v;
8. int main()
9. {
10.     cin>>v>>n;
11.     for(int i = 1;i<=n;i++)
12.     {
13.         cin>>arr[i];
14.     }
15.     for(int i = 1;i<=n;i++)
16.     {
17.         for(int j = 1;j<=v;j++)
18.         {
19.             dp[i][j] = dp[i-1][j];
20.             if(j>=arr[i])
21.                 dp[i][j] = max(dp[i][j], dp[i-1][j-arr[i]] + arr[i]);
22.         }
23.     }
24.     cout<<(v - dp[n][v])<<endl;
25.     return 0;
26. }

复制代码

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。