[关闭]
@laofang 2016-06-19T02:17:18.000000Z 字数 10585 阅读 1085

多项式加法

java

Description
给定两个多项式P(x)与Q(x)，通过链表实现它们的加法。
Input
有若干组，每组有2个多项式。每组输入时先输入第1个多项式，再输入第2个多项式。每组用若干对整数表示，依序每两个相邻的整数表示多项式的一项，分别是它的系数和幂。当输入的幂为负数时，表示一个多项式的结束。一个多项式中各项的次序是随机的。
Output
对每组中两个多项式，先输出“Case #:”,其中“#”是测试数据序号。接着在下面三行上分别输出这两多项式，以及这两多项式的和。要求按降幂排列输出多项式的各项，每一项用(a,n)对的形式，其中a是系数，n是幂。相邻两对之间无空格。系数为零的项不输出。对零多项式，只输出0。
Sample Input
-1 2 3 -1 1 2 2 -1
-2 2 4 4 3 -1 2 2 6 1 5 -1
Sample Output
Case 1:
(-1,2)
(1,2)
0
Case 2:
(4,4)(-2,2)
(2,2)(6,1)
(4,4)(6,1)

图镇

此处输入图片的描述

一路艰辛一路坑(第一份代码是通过的, 其他都是不通过的):

感觉题目也没什么好讲的. 显然是一道水题. 虽然说用的是链表, 但是好久没有用过这个东西了, 自己首先想到的还是一个键值对数组或者集合之类的玩意.
假设系数用key来存, 指数用value
一开始想到的是map,但是因为题目要用key做运算, 用value做排序,之前没有接触过map,直接跳过. 现在回过头想, 似乎用map也可以,而且如果用key保存指数会不会更简单.
最后选择了用一个list<key,value>来维护, 于是就有了第一份错误代码, 也正式开始入坑.
可能是好久没有写这种东西了, 自己首先想到的直接就是<Key , Value>泛型

哈哈哈好像我用到了C#的名词, 哈哈哈不管了继续说

  1. 用javafx.util.Pair做键值对, 一路写下来很顺畅. 开心一提交, 判题系统不支持这个包.
  2. 问了得知单个键值对可以用Entry存储, 但是这是个接口, 于是第二个版本出来了, 自己实现了这个接口, 修改几下代码, 一测试, 通过. 信心满满一提交, arrayList.sort(c)直接运行错误, 不知道是哪里的问题.
  3. 自己猜测是不是泛型不好用? 于是直接把泛型去掉, 装两个int属性的 类. 代码轻轻一改, 提交. 还是有问题.
  4. 那既然这样, 就是内置srot方法有问题咯, 很显然这个时候已经深深陷入这个问题出不来了, 那你sort有问题我就给你写一个sort咯, 好第四个错误代码版本出来. 重写compare, 自己构造一个sort, 提交, 报一个新错误我的分割方法里有空串, 转成int异常
    看起来sort这一关过去了但是
    hhh心好累
    然后偷偷看了组长的c++代码,模仿了一下:每次读一行之后, 以这个行作为输入源, 每次读入一个int, 显然这个思路用java比c++好实现, 好吧那就nextInt()咯
    这个代码一题叫, 诶Wrong Answer
    噢我的天, WA了, 那个高兴....
    第一个wa:
  1. =================/input.out
  2. Right:
  3. (6,3)(1,2)
  5. -----------------
  6. Your:
  7.  (6,3) (1,2) 
  9. =================

哦原来是多输出一个空格, 然后看看代码, 诶我最后输出额米有多余空格啊, 往前翻啊翻,
哦, 输出原多项式的时候多输了一个, 好吧, 去掉, 提交
第二个wa

  1. =================/input.out
  2. Right:
  3. 3,4)(6,3)(1,2)
  5. -----------------
  6. Your:
  7. 0,6)(3,4)(6,3)(1,2)
  9. =================

这...什么可能!!! 我明明判断0就不输出啊
啊啊啊仔细看看代码
哦
又是输出原多项式的时候忘记了
神经病啊
你多项式写个有意思!!!
还让我给你判断
完了我直接给你打印出来你还不肯

好吧神经病鬼神经病, 代码还是要交的
加个if
提交
ac

