Leetcode题库第２题：两数相加用Julia怎么解？

NeutronT · 2020 年2 月 2 日 09:20

想通过做Leetcode题来熟悉Julia编程，结果到第2题就卡住了，来社区求教！

题目是：

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 → 4 → 3) + (5 → 6 → 4)
输出：7 → 0 → 8
原因：342 + 465 = 807

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

woclass · 2020 年2 月 2 日 13:24

可以学学 C 的风格，弄个 struct。

框架给你打好了。

发现之前的小问题：julia 默认 struct 不可变，可以用 == 比较。mutable struct 可变，需要自行实现 ==，不然默认都是 false。

目前版本用的是 mutable struct + 自定义的 ==。

fix：上一版 == 实现的有 bug，又加了几个测试
update: 加了点 addTwoNumbers 的测试。用的时候看情况把测试数量调小一点，不然一堆报错。

using Test
import Base: (+), (==)

abstract type ListNode end
mutable struct Node <: ListNode
    val::UInt8 #再小就要手动处理 bit 流
    next::ListNode
end

# List Node Null
struct Null <: ListNode end
# const null = LnNull()
null = Null()
==(::Null, ::Null) = true
==(::Null, ::Node) = false
==(::Node, ::Null) = false
# 可变数据结构不能使用 == 直接比较
function ==(ln1::Node, ln2::Node)
    ln1.val  != ln2.val  && return false
    ln1.next != ln2.next && return false
    true
end

function addTwoNumbers(ln1::ListNode, ln2::ListNode)
    # 在此作答
end
# 重载 +, 便于使用
# 可以直接写 `Node(0) + Node(1)`
# 而不是每次都要调用函数
+(ln1::ListNode, ln2::ListNode) = addTwoNumbers(ln1, ln2)

#= 辅助函数（答题非必须）
=#
"数字转数组"
function num2arr(n::Integer)
    ## 1- digits 法
    # digits 输出为倒序
    #   digits(123) == [3, 2, 1]
    n |> digits |> reverse

    ## 2-string 法
    # s = string(n)
    # a = []
    # for c in s
    #     push!(a, parse(UInt8, c))
    # end
    # a
end
function num2ln(n::Integer)
    arr = num2arr(n)
    ln = null
    for i in arr
        ln = Node(UInt8(i), ln)
    end
    ln
end
Node(n::Integer) = num2ln(n)
Node() = null

# 单元测试
@testset "Node" begin
    # not equal
    @test Node()  != Node(1)
    @test Node(1) != Node()
    @test Node(1) != Node(2)
    @test Node(2) != Node(1)
    @test Node(10) != Node(0)
    @test Node(123456) != Node(123455)
    @test BigInt(123456789) |> Node != null

    # null
    @test Node() == Null()
    @test Node() == null

    # Int64
    @test Node(0) == Node(0x00, Null())
    @test Node(1) == Node(0x01, Null())
    @test 1234 |> Node ==
        Node(0x04, Node(0x03, Node(0x02, Node(0x01, Null()))))

    # Unsigned
    @test 0xFF |> Node == 
        Node(0x05, Node(0x05, Node(0x02, Null())))
    @test 0xFFFF |> Node == 
        Node(0x05, Node(0x03, Node(0x05, Node(0x05, Node(0x06, Null())))))

    # BigInt
    @test BigInt(123456789) |> Node == 
        Node(0x09, Node(0x08, Node(0x07, Node(0x06, Node(0x05, Node(0x04, Node(0x03, Node(0x02, Node(0x01, Null())))))))))
end

@testset "addTwoNumbers" begin
    @test Node(0) + Node(0) == Node(0)
    @test Node(1) + Node(9) == Node(10)

    @test Node(10) + Node(0) == Node(10)
    @test Node(123) + Node(0) == Node(123)
    @test Node(511) + Node(513) == Node(1024)
    
    @test Node(9) + Node(9) == Node(2*9)

    i=2^4
    @test Node(i) + Node(i) == Node(2*i)

    for i=1:2^8+1
        @test Node(i) + Node(0) == Node(i)
        @test Node(0) + Node(i) == Node(i)
        @test Node(i) + Node(i) == Node(2*i)
        @test Node(i+1) + Node(i-1) == Node(2*i)
    end
end

woclass · 2020 年2 月 2 日 18:37

我写了一版，顺便找了点的对比的

递归还是快啊

using BenchmarkTools
import Base: (+), (==)

