LeetCode415. 字符串相加(字符串)

https://leetcode-cn.com/problems/add-strings/submissions/

给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和。

注意:
num1 和num2 的长度都小于 5100.
num1 和num2 都只包含数字 0-9.
num1 和num2 都不包含任何前导零。
你不能使用任何內建 BigInteger 库, 也不能直接将输入的字符串转换为整数形式。

思路:两个字符串先处理等长的部分,在处理不等长的部分,注意进位。先把字符串逆置,从低位相加,得出结果后再逆置,即为和

void inverse(char *src, int len){
    int i = 0;
    while(i  len / 2){
        char tmp = src[i];
        src[i] = src[len - i - 1];
        src[len - i - 1] = tmp;
        i++;
    }
}

void do_proc(char *ret, char *num1, int len1, int len2, int carry){
     int len = len1 - len2;
     int j = 0;
     for(; j  len; j++){
         int num = (*num1 - '0') + carry;
         if(num  9){
              carry = 1;
              num = num % 10;
          }else{
              carry = 0;
          }
          ret[len2 + j] = num + '0';
          num1++;
      }
      if(0 == carry){
          ret[len2 + j] = '\0';
      }else{
          ret[len2 + j] = carry + '0';
          ret[len2 + j + 1] = '\0';
      }
      inverse(ret, strlen(ret));
}

char* addStrings(char* num1, char* num2) {
    int len1 = strlen(num1);
    int len2 = strlen(num2);
    int len = 0;
    len  = len1  len2 ? len1 : len2;
    char *ret = (char *)malloc((len1 + len2 - len + 2)*sizeof(char));
    
    // 逆置字符串
    inverse(num1, len1);
    inverse(num2, len2);
    int carry = 0;
    int i = 0; 
    for(i = 0; i  len; i++){ // 处理公共部分
        int num = (*num1 - '0') + (*num2 - '0') + carry;
        if(num  9){
            carry = 1;
            num = num % 10;
        }else{
            carry = 0;
        }
        ret[i] = num + '0';
        num1++;
        num2++;
    }
    
    if(len1 == len2){  //字符串长度相等
        if(0 == carry){
            ret[i] = '\0';
        }else{
            ret[i] = carry + '0';
            ret[++i] = '\0';
        }
        inverse(ret, strlen(ret));
        return ret;
    }else{             // 字符串长度不相等
        if(len1  len2){
            do_proc(ret, num1, len1, len2, carry);
        }else{
            do_proc(ret, num2, len2, len1, carry);
        }
    }
    return ret;
}
最新回复(0)
/jishu7ujs2_2FeELVlNeW0GKH1tUNvxsJQ3Dkf6P16QvKSWPk0_3D4858774
8 简首页