哦

通过的代码, 虽然难看的自己都不好意思, 但是终究还是要贴上来的. 毕竟
许久没有对自己智商绝望到绝望的地步了

  1. package com.company;
  4. import java.util.*;
  5. class element{
  6.     int key;
  7.     int value;
  8.     public element(int k, int v){
  9.         this.key = k;
  10.         this.value = v;
  11.     }
  12.     public int getKey() {
  13.         return this.key;
  14.     }
  16.     public int getValue() {
  17.         return this.value;
  18.     }
  19.     public int setValue(int value) {
  20.         this.value = value;
  21.         return value;
  22.     }
  23. }
  25. public class Main {
  26.     static Comparator<element> c = new Comparator<element>() {
  27.         @Override
  28.         public int compare(element o1, element o2) {
  29.             return o2.getValue()-o1.getValue();
  30.         }
  31.     };
  32.     public static void mysort(LinkedList<element> a, Comparator c){
  33.         int N = a.size();
  34.         for (int i=1; i<N; i++)
  35.             for(int j=i;j>0 && less(c,a.get(j),a.get(j-1)); j--)
  36.                 exch(a,j,j-1);
  37.     }
  38.     private  static  boolean less(Comparator c, element v, element w){
  39.         return c.compare(v,w) < 0;
  40.     }
  41.     private  static void exch(LinkedList a, int i, int j){
  42.         Object t = a.get(i);
  43.         a.set(i,a.get(j));
  44.         a.set(j,t);
  45.     }
  46.     public static void main(String[] args) {
  47.         Scanner scanner = new Scanner(System.in);
  49.         LinkedList<element> la = new LinkedList<>();
  50.         LinkedList<element> lb = new LinkedList<>();
  51.         int Index = 1;
  52.         while (scanner.hasNext()){
  53.             String line = scanner.nextLine();
  54.             Scanner stringin = new Scanner(line);
  55.             System.out.println("Case "+(Index++)+":");
  56.             while (stringin.hasNext()){
  57.                 int d = stringin.nextInt();
  58.                 int m = stringin.nextInt();
  59.                 if (m>=0){
  60.                     la.add(new element(d,m));
  61.                     continue;
  62.                 }
  63.                 mysort(la,c);
  64.                 for (element anArrayList : la) {
  65.                     if(anArrayList.getKey() != 0)
  66.                         System.out.print("(" + anArrayList.getKey() + "," + anArrayList.getValue() + ")");
  67.                 }
  68.                 System.out.println();
  69.                 lb.addAll(la);
  70.                 la.clear();
  71.             }
  72.             mysort(lb,c);
  73.             int i=1;
  74.             boolean isZero = true;
  75.             while(i<lb.size()){
  76.                 if(Objects.equals(lb.get(i - 1).getValue(), lb.get(i).getValue())){
  77.                     int sum = lb.get(i-1).getKey()+lb.get(i).getKey();
  78.                     lb.set(i-1,new element(sum,lb.get(i-1).getValue()));
  79.                     lb.remove(i);
  80.                 }
  81.                 else{
  82.                     i++;
  83.                 }
  84.             }
  86.             for(i=0;i<lb.size();i++){
  88.                 if(lb.get(i).getKey() != 0){
  89.                     isZero = false;
  90.                     System.out.print("("+lb.get(i).getKey()+","+lb.get(i).getValue()+")");
  91.                 }
  92.             }
  94.             if (isZero)
  95.                 System.out.println("0");
  96.             else
  97.                 System.out.println();
  98.             la.clear();
  99.             lb.clear();
  100.         }
  101.     }
  102. }

