Yefei.Blog

个人日记 WIKI

用户工具

站点工具


leetcode:002-add-two-numbers

002: Add two numbers

题目要求计算两个数组的和,每一位都是一个数字,如果其中一位数字的和大于等于10则向链表下一位进一

第一次尝试

Test 通过了, 但是提交却不通过,网站报 Runtime Error,输入值为 [0], [1]。
使用了相同的输入值在我本地测试是没有任何问题的,不明白为什么报错。
2016/10/5更新: 找到问题所在 out_p→next 没有设置默认值为 NULL。 m( 这个错误在 clang 上面会被默认设为 NULL, 不同的编译器处理的方式不一样。 m(

add_two_numbers.c
#include <stdio.h>
#include <stdlib.h>
 
struct ListNode {
	int val;
	struct ListNode *next;
};
 
/*
 解题代码
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
	if (l1 == NULL) return l2;
	if (l2 == NULL) return l1;
 
	struct ListNode *out = malloc(sizeof(struct ListNode));
	struct ListNode *out_p = out;
 
	int v, t = 0;
 
	while (1) {
		v = (l1 == NULL ? 0 : l1->val) + (l2 == NULL ? 0 : l2->val) + t;
		if (v >= 10) {
			v = v - 10;
			t = 1;
		}
		else {
			t = 0;
		}
 
		out_p->val = v;
		out_p->next = NULL;
 
		l1 = l1 == NULL ? NULL : l1->next;
		l2 = l2 == NULL ? NULL : l2->next;
 
		if (l1 == NULL && l2 == NULL && t == 0) {
			break;
		}
 
		out_p = out_p->next = malloc(sizeof(struct ListNode));
	}
 
	return out;
}
 
struct ListNode* createNode(int val) {
	struct ListNode *newNode = malloc(sizeof(struct ListNode));
	newNode->val = val;
	newNode->next = NULL;
	return newNode;
}
 
void printNodes(char *name, struct ListNode* list) {
	printf("Nodes: %s", name);
	struct ListNode *p = list;
	while (p != NULL) {
		printf(" > %d", p->val);
		p = p->next;
	}
	printf("\n");
}
 
int main() {
	struct ListNode *l1, *l2, *p;
	p = l1 = createNode(0);
	p = l1->next = createNode(3);
	p = p->next = createNode(4);
 
	p = l2 = createNode(1);
	p = l2->next = createNode(8);
	p = p->next = createNode(1);
 
	printNodes("L1", l1);
	printNodes("L2", l2);
 
	struct ListNode * out = addTwoNumbers(l1, l2);
	printNodes("Out", out);
 
	return 0;
}

Python 版本

一次通过

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        out = ListNode(0)
        out_p = out
        t = 0
        while True:
            v = t
            if l1: v += l1.val
            if l2: v += l2.val
 
            if v >= 10:
                v = v - 10
                t = 1
            else:
                t = 0
 
            out_p.val = v
 
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
 
            if l1 is None and l2 is None:
                break
 
            out_p.next = ListNode(0)
            out_p = out_p.next
        if t > 0:
            out_p.next = ListNode(t)
        return out

其他解法臆想

给定的是两个不定长度的数组,每个槽中只有一个数字。
如果我把两个数组中的数字直接取出拼成一个完整的数字,然后将两个完整的数字相加,得出的结果在分割为新的数组。

这里引申出来两问题:

1. l1 数组只有一个数字 5,l2 数组有三个数字 365,相加结果不符合要求。

  解决办法:将短的数组中的数字后面补 0 到和长的数组一致

2. 相加结果向后一位进一问题,纯数字相加都是向左进一,不符合要求。

  解决办法:把两个数组的数字颠倒过来相加,即可满足需求
leetcode/002-add-two-numbers.txt · 最后更改: 2016/10/05 23:30 由 yefei