猫史档案馆

前面的题目在这里喵community/5喵717

 

第一大题

 

(寻找被移除的元素)

 

问题:原有长度为 n+1公差为1等升数列，将数列输到程序的数组时移除了一个元素，导致长度为 n 的开序数组可能不再连续，除非被移除的是第一个或最后之个元素。需要在数组不连续时，找出被移除的元素。试补全程序。

#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+ ①) {
               ②;
           }else{
             ③
           }
      }
     return ④;
}
 
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 == ⑤) {
        cout << "Sequence is consecutive" << endl;
    }else{
           cout << "Missing number is " << ,missing numbeer << endl;
    }
    return 0;
}

这就是我说的那道超级坑的二分。

 

我们先来看一下主函数，很好理解。先输入，然后调用missing_number找缺失值，如果缺失值是⑤，就说明序列本身有序（即缺失的为第一个/最后一个元素），否则输出Missing number is

 

重点就在于这个missing_number函数，学过二分的人应该都会。

 

第一空：

这空就是一个判定，如果当前mid位置之前没有缺少元素，更改 l 边界值，否则更改r

怎么判断呢？相信大家都知道。如果没缺元素，说明数组是一组连续的自然数，那么只要开头数字+个数就行了。也就是nums[0]+mid，选B

 

第二空：

如果没缺，那我们就要更改左边边界值。考虑AD选项。如果当前位置前面不缺，那缺的值要么是开头要么是往后的数字。

那这项就可以直接扔掉了。所以left=mid+1

选A

 

第三空：

根据二分国际惯例，right=mid。为什么不选mid-1，因为可能nums[mid-1]和nums[mid]中间就缺了一个数字。

如果将right设为mid-1，很可能就找不到这个数字了

选C

 

第四空：

这空大家画几个例子分析一下就行了，left表达的是缺失的后一个值

那假设数组连续，则nums[left]应为nums[0]+left

选A

 

第五空：

很重要！

很多人选的B，请大家测一下123457这种情况B会干什么

剩下的选项只有D合理了

测了数据也说明dau是对的。

 

第二大题

 

(编辑距离）

 

给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace），一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。

#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]=(1);
            else if(j==0)
                dp[i][j]=(2);
            else if((3))
                dp[i][j]=(4);
            else
                dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],(5)); 
        }
    }
    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我第一步先列表。

不过在列表之前，我们得先确定第一空和第二空填啥

 

第一空：

现在我们知道dp[n][m]表示str1的前n项和str2的前m项的最小编辑次数。

那么i=0或j=0时，也就是至少有一个空串时，那肯定得把所有东西删掉。

选A，删除的长度由j决定（你i都是0了）

 

 

第二空：

选B，和上同理

 

好了，明确了第一空、第二空，我们就开始列表

先画出这样一个表

呃 那个圆圈中间一个斜杠的你可以理解为空集，但我更愿意理解成德语字母ö的音标（喜欢这么写）

好我们继续往下走，用脑子想一想就知道下面两个判断肯定一个是判断两个字母相同的的，一个是判断两个不同的。

第三空就出来了，根据下面一个的转移方程（一看这么复杂肯定不是相同）

选A

 

第四空：那如果相同，这2个字符串如果扣掉这个相同的字符，那编辑次数肯定不变，也就直接继承i-1 j-1，选B

 

第五空：

当前字符串可有上，左，左上三个方向继承而来，这个很容易想到吧，那么就很清楚了，取三个的最小值，选C

 

整体不是很难