阅读程序2

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int f(string x,string y){
	int m=x.size();
	int n=y.size();
	vector<vector<int>>v(m+1,vector<int>(n+1,0));
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			if(x[i-1]==y[j-1]){
				v[i][j]=v[i-1][j-1]+1;
			}else{
				v[i][j]=max(v[i-1][j],v[i][j-1]);
			}
		}
	}
	return v[m][n];
}
bool g(string x,string y){
	if(x.size() != y.size()){
		return false;
	}
	return f(x+x,y)==y.size();
}
int main(){
	string x,y;
	cin>>x>>y;
	cout<<g(x,y)<<endl;
	return 0;
}

这段代码的f函数是用dp求字符串x和y中的最长公共子序列的长度，g函数则是找x + x这个字符串中是否包含了字符串y，是则返回1，不是则返回0

完善程序1

#include <iostream>
#include <vector>
using namespace std;
int find_missing(vector<int>& nums) {
	int left = 0, right = nums.size() - 1;
	while (left < right){
		int mid = left + (right - left) / 2;
		if (nums[mid] == mid + nums[0]) {
			left = mid + 1;
		} else {
			right = mid;
		}
	}
	return left + nums[0];
}
int main() {
	int n;
	cin >> n;
	vector<int> nums(n);
	for (int i = 0; i < n; i++) cin >> nums[i];
	int missing_number = find_missing(nums);
	if (missing_number == nums[n - 1]) {
		cout << "Sequence is consecutive" << endl;
	}else{
		cout << "Missing number is " << missing_number << endl;
	}
	return 0;
}

原有长度为n + 1的等差升序数列，数列输入到程序的数组时移除了一个元素，导致不连续，求少了哪个数。代码是利用二分查找缺失的数字，再输出

完善程序2

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int min(int x, int y, int z) {
   return min(min(x, y), z);
}
int edit_dist_dp(string str1, string str2) {
   int m = str1.length();
   int n = str2.length();
   vector<vector<int>> dp(m + 1, vector<int>(n + 1));
   for (int i = 0; i <= m; i++) {
   	for (int j = 0; j <= n; j++) {
   		if (i == 0)
   			dp[i][j] = j;
   		else if (j == 0)
   			dp[i][j] = i;
   		else if (str1[i - 1] == str2[j - 1])
   			dp[i][j] = dp[i - 1][j - 1];
   		else
   			dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]);
   	}
   }
   return dp[m][n];
}
int main() {
   string str1, str2;
   cin >> str1 >> str2;
   cout << "Mininum number of operation:" << edit_dist_dp(str1, str2) << endl;
   return 0;
}

给定两个字符串，每次操作可以选择删除，插入，替换一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。这题是一个dp问题，dp[i][j]代表把字符串1的前i个字符 转为字符串2的前j个字符需要的最少操作次数。 这个dp问题分为两种情况： 1.str1[i - 1] == str2[j - 1]，当前的字符相等，那么这两个字符不需要操作也是相等的，所以dp[i][j] = dp[i - 1][j - 1] 2.str1[i - 1] != str2[j - 1]，当前字符不相等，所以要进行操作，可以选择增加，删除，修改，三种操作，那么最少操作次数自然是从三种操作中选择次数最小的来操作。所以dp[i][j] = min(dp[i - 1][j - 1],dp[i - 1][j], dp[i][j - 1]) + 1