解决该问题的基本思路为:
1. 首先获取两个输入字符串A和B的长度n和m,并初始化进位标志flag为0,以及36进制的基数standard为36,和结果字符串res为空字符串。
2. 将字符串A和B逆序处理,方便从低位开始相加。
3. 从低位开始逐位相加,同时考虑进位的情况。如果当前位小于字符串长度n或m,就将当前位的字符转换为对应的10进制数,然后加上进位flag。如果相加结果大于等于基数36,则需要进位,更新进位标志和当前位的值。
4. 将相加后的结果转换为36进制的字符,并添加到结果字符串res中。
5. 如果最高位相加后仍有进位,将进位加到结果字符串的末尾。
6. 最后将结果字符串res逆序输出,得到最终的相加结果。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param A string字符串
* @param B string字符串
* @return string字符串
*/
string thirtysixAdd(string A, string B) {
// write code here
int n = A.size();
int m = B.size();
int flag = 0;
int standard = 36;
string res = "";
reverse(A.begin(), A.end());
reverse(B.begin(), B.end());
for (int i = 0; i < max(n, m); i++) {
int cur = flag;
if (i < n) {
cur += A[i] >= '0' && A[i] <= '9' ? A[i] - '0' : A[i] - 'a' + 10;
}
if (i < m) {
cur += B[i] >= '0' && B[i] <= '9' ? B[i] - '0' : B[i] - 'a' + 10;
}
if (cur >= standard) {
flag = cur / standard;
cur = cur % standard;
} else {
flag = 0;
}
res += cur >= 10 ? cur - 10 + 'a' : cur + '0';
}
if (flag) res += flag + '0';
reverse(res.begin(), res.end());
return res;
}
};
static const auto io_sync_off = []() { //lambda函数
// turn off sync,关闭输入输出流的缓存
std::ios::sync_with_stdio(false);
// untie in/out streams,实现输入和输出流的解绑
std::cin.tie(nullptr);
return nullptr;
}
();
算法基本思想:
该算法实现了将两个36进制的字符串相加的功能。首先将两个字符串逆序处理,然后从低位开始逐位相加,并考虑进位的情况。最后将结果逆序输出即可得到相加后的36进制字符串。
时间复杂度:
O(max(n, m)),其中n和m分别为字符串A和B的长度,需要遍历两个字符串中较长的那个。
空间复杂度:
O(max(n, m)),需要存储结果字符串的空间,空间复杂度与输入字符串长度相关。

京公网安备 11010502036488号