时间戳

首页 > 解决方案 > 将表示为链表的数字相乘

java - 将表示为链表的数字相乘

问题描述

我一直在尝试解决这个问题一段时间，但到目前为止我的方法都没有奏效。

给你两个代表大数字的链接列表，其中列表的头部代表最低有效数字。返回一个新列表，该列表存储两个列表相乘的结果。

我尝试了一种算法，该算法适用于第一个列表是单个数字，但仅此而已。

  1. 初始化一个新列表。
  2. 初始化进位。
  3. 虽然节点 1 不为空：
  4. 虽然节点 2 不为空：
  5. 如果节点 3 的 next 不为 null，则将其值添加到进位；
  6. 将节点 3 的下一个设置为节点 1 * 节点 2 的值 + 进位。
  7. 将节点 2 设置为下一个，将节点 3 设置为下一个。
  8. 在第 4 节设置时结束
  9. 将节点 1 设置为节点 1 的下一个。
  10. 在第 3 节设置时结束。
  11. 返回列表设置在第 1 节。

这显然有问题。我还尝试为第一个循环的每次迭代设置一个“powCounter”，并将该值乘以 10 到 powCounter 的幂。但这也不起作用。

我真的很感激任何帮助！

标签： javaloopsrecursionlinked-listbiginteger

解决方案

像在纸上那样做。

大概，在让你写作之前multiply(a, b)，他们已经让你写作了add(a, b)，对吧？所以用那个。

您说您已经编写了与单个数字相乘的逻辑，所以我们调用它multiplySingle(a, digit)。

您还需要一个辅助方法，例如shiftLeft(a, n)，将n0 添加到数字的末尾，即添加到列表的开头。egshiftLeft([4,3,2,1], 2)应该返回[0,0,4,3,2,1]，意思1234 * 10² = 123400。

所以，在纸上你会123像456这样乘以：

123 * 456
    45600  =  1 * 456 * 100  =  shiftLeft(multiplySingle([6,5,4], 1), 2)
     9120  =  2 * 456 * 10   =  shiftLeft(multiplySingle([6,5,4], 2), 1)
     1368  =  3 * 456 * 1    =  shiftLeft(multiplySingle([6,5,4], 3), 0)
    =====
    56088  = 45600 + 9120 + 1368  =  add(add([0,0,6,5,4], [0,2,1,9]), [8,6,3,1])

祝你好运为此编写代码。

仅供参考：方法的想法shiftLeft()是基于内置BigInteger和BigDecimal类中的类似方法。

  • BigInteger shiftLeft(int n)

    返回BigInteger值为 的(this << n)。移位距离n可能是负数，在这种情况下，此方法执行右移。（计算floor(this * 2ⁿ)。）

  • BigDecimal movePointRight(int n)

    返回一个BigDecimal与此等效的 a，小数点n向右移动。如果n是非负数，则调用只是n从比例中减去。如果n为负，则调用等效于movePointLeft(-n)。此调用返回的BigDecimal具有 value(this × 10ⁿ)和 scale max(this.scale()-n, 0)。

推荐阅读