拼多多笔试最后一题什么鬼啊，例子没看懂啊

最小编辑距离问题，用动态规划来做，很经典的题目。

动态规划

leetcode72吧！

''' 可惜了，最后两题sql不会写。。。 提供下第二题的一种方法： ''' cnt = [int(i) for i in input().split()] ret = [] for i in range(10): #将备选数字从小到大排好 if cnt[i]: ret.extend([i] * cnt[i]) a, b = int(input()), int(input()) if a > b: #保证a的位数比b小 a, b = b, a left, right = 0, 0 #最终两个数字 while a: # 对left,right逐步填入各位的数字 tmp = ret.pop(0) if (left*10+tmp) <= (right*10+tmp): #判断当前数字填入哪一边 left = left*10+tmp a -= 1 else: right = right*10+tmp b -= 1 while b: # 若right还未填满，将剩下数字按需填入 right = right*10+ret.pop(0) b -= 1 print(left * right)

两道sql题才做得我怀疑人生

很简单 dp求最长公共子串 然后用最长的长度减这个长度就行了

删除r，删e，把h替换成r

我觉得是这个用例错了 我ac的代码里 这个用例结果跟测试的不一样 很坑

class Solution { public:     int minDistance(string word1, string word2) {         vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1));         auto len1=word1.size(),len2=word2.size();         for(int i=1;i<=len1;++i) dp[i][0]=i;         for(int i=1;i<=len2;++i) dp[0][i]=i;                  for(int i=1;i<=len1;i++)         {             for(int k=1;k<=len2;k++)             {                 dp[i][k]=min_3(dp[i-1][k]+1,dp[i][k-1]+1,dp[i-1][k-1]+(word1[i-1]==word2[k-1]?0:1));             }         }         return dp[len1][len2];     }          int min_3(int x,int y,int z)     {         return min(min(x,y),z);     } }; 跑去leetcode上把这题刷出来了，dp[i][k]表示word1的前i个变成word2的前k个，最少需要多少步。则dp[i][k]=min( dp[i-1][k]+1,   dp[i][k-1] +1 ,   dp[i-1][k-1]+ (word1[i-1]==word[k-1]?0:1)  ); 即，由word1的前i-1个和word2的前k个的结果+1（把最后多的这个删掉） 、 word1的前i个和word2的前j-1个的结果+1（添加多出来的这一个） 、 word1的前i-1个和word2的前j-1个的结果加1或者0（看最后添加的这两个是否相等）。这三种结果中选最小的就行了。

编辑距离

动态规划 import java.util.Scanner; public class Main{     public static void main(String[] args) {         Scanner in = new Scanner(System.in);         String t = in.nextLine();         String p = in.nextLine();         System.out.println(string_compare(t, p));     }     static int string_compare(String s, String t) {         int i, j;         char s_i, t_j;         int[][] m = new int[s.length() + 1][t.length() + 1];         for (i = 0; i <= s.length(); i++) {             m[i][0] = i;         }         for (j = 0; j <= t.length(); j++) {             m[0][j] = j;         }         for (i = 1; i <= s.length(); i++) {             for (j = 1; j <= t.length(); j++) {                 m[i][j] = Math.min(m[i - 1][j] + 1, m[i][j - 1] + 1);//m[i - 1][j] + 1, m[i][j - 1] + 1表示s或t有个插入                 m[i][j] = Math.min(m[i][j], m[i - 1][j - 1] + (s.charAt(i - 1) == t.charAt(j - 1) ? 0: 1));//m[i - 1][j - 1]+1表示替换             }         }         return m[s.length()][t.length()];     } }

NLP经典问题，最小编辑距离。用于判断字符串相似性的经典算法。

leetcode原题吧

最后一题是经典的动态规划题，会做的话还是挺简单的，我反而第二题只过了30%。。

第一题怎么做，，贪心吗？

第三题怎么做啊，用例过了但是AC0

大佬们前面三道都AC了吗？第三道我心态崩了。。。不知道要不要按照它那个输入用例把{}和，也输进去。。。

第三题 咋做的? java表示处理输入都好难啊