321. Create Maximum Number (Hard)
You are given two integer arrays nums1 and nums2 of lengths m and n respectively. nums1 and nums2 represent the digits of two numbers. You are also given an integer k.
Create the maximum number of length k <= m + n from digits of the two numbers. The relative order of the digits from the same array must be preserved.
Return an array of the k digits representing the answer.
Example
Input: nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5
Output: [9,8,6,5,3]
class Solution:
def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
# 思路。。。
# 最大需要每个位置数字最大，
# 但选择最大的数字有顺序约束
# 而且当可选最大数字相同时，需要程序tracking 2种不同结果。
def prep(nums, k):
drop = len(nums) - k
out = []
for num in nums:
while drop and out and out[-1] < num:
out.pop()
drop -= 1
out.append(num)
return out[:k]
def merge(a, b):
return [max(a, b).pop(0) for _ in a+b]
return max(merge(prep(nums1, i), prep(nums2, k-i)) for i in range(k+1) if i <= len(nums1) and k-i <= len(nums2))
没思路。。。看到答案用了greedy方法。。。 prep function只是在一个数组中按照顺序找出K个最大的数。先算一下需要drop多少个数， 如果当前值大于栈顶元素，说明需要更新栈顶。 merge function这一步是按照a，b的lexcial顺序找到最大的元素，a+b总共有K个元素，所以pop k次。 最后return所有K+1个分割可能产生的结果取最大的。基本不可能现想出来解法。
322. Coin Change （Medium）
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
if amount==0: return 0 if coins else -1
dp = dict()
for c in coins:
dp[c]=1
for a in range(1,amount+1):
for c in coins:
if a+c<=amount and a in dp:
if a+c in dp:
dp[a+c]=min(dp[a+c],dp[a]+1)
else:
dp[a+c]=dp[a]+1
return dp[amount] if amount in dp else -1
#ANSWER
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for x in range(coin, amount + 1):
dp[x] = min(dp[x], dp[x - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
#MY ANSWER
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
if amount==0: return 0
#dp[i] = min(dp[i-coin] + 1)
dp = [float('inf')]*(1+amount)
for i in range(1,amount+1):
for c in coins:
if c==i: dp[i]=1
dp[i] = min(dp[i],dp[i-c]+1) if i-c>=0 else dp[i]
print(dp)
return dp[amount] if dp[amount]!=float('inf') else -1
感觉是个DP问题，递归关系？ dp【i】是需要达到amount i需要的次数。 初始coins值的dp【coins_val】=1. 对于每一个有dp值的位置，都用coints_val 更新， dp【i+val】=min（dp【i+val】，dp【i】+1）直到amount。 由于不能开过大内存，所以dp变成dict。
答案写法更标准， dp【x】=min（dp【x】，dp【x-coin】+1） x大于等于coin小于等于amount。
323. Number of Connected Components in an Undirected Graph （Medium）
You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph.
Return the number of connected components in the graph.
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
dic = collections.defaultdict(set)
for a ,b in edges:
dic[a].add(b)
dic[b].add(a)
visited = set()
def dfs(i):
visited.add(i)
for j in dic[i]:
if j not in visited:
dfs(j)
c = 0
for i in range(n):
if i not in visited:
c+=1
dfs(i)
return c
#UNIONFIND
class Solution:
class UnionFind:
def __init__(self,n):
self.parent=[i for i in range(n)]
self.rank=[0]*n
self.n=n
def find(self,x):
if x!=self.parent[x]:
self.parent[x]=self.find(self.parent[x])
return self.parent[x]
def union(self,x,y):
px=self.find(x)
py=self.find(y)
if px!=py:
self.n-=1
if self.rank[px]<self.rank[py]:
self.parent[px]=py
elif self.rank[px]>self.rank[py]:
self.parent[py]=px
else:
self.parent[py]=px
self.rank[px]+=1
def countComponents(self, n: int, edges: List[List[int]]) -> int:
uf=self.UnionFind(n)
for edge in edges:
uf.union(*edge)
return uf.n
注意unionfind中 if x!=self.parent[x] 爸爸=找爸爸（爸爸） self.parent[x]=self.find(self.parent[x])， union只有rank相同时候才需要+rank。
324. Wiggle Sort II （Medium）
Given an integer array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....
You may assume the input array always has a valid answer.
def wiggleSort(self, nums):
count = [0]*5001
for n in nums:
count[n]+=1
odd = 1
even = 0
for n in range(5000,-1,-1):
if odd >= len(nums) and even >= len(nums):
break
if count[n] == 0:
continue
while count[n] and (odd < len(nums) or even < len(nums)):
count[n]-=1
if odd < len(nums):
nums[odd] = n
odd+=2
else:
nums[even] = n
even+=2
class Solution(object):
def wiggleSort(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
arr = sorted(nums)
for i in range(1, len(nums), 2): nums[i] = arr.pop()
for i in range(0, len(nums), 2): nums[i] = arr.pop()
class Solution:
def wiggleSort(self, A: List[int]) -> None:
N = len(A)
count = [0] * 5001
self.curr_val = A[0]
for v in A:
count[v] += 1
self.curr_val = max(self.curr_val, v)
def next_val():
while count[self.curr_val] == 0: self.curr_val -= 1
count[self.curr_val] -= 1
return self.curr_val
for i in range(1, N, 2): A[i] = next_val()
for i in range(0, N, 2): A[i] = next_val()
思路：从sorted 最大到最小，奇数位置放置，然后偶数位置放置数字。时间要降低到O（n）只能用count sort了。
325. Maximum Size Subarray Sum Equals k （Medium）
Given an integer array nums and an integer k, return the maximum length of a subarray that sums to k. If there isn't one, return 0 instead.
class Solution:
def maxSubArrayLen(self, nums: List[int], k: int) -> int:
nums = [0]+nums
for i in range(1,len(nums)):
nums[i] = nums[i]+nums[i-1]
dic = dict()
res = 0
for i ,n in enumerate(nums):
# n-b = k
if n-k in dic:
res = max(res, i-dic[n-k])
#because max length, so n only update at the first time
if n not in dic:
dic[n]=i
return res
该保留更早的index使长度更长。
326. Power of Three （Easy）
Given an integer n, return true if it is a power of three. Otherwise, return false.
An integer n is a power of three, if there exists an integer x such that n == 3x.
class Solution:
def isPowerOfThree(self, n: int) -> bool:
if n==0: return False
while n:
if n==1: return True
if n%3!=0:
return False
n//=3
return True
class Solution:
def isPowerOfThree(self, n: int) -> bool:
if n<1: return False
while n%3==0:
n//=3
return n==1
327. Count of Range Sum (Hard)
Given an integer array nums and two integers lower and upper, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j inclusive, where i <= j.
#TLE
class Solution:
def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
presum = [0]*(len(nums)+1)
for i,n in enumerate(nums):
presum[i+1]=presum[i]+n
res=0
for i in range(1,len(nums)+1):
for j in range(i):
if upper>=presum[i]-presum[j]>=lower:
res+=1
return res
#ANSWER 1 PrefixSum+MergeSort
class Solution:
def countRangeSum(self, nums, lower, upper):
cumsum = [0]*(len(nums)+1)
for i,num in enumerate(nums):
cumsum[i+1]=cumsum[i]+num
def sort(lo, hi):
mid = (lo + hi) // 2
if mid == lo:
return 0
count = sort(lo, mid) + sort(mid, hi)
i = j = mid
for left in cumsum[lo:mid]:
while i < hi and cumsum[i] - left < lower: i += 1
while j < hi and cumsum[j] - left <= upper: j += 1
count += j - i
cumsum[lo:hi] = sorted(cumsum[lo:hi])
return count
return sort(0, len(cumsum))
#ANSER Binary Indexed Tree + Binary Search
class BIT:
def __init__(self,size):
self.size = size
self.bit = [0]*(self.size+1)
def update(self,ind):
while ind <= self.size:
self.bit[ind] += 1
ind += (ind & -ind)
def query(self,ind):
res = 0
while ind>0:
res += self.bit[ind]
ind -= ind & -ind
return res
class Solution:
def countRangeSum(self, nums, lower, upper):
cumsum = [0]
for n in nums:
cumsum.append(cumsum[-1]+n)
res = 0
sorted_cumsum = sorted(cumsum)
bit= BIT(len(sorted_cumsum))
for sum_j in cumsum:
sum_i_count = bit.query(bisect.bisect_right(sorted_cumsum, sum_j - lower)) - bit.query(bisect.bisect_left(sorted_cumsum, sum_j - upper))
res += sum_i_count
bit.update(bisect.bisect_left(sorted_cumsum, sum_j)+1)
return res
首次尝试O（n^2）time limit exccded。 看来得低于O（n^2）才可以。。。改进方法是增加mergesort。 思路：先算cumsum。 目标找出cumsum【right】-cumsum【left】在upper lower 之间的这样的pair个数。 定义helper function merge sort。 返回值是满足条件的个数，先递归找出只在lomid和midhi之间的个数。若left~right横跨mid， 对于每一个left in sumsum【lo：mid】 找出满足upper lower bond的 right。其中满足lower bound的index 是i， 满足upper bound 的index 是j 所以 count+=j-i。
又忘记了有segment tree 和binary indexed tree这两种数据结构。。。。
collection = empty
for sum_j in Sum:
sum_i_count = how many sum_i in this collection that sum_j - upper <= sum_i <= sum_j - lower
res += sum_i_count
put sum_j into this collection
328. Odd Even Linked List (Medium)
Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.
The first node is considered odd, and the second node is even, and so on.
Note that the relative order inside both the even and odd groups should remain as it was in the input.
You must solve the problem in O(1) extra space complexity and O(n) time complexity.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head: return head
odd_head=head
even_head=head.next
cur=head
odd_tail=None
c=0
while cur:
curnext=cur.next
c+=1
if c%2==1:
#cur is odd node
cur.next=cur.next.next if cur.next else None
odd_tail=cur
else:
#cur is even node
cur.next=cur.next.next if cur.next else None
cur=curnext
if odd_tail:
odd_tail.next=even_head
return odd_head
#ANSWER
class Solution:
def oddEvenList(self, head: ListNode) -> ListNode:
if not head: return head
odd = head
even = head.next
evenhead = even
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = evenhead
return head
#MY ANSWER
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head : return head
if not head.next: return head
A = head
B = head.next
c = 0
odd = A
even = B
while head and head.next:
headnext = head.next
head.next=head.next.next
head = headnext
c+=1
if c%2==0:
odd = head
else:
even = head
odd.next = B
return A
329. Longest Increasing Path in a Matrix (Hard)
Given an m x n integers matrix, return the length of the longest increasing path in matrix.
From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).
class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
dirs = [[0,1],[1,0],[0,-1],[-1,0]]
m=len(matrix)
n=len(matrix[0])
if not matrix: return 0
cache= [[0]*n for _ in range(m)]
res=0
def dfs(i,j):
if cache[i][j]!=0: return cache[i][j]
for d in dirs:
x=i+d[0]
y=j+d[1]
if m>x>=0 and n>y>=0 and matrix[x][y]>matrix[i][j]:
cache[i][j]=max(cache[i][j],dfs(x,y))
cache[i][j]+=1
return cache[i][j]
for i in range(m):
for j in range(n):
res=max(res,dfs(i,j))
return res
#DFS+MEM
class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
m,n = len(matrix),len(matrix[0])
res = 0
@lru_cache(None)
def dfs(i,j):
res = 0
for ii,jj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
if m>ii>=0 and n>jj>=0 and matrix[i][j]<matrix[ii][jj]:
res = max(res, dfs(ii,jj))
return res+1
for i in range(m):
for j in range(n):
res = max(res, dfs(i,j))
return res
DFS+mem 太晚了直接看答案了。。。因为是strictly increasing path 所以是DAG，所以dfs（i，j） path length 是可以用mem记住的。 但通常的DFS是不能用mem的。
330. Patching Array （Hard）
Given a sorted integer array nums and an integer n, add/patch elements to the array such that any number in the range [1, n] inclusive can be formed by the sum of some elements in the array.
Return the minimum number of patches required.
class Solution:
def minPatches(self, nums: List[int], n: int) -> int:
'''Initialize the range [1, miss) = [1, 1) = empty
While n is not covered yet
if the current element nums[i] is less than or equal to miss
extends the range to [1, miss + nums[i])
increase i by 1
otherwise
patch the array with miss, extends the range to [1, miss + miss)
increase the number of patches
Return the number of patches
'''
patches=0
i=0
miss=1
while miss<=n:
if i<len(nums) and nums[i]<=miss:
#miss is covered
miss+=nums[i]
i+=1
else:
#patch miss to aray
miss+=miss
patches+=1
return patches
太晚没思路直接看答案， 答案思路：假设miss 是最小的missing number， 但我们知道【1，miss） 已经covered。 要cover miss，需要添加小于等于miss的数字。
假设我们添加的数字是x，那么区间【1，miss） 【x，x+miss）都covered。由于x小于等于miss。 所以两个区间可以合并为【1，x+miss）我们想选一个range cover最大的x，显然当x=miss时候区间最大。所以算法是：
初始化区间【1，miss）=【1，1）
当n还没covered，如果 nums【i】小于等于miss，增加区间为【1，miss+nums【i】），i++ 否则， 数组里添加miss， 增加区间为【1，miss+miss), res+=1