abstract type ListNode end
mutable struct Node <: ListNode
    val::UInt8 #再小就要手动处理 bit 流
    next::ListNode
end

# List Node Null
struct Null <: ListNode end
# const null = LnNull()
null = Null()
==(::Null, ::Null) = true
==(::Null, ::Node) = false
==(::Node, ::Null) = false
# 可变数据结构不能使用 == 直接比较
function ==(ln1::Node, ln2::Node)
    ln1.val  != ln2.val  && return false
    ln1.next != ln2.next && return false
    true
end

# 节点相加，带进位，忽略 next
function addVal(val1::UInt8, val2::UInt8, carry::UInt8)
    val_sum = val1 + val2 + carry
    new_val = val_sum % 10 # 只保留 1 位数
    carry   = val_sum ÷ 10  # 是否有进位

    new_val, carry
end
addNodesVal(ln1::Node, ln2::Node, carry=false) =
    addVal(ln1.val, ln2.val, UInt8(carry))
addNodesVal(ln::Node, ::Null, c::Bool) =
    addVal(ln.val, UInt8(0), UInt8(c))
addNodesVal(::Null, ln::Node, c::Bool) =
    addVal(ln.val, UInt8(0), UInt8(c))
addNodesVal(::Null,   ::Null, c::Bool) = (UInt8(c), 1)

function addTwoNumbers_wo2(ln1::ListNode, ln2::ListNode)
    val, carry = addNodesVal(ln1, ln2)
    ln3 = Node(val, null)
    next_node = ln3

    while carry==1 || ln1.next!=null || ln2.next!=null
        _val, carry = addNodesVal(ln1.next, ln2.next, carry)
        next_node.next = Node(_val, null)

        # 下一圈初始化
        ln1.next!=null && (ln1 = ln1.next)
        ln2.next!=null && (ln2 = ln2.next)
        next_node = next_node.next
    end

    ln3
end

# [两数相加 - 两数相加 - 力扣（LeetCode）](https://leetcode-cn.com/problems/add-two-numbers/solution/liang-shu-xiang-jia-by-leetcode/)
function addTwoNumbers_leetcode(ln1::ListNode, ln2::ListNode)
    root_node = Node(0xff, null)
    cur_node = root_node
    carry = 0
    
    while ln1!=null || ln2!=null
        v1 = ln1!=null ? ln1.val : 0
        v2 = ln2!=null ? ln2.val : 0
        
        temp = v1 + v2 + carry
        carry = temp ÷ 10 # 整除
        
        cur_node.next = Node(temp%10, null)
        cur_node = cur_node.next
        
        ln1!=null && (ln1 = ln1.next)
        ln2!=null && (ln2 = ln2.next)
    end
    if carry > 0
        cur_node.next = Node(a, null)
    end
    root_node.next
end

# [LeetCode: Add Two Numbers » CodersCat](https://coderscat.com/leetcode-add-two-numbers)
function addTwoNumbers_coderscat(ln1::ListNode, ln2::ListNode)
    root_node = Node(0xff, null)
    cur_node = root_node
    carry = 0
    sum = 0
    
    while ln1!=null || ln2!=null
        sum = carry
        ln1!=null && (sum += ln1.val)
        ln2!=null && (sum += ln2.val)
        
        if sum >= 10
            carry = sum ÷ 10
            sum %= 10
        else 
            carry = 0
        end
        
        cur_node.next = Node(sum, null)
        cur_node = cur_node.next
        
        ln1!=null && (ln1 = ln1.next)
        ln2!=null && (ln2 = ln2.next)
    end
    if carry > 0
        cur_node.next = Node(a, null)
    end
    root_node.next
end

# - [使用伪头节点，对应位依次相加，记录进位 - 两数相加 - 力扣（LeetCode）](https://leetcode-cn.com/problems/add-two-numbers/solution/shi-yong-wei-tou-jie-dian-dui-ying-wei-yi-ci-xiang/ )
function addTwoNumbers_brooot(ln1::ListNode, ln2::ListNode)
    root_node = Node(0xff, null)
    cur_node = root_node
    carry = 0
    sum = 0
    
    while ln1!=null || ln2!=null || carry>0
        sum = carry
        ln1!=null && (sum += ln1.val)
        ln2!=null && (sum += ln2.val)
        carry = sum ÷ 10
        
        cur_node.next = Node(sum%10, null)
        cur_node = cur_node.next
        
        ln1!=null && (ln1 = ln1.next)
        ln2!=null && (ln2 = ln2.next)
    end
    if carry > 0
        cur_node.next = Node(a, null)
    end
    root_node.next
