8.1 字符串中等 43 Multiply Strings 38 Count and Say

43 Multiply Strings【默写】

那个难点我就没想先解决，原本想法是先想其他思路，但也没想出。本来只想chat一下使用longlong数据类型直接stoi()得不得行，然后就看到了答案，直接一个默写的大动作。但这道题确实考察的是还原乘法，整体数字相乘这条路大概是行不通的，只能按照列竖式的乘法拆分思路（官方题解的法一我没看）

class Solution {
public:string multiply(string num1, string num2) {//逐位做乘法//难点：实现从后到前的存储--->位置i+j i+j+1使用数组int m = num1.size() , n = num2.size();vector<int> pos(m+n,0);for(int i = m-1 ; i >= 0 ; --i){for(int j = n-1 ; j >= 0 ;--j){int mul = (num1[i] - '0')*(num2[j] - '0');int p1 = i+j , p2 = i+j+1;//进位 当前位int sum = mul + pos[p2];pos[p2] = sum %10;pos[p1] += sum /10;}}string res = "";for(int n : pos){if(res.empty() && n == 0)continue;res += (n + '0');}return res.empty()?"0":res;}
};

38 Count and Say

难点在于读懂cAs(n)这个函数是在对cAs(n-1)做run length encoding，初始值是“1”：

class Solution {
public:string countAndSay(int n) {//公式题//个数+主体 -->个数个主体//递归 比较合适if(n == 1){return "1";}string last = countAndSay(n-1);string res = "";//个数 int count = 0;//数字for(int i = 0 ; i < last.size() ; i++){char ch = last[i];count++;if(i == last.size()-1 || last[i+1] != ch ){res += (count + '0');res += ch;count = 0;}}return res;}
};