GoLang, 原创, ,

【算法】两数相加（GoLang）

两数相加题目和测试地址： https://leetcode-cn.com/problems/add-two-numbers/

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：

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

最初实现绕了个弯，先把链表转为数字，数字相加后在转换为链表，这其中遇到了越界问题于是又手写了个大数相加函数，这样想来自然也快不起来，先展示下最初代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	num1 := BuildListSum(l1)
	num2 := BuildListSum(l2)
    numResult := AddTwoString(num1, num2)
	//fmt.Println(numResult)
	return BuildSumList(numResult)
}

func BuildListSum (listNote *ListNode) string {
	num1 := ""
	i := 0
	for e := listNote; e != nil; e = e.Next {
		num1 = fmt.Sprintf("%v%v", e.Val, num1)
		i++
	}
	return num1
}


func BuildSumList(num string) *ListNode {
	var listNote *ListNode
	count := len(num)
	for i := 0; i < count; i++ {
		//fmt.Println(numString[i:i+1])
		n,_ := strconv.Atoi(num[i:i+1])
		if listNote == nil {
			listNote = &ListNode{n, nil}
		} else {
			listNote = &ListNode{n, listNote}
		}
	}
	return listNote
}

func AddTwoString(num1, num2 string) string {
	result := ""
	if len(num1) ==0 && len(num2) ==0 {
		return "0"
	}
	if len(num2) > len(num1) {
		tmp := num1
		num1 = num2
		num2 = tmp
	}
	needInc := 0
	length1 := len(num1) -1
	length2 := len(num2) - 1
	for i := 0; i <= length2; i++ {
		tmp1 := num1[length1-i] - '0'
		tmp2 := num2[length2-i] - '0'
		tmpSum := int(tmp1) + int(tmp2) + needInc
		if tmpSum >= 10 {
			needInc = 1
		} else {
			needInc = 0
		}
		c3 := tmpSum % 10 + '0'
		result = fmt.Sprintf("%c%s",c3,result)
	}
	leftLength := length1 - length2
	for leftLength > 0 {
		c1 := num1[leftLength-1]-'0'
		sum :=  int(c1) + needInc
		if sum >= 10 {
			needInc = 1
		} else {
			needInc = 0
		}
		c3 := (sum %10) + '0'
		result = fmt.Sprintf("%c%s",c3,result)
		leftLength--
	}
	if needInc == 1 {
		result = fmt.Sprintf("1%s",result)
	}
	return result
}

执行用时 :20 ms, 在所有 golang 提交中击败了34.31%的用户
内存消耗 :6.1 MB, 在所有 golang 提交中击败了5.17%的用户

后面看到其他人的时间和内存都很小，才发现自己绕了一大圈，不需要转成数字，直接使用链表中的元素相加，注意进位就可以了，下面是做了一次优化的代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	result := &ListNode{}
	listNote := result
	left := 0
	for {
		e1 := l1
		e2 := l2
		if e1 == nil || e2 == nil {
			break
		}
		v := e1.Val + e2.Val + left
		if v >= 10 {
			left = 1
		} else {
			left = 0
		}
		n := v % 10
		listNote.Next = &ListNode{Val:n}
		l1 = l1.Next
		l2 = l2.Next
		listNote = listNote.Next
	}
	if l1 != nil {
		for e := l1; e != nil; e = e.Next {
			v := e.Val + left
			if v >= 10 {
				left = 1
			} else {
				left = 0
			}
			n := v % 10
			listNote.Next = &ListNode{Val:n}
			listNote = listNote.Next
		}
	}
	if l2 != nil {
		for e := l2; e != nil; e = e.Next {
			v := e.Val + left
			if v >= 10 {
				left = 1
			} else {
				left = 0
			}
			n := v % 10
			listNote.Next = &ListNode{Val:n}
			listNote = listNote.Next
		}
	}
	if left > 0 {
		listNote.Next = &ListNode{Val:1}
	}
	return result.Next
}

执行结果：

执行用时 :16 ms, 在所有 golang 提交中击败了63.46%的用户
内存消耗 :4.9 MB, 在所有 golang 提交中击败了94.01%的用户

发现还有人有更精简的代码，于是在重写下

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	result := &ListNode{}
	listNote := result
	left := 0
	for l1 != nil || l2 != nil || left > 0 {
		sum := left
		if l1 != nil {
			sum += l1.Val
			l1 = l1.Next
		}
		if l2 != nil {
			sum += l2.Val
			l2 = l2.Next
		}
		if sum >= 10 {
			left = 1
		} else {
			left = 0
		}
		listNote.Next = &ListNode{Val:sum % 10}
		listNote = listNote.Next
	}
	return result.Next
}

执行结果：

执行用时 :8 ms, 在所有 golang 提交中击败了97.50%的用户
内存消耗 :4.9 MB, 在所有 golang 提交中击败了94.01%的用户

从20ms到 8ms算是提升了不少，每次也从6.1M降至4.9M

(606)

Related Post