题目描述

给定两个多项式的系数，第i项表示指数为n-i的系数。输出两个多项式的求和结果。

输入描述

第一行表示一个多项式的系数，第二行表示另一行多项式的系数，第三行表示多项式运算符

运算符只包含+、-、*。数组长度小于等于128，数组范围为 $[-512, 512]$

输出描述

输出运算后的系数数组，需要去除前缀零。

样例

输入

[1 2 3 4 5 6]
[-4 -5 -6]
+

输出

[1 2 3 0 0 0]

说明

多项式系数数组 $[1$ $2$ $3$ $4$ $5$ $6]$

表示多项式 $A(x)=x^5+2x^4+3x^3+4x^2+5x+6$

多项式系数数组 $[-4$ $-5$ $-6]$

表示多项式 $B(X)=-4x^2-5x-6$

$A(x)+B(X)=x^5 +2x^4 + 3x^3$ ，对应的多项式系数数组为 $[1$ $2$ $3$ $0$ $0$ $0]$

前置知识

不熟悉大数加法/乘法的同学可以先学习一下这两道Leetcode的题目

大数加法：2. 两数相加 - 力扣（LeetCode）

大数乘法：43. 字符串相乘 - 力扣（LeetCode）

题解思路

给定两个多项式的系数数组，要求对这两个多项式进行加法、减法或乘法操作。多项式的计算可以通过以下步骤实现：

输入和反转数组：
- 多项式是按降幂顺序给出的，例如 [1, 2, 3] 表示 $x^2 + 2x + 3$ 。
- 为了方便运算，先将数组反转，使其按升幂顺序排列。这样，指数为 i 的项对应数组中的第 i 个元素。
运算符选择：
- 若操作符为 +，则对两个系数数组逐位相加。
- 若操作符为 -，则逐位相减。
- 若操作符为 *，则需要逐项相乘，模拟多项式乘法。
去除前导零：
- 运算结束后，可能会产生高次项的系数为零的情况。
- 将多项式结果的前导零去除（除非最终结果是 0，避免无效的高次项）。

代码复杂度分析

时间复杂度：
- 加法和减法：逐位相加或相减，时间复杂度为 $O(n)$ 。
- 乘法：双重循环模拟多项式乘法，时间复杂度为 $O(n^2)$ 。
空间复杂度：
- 需要额外的数组存储运算结果，因此空间复杂度为 $O(n^2)$ 。

时间复杂度

乘法是 $O(n^2)$ ，加法/减法是 $O(n)$

代码

C++

#include <bits/stdc++.h>
using namespace std;

// 加法运算
vector<int> add(vector<int>& a, vector<int>& b) {
    int n = max(a.size(), b.size());
    vector<int> res(n, 0);
    // 将两个数组逐位相加
    for (int i = 0; i < n; i++) {
        if (i < a.size()) res[i] += a[i];
        if (i < b.size()) res[i] += b[i];
    }
    reverse(res.begin(), res.end());
    // 去除前导零
    while (res.size() > 1 && res[0] == 0) {
        res.erase(res.begin());
    }
    return res;
}

// 减法运算
vector<int> subtract(vector<int>& a, vector<int>& b) {
    int n = max(a.size(), b.size());
    vector<int> res(n, 0);
    // 将两个数组逐位相减
    for (int i = 0; i < n; i++) {
        if (i < a.size()) res[i] += a[i];
        if (i < b.size()) res[i] -= b[i];
    }
    reverse(res.begin(), res.end());
    // 去除前导零
    while (res.size() > 1 && res[0] == 0) {
        res.erase(res.begin());
    }
    return res;
}

// 乘法运算
vector<int> multiply(vector<int>& a, vector<int>& b) {
    int n = a.size() + b.size() - 1;
    vector<int> res(n, 0);
    // 双重循环模拟多项式乘法
    for (int i = 0; i < a.size(); i++) {
        for (int j = 0; j < b.size(); j++) {
            res[i + j] += a[i] * b[j];
        }
    }
    reverse(res.begin(), res.end());
    // 去除前导零
    while (res.size() > 1 && res[0] == 0) {
        res.erase(res.begin());
    }
    return res;
}

