0002.Add Two Numbers

0002.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.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

思路

大数加法的思路,这里只是把存储从数组变成了链表。

从末尾开始加,超过10就进位,主要是注意边界条件,两个链表各自为空的情况

  • 时间复杂度 O(maxlen)
  • 空间复杂度 O(maxlen)

代码

impl Solution {
pub fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {

let (mut l1, mut l2) = (l1,l2);
let mut dummy_head = Some(Box::new(ListNode::new(0)));
let mut tail = &mut dummy_head;
let (mut l1_end, mut l2_end, mut overflow) = (false,false,false);

loop {
let l1_value = match l1 {
Some(node) => { l1 = node.next; node.val},
None => { l1_end = true; 0},
};
let l2_value = match l2 {
Some(node) => { l2 = node.next; node.val},
None => { l2_end = true; 0},
};

if l1_end && l2_end && !overflow {
break dummy_head.unwrap().next
}

let sum = l1_value + l2_value + if overflow { 1 } else { 0 };
let sum = if sum >= 10 { overflow=true; sum -10} else {
overflow=false; sum
};

tail.as_mut().unwrap().next = Some(Box::new(ListNode::new(sum)));
tail = &mut tail.as_mut().unwrap().next
}
}
}
  • 执行用时: 0 ms
  • 内存消耗: 2.1 MB

题型与相似题

题型

  1. 链表
  2. 大数运算

相似题

代码

add_two_numbers

0001. Two Sum

0001. Two Sum

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].

思路

  1. 暴力 时间复杂度 O(n2) 空间复杂度 O(1)
  2. 哈希 时间复杂度 O(n) 空间复杂度 O(n))
  3. 排序再查找 时间复杂度 O(nlogn) 此题返回下标不可行,相似题可行

暴力两次循环

学过其他语言的,很容易写出的代码

impl Solution
{
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {

let len = nums.len();
for i in 0..len {
for j in i+1..len {
if nums[i] + nums[j] == target {
return vec![i as i32, j as i32];
}
}
}

vec![]
}
}

  • 执行用时: 40 ms
  • 内存消耗: 2.1 MB

for循环两次,判断是否相等。
如果要使用数组的迭代器,那第二次循环只能重头开始,需要判断index是否相等。

impl Solution
{
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {

for(i, num_i) in nums.iter().enumerate()
{
for (j, num_j) in nums.iter().enumerate()
{
if i != j && num_i + num_j == target
{
return vec![i as i32, j as i32]
}
}
}
vec![]
}
}

  • 执行用时: 76 ms
  • 内存消耗: 2 MB

HashMap

我们考虑使用HashMap,拿空间换时间。
如果没有在哈希表中就插入,有就返回结果。

use std::collections::HashMap;

impl Solution {
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut map = HashMap::with_capacity(nums.len());
for(index,num) in nums.iter().enumerate() {
if let Some(&find) = map.get(&(target-num)) {
return vec![find as i32, index as i32];
}
map.insert(num,index);
}
vec![]
}
}

  • 执行用时: 0 ms
  • 内存消耗: 2.3 MB

需要注意,返回的是索引,所以插入哈希表时key应该是nums中的值,value才是index。

问题与优化思路

问题:
对Rust语法不算熟悉,需要查文档才能知道HashMap的用法。
做算法题,开始得画图来理清自己的思路,确定需求和数据边界,这题中返回下标是首先要确定的需求。

优化思路:
此题如果不返回下标,会有先排序后查找的算法作为X Sum的基础解决算法。
X Sum的解题思路主要是把它转化为(X-1)Sum,最后成为2Sum问题,得到最后的答案。
这其中的转换就是,选出一个元素a,然后就变成target为 -a 的(X-1)Sum 问题。

题型与相似题

题型

  1. 数组
  2. 哈希表

相似题

  1. Two Sum II – Input array is sorted
  2. Two Sum III – Data structure design
  3. 3 Sum
  4. 3 Sum Smaller
  5. 3 Sum Closet
  6. 4 Sum

代码

two_sum

参考资料