这是我实现的一个版本, 但是判题系统不给用javafx.util.Pair

  1. package com.company;
  5. import java.math.BigDecimal;
  6. import java.math.BigInteger;
  7. import javafx.util.Pair;
  8. import java.util.*;
  9. public class Main {
  10.     static Comparator<Pair<Integer,Integer>> c = new Comparator<Pair<Integer, Integer>>() {
  11.         @Override
  12.         public int compare(Pair<Integer, Integer> o1, Pair<Integer, Integer> o2) {
  13.             return o2.getValue()-o1.getValue();
  14.         }
  15.     };
  16.     public static void main(String[] args) {
  17.         Scanner scanner = new Scanner(System.in);
  19.         ArrayList<Pair<Integer,Integer>> arrayList = new ArrayList<>();
  20.         ArrayList<Pair<Integer,Integer>> arrayListSum = new ArrayList<>();
  21.         int Index = 1;
  22.         while (scanner.hasNext()){
  24.             String [] first = scanner.nextLine().split(" ");
  25.             System.out.println("Case "+(Index++)+":");
  26.            for(int x = 0; x<first.length;x+=2){
  27.                 int d = Integer.parseInt(first[x]);
  28.                 int m = Integer.parseInt(first[x+1]);
  29.                 if (m>=0){
  30.                     arrayList.add(new Pair<>(d,m));
  31.                     continue;
  32.                 }
  33.                arrayList.sort(c);
  34.                for (Pair<Integer, Integer> anArrayList : arrayList) {
  35.                    System.out.print("(" + anArrayList.getKey() + "," + anArrayList.getValue() + ") ");
  36.                }
  37.                System.out.println();
  38.                arrayListSum.addAll(arrayList);
  39.                arrayList.clear();
  40.             }
  41.             arrayList.clear();
  42.             arrayList.addAll(arrayListSum);
  43.             arrayList.sort(c);
  45.             int i=1;
  46.             boolean isZero = true;
  47.             while(i<arrayList.size()){
  48.                 if(Objects.equals(arrayList.get(i-1).getValue(), arrayList.get(i).getValue())){
  49.                     int sum = arrayList.get(i-1).getKey()+arrayList.get(i).getKey();
  50.                     arrayList.set(i-1,new Pair<>(sum,arrayList.get(i-1).getValue()));
  51.                     arrayList.remove(i);
  52.                 }
  53.                 else{
  54.                     i++;
  55.                 }
  56.             }
  57.             for(i=0;i<arrayList.size();i++){
  58.                 if(arrayList.get(i).getKey() != 0){
  59.                     isZero = false;
  60.                     System.out.print("("+arrayList.get(i).getKey()+","+arrayList.get(i).getValue()+")");
  61.                 }
  62.             }
  63.             if (isZero==true)
  64.                 System.out.println("0");
  65.             else
  66.                 System.out.println();
  67.         }
  68.     }
  69. }

第二次写成这个鬼样子, 我觉得已经超出了题目的意思了.
虽然还是没有过////
说什么 arrayList.sort(c) 有问题.... 本地可以跑.....

  1. package com.company;
  4. import java.util.*;
  5. import  java.util.Map.Entry;
  6. import java.util.ArrayList;
  7. class myEntry<K,V> implements Entry<K,V>{
  8.     K key;
  9.     V value;
  10.     public myEntry(K k, V v){
  11.         this.key = k;
  12.         this.value = v;
  13.     }
  14.     @Override
  15.     public K getKey() {
  16.         return this.key;
  17.     }
  19.     @Override
  20.     public V getValue() {
  21.         return this.value;
  22.     }
  24.     @Override
  25.     public V setValue(V value) {
  26.         this.value = value;
  27.         return value;
  28.     }
  29. }
  31. public class Main {
  32.     static Comparator<myEntry<Integer,Integer>> c = (o1, o2) -> o2.getValue()-o1.getValue();
  33.     public static void main(String[] args) {
  34.         Scanner scanner = new Scanner(System.in);
  36.         ArrayList<myEntry<Integer,Integer>> arrayList = new ArrayList<>();
  37.         ArrayList<myEntry<Integer,Integer>> arrayListSum = new ArrayList<>();
  38.         int Index = 1;
  39.         while (scanner.hasNext()){
  41.             String [] first = scanner.nextLine().split("[\\p{Blank}]");
  42.             System.out.println("Case "+(Index++)+":");
  43.            for(int x = 0; x<first.length;x+=2){
  44.                 int d = Integer.parseInt(first[x]);
  45.                 int m = Integer.parseInt(first[x+1]);
  46.                 if (m>=0){
  47.                     arrayList.add(new myEntry<>(d,m));
  48.                     continue;
  49.                 }
  50.                arrayList.sort(c);
  51.                for (myEntry<Integer, Integer> anArrayList : arrayList) {
  52.                    System.out.print("(" + anArrayList.getKey() + "," + anArrayList.getValue() + ") ");
  53.                }
  54.                System.out.println();
  55.                arrayListSum.addAll(arrayList);
  56.                arrayList.clear();
  57.             }
  59.             arrayList.clear();
  60.             arrayList.addAll(arrayListSum);
  61.             arrayList.sort(c);
  63.             int i=1;
  64.             boolean isZero = true;
  65.             while(i<arrayList.size()){
  66.                 if(Objects.equals(arrayList.get(i - 1).getValue(), arrayList.get(i).getValue())){
  67.                     int sum = arrayList.get(i-1).getKey()+arrayList.get(i).getKey();
  68.                     arrayList.set(i-1,new myEntry<>(sum,arrayList.get(i-1).getValue()));
  69.                     arrayList.remove(i);
  70.                 }
  71.                 else{
  72.                     i++;
  73.                 }
  74.             }
  75.             for(i=0;i<arrayList.size();i++){
  76.                 if(arrayList.get(i).getKey() != 0){
  77.                     isZero = false;
  78.                     System.out.print("("+arrayList.get(i).getKey()+","+arrayList.get(i).getValue()+")");
  79.                 }
  80.             }
  81.             if (isZero)
  82.                 System.out.println("0");
  83.             else
  84.                 System.out.println();
  85.         }
  86.     }
  87. }

