一、添加字符
題目解析
這道題，給定兩個字符串
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;
}
到這里本篇文章內容就結束了
感謝各位的支持
 | GmaGIS V0.0.1a3 更新日志)