int main() {
    string s;
    getline(cin, s);
    stringstream ss(s.substr(1, s.length() - 2));
    vector<int> a;
    int x;
    while (ss >> x) a.push_back(x);
    reverse(a.begin(), a.end());

    getline(cin, s);
    ss.clear();
    ss.str(s.substr(1, s.length() - 2));
    vector<int> b;
    while (ss >> x) b.push_back(x);
    reverse(b.begin(), b.end());

    char op;
    cin >> op;

    vector<int> res;
    if (op == '+') res = add(a, b);
    else if (op == '-') res = subtract(a, b);
    else if (op == '*') res = multiply(a, b);

    // 输出结果并格式化为多项式的数组表示
    cout << "[";
    for (int i = 0; i < res.size(); i++) {
        if (i != 0) cout << " ";
        cout << res[i];
    }
    cout << "]" << endl;

    return 0;
}

python代码

def readIn ():
        x = list(map(int , input()[1:-1].split(' ')))
        y = list(map(int , input()[1:-1].split(' ')))
        return x , y
def solve(x):
        return x[::-1]
def mul (a , b , n , m):
        ans = [0] * (n + m - 1)
        for i in range(n):
                for j in range(m):
                        ans[i + j] += a[i] * b[j]
        return ans
        
a , b = readIn()
n = len(a)
m = len(b)
a = solve(a)
b = solve(b)
c = input()
ans = []
if c == '-':
        for i in range(max(n , m)):
                s = 0
                if i < n:
                        s += a[i]
                if i < m:
                        s -= b[i]
                ans.append(s)
                
if c == '*':
        ans = mul(a , b , n , m)
                        
if c == '+':
        for i in range(max(n , m)):
                s = 0
                if i < n:
                        s += a[i]
                if i < m:
                        s += b[i]
                ans.append(s)

def get(x):
        while len(x) > 1 and x[-1] == 0:
                x.pop()
        return x
        
ans = solve(get(ans))

output = "[" + " ".join(map(str , ans)) + "]"

print (output)

Java代码

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] a = parseInput(in.nextLine());
        int[] b = parseInput(in.nextLine());
        char op = in.nextLine().charAt(0);

        int[] result;
        if (op == '+') {
            result = add(a, b);
        } else if (op == '-') {
            result = subtract(a, b);
        } else {
            result = multiply(a, b);
        }

        System.out.print("[");
        boolean first = true;
        for (int num : result) {
            if (!first) System.out.print(" ");
            System.out.print(num);
            first = false;
        }
        System.out.println("]");
    }

    // 解析输入的数组字符串
    private static int[] parseInput(String s) {
        s = s.replace("[", "").replace("]", "");
        String[] tokens = s.split("\\s+");
        int[] arr = new int[tokens.length];
        for (int i = 0; i < tokens.length; i++) {
            arr[i] = Integer.parseInt(tokens[i]);
        }
        return reverse(arr);
    }

    // 反转数组
    private static int[] reverse(int[] arr) {
        for (int i = 0; i < arr.length / 2; i++) {
            int temp = arr[i];
            arr[i] = arr[arr.length - i - 1];
            arr[arr.length - i - 1] = temp;
        }
        return arr;
    }

    // 加法
    private static int[] add(int[] a, int[] b) {
        int maxLen = Math.max(a.length, b.length);
        int[] result = new int[maxLen];
        for (int i = 0; i < maxLen; i++) {
            result[i] = (i < a.length ? a[i] : 0) + (i < b.length ? b[i] : 0);
        }
        return reverse(trimLeadingZeros(result));
    }

    // 减法
    private static int[] subtract(int[] a, int[] b) {
        int maxLen = Math.max(a.length, b.length);
        int[] result = new int[maxLen];
        for (int i = 0; i < maxLen; i++) {
            result[i] = (i < a.length ? a[i] : 0) - (i < b.length ? b[i] : 0);
        }
        return reverse(trimLeadingZeros(result));
    }

    // 乘法
    private static int[] multiply(int[] a, int[] b) {
        int[] result = new int[a.length + b.length - 1];
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < b.length; j++) {
                result[i + j] += a[i] * b[j];
            }
        }
        return reverse(trimLeadingZeros(result));
    }

    // 去除前导零
    private static int[] trimLeadingZeros(int[] arr) {
        int nonZeroIndex = 0;
        while (nonZeroIndex < arr.length - 1 && arr[nonZeroIndex] == 0) {
            nonZeroIndex++;
        }
        return Arrays.copyOfRange(arr, nonZeroIndex, arr.length);
    }
}

#P1539. 2023.09.27-秋招-第二题-计算式

2023.09.27-秋招-第二题-计算式