end

# [最简写法 - 两数相加 - 力扣（LeetCode）](https://leetcode-cn.com/problems/add-two-numbers/solution/zui-jian-xie-fa-by-baal-3/)
function addTwoNumbers_Baal(ln1::ListNode, ln2::ListNode)
    root_node = Node(0xff, null)
    cur_node = root_node
    carry = 0
    
    while ln1!=null || ln2!=null || carry>0
        cur_node.next = Node(0, null)
        cur_node = cur_node.next

        ln1 = ln1!=null ? (carry+=ln1.val; ln1.next) : ln1
        ln2 = ln2!=null ? (carry+=ln2.val; ln2.next) : ln2
        
        cur_node.val = carry % 10
        carry = carry ÷ 10
    end
    root_node.next
end

function addTwoNumbers_Baal2(ln1::ListNode, ln2::ListNode)
    ln3, _ = addTwoNumbers_Baal2_rec(ln1, ln2)
    ln3
end
function addTwoNumbers_Baal2_rec(ln1::ListNode, ln2::ListNode, carry=0)
    if ln1==null && ln2==null && carry==0
        return null, 0
    end
    
    ln1 = ln1!=null ? (carry+=ln1.val; ln1.next) : ln1
    ln2 = ln2!=null ? (carry+=ln2.val; ln2.next) : ln2
    
    cur_node = Node(carry%10, null)
    carry = carry ÷ 10
    
    next, carry = addTwoNumbers_Baal2_rec(ln1, ln2, carry)
    cur_node.next = next
    
    cur_node, carry
end


#= 辅助函数 
=#
"数字转数组"
function num2arr(n::Integer)
    ## 1- digits 法
    # digits 输出为倒序
    #   digits(123) == [3, 2, 1]
    n |> digits |> reverse
end
function num2ln(n::Integer)
    arr = num2arr(n)
    ln = null
    for i in arr
        ln = Node(UInt8(i), ln)
    end
    ln
end
Node(n::Integer) = num2ln(n)
Node() = null

# test 
big_num = big"1122334455667788990998877665544332211"
result_big_num = big_num*2
big_node = Node(big_num)
result_node = Node(result_big_num)

# @btime $big_num + $big_num
@show  addTwoNumbers_wo2(big_node, big_node)==result_node
@btime addTwoNumbers_wo2($big_node, $big_node)

@show  addTwoNumbers_leetcode(big_node, big_node)==result_node
@btime addTwoNumbers_leetcode($big_node, $big_node)

@show  addTwoNumbers_coderscat(big_node, big_node)==result_node
@btime addTwoNumbers_coderscat($big_node, $big_node)

@show  addTwoNumbers_brooot(big_node, big_node)==result_node
@btime addTwoNumbers_brooot($big_node, $big_node)

@show  addTwoNumbers_Baal(big_node, big_node)==result_node
@btime addTwoNumbers_Baal($big_node, $big_node)
@show  addTwoNumbers_Baal2(big_node, big_node)==result_node
@btime addTwoNumbers_Baal2($big_node, $big_node)

addTwoNumbers_wo2(big_node, big_node) == result_node = true
  15.700 μs (37 allocations: 1.16 KiB) 
addTwoNumbers_leetcode(big_node, big_node) == result_node = true
  18.799 μs (38 allocations: 1.19 KiB)      
addTwoNumbers_coderscat(big_node, big_node) == result_node = true
  19.500 μs (38 allocations: 1.19 KiB)      
addTwoNumbers_brooot(big_node, big_node) == result_node = true
  19.999 μs (38 allocations: 1.19 KiB)      
addTwoNumbers_Baal(big_node, big_node) == result_node = true
  20.699 μs (38 allocations: 1.19 KiB)      
addTwoNumbers_Baal2(big_node, big_node) == result_node = true
  13.299 μs (75 allocations: 2.33 KiB)

geebbon · 2021 年1 月 30 日 02:52

function reverse_string(a)
    astring = string(a)
    a_rev = astring[collect(length(astring):-1:1)]
    a_num = parse(Int, a_rev)
end


function twoAdd(a,b)
    c = reverse_string(a) + reverse_string(b)
    c_rev = reverse_string(c)
end

twoAdd(123, 482)

Leetcode题库第２题：两数相加 用Julia怎么解？

Leetcode题库第２题：两数相加用Julia怎么解？