LeetCode Problem 2 - Add Two Numbers

继续第二道题目,下面是问题描述:

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

这个问题比较简单,基本上解题思路是比较清晰的。输入是两个链表,链表的元素都是单个数字(0-9),要求将两个列表的相应节点数字相加,并作为结果链表返回。

这个题咋看可以马上开始解答,但是在此之前还是有一些需要注意的地方。第一点是,题目并没有说明链表的长度,所以 A 和 B 两个链表可能不一定相同长度,那么如果一个链表更长,那么相加怎么处理呢?这里就考虑直接返回即可,相当于+0。第二点是,如果相加溢出怎么处理,其实题目的例子里面已经很清晰了,溢出会发生进位,依次向后处理。第三点是,如果最后一位发生进位呢,这点容易被遗忘,需要新增一个节点。

下面是具体的代码:

// Problem 2. Add Two Numbers
// URL: https://leetcode.com/problems/add-two-numbers/tabs/description

// ListNode defines a singly-linked list
type ListNode struct {
	Val  int
	Next *ListNode
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	head := &ListNode{0, nil} // sentinel node
	carry := 0                // carray bit

	for tail := head; l1 != nil || l2 != nil || carry != 0; tail = tail.Next {
		sum := carry

		if l1 != nil {
			sum += l1.Val
			l1 = l1.Next
		}

		if l2 != nil {
			sum += l2.Val
			l2 = l2.Next
		}

		tail.Next, carry = &ListNode{sum % 10, nil}, sum/10
	}

	return head.Next // discard sentinel node
}

这里在链表加了一个哨兵节点,主要是为了处理方便。完整的代码参见这里,以及测试代码

LeetCode Problem 1 - Two Sum

最近开始在 LeetCode 网站上刷题,准备练练脑子。因为经常不动脑,感觉快生锈了。这个是第一题,比较简单。所有的解题代码都放在 Github 上。

问题描述:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

题目描述的很清楚了,就是要从整数列表里面找出符合需求的两个数字,他们之和等于给定的目标值。输入是整数列表,输出是两个数字下标的列表。从给的例子上看,我们可以假设返回的列表,下标小的放在前面,比如是 [0, 1] 而不是 [1, 0]。那假如没有找到符合要求的数字呢,应该返回什么呢?题目里面没有明确说明,我自己觉得这里应该返回一个空值。

思路一

首先,我们可以想到一种最简单的方法,就是遍历所有组合,这种方法比较暴力也很有效。下面的代码用 go 语言编写:

func twoSum(nums []int, target int) []int {
	n := len(nums)

	if n < 2 {
		return nil
	}

	for i := 0; i < n-1; i++ {
		for j := i + 1; j < n; j++ {
			if nums[i]+nums[j] == target {
				return []int{i, j}
			}
		}
	}

	return nil
}

这个方法没什么好解释的,它的时间复杂度是O(n^2)

思路二

如果我们要降低时间复杂度,就必须减少迭代的次数。可以想到的一个优化思路是,针对数组进行排序,然后定义两个指针,分别从头和尾两个方向逼近,看起来有点像快速排序。如果指针指向的两个数之和大于目标值,则右边的指针左移。反之,左边的指针右移。直到找到符合需求的两个数。因为排序的最佳时间复杂度可以达到O(nlogn),接下来只遍历一次,时间复杂度是O(n),所以总的时间复杂度为 O(nlogn)。

这是一个不错的思路,但是这道题目要返回数字的下标,但是如果我们先排序会导致顺序就和初始状态不一样,所以还得想办法记录,所以这个思路最终实现也挺别扭的,就放弃了。

思路三

回到题目,我们要求出 a+b=target,反过来看,如果我们当前遍历的数字是 a,也就是我们要看 target - a 这个结果在数组里面是否存在。为了加快查找的效率,我们可以用额外的空间换时间效率,哈希表是一个很好的策略。在遍历的时候我们把每个数字和它对应的坐标保存到一个哈希表中。相应的代码如下:

func twoSum(nums []int, target int) []int {
	tbl := make(map[int]int, len(nums))

	for i, v := range nums {
		if j, ok := tbl[target-v]; ok {
			return []int{j, i}
		}

		tbl[v] = i
	}

	return nil
}

完整代码

完整的代码参见这里,以及测试代码