LeetCode 每日一题 2022/8/29-2022/9/4
记录了初步解题思路 以及本地实现代码;并不一定为最优 也希望大家能一起探讨 一起进步
目录
- 8/29 1470. 重新排列数组
- 8/30 998. 最大二叉树 II
- 8/31 946. 验证栈序列
- 9/1 1475. 商品折扣后的最终价格
- 9/2 687. 最长同值路径
- 9/3 646. 最长数对链
- 9/4
8/29 1470. 重新排列数组
重新排序 x0,xn,x1,xn+1 …
def shuffle(nums, n):
"""
:type nums: List[int]
:type n: int
:rtype: List[int]
"""
ans = [0]*(2*n)
for i in range(n):
ans[i*2] = nums[i]
ans[i*2+1] = nums[i+n]
return ans
8/30 998. 最大二叉树 II
当前节点小于val 则val为根节点当前为左子节点
当前节点大于val 则val递归入当前节点右子树中
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def insertIntoMaxTree(root, val):
"""
:type root: TreeNode
:type val: int
:rtype: TreeNode
"""
pre,cur = None,root
while cur:
if val > cur.val:
node = TreeNode(val,cur,None)
if not pre:
return node
pre.right = node
return root
else:
pre = cur
cur = cur.right
pre.right = TreeNode(val)
return root
8/31 946. 验证栈序列
将当前push入栈
判断栈顶元素是否与pop相同
如果相同则考虑下一个
如果不同则继续push
def validateStackSequences(pushed, popped):
"""
:type pushed: List[int]
:type popped: List[int]
:rtype: bool
"""
l = []
n = len(pushed)
loc = 0
for p in popped:
if l and l[-1]==p:
l.pop()
continue
tag = False
while loc<n:
if pushed[loc]==p:
loc+=1
tag = True
break
l.append(pushed[loc])
loc+=1
if not tag:
return False
return True
9/1 1475. 商品折扣后的最终价格
从后往前考虑
stack 保存非递减序列
当前价格可以在stack中找到第一个小于等于它的数
def finalPrices(prices):
"""
:type prices: List[int]
:rtype: List[int]
"""
stack = []
n = len(prices)
for i,v in enumerate(prices[::-1]):
diff = 0
while stack:
if stack[-1]>v:
stack.pop()
else:
diff = stack[-1]
break
stack.append(v)
prices[n-1-i] = v-diff
return prices
9/2 687. 最长同值路径
check用来判断当前节点能够返回给父节点最多的节点数
分别考虑左右子树
l,r为左右子树能够提供给当前节点的节点数
如果子节点与当前节点相同 则提供的节点数可用curl=l curr=r
更新路径为左右两边节点和 curl+curr
能够提供给父节点的只能是一侧加上自己 max(curl,curr)+1
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def longestUnivaluePath(root):
"""
:type root: TreeNode
:rtype: int
"""
global ans
ans = 0
def check(node):
if not node:
return 0
global ans
l,r = 0,0
curl,curr = 0,0
if node.left:
l = check(node.left)
if node.val==node.left.val:
curl = l
if node.right:
r = check(node.right)
if node.val==node.right.val:
curr = r
ans = max(ans,curl+curr)
return max(curl,curr)+1
check(root)
return ans
9/3 646. 最长数对链
记录每一个出现的第一个数字后能够有的最小数
check检验第二个数为num后最多能接几个数对
def findLongestChain(pairs):
"""
:type pairs: List[List[int]]
:rtype: int
"""
m = {}
l = []
for a,b in pairs:
if a not in m:
l.append(a)
m[a] = b
elif m[a]>b:
m[a] = b
l.sort()
mem = {}
def check(num):
ans = 1
if num in mem:
return mem[num]
for s in l:
if s>num:
ans = max(ans,check(m[s])+1)
mem[num] = ans
return ans
ans = 0
for s in l:
ans = max(ans,check(m[s]))
return ans
9/4