1009. Product of Polynomials (25)
题目阐述
This time, you are supposed to find A*B where A and B are two polynomials.
Input Specification:
Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial: K N1 aN1 N2 aN2 … NK aNK, where K is the number of nonzero terms in the polynomial, Ni and aNi (i=1, 2, …, K) are the exponents and coefficients, respectively. It is given that 1 <= K <= 10, 0 <= NK < … < N2 < N1 <=1000.
Output Specification:
For each test case you should output the product of A and B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate up to 1 decimal place.
Sample Input
2 1 2.4 0 3.2
2 2 1.5 1 0.5
Sample Output
3 3 3.6 2 6.0 1 1.6
- 原题链接
题目分析
这道题和之前的多项式相加形式是一样的，只需要先用hashmap把多项式A的指数做key，系数作为value存起来，接下来对B中的每一项取出来分别和A式的每一项相乘，结果的放入一个新的hashmap中，如果同指数已经存在，则系数相加即可。总的时间复杂度是O(N*M)，需要注意的是输出结果里必须按照降幂的形式打印，附上代码如下；
package PAT;import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;public class Main {
public static void main(String[] args) {Scanner s = new Scanner(System.in);Map<Integer, Double> map = new HashMap<>();Map<Integer, Double> product = new HashMap<>();int n = s.nextInt();int[] arr = new int[n];for(int i=0; i<n; i++) {int u = s.nextInt();arr[i] = u;double v = s.nextDouble();map.put(u, v);}int m = s.nextInt();for(int i=0; i<m; i++) {int u = s.nextInt();double v = s.nextDouble();for(int j=0; j<n; j++) {int p = arr[j] + u;double q = map.get(arr[j]) * v;if(product.containsKey(p)) {double temp = product.get(p);temp += q;if(Math.abs(temp) < 0.00001) product.remove(p);else {temp = Math.round(temp * 10)/ 10.0;product.put(p, temp);}} elseproduct.put(p, Math.round(q * 10) / 10.0);}}List<Integer> list = new ArrayList<>();Set<Integer> set = product.keySet();for(int i : set)list.add(i);Collections.sort(list);Collections.reverse(list); System.out.print(product.size());for(int i : list)System.out.print(" " + i + " " + product.get(i));}}
思考
这里降幂输出时候，取出的keyset是一个集合，得先对所有key实现排序，然后逐个输出，这里其实可以用java8里的流来把代码写的简洁点，但是我刷题的PAT里的编译器是javac1.6，所以还是老老实实使用工具类把。