一、 大数乘法

解法一：普通竖式法

题解思路： 模拟拆分乘法竖式，遍历t,每次相乘之和末位补n-1-i个零之后，与之前的值相加

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param s string字符串 第一个整数
     * @param t string字符串 第二个整数
     * @return string字符串
     */
    string add_string(string &s1,string &s2){
        if(s1=="0") return s2;
        int len1 = s1.length()-1,len2 = s2.length()-1;
        int jinwei = 0;  // 有没有进位
        string ans;
        while(len1>=0 || len2>=0 || jinwei>0)
        {
            int val1 = len1 >= 0 ? s1.at(len1) - '0' : 0;  // 提取s1各个位的值，将其转为int
            int val2 = len2 >= 0 ? s2.at(len2) - '0' : 0;  //提取s2各个位的值，将其转为int
            int res = val1 + val2 +jinwei;                 
            jinwei = res / 10;
            ans += to_string(res % 10);   // ans 加上相加之后的个位
            len1 --;
            len2 --;
        }
        reverse(ans.begin(),  ans.end()); // 同样，ans保存的是相加之后的逆序，所以需要翻转
        return ans;
    }
    string solve(string s, string t) {
        // write code here
        if(s == "0" || t == "0") return "0"; //判断是否是乘0
        int m = s.size();  //s的长度
        int n = t.size();  // t的长度
        string ans = "0"; //存储最后的答案
        for(int i = n-1;i>=0; i--)
        {
            string cur; // 存储本次乘法所产生的中间值
            int jinwei = 0; // 保存进位的值
            for(int j = n-1;j>i;j--) // 补n-1-i个0
                cur.push_back('0');
            int val = t.at(i) - '0';  //当前要乘以s的值，转为int型
            for(int j = m-1;j>=0;j--)  //循环取数相乘
            {
                int x = s.at(j) - '0';
                int pro = x * val + jinwei; // 相乘加上之前的进位
                jinwei = pro/10;            //需要向下一轮进位的数
                cur += to_string(pro % 10); // 加入当前乘完之后的个位上的值
            }
            if(jinwei) cur += to_string(jinwei);  //如果所有位乘完，进位值不为0,再将进位值加到末尾
            reverse(cur.begin(), cur.end()); //cur保存的是乘完之后值的逆序，需要翻转
            ans = add_string(ans, cur); // 加上中间值
          }
        return ans;
     }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

时间复杂度：O(MN+N^2): M为s的长度，N为t的长度，中间存储字符串最长为(M+N),需要乘以N次，所以字符串相加次数也为N。所以时间复杂度为O((M+N)N)
空间复杂度：O(M+N):需要一个存储中间值的字符串，该字符串最长为(M+N);

解法二::多项式乘法

题解思路： 将每个数转换为多项式表示，这样就利用多项式乘法对其求积。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param s string字符串 第一个整数
     * @param t string字符串 第二个整数
     * @return string字符串
     */
    string solve(string s, string t) {
        if(s == "0" || t == "0") return "0"; // 乘以0直接返回字符串“0”
        int m = s.length(), n = t.length();
        vector<int> ans = vector<int>(m+n);  //用于保存相应幂次的权值
        for(int i = 0;i<m;i++)
        {
            int x = s[i]-'0';
            for(int j = 0;j<n;j++)
            {
                int y = t[j] - '0';
                ans[m+n-2-i-j] += x*y;   // 将权重加到相应幂次位上
            }
        }
        // 从低位向高位进位
        for(int i = 0;i<=m+n-2;i++)
        {
            ans[i+1] += ans[i] /10; // 向高位进位
            ans[i]  = ans[i] %10;
        }
        //最后是否有进位到最高位
        int index = (ans[m+n-1] == 0 ? m+n-2 : m+n-1);

        //从最高位组成字符串
        string res;
        while(index>=0){
            int tmp = ans[index--];
            res += to_string(tmp);
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

时间复杂度：O(MN);多项式每一项都要与另一个数的多项式每一项相乘，如上图所示
空间复杂度：O(M+N);最差两个多项式的x次方都不相同，需要M+N的空间存储对应次方的系数

二、编辑距离(二)

解法:

我们可以对任意一个单词进行三种操作：
在单词 A 中插入一个字符；
在单词 A 中插入一个字符；
修改单词 A 的一个字符。
我们说word1和word2的编辑距离为X，意味着word1经过X步，变成了word2，咋变的你不用管，反正知道就需要X步，并且这是个最少的步数。
有word1和word2，我们定义dp[i][j]的含义为：word1的前i个字符和word2的前j个字符的编辑距离。意思就是word1的前i个字符，变成word2的前j个字符，最少需要这么多步。
当我们获得 D[i][j-1]，D[i-1][j] 和 D[i-1][j-1] 的值之后就可以计算出 D[i][j]。

D[i][j-1] 为 A 的前 i 个字符和 B 的前 j - 1 个字符编辑距离的子问题。即对于 B 的第 j 个字符，我们在 A 的末尾添加了一个相同的字符，那么 D[i][j] 最小可以为 D[i][j-1] + ic；
D[i-1][j] 为 A 的前 i - 1 个字符和 B 的前 j 个字符编辑距离的子问题。即对于 A 的第 i 个字符，我们在 B 的末尾添加了一个相同的字符，即删除A的末尾元素，那么 D[i][j] 最小可以为 D[i-1][j] + dc；
D[i-1][j-1] 为 A 前 i - 1 个字符和 B 的前 j - 1 个字符编辑距离的子问题。即对于 B 的第 j 个字符，我们修改 A 的第 i 个字符使它们相同，那么 D[i][j] 最小可以为 D[i-1][j-1] + rc。特别地，如果 A 的第 i 个字符和 B 的第 j 个字符原本就相同，那么我们实际上不需要进行修改操作。在这种情况下，D[i][j] 最小可以为 D[i-1][j-1]。

class Solution {
public:
 /**
  * min edit cost
  * @param str1 string字符串 the string
  * @param str2 string字符串 the string
  * @param ic int整型 insert cost
  * @param dc int整型 delete cost
  * @param rc int整型 replace cost
  * @return int整型
 参考链接：https://leetcode-cn.com/problems/edit-distance/solution/bian-ji-ju-chi-by-leetcode-solution/
 */
 int minEditCost(string str1, string str2, int ic, int dc, int rc) {
     int n=str1.size(),m=str2.size();
     //str1为空串
     if(n==0)return ic*m;
     if(m==0)return dc*n;
     vector<vector<int>>dp(n+1,vector<int>(m+1));//定义编辑代价矩阵
     //定义边界条件
     for(int i=0;i<n+1;i++){
         dp[i][0]=dc*i;
     }
     for(int j=0;j<m+1;j++){
         dp[0][j]=ic*j;
     }
     //计算剩余的编辑代价矩阵
     for(int i=1;i<n+1;i++){
         for(int j=1;j<m+1;j++){
             if(str1[i-1]==str2[j-1])
                 dp[i][j]=dp[i-1][j-1];
             else
                 dp[i][j]=min(dp[i-1][j]+dc,min(dp[i][j-1]+ic,dp[i-1][j-1]+rc));
         }
     }
     return dp[n][m];
 }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37