记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
目录
7/14 1290. 二进制链表转整数
遍历每个点
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def getDecimalValue(head):
"""
:type head: Optional[ListNode]
:rtype: int
"""
cur=head
ans=0
while cur:
ans = ans*2+cur.val
cur=cur.next
return ans
7/15 3136. 有效单词
依次判断各个条件
def isValid(word):
"""
:type word: str
:rtype: bool
"""
if len(word)<3:
return False
hasy,hasf=False,False
for c in word:
if c.isalpha():
if c.lower() in 'aeiou':
hasy=True
else:
hasf=True
elif not c.isdigit():
return False
return hasy and hasf
7/16 3201. 找出有效子序列的最大长度 I
有效子序列满足间隔一个的数字奇偶性相同
一共四种情况 全奇 全偶 奇偶 偶奇 依次考虑
def maximumLength(nums):
"""
:type nums: List[int]
:rtype: int
"""
ans=0
for p in [[0,0],[1,1],[1,0],[0,1]]:
cnt=0
for num in nums:
if num%2==p[cnt%2]:
cnt+=1
ans=max(ans,cnt)
return ans
7/17 3202. 找出有效子序列的最大长度 II
有效子序列偶数项或奇数项 模k同余
枚举两数相加和的模为m
f[x]表示当前最后一项为x的子序列最长长度
def maximumLength(nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
ans=0
for m in range(k):
f=[0]*k
for x in nums:
x%=k
f[x]=f[m-x]+1
ans=max(ans,max(f))
return ans
7/18 2163. 删除元素后和的最小差值
计算前缀最小和premin[i] 以及后缀最大和sufmax[i]
答案为premin[i]-sufmax[i+1]
后缀最大和 用最小堆维护最大和
前缀最小和同理
def minimumDifference(nums):
"""
:type nums: List[int]
:rtype: int
"""
import heapq
m=len(nums)
n=m//3
minh=nums[-n:]
heapq.heapify(minh)
sufmax=[0]*(m-n+1)
sufmax[-1]=sum(minh)
for i in range(m-n-1,n-1,-1):
sufmax[i]=sufmax[i+1]+nums[i]-heapq.heappushpop(minh, nums[i])
maxh=[-x for x in nums[:n]]
heapq.heapify(maxh)
premin=-sum(maxh)
ans=premin-sufmax[n]
for i in range(n,m-n):
premin+=nums[i]+heapq.heappushpop(maxh,-nums[i])
ans=min(ans,premin-sufmax[i+1])
return ans
7/19 1233. 删除子文件夹
先将folder内排序
字典树
考虑每一个文件路径 end作为结束标签
如果当前路径已经遇到了一个end说明当前路径为子文件夹 无需继续
def removeSubfolders(folder):
"""
:type folder: List[str]
:rtype: List[str]
"""
folder.sort()
m = {}
for s in folder:
l = s[1:].split("/")
cur = m
end = True
for cd in l:
if cd in cur:
if "end" in cur[cd]:
end = False
break
else:
cur = cur[cd]
else:
cur[cd]={}
cur = cur[cd]
if end:
cur["end"]=1
global ans
ans = []
def func(node,l):
global ans
for k,v in node.items():
if k=="end":
ans.append("/"+"/".join(l))
continue
else:
func(v,l+[k])
func(m,[])
return ans
7/20 1948. 删除系统中的重复文件夹
使用construct将路劲序列化 freq[x]记录序列x出现的次数
operate将只出现一次的序列加入到答案中
class Trie:
def __init__(self):
self.serial = ""
self.children = dict()
def deleteDuplicateFolder(paths):
"""
:type paths: List[List[str]]
:rtype: List[List[str]]
"""
from collections import Counter
root=Trie()
for p in paths:
cur=root
for node in p:
if node not in cur.children:
cur.children[node]=Trie()
cur=cur.children[node]
freq=Counter()
def construct(node):
if not node.children:
return
v=list()
for f,c in node.children.items():
construct(c)
v.append(f+"("+c.serial+")")
v.sort()
node.serial="".join(v)
freq[node.serial]+=1
construct(root)
ans=list()
path=list()
def operate(node):
if freq[node.serial]>1:
return
if path:
ans.append(path[:])
for f,c in node.children.items():
path.append(f)
operate(c)
path.pop()
operate(root)
return ans