leetcode43：字符串相乘（multiply-strings）

[carloscn]

问题描述

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:

输入: num1 = "2", num2 = "3" 输出: "6" 示例 2:

输入: num1 = "123", num2 = "456" 输出: "56088"   提示：

1 <= num1.length, num2.length <= 200 num1 和 num2 只能由数字组成。 num1 和 num2 都不包含任何前导零，除了数字0本身。

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/multiply-strings

[carloscn]

问题分析

把乘法分为两步，一步叫做single_multi和cross_add。

#define _P(_x) (int32_t)((_x) - '0')
#define _V(_x) (char)((_x) + '0')

static int32_t single_multi(char *a, char b, char *out)
{
    int32_t ret = 0;
    char *ret_str = NULL;
    size_t i = 0;
    size_t len = 0;
    int32_t p = 0;
    int32_t c = 0;

    UTILS_CHECK_PTR(a);
    UTILS_CHECK_PTR(out);
    UTILS_CHECK_LEN(len = strlen(a));

    ret_str = (char *)calloc(sizeof(char), len + 2);
    UTILS_CHECK_PTR(ret_str);

    for (i = 0; i < len; i ++) {
        c = _P(b) * _P(a[len - i - 1]) + c;
        p = c % 10;
        c = c / 10;
        ret_str[i] = _V(p);
    }
    if (c != 0) {
        ret_str[i++] = _V(c);
    }

    ret = utils_str_reverse(ret_str);
    UTILS_CHECK_RET(ret);

    strcpy(out, ret_str);

finish:
    UTILS_SAFE_FREE(ret_str);
    return ret;
}

static int32_t cross_add(char *a, char *b, size_t index, char *out)
{
    int32_t ret = 0;
    char *ret_str = NULL;
    int32_t i = 0, j = 1;
    size_t a_len = 0;
    size_t b_len = 0;
    size_t max_len = 0;
    int32_t p = 0;
    int32_t c = 0;
    int32_t c1 = 0, c2 = 0;

    UTILS_CHECK_PTR(a);
    UTILS_CHECK_PTR(b);
    UTILS_CHECK_PTR(out);
    UTILS_CHECK_LEN(a_len = strlen(a));
    UTILS_CHECK_LEN(b_len = strlen(b));

    max_len = (a_len > b_len) ? a_len : b_len;

    ret_str = (char *)calloc(sizeof(char), max_len + 3);
    UTILS_CHECK_PTR(ret_str);

    b[b_len] = '0';
    for (i = 0, j = 1 - index; i < max_len + 1; i ++, j ++) {
        c1 = (i > a_len - 1) ? 0 : _P(a[a_len - i - 1]);
        c2 = (j > b_len) ? 0 : _P(b[b_len - j]);
        c = c1 + c2 + c;
        p = c % 10;
        c = c / 10;
        ret_str[i] = _V(p);
    }

    while (-- i) {
        if (ret_str[i] == '0') {
            ret_str[i] = '\0';
        } else {
            break;
        }
    }

    ret = utils_str_reverse(ret_str);
    UTILS_CHECK_RET(ret);

    strcpy(out, ret_str);

finish:
    UTILS_SAFE_FREE(ret_str);
    return ret;
}

static int32_t multi_str(const char *a_str, const char *b_str, char *out)
{
    int32_t ret = 0;
    size_t a_len = 0, b_len = 0;
    size_t i = 0;
    char *cacu_buf = NULL;

    UTILS_CHECK_PTR(a_str);
    UTILS_CHECK_PTR(b_str);
    UTILS_CHECK_PTR(out);
    UTILS_CHECK_LEN(a_len = strlen(a_str));
    UTILS_CHECK_LEN(b_len = strlen(b_str));

    if (a_len < b_len) {
        ret = -1;
        goto finish;
    }

    if ((a_len == 1 && a_str[0] == '0') ||
        (b_len == 1 && b_str[0] == '0')) {
        out[0] = '0';
        out[1] = '\0';
    }

    cacu_buf = (char *)calloc(sizeof(char), a_len + 2);
    UTILS_CHECK_PTR(cacu_buf);

    ret = single_multi(a_str, b_str[b_len - 1], cacu_buf);
    UTILS_CHECK_RET(ret);

    for (i = 1; i < b_len; i ++) {
        ret = single_multi(a_str, b_str[b_len - i - 1], out);
        UTILS_CHECK_RET(ret);
        ret = cross_add(cacu_buf, out, i, out);
        strcpy(cacu_buf, out);
    }

finish:
    UTILS_SAFE_FREE(cacu_buf);
    return ret;
}

