LeetCode 每日一题 2024/3/11-2024/3/17
记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
目录
- 3/11 2129. 将标题首字母大写
- 3/12 1261. 在受污染的二叉树中查找元素
- 3/13 2864. 最大二进制奇数
- 3/14 2789. 合并后数组中的最大元素
- 3/15 2312. 卖木头块
- 3/16 2684. 矩阵中移动的最大次数
- 3/17 310. 最小高度树
3/11 2129. 将标题首字母大写
从头按规则依次判断
curLen记录当前字母个数
如果遇到空格时少于等于两个则特殊处理
start记录下一个字母是否是首字母
def capitalizeTitle(title):
"""
:type title: str
:rtype: str
"""
start = True
curLen = 0
ans = []
for c in title:
if c!=" ":
if start:
ans.append(c.upper())
else:
ans.append(c.lower())
curLen+=1
start = False
else:
start = True
if curLen<=2:
for i in range(curLen):
ans[-1-i] = ans[-1-i].lower()
curLen=0
ans.append(" ")
if curLen<=2:
for i in range(curLen):
ans[-1-i] = ans[-1-i].lower()
return ''.join(ans)
3/12 1261. 在受污染的二叉树中查找元素
根据树结构还原
并且存储出现过的数值
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class FindElements(object):
def __init__(self, root):
"""
:type root: TreeNode
"""
self.m = {}
root.val = 0
self.root = root
l = [root]
while l:
tmp = []
for node in l:
v = node.val
self.m[v]=1
if node.left:
node.left.val = v*2+1
tmp.append(node.left)
if node.right:
node.right.val = v*2+2
tmp.append(node.right)
l=tmp[:]
def find(self, target):
"""
:type target: int
:rtype: bool
"""
return target in self.m
3/13 2864. 最大二进制奇数
二进制奇数说明最低位必定为1
统计字符串中1的个数 最低位为1 剩余从高到低往下排
def maximumOddBinaryNumber(s):
"""
:type s: str
:rtype: str
"""
n=len(s)
m = s.count("1")
return "1"*(m-1)+"0"*(n-m)+"1"
3/14 2789. 合并后数组中的最大元素
从后往前将元素依次放入一个单调递增的栈
如果当前元素小于等于栈顶元素 说明可以合并
def maxArrayValue(nums):
"""
:type nums: List[int]
:rtype: int
"""
l = []
for num in nums[::-1]:
if not l or l[-1]<num:
l.append(num)
else:
l[-1]+=num
return max(l)
3/15 2312. 卖木头块
dp
使用dp[i][j]来存储i*j能够得到的值
按竖着横着切开
def sellingWood(m, n, prices):
"""
:type m: int
:type n: int
:type prices: List[List[int]]
:rtype: int
"""
dp = [[0]*(n+1) for _ in range(m+1)]
for x,y,v in prices:
dp[x][y]=v
for i in range(1,m+1):
for j in range(1,n+1):
for k in range(1,j//2+1):
dp[i][j] = max(dp[i][j],dp[i][k]+dp[i][j-k])
for k in range(1,i//2+1):
dp[i][j] = max(dp[i][j],dp[k][j]+dp[i-k][j])
return dp[m][n]
3/16 2684. 矩阵中移动的最大次数
每一步必定往右挪动
dfs 从第一列往后走
def maxMoves(grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
n,m=len(grid),len(grid[0])
mem = {}
def dfs(i,j):
if (i,j) in mem:
return mem[(i,j)]
v = 0
if j+1<m:
if grid[i][j+1]>grid[i][j]:
v = max(v,1+dfs(i,j+1))
if i-1>=0 and grid[i-1][j+1]>grid[i][j]:
v = max(v,1+dfs(i-1,j+1))
if i+1<n and grid[i+1][j+1]>grid[i][j]:
v = max(v,1+dfs(i+1,j+1))
mem[(i,j)] = v
return v
ans = 0
for i in range(n):
ans = max(ans,dfs(i,0))
return ans
3/17 310. 最小高度树
无向图内 MHT的根节点必定是在中间 不会是叶节点
所以将叶节点按层 一层一层去除后 留下来的必定是到所有叶节点高度最小的点 这样的点可能有两个
res记录还会存在的节点
所以可以先建立每个节点的出入度degree 如果为1 说明改点在图中属于叶节点 将会被去除 从res中取出 加入到去除列表
同时建立节点之间的连接关系图 graph记录每个节点与多少个其它节点连接
当res的个数大于2时说明还需要继续去除叶节点
获取当前层数的叶节点个数l
从去除列表中取出节点
遍历该节点连接的其他节点 并将这些节点的degree-1 若此时degree变为1了 说明这个节点变成了叶节点 同样加入到去除列表
直至res中的个数小于等于2时 留下的便是MHT的根节点
def findMinHeightTrees(n, edges):
"""
:type n: int
:type edges: List[List[int]]
:rtype: List[int]
"""
res = set([x for x in range(n)])
if n <=2:
return list(res)
degree = [0] * n
graph = [[] for x in range(n)]
for [x,y] in edges:
graph[x].append(y)
graph[y].append(x)
degree[x]+=1
degree[y]+=1
removelist = []
for i in range(n):
if degree[i]==1:
removelist.append(i)
res.remove(i)
while len(res)>2:
l = len(removelist)
for _ in range(l):
i = removelist.pop(0)
for x in (graph[i]):
degree[x] -= 1
if degree[x]==1:
removelist.append(x)
res.remove(x)
return list(res)