换汤不换药再来一波

  1. package com.company;
  4. import java.util.*;
  5. class element{
  6.     int key;
  7.     int value;
  8.     public element(int k, int v){
  9.         this.key = k;
  10.         this.value = v;
  11.     }
  12.     public int getKey() {
  13.         return this.key;
  14.     }
  16.     public int getValue() {
  17.         return this.value;
  18.     }
  19.     public int setValue(int value) {
  20.         this.value = value;
  21.         return value;
  22.     }
  23. }
  25. public class Main {
  26.     static Comparator<element> c = new Comparator<element>() {
  27.         @Override
  28.         public int compare(element o1, element o2) {
  29.             return o2.getValue()-o1.getValue();
  30.         }
  31.     };
  32.     public static void main(String[] args) {
  33.         Scanner scanner = new Scanner(System.in);
  35.         List<element> la = new LinkedList<>();
  36.         List<element> lb = new LinkedList<>();
  37.         int Index = 1;
  38.         while (scanner.hasNext()){
  40.             String [] first = scanner.nextLine().split("[\\p{Blank}]");
  41.             System.out.println("Case "+(Index++)+":");
  42.             for(int x = 0; x<first.length;x+=2){
  43.                 int d = Integer.parseInt(first[x]);
  44.                 int m = Integer.parseInt(first[x+1]);
  45.                 if (m>=0){
  46.                     la.add(new element(d,m));
  47.                     continue;
  48.                 }
  49.                 la.sort(c);
  50.                 for (element anArrayList : la) {
  51.                     System.out.print("(" + anArrayList.getKey() + "," + anArrayList.getValue() + ") ");
  52.                 }
  53.                 System.out.println();
  54.                 lb.addAll(la);
  55.                 la.clear();
  56.             }
  57.             lb.sort(c);
  58.             int i=1;
  59.             boolean isZero = true;
  60.             while(i<lb.size()){
  61.                 if(Objects.equals(lb.get(i - 1).getValue(), lb.get(i).getValue())){
  62.                     int sum = lb.get(i-1).getKey()+lb.get(i).getKey();
  63.                     lb.set(i-1,new element(sum,lb.get(i-1).getValue()));
  64.                     lb.remove(i);
  65.                 }
  66.                 else{
  67.                     i++;
  68.                 }
  69.             }
  70.             for(i=0;i<lb.size();i++){
  71.                 if(lb.get(i).getKey() != 0){
  72.                     isZero = false;
  73.                     System.out.print("("+lb.get(i).getKey()+","+lb.get(i).getValue()+")");
  74.                 }
  75.             }
  76.             if (isZero)
  77.                 System.out.println("0");
  78.             else
  79.                 System.out.println();
  80.         }
  81.     }
  82. }

