Java自定义Polynomial类如何正确判断两个多项式相等

当前代码存在4处核心逻辑错误，逐一修复后即可通过所有测试用例：

• Monomial双参数构造方法的次数校验逻辑失效：未对传入的degree参数做判断，反而读取了未赋值的this.degree，非法负次数无法被拦截
• findAnyDupesHelper方法逻辑错误：仅校验当前节点、未递归遍历后续节点，且重复判断的返回值逻辑反转
• findSameHelper方法遍历逻辑缺失：仅匹配链表首项，无法查找非首项位置的单项式
• findSame与相等判断逻辑不完整：未做双向包含校验，无法识别顺序不同但元素完全一致的链表，也无法校验链表长度一致性

修复后代码 #

Monomial 类 #

public class Monomial {

  int coef;
  int degree;

  public Monomial(int coef) throws IllegalArgumentException {
    super();
    this.degree = 1;
    this.coef = coef;
  }

  public Monomial(int degree, int coef) throws IllegalArgumentException {
    // 修复：校验传入的degree参数，而非未初始化的this.degree
    if (degree < 0) {
      throw new IllegalArgumentException("non positive degree");
    }
    this.coef = coef;
    this.degree = degree;
  }

  public int getDegree() {
    return this.degree;
  }

  public int getCoef() {
    return this.coef;
  }

  public boolean sameMonomial(Monomial that) {
    return this.coef == that.getCoef()
            && this.degree == that.getDegree();
  }
}

ILoMonomial 接口与实现类 #

public interface ILoMonomial {

  boolean findAnyDupes();
  boolean findAnyDupesHelper(int degree);

  boolean findSameHelper(Monomial that);

  boolean findSame(ILoMonomial that);

}

public class MtLoMonomial implements ILoMonomial {

  MtLoMonomial(){}

  @Override
  public boolean findAnyDupes() {
    // 空链表无重复项，合法
    return true;
  }

  @Override
  public boolean findAnyDupesHelper(int degree) {
    // 空链表不可能存在重复项，合法
    return true;
  }

  @Override
  public boolean findSameHelper(Monomial that) {
    // 空链表不存在任何目标单项式
    return false;
  }

  @Override
  public boolean findSame(ILoMonomial that) {
    // 空链表仅与另一个空链表相等
    return that instanceof MtLoMonomial;
  }

}

public class ConsLoMonomial implements ILoMonomial {

  Monomial first;
  ILoMonomial rest;


  ConsLoMonomial(Monomial first, ILoMonomial rest) {
    this.first = first;
    this.rest = rest;
  }

  @Override
  public boolean findAnyDupes() {
    // 先校验当前首项次数是否在后续重复，再递归校验后续部分
    return this.rest.findAnyDupesHelper(this.first.getDegree()) &&
            this.rest.findAnyDupes();
  }

  @Override
  public boolean findAnyDupesHelper(int degree) {
    // 修复：当前节点匹配到重复次数则返回不合法，否则递归遍历后续节点
    if (degree == this.first.degree) {
      return false;
    }
    return this.rest.findAnyDupesHelper(degree);
  }


  @Override
  public boolean findSameHelper(Monomial that) {
    // 修复：当前首项匹配则返回true，否则递归在后续节点查找
    if (that.sameMonomial(this.first)) {
      return true;
    }
    return this.rest.findSameHelper(that);
  }

  @Override
  public boolean findSame(ILoMonomial that) {
    // 当前首项在对方链表不存在则直接返回不相等，否则递归判断剩余部分
    if (!that.findSameHelper(this.first)) {
      return false;
    }
    return this.rest.findSame(that);
  }

}

Polynomial 类 #

public class Polynomial {
  ILoMonomial monomials;

  public Polynomial(ILoMonomial monomials) {
    // 构造时强制校验无重复次数项
    if (!monomials.findAnyDupes()) {
      throw new IllegalArgumentException("Duplicate monomial degree found");
    }
    this.monomials = monomials;
  }

  public boolean samePolynomial(Polynomial other) {
    // 无重复项的前提下，双向包含即可判定完全相等，与单项式顺序无关
    return this.monomials.findSame(other.monomials) && other.monomials.findSame(this.monomials);
  }
}

测试结果 #

修复后所有测试用例均可正常通过：

• 非首项单项式查找正常返回正确结果
• 顺序反转但项完全一致的多项式会被判定为相等
• 原有重复次数校验、单项式相等判断逻辑不受影响

内容的提问来源于stack exchange，提问作者Silas Spencer