Невозможно правильно отформатировать вывод «Добавить два числа» в Ruby (односвязный список) - PullRequest
Новая
       52

Невозможно правильно отформатировать вывод «Добавить два числа» в Ruby (односвязный список)

0 голосов
/ 09 мая 2020

Попытка решить задачу leetcode "сложить два числа" в Ruby (https://leetcode.com/problems/add-two-numbers/). Я знаю, что вообще не решил проблему, просто пытаюсь сначала получить результат в правильном формате «ListNode». ListNode, который я пытаюсь добавить, продолжает писать поверх себя, потому что он находится в while l oop, но я работал над этим вечно и не могу понять, как получить результат так, как этого хочет leetcode.

Любая помощь приветствуется!

Вот мой код: 

# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0)
#         @val = val
#         @next = nil
#     end
# end

# @param {ListNode} l1
# @param {ListNode} l2
# @return {ListNode}

def add_two_numbers(l1, l2)
    current_output = head = ListNode.new()
    while l1.next != nil
        sum = l1.val + l2.val
        if current_output.next != nil
            current_output = current_output.next
        else
            current_output.next = ListNode.new(sum)
            current_output.next = current_output.next.next
        end

        l1.val = l1.next.val
        l1.next = l1.next.next
        l2.val = l2.next.val
        l2.next = l2.next.next
    end
    last_sum = l1.val + l2.val
    #current_output.next = ListNode.new(last_sum)
    return current_output 
end

Примечание: он требует, чтобы выводом был объект ListNode, поэтому я не могу создать свой собственный класс LinkedList

Ответы [ 2 ]

1 голос
/ 09 мая 2020

Classi c solution 

def add_two_numbers(l1, l2)
  head = ListNode.new
  carry = 0
  curr = head

  until l1.nil? && l2.nil? && carry.zero?
    v1 = l1&.val || 0
    v2 = l2&.val || 0
    carry, digit = (v1 + v2 + carry).divmod(10)
    curr.next = ListNode.new(digit)
    curr = curr.next
    l1 = l1&.next
    l2 = l2&.next
  end

  head.next
end

Обратите внимание, что l1 и l2 могут иметь разную длину, поэтому вы должны закончить l oop, когда оба узла станут nil.

Если вы не знаете синтаксис obj&.mthd, это называется «безопасная навигация», что означает, что если obj равно nil, немедленно вернуть nil без вызова mthd в теме. Если obj не nil, верните все, что возвращает obj.mthd.

Обман

Вы можете вычислить целое число, которое представляет каждый список, сложить их вместе, и построим список результатов на основе суммы. 

# Monkey-patch ListNode
# to make a list enumerable,
# so that we can call `reduce` on it.
ListNode.class_eval do
  include Enumerable

  def each(&block)
    return enum_for(:each) unless block
    block.(@val)
    @next.each(&block) if @next
  end
end

def add_two_numbers(l1, l2)
  n1 = l1.reduce(""){|s, n| "#{n}#{s}"}.to_i
  n2 = l2.reduce(""){|s, n| "#{n}#{s}"}.to_i

  head = ListNode.new
  (n1 + n2).digits.reduce(head) do |prev_node, digit|
    ListNode.new(digit).tap{|node| prev_node.next = node}
  end

  head.next
end
1 голос
/ 09 мая 2020

вот код, который суммирует два связанных списка, затем я разобью его, чтобы вы могли принять его часть и использовать их, однако он недостаточно хорошо протестирован, так как я только что написал его сейчас после взлома this сообщение в блоге и внесение в него небольших правок: 

class Node
  attr_accessor :value, :next

  def initialize(value, next_node)
      @value = value
      @next = next_node
  end
end


class LinkedList
  include Enumerable
  def initialize
    @head = nil
  end

  def add_to_list(value)
    return @head = Node.new(value, nil) unless @head
    current_node = @head
    while current_node.next != nil
      current_node = current_node.next
    end
    current_node.next = Node.new(value, nil)
  end

  def each
    current = @head
    while current
      yield current.value
      current = current.next
    end
  end

  def to_i
    self.reduce(""){ |s, l| "#{l}#{s}" }.to_i
  end
end


list1 = LinkedList.new
list2 = LinkedList.new
sum = LinkedList.new

list1.add_to_list(2)  # => #<Node:0x000055951cb54940 @value=2, @next=nil>
list1.add_to_list(4)  # => #<Node:0x000055951cb545f8 @value=4, @next=nil>
list1.add_to_list(3)  # => #<Node:0x000055951cb543a0 @value=3, @next=nil>

list2.add_to_list(5)  # => #<Node:0x000055951cb54170 @value=5, @next=nil>
list2.add_to_list(6)  # => #<Node:0x000055951cb7bf40 @value=6, @next=nil>
list2.add_to_list(4)  # => #<Node:0x000055951cb7bd10 @value=4, @next=nil>

result = list1.to_i + list2.to_i  # => 807
result.digits.each do |i|
  sum.add_to_list(i)
end
puts list1.to_i  # => nil
puts list2.to_i  # => nil
puts sum.to_i  # => nil

# >> 342
# >> 465
# >> 807

в приведенном выше коде следующее определение узла связанного списка: 

class Node
  attr_accessor :value, :next

  def initialize(value, next_node)
      @value = value
      @next = next_node
  end
end

узел имеет value и указатель на узел, который идет после него в связанном списке.

позволяет разбить связанный список, который в этом случае имеет только два метода: первый - add_to_list: 

  def add_to_list(value)
    return @head = Node.new(value, nil) unless @head
    current_node = @head
    while current_node.next != nil
      current_node = current_node.next
    end
    current_node.next = Node.new(value, nil)
  end

он принимает целое число в качестве значения, а затем создает для него узел в связанном списке.

второй метод - to_i, который преобразует связанный список backward в целое число. так что позже мы можем сделать list1.to_i + list2.to_i, который дает нам сумму двух списков: 

  def each
    current = @head
    while current
      yield current.value
      current = current.next
    end
  end

  def to_i
    self.reduce(""){ |s, l| "#{l}#{s}" }.to_i
  end

теперь давайте перейдем к коду, который выполняет фактические вычисления:

  • вот инициализация list1, list2, and the sum lists: 
list1 = LinkedList.new
list2 = LinkedList.new
sum = LinkedList.new

list1.add_to_list(2)  # => #<Node:0x000055951cb54940 @value=2, @next=nil>
list1.add_to_list(4)  # => #<Node:0x000055951cb545f8 @value=4, @next=nil>
list1.add_to_list(3)  # => #<Node:0x000055951cb543a0 @value=3, @next=nil>

list2.add_to_list(5)  # => #<Node:0x000055951cb54170 @value=5, @next=nil>
list2.add_to_list(6)  # => #<Node:0x000055951cb7bf40 @value=6, @next=nil>
list2.add_to_list(4)  # => #<Node:0x000055951cb7bd10 @value=4, @next=nil>
  • и здесь выполняется фактическая сумма обоих list1, and list2: 
result = list1.to_i + list2.to_i  # => 807
  • вот преобразование целочисленного значения result в связанный список: 
result.digits.each do |i|
  sum.add_to_list(i)
end
  • и вот содержимое list1, list2, and sum переменных, распечатанных: 
puts list1.to_i  # => nil
puts list2.to_i  # => nil
puts sum.to_i  # => nil

# >> 342
# >> 465
# >> 807

, поэтому в вашем методе add_two_numbers проблемы все, что вы хотите, - это преобразовать два связанных списка в целые числа надлежащим образом, затем сложить их сумму, а затем преобразовать полученное целое число в связанный список, который будет возвращен в качестве окончательного решения, и убедитесь, что вы выполнили достаточно тестовых примеров и протестировали угловые случаи .

...