8.1 字符串中等 43 Multiply Strings 38 Count and Say
发布时间
阅读量：
阅读量
43 Multiply Strings【默写】
那个难点我没有打算一开始就去解决；我的想法是从其他思路入手；结果却一直都没有想到办法；最初只是试探性地考虑了一下是否可以直接使用$...$类型调用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;
}
};
AI写代码38 Count and Say
难点在于理解cAs(n)这个函数是如何基于前一结果cAs(n-1)进行run-length编码分析的，在初始状态下该函数的值为"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;
}
};
AI写代码全部评论 (0)
还没有任何评论哟~