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黑洞網,博客園同步跟新
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/271833.html
標籤：Python
上一篇：基于keras的文本情感識別
下一篇：爬取本blog所有文章鏈接