手动重写sort方法
顺便贴一下错误信息:

  1. Main.java:47: error: cannot find symbol
  2.                 la.sort(c);
  3.                   ^
  4.   symbol:   method sort(Comparator<element>)
  5.   location: variable la of type List<element>
  6. Main.java:55: error: cannot find symbol
  7.             lb.sort(c);
  8.               ^
  9.   symbol:   method sort(Comparator<element>)
  10.   location: variable lb of type List<element>
  11. 2 errors

编译通过的代码, 运行错误

  1. Exception in thread "main" java.lang.NumberFormatException: For input string: ""
  2.     at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65)
  3.     at java.lang.Integer.parseInt(Integer.java:504)
  4.     at java.lang.Integer.parseInt(Integer.java:527)
  5.     at Main.main(Main.java:55)
  1. package com.company;
  4. import java.util.*;
  5. class element{
  6.     int key;
  7.     int value;
  8.     public element(int k, int v){
  9.         this.key = k;
  10.         this.value = v;
  11.     }
  12.     public int getKey() {
  13.         return this.key;
  14.     }
  16.     public int getValue() {
  17.         return this.value;
  18.     }
  19.     public int setValue(int value) {
  20.         this.value = value;
  21.         return value;
  22.     }
  23. }
  25. public class Main {
  26.     static Comparator<element> c = new Comparator<element>() {
  27.         @Override
  28.         public int compare(element o1, element o2) {
  29.             return o2.getValue()-o1.getValue();
  30.         }
  31.     };
  32.     public static void mysort(LinkedList<element> a, Comparator c){
  33.         int N = a.size();
  34.         for (int i=1; i<N; i++)
  35.             for(int j=i;j>0 && less(c,a.get(j),a.get(j-1)); j--)
  36.                 exch(a,j,j-1);
  37.     }
  38.     private  static  boolean less(Comparator c, element v, element w){
  39.         return c.compare(v,w) < 0;
  40.     }
  41.     private  static void exch(LinkedList a, int i, int j){
  42.         Object t = a.get(i);a.set(i,a.get(j));a.set(j,t);
  43.     }
  44.     public static void main(String[] args) {
  45.         Scanner scanner = new Scanner(System.in);
  47.         LinkedList<element> la = new LinkedList<>();
  48.         LinkedList<element> lb = new LinkedList<>();
  49.         int Index = 1;
  50.         while (scanner.hasNext()){
  52.             String [] first = scanner.nextLine().trim().split("[\\p{Blank}]");
  53.             System.out.println("Case "+(Index++)+":");
  54.             for(int x = 0; x<first.length-1;x+=2){
  55.                 int d = Integer.parseInt(first[x]);
  56.                 int m = Integer.parseInt(first[x+1]);
  57.                 if (m>=0){
  58.                     la.add(new element(d,m));
  59.                     continue;
  60.                 }
  61.                 mysort(la,c);
  62.                 for (element anArrayList : la) {
  63.                     System.out.print("(" + anArrayList.getKey() + "," + anArrayList.getValue() + ") ");
  64.                 }
  65.                 System.out.println();
  66.                 lb.addAll(la);
  67.                 la.clear();
  68.             }
  69.             mysort(lb,c);
  70.             int i=1;
  71.             boolean isZero = true;
  72.             while(i<lb.size()){
  73.                 if(Objects.equals(lb.get(i - 1).getValue(), lb.get(i).getValue())){
  74.                     int sum = lb.get(i-1).getKey()+lb.get(i).getKey();
  75.                     lb.set(i-1,new element(sum,lb.get(i-1).getValue()));
  76.                     lb.remove(i);
  77.                 }
  78.                 else{
  79.                     i++;
  80.                 }
  81.             }
  82.             for(i=0;i<lb.size();i++){
  83.                 if(lb.get(i).getKey() != 0){
  84.                     isZero = false;
  85.                     System.out.print("("+lb.get(i).getKey()+","+lb.get(i).getValue()+")");
  86.                 }
  87.             }
  88.             if (isZero)
  89.                 System.out.println("0");
  90.             else
  91.                 System.out.println();
  92.             la.clear();
  93.             lb.clear();
  94.         }
  95.     }
  96. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注