后台-插件-广告管理-内容页广告位一(手机)

您现在的位置是:首页 > 编程语言 > pythonpython

python3合并两个有序列表 and 加一

2021-04-18 18:39:18python人已围观

简介21.合并两个有序列表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1:
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[

21.合并两个有序列表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1:

输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
示例 2:

输入:l1 = [], l2 = []
输出:[]
示例 3:

输入:l1 = [], l2 = [0]
输出:[0]

常规思路:

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
new_list = ListNode(-1,None)
head = new_list
while l1 and l2:
if l1.val<l2.val:
new_list.next = l1
new_list=new_list.next
l1=l1.next
else:
new_list.next = l2
new_list=new_list.next
l2=l2.next
if l1:
new_list.next = l1
if l2:
new_list.next = l2
return head.next
1
递归思路

if not l1: return l2 # 终止条件,直到两个链表都空
if not l2: return l1
if l1.val <= l2.val: # 递归调用
l1.next = self.mergeTwoLists(l1.next,l2)
return l1
else:
l2.next = self.mergeTwoLists(l1,l2.next)
return l2

加一
给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一。
最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。

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

示例 1:

输入:digits = [1,2,3]
输出:[1,2,4]
解释:输入数组表示数字 123。
示例 2:

输入:digits = [4,3,2,1]
输出:[4,3,2,2]
解释:输入数组表示数字 4321。
示例 3:

输入:digits = [0]
输出:[1]

思路1:字符串和整型相互转然后+1,思路简单,但是耗用内存

class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
str1 = ''
lst = []
for i in digits:
str1 += str(i)
str1 = str(int(str1)+1)
for i in str1:
lst.append(int(i))
return lst

思路2:直接操作;将最后一位加一,然后判断是否需要进位,以及考虑最坏情况

class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
addone = 0
digits[-1] += 1
for i in range(len(digits)-1,-1,-1):
if addone == 1:
digits[i] += addone
addone = 0
if digits[i] == 10:
digits[i] = 0
addone = 1
else:
return digits
if digits[0] == 0:
digits.insert(0, 1)
return digits

思路3:

newlst = []
while digits and digits[-1] == 9:
digits.pop()
newlst.append(0)
if not digits:
return [1] + newlst
else:
digits[-1] += 1
return digits + newlst

本文首发于python黑洞网,博客园同步跟新

文章来源:查看

Tags:有序   合并   两个   列表   python3

很赞哦! ()

后台-插件-广告管理-内容页广告位二(手机)

相关文章

后台-插件-广告管理-内容页广告位三(手机)
后台-插件-广告管理-内容页广告位四(手机)

文章评论

留言与评论(共有 0 条评论)
   
验证码:

本栏推荐

站点信息

  • 文章统计13614篇文章
  • 浏览统计468次浏览
  • 评论统计1个评论
  • 标签管理标签云
  • 统计数据:统计代码
  • 微信公众号:扫描二维码,关注我们