LeetCode攀登之旅(1)

  • 2019 年 10 月 5 日
  • 筆記

LeetCode攀登之旅(1)

1.题目

2.解法

2.1 解法一

2.2 解法二

3.结果

4.作者的话

1.题目

Question:

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

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

Example:

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

2.解法

2.1 解法一

Thinking:

特殊情况:

两个链表开头均为0,直接返回其中一个链表即可;第一个链表开头为0,第二个链表开头不为0,返回第二个链表;第一个链表开头不为0,第二个链表开头为0,返回第一个链表。

其他情况如下:

如上例子所示得到807,然后逆向翻转即可得到7->0->8,那么怎么得到807呢,这个直接看上面Explanation:342+465,那么342与564又怎么得到呢?

很简单,分别对两个链表逆转组合的数即为这两个数,那么在链表操作,又如何得到这两个数?

以其中一个数字342为例子,他是由2*1+4*10+3*100得到的,那么只需要设置个参数t,首次赋值t=1,后面每次乘以10,作累加即可。另外一个数字同此方法,那么两数相加得到807,怎么展开成7、0、8,并分别赋给链表节点呢。

  • 将807每次除以10,所得的余数刚好为7,继续以807/10的结果按照前面操作依次得到0、8;
  • 在每次得到的数字7或者0、8的同时,可通过创建动态链表节点,并赋值即可。

到这里就有问题了,你怎么保证两数相加所得到的数不超过int范围。。。万一所给的链表很长,岂不是一下子就越界了。。那么以下代码运行就出现了这种问题。。所以不建议。

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {      struct ListNode* p=(struct ListNode*)malloc(sizeof(struct ListNode));      struct ListNode *s, *r=p;  //r 为表尾指针      int t=1;      int a=0,b=0,c;      if(l1->val==0&&l2->val==0)      {          return l1;      }      else if(l1->val==0&&l2->val!=0)      {          return l2;      }      else if(l1->val!=0&&l2->val==0)      {          return l1;      }      else      {          while(l1)          {              a += t*(l1->val);              l1 = l1->next;              t *= 10;          }          t=1;          while(l2)          {                b += t*(l2->val);              l2 = l2->next;              t *= 10;          }          c = a + b;          while(c)          {              s=(struct ListNode *)malloc(sizeof(struct ListNode));              s->val=c%10;              r->next=s;              r=s;              c=c/10;          }          r->next = NULL;          return p->next;        }    }

2.2 解法二

Thinking:

特殊情况:链表一为空,返回链表二;链表二为空,返回链表一;

当链表一或者链表二一开始都不为空时,思考如下:

# 正方向直接算结果  (2 -> 4 -> 3)  (5 -> 6 -> 4)  (7 -> 0 -> 8)

那就是,当对应位置上的数相加超过10,就会使得下一位+1,有点类似于普通的两数相加,只不过反过来了。看出以上规律了?

那么我们这里很明确,因为当前位置上的数,最多两个9,和最大18,向后进位最多1,也就是当前位置上的两个数之和只要超过10,那么让他往后加上一个flag数即可,此处的flag为0或者1。

当前位置最终的数为两个链表对应位置数之和除以10的余数!

下一位是否进位通过前面一位对应两个链表相加,除以10的结果向前取整!

c语言实现

那么接下来,进入算法实现环节,首先来看c语言实现:

  • 定义一个头结点head,并赋初值为0,可以不赋值;
  • 定义动态节点s,此节点对应的值为每次两链表运算所得的数;
  • 定义r节点,表示尾节点,采用尾插法,每次链向s;
  • 特殊情况处理;
  • 两链表循环内部操作;
  • 利用尾节点直接指向头节点的下一个节点,并释放头结点,返回r所指的head的下一个节点,即为最终结果。
struct ListNode * addTwoNumbers( struct ListNode * l1, struct ListNode * l2 )  {      struct ListNode * head, *r, *s;      int tr;      head = (struct ListNode *)malloc( sizeof(struct ListNode) );      head->val = 0;      r = head;      if (l1 == NULL)          return(l2);      if (l2 == NULL)          return(l1);      int tsum;      int flag = 0;      while (l1||l2)      {          tsum = 0;          if (l1)          {              tsum += l1->val;              l1 = l1->next;          }          if (l2)          {              tsum += l2->val;              l2 = l2->next;          }          tr = (tsum + flag) % 10;          flag = (int) ( (tsum + flag) / 10);          s = (struct ListNode * ) malloc( sizeof(struct ListNode) );          s->val = tr;          r->next = s;          r = r->next;      }      if ( flag )      {          s = (struct ListNode *)malloc( sizeof(struct ListNode) );          s->val = 1;          r->next = s;          r = s;      }      r->next = NULL;      r = head->next;      free(head);      return(r);  }

python语言实现

  • c与py链表操作不同

python链表操作与c语言链表操作不同,在python中直接使用ListNode(0)即可表示为当前节点赋值为0,并同时创建了当前节点。同理,c语言与python语言的next操作也不一样!

  • 整除,c语言中使用int强制从float转换,而python中使用两个/,即//直接返回向下取整结果。

其余思想同上!

# Definition for singly-linked list.  # class ListNode:  #     def __init__(self, x):  #         self.val = x  #         self.next = None    class Solution:      def addTwoNumbers(self, l1, l2):          """          :type l1: ListNode          :type l2: ListNode          :rtype: ListNode          """          if l1 is None:              return l2          if l2 is None:              return l1          head = ListNode(0)          r = head          flag=0          while l1 or l2:              tsum = 0              if l1:                  tsum += l1.val                  l1=l1.next              if l2:                  tsum += l2.val                  l2=l2.next              tr = ((tsum + flag) % 10)              flag = ((tsum + flag) // 10)              r.next = ListNode(tr)              r = r.next          if flag:              r.next = ListNode(1)          r = head.next          del head          return r

3.结果

LeetCode中,c语言第一次通过击败人数才60%左右,再次提交就100%了。哈哈~~~

c提交图

python通过后,第一次击败人数95.74%,后面再提交58%。。然后再提交,就又高了,很不准确~~~

python提交图

4.作者的话

最后,您如果觉得本公众号对您有帮助,欢迎您多多支持,转发,谢谢!

更多刷题,请关注本公众号算法系列!