21. Merge Two Sorted Lists （Easy）
Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
# 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: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummy_head = ListNode(val='NULL')
cur = dummy_head
while l1 and l2:
if l1.val<l2.val:
cur.next = l1
l1=l1.next
else:
cur.next = l2
l2=l2.next
cur = cur.next
if l1:
cur.next = l1
if l2:
cur.next = l2
return dummy_head.next
22. Generate Parentheses (Medium)
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
# 1(2)3
# 1(2)3(4)5 1(2(3)4)5
if n==1: return ['()']
level_result = ['()']
for level in range(n-1):
level_result_tmp = set()
for result in level_result:
for ind in range(len(result)+1):
if ind==0:
new = '()'+result[ind:]
elif ind==len(result):
new = result+'()'
else:
new = result[:ind] +'()'+result[ind:]
level_result_tmp.add(new)
level_result = list(level_result_tmp)
return level_result
#answer way of writing
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
if n==0: return [""]
res =[]
for i in range(n):
left = self.generateParenthesis(i)
right = self.generateParenthesis(n-i-1)
for l in left:
for r in right:
res.append("({}){}".format(l,r))
return res
答案用了递归，逻辑简单，把所有复杂表示简化为（{}）{} 。 自己方法是通过观察逐层增加构建答案。
23. Merge k Sorted Lists (hard)
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
# 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,l2):
dummy_head = ListNode(val='NULL')
cur = dummy_head
while l1 and l2:
if l1.val<l2.val:
cur.next = l1
l1=l1.next
else:
cur.next = l2
l2=l2.next
cur = cur.next
if l1:
cur.next = l1
if l2:
cur.next = l2
return dummy_head.next
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
# 0 1 2 4 5
if not lists:
return None
elif len(lists)==1:
return lists[0]
elif len(lists)==2:
return self.mergeTwoLists(lists[0],lists[1])
else:
l = len(lists)
left = self.mergeKLists(lists[:l//2])
right = self.mergeKLists(lists[l//2:])
return self.mergeTwoLists(left,right)
已经知道merge two了， 如何merge K？递归容易写， iterative如何写(假设已经有merge2 function m2)？
0 1 2 3 4
while bitmask < len(list)=5
bitmask = 0001
partner= rank ^ bitmask; I am sending = rank & bitmask；
0=>0^1=1 False
1=>1^1=0 True
2=>2^1=3 False
3=>3^1=2 True
4 =>4^1=5 (no 5) False
（01 1 23 3 4）
bitmask = 0010
0=>0^2=2 False
1=>1^2=3 False
2=>2^2=0 True
3=>3^2=1 True
4=>4^2=6 （no 6） False
（0123 13 23 3 4）
bitmask = 0100
0=>0^4 = 4 False
1=>1^4= 5 False
2=>2^4=6 False
3=>3^4=7 False
4=>4^4=0 True
（01234 13 23 3 4）
或者不用bit方法，开始segmentation 是1，i 收集 i， i+seg信息， 之后segment变为2 ...
k=len(lists)
seg=1
while seg<k:
for i in range(0,k,seg*2):
if i+seg<k:
lists[i]=m2(lists[i],lists[i+seg])
seg*=2
24. Swap Nodes in Pairs (Medium)
Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or (head and not head.next): return head
newhead = head.next
tmp = newhead.next
newhead.next = head
head.next = self.swapPairs(tmp)
return newhead
注意边界条件， 至少需要2个才能玩的起来， 如果没有或者只有一个元素，直接return。
25. Reverse Nodes in k-Group （Hard）
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.
Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
cur = head
counter = 0
can_reverse = False
while cur:
counter+=1
cur=cur.next
if counter>=k:
can_reverse = True
break
forthnode = cur
if not can_reverse:
return head
#can_reverse, let's reverse k
cur = head
pre = None
c=0
while cur:
curnext = cur.next
cur.next = pre
pre = cur
cur = curnext
c+=1
if c==k:
break
head.next = self.reverseKGroup(forthnode,k)
return pre
没想到做出来了， 。。。
26. Remove Duplicates from Sorted Array （Easy）
Input: nums = [1,1,2]
Output: 2, nums = [1,2,]
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,,,,,]
典型的two pointer， array已经sorted，p1 保存将要储存元素位置， p2 扫nums，pre保留之前扫过的数值，如果和pre不同就保存在p1 位置， p1++
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
pre=None
i=0
for j,n in enumerate(nums):
if n!=pre:
nums[i]=nums[j]
i+=1
pre = n
return i
27. Remove Element (Easy)
Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
i=0
for j,n in enumerate(nums):
if n!=val:
nums[i]=n
i+=1
return i
in-place 依旧是考察two pointer
28. Implement strStr() （Easy）
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if len(needle)>len(haystack): return -1
res = -1
#0 1 2 3 4
# 4
# 5 -1 range(5)
for i in range(len(haystack)-len(needle)+1):
if haystack[i:i+len(needle)] == needle:
return i
return res
29. Divide Two Integers (Medium)
Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.
INT_MIN=-2**31
INT_MAX=2**31-1
if not divisor or (dividend == INT_MIN and divisor == -1):
return INT_MAX
sign= (dividend>0) ^ ( divisor>0)
dividend, divisor=abs(dividend), abs(divisor)
c=0
while dividend >= divisor:
temp = divisor
level = 1
while dividend >= (temp<<1):
level = level<<1
temp = temp<<1
dividend-=temp
c+=level
return -c if sign else c
###my solution
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
sign = (dividend>0 and divisor>0) or (dividend<0 and divisor<0)
divident = abs(dividend)
divisor = abs(divisor)
res = 0
while divident>=divisor:
mask = 1
tmp = divisor
while divident >= (tmp<<1):
mask = mask << 1
tmp = tmp << 1
res+= mask
divident-=tmp
res = res if sign else -res
if res>= 2**31-1: return 2**31-1
if res<=-2**31:return -2**31
return res
30. Substring with Concatenation of All Words (Hard)
You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
if not s or not words: return []
wc=Counter(words)
nwords = len(words)
lword = len(words[0])
head = list(zip(*words))[0]
res=[]
for i in range(len(s)-lword*nwords+1):
if s[i] in head:
substring = s[i:i+lword*nwords]
temp =dict()
for j in range(nwords):
key = substring[j*lword:(j+1)*lword]
temp[key]=temp.get(key,0)+1
if temp==wc:
res.append(i)
return res
Too late today, 知道应该用Counter_dict做比较但没写出来，思路：扫所有字符， 发现在头字符列表中，测试i:i+lword*nwords的字符范围是不是和Counter_dict一样， 一样就append i。
two pointer + counter dict 应用。