fn single_multi(in_str:&String, b:char) -> String
{
    let mut ret_str:String = String::new();
    let in_len:usize = (*in_str).len();
    let mut in_str_dup:String = String::from(in_str);
    let mut i:usize = 0;
    let mut b_int:i32 = ((b as u8) - ('0' as u8)) as i32;
    let mut p:i32 = 0;
    let mut c:i32 = 0;

    if 0 == in_len {
        return ret_str;
    }

    let in_str_int:Vec<i32> = in_str_dup.chars().
                                map(|x| x.to_digit(10).unwrap() as i32).collect();

    while i < in_len {
        c = b_int * in_str_int[in_len - i- 1] + c;
        p = c % 10;
        c = c / 10;
        ret_str.push(((p as u8) + ('0' as u8)) as char);
        i += 1;
    }

    if c != 0 {
        ret_str.push(((c as u8) + ('0' as u8)) as char);
    }

    utils::str::reverse(&mut ret_str);

    return ret_str;
}

fn cross_add(a_str:&String, b_str:&String, index:usize) -> String
{
    let mut ret_str:String = String::new();
    let mut a_str_dup:String = String::from(a_str);
    let mut b_str_dup:String = String::from(b_str);
    let a_len:usize = (*a_str).len();
    let b_len:usize = (*b_str).len();
    let mut c:i32 = 0;
    let mut p:i32 = 0;

    let mut i:usize = 0;

    if 0 == a_len || 0 == b_len {
        return ret_str;
    }

    while i < index {
        b_str_dup.push('0');
        i += 1;
    }

    let mut a_int:Vec<i32> = a_str_dup.chars().map(|x| x.to_digit(10).unwrap() as i32).collect();
    let mut b_int:Vec<i32> = b_str_dup.chars().map(|x| x.to_digit(10).unwrap() as i32).collect();

    i = 0;
    let mut j:usize = 0;
    let max_len:usize = utils::num::max(a_int.len(), b_int.len());
    while i < max_len {
        let mut c1 = if i >= a_int.len() { 0 } else { a_int[a_int.len() - i - 1]};
        let mut c2 = if i >= b_int.len() { 0 } else { b_int[b_int.len() - i - 1]};
        c = c1 + c2 + c;
        p = c % 10;
        c = c / 10;
        ret_str.push(((p as u8) + ('0' as u8)) as char);
        i += 1;
    }

    utils::str::reverse(&mut ret_str);

    return ret_str;
}

fn multi_str(a_str:&String, b_str:&String) -> String
{
    let mut ret_str:String = String::new();
    let mut a_str_dup:String = String::from(a_str);
    let mut b_str_dup:String = String::from(b_str);
    let a_len:usize = (*a_str).len();
    let b_len:usize = (*b_str).len();
    let mut i:usize = 1;

    if a_len < b_len {
        return ret_str;
    }

    let mut b:Vec<char> = b_str_dup.chars().map(|x| x as char).collect();
    let mut ret_1 = single_multi(&a_str_dup, b[b.len() - 1]);
    let mut ret_2:String = String::new();

    while i < b.len() {
        ret_2 = single_multi(&a_str_dup, b[b.len() - i - 1]);
        ret_1 = cross_add(&ret_1, &ret_2, i);
        i += 1;
    }

    ret_str = ret_1;
    return ret_str;
}

[carloscn]

code

https://github.com/carloscn/structstudy/blob/master/rust_programming/str/src/n46_multiply_strings_43.rs https://github.com/carloscn/structstudy/blob/master/c_programming/str/n46_multiply_strings_43.c