记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
7/10 16. 最接近的三数之和
排序
先确定一个最小数
双指针确定之后两个数
def threeSumClosest(nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
nums.sort()
res = 10000000
for i in range(len(nums)):
if i>0 and nums[i]==nums[i-1]:
continue
l,r = i+1,len(nums)-1
while l<r:
s = nums[i]+nums[l]+nums[r]
if s==target:
return target
if abs(target-res)>abs(target-s):
res = s
if s>target:
tmpr = r-1
while l<tmpr and nums[tmpr]==nums[r]:
tmpr-=1
r=tmpr
else:
tmpl = l+1
while tmpl<r and nums[tmpl]==nums[l]:
tmpl+=1
l=tmpl
return res
7/11 1911. 最大子序列交替和
dp
dp[i][0/1] 表示第i个数坐标为偶数或奇数的最大交替和
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+nums[i])
dp[i][1]=max(dp[i-1][1],dp[i-1][0]-nums[i])
def maxAlternatingSum(nums):
"""
:type nums: List[int]
:rtype: int
"""
dp0,dp1=nums[0],0
for i in range(1,len(nums)):
dp0,dp1=max(dp0,dp1+nums[i]),max(dp1,dp0-nums[i])
return max(dp0,dp1)
7/12 2544. 交替数字和
从低位到高位
模拟两种情况
最后判断哪种情况最高位为正
def alternateDigitSum(n):
"""
:type n: int
:rtype: int
"""
s0,s1=0,0
tag = 0
while n>0:
v = n%10
n = n//10
if tag==0:
s0+=v
s1-=v
else:
s0-=v
s1+=v
tag ^=1
return s0 if tag else s1
7/13 931. 下降路径最小和
dp[i][j]记录到达位置i,j的最小路径
路径必定从上至下 所以只需要一位数组dp[j]记录当前行的状态
def minFallingPathSum(matrix):
"""
:type matrix: List[List[int]]
:rtype: int
"""
dp = matrix[0][:]
n,m = len(matrix),len(matrix[0])
print(dp)
for i in range(1,n):
tmp = dp[:]
for j in range(m):
v = float("inf")
if j>0:
v = min(v,tmp[j-1])
v = min(v,tmp[j])
if j<m-1:
v = min(v,tmp[j+1])
dp[j]=v+matrix[i][j]
return min(dp)
7/14 979. 在二叉树中分配硬币
dfs
func(node) 用来汇总node为根节点的子树下拥有的硬币数c,和节点数n
而node节点对外的分配硬币数为|c-n|
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def distributeCoins(root):
"""
:type root: TreeNode
:rtype: int
"""
global ans
ans = 0
def func(node):
global ans
if not node:
return 0,0
lc,ln = func(node.left)
rc,rn = func(node.right)
c,n=lc+rc+node.val,ln+rn+1
ans += abs(c-n)
return c,n
func(root)
return ans
7/15 18. 四数之和
排序后 从小到大判断
先确定两个数
再使用双指针确定最后两个数文章来源：https://www.toymoban.com/news/detail-573370.html
def fourSum(nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
if not nums and len(nums)<4:
return []
ans =[]
nums.sort()
n = len(nums)
for i in range(n-3):
if i>0 and nums[i]==nums[i-1]:
continue
if sum(nums[i:i+4])>target:
break
if nums[i]+sum(nums[-3:])<target:
continue
for j in range(i+1,n-2):
if j>i+1 and nums[j]==nums[j-1]:
continue
if nums[i]+sum(nums[j:j+3])>target:
break
if nums[i]+nums[j]+sum(nums[-2:])<target:
continue
l,r=j+1,n-1
while l<r:
cur = nums[i]+nums[j]+nums[l]+nums[r]
if cur==target:
ans.append([nums[i],nums[j],nums[l],nums[r]])
while l<r and nums[l]==nums[l+1]:
l+=1
l+=1
while l<r and nums[r]==nums[r-1]:
r-=1
r-=1
elif cur<target:
l+=1
else:
r-=1
return ans
7/16 834. 树中距离之和
画图可知
节点i 和相邻节点j
已知ans[i]为i到其他节点距离和
从i到j 距离和变化为
j的子树节点 距离-1 size[j]
非子树节点 距离+1 n-size[j]
size[i]用来存储子树内节点个数
dfs用来计算size 并统计到节点0的距离和ans[0]
func用来计算相邻节点距离和 出父节点外文章来源地址https://www.toymoban.com/news/detail-573370.html
def sumOfDistancesInTree(n, edges):
"""
:type n: int
:type edges: List[List[int]]
:rtype: List[int]
"""
m=[[] for _ in range(n)]
for i,j in edges:
m[i].append(j)
m[j].append(i)
ans = [0]*n
size= [1]*n
def dfs(x,pre,dep):
ans[0]+=dep
for y in m[x]:
if y!=pre:
dfs(y,x,dep+1)
size[x]+=size[y]
dfs(0,-1,0)
def func(x,pre):
for y in m[x]:
if y!=pre:
ans[y] = ans[x]+n-2*size[y]
func(y,x)
func(0,-1)
return ans
到了这里，关于LeetCode 每日一题 2023/7/10-2023/7/16的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
