|
记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
9/5 652. 寻找重复的子树
一个子树的结构由根节点值 左子树 右子树构成
如果两个子树三部分都相同 可以看作相同
将各个不同的子树编号 空节点为0
如果编号相同 则结构相同
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def findDuplicateSubtrees(root):
"""
:type root: TreeNode
:rtype: List[TreeNode]
"""
def dfs(node):
if not node:
return 0
tag = (node.val,dfs(node.left),dfs(node.right))
if tag in m:
tr,ind = m[tag]
rep.add(tr)
return ind
else:
global idx
idx +=1
m[tag] = (node,idx)
return idx
global idx
m = {}
rep = set()
dfs(root)
return list(rep)
9/6 828. 统计子串中的唯一字符
考虑某一位置上的X被统计到的次数
X…X…X
包含中间X的子串往前不能包含前一个X 往后不能包含后一个X
假设第一个X位置为n1 第二个X位置为n2 第三个X位置为n3
前面包含不同的字符个数为 n2-n1-1个
后面包含不同的字符个数为 n3-n2-1个
所有情况
在前面可以有n2-n1-1+1=n2-n1种选择方式
同理后面有n3-n2中选择方式
所以包含X的子串 X被统计的次数为(n2-n1)*(n3-n1)
def uniqueLetterString(s):
"""
:type s: str
:rtype: int
"""
num = len(s)
from collections import defaultdict
m = defaultdict(list)
for i,c in enumerate(s):
m[c].append(i)
ans = 0
for l in m.values():
n = len(l)
if len(l)==1:
left = l[0]+1
right = num-l[0]
ans += left*right
continue
left = l[0]+1
right = l[1]-l[0]
ans += left*right
left = l[n-1]-l[n-2]
right = num-l[n-1]
ans += left*right
for i in range(1,n-1):
left = l[i]-l[i-1]
right = l[i+1]-l[i]
ans +=left*right
return ans
9/7 1592. 重新排列单词间的空格
统计单词个数 空格个数
将空格均匀分配给各个
def reorderSpaces(text):
"""
:type text: str
:rtype: str
"""
words = []
space = 0
cur = ""
for c in text:
if c==" ":
if cur!="":
words.append(cur)
space+=1
cur = ""
else:
cur += c
if cur!="":
words.append(cur)
n = len(words)-1
if n==0:
return words[0]+" "*space
num = space//n
s = " "*num
ans = s.join(words)
ans += " "*(space%n)
return ans
9/8 667. 优美的排列 II
只需要k+1个数能够拍列出包含k个差值的组合
1,k+1,2,k…
拍完后排列即可 k+2,k+3…n
def constructArray(n, k):
"""
:type n: int
:type k: int
:rtype: List[int]
"""
l,r=1,k+1
ans = []
while l<r:
ans.append(l)
ans.append(r)
l+=1
r-=1
if l==r:
ans.append(l)
return ans+[i for i in range(k+2,n+1)]
9/9 1598. 文件夹操作日志搜集器
记录当前距离主文件夹步数
def minOperations(logs):
"""
:type logs: List[str]
:rtype: int
"""
ans = 0
for log in logs:
if log[0]!=".":
ans +=1
elif log[1]==".":
ans = max(0,ans-1)
return ans
9/10 669. 修剪二叉搜索树
递归 判断当前节点值是否在区间内
如果小于区间 那么只需判断右子树
如果大于区间 那么只需判断左子树
在区间内 则判断左右子树
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def trimBST(root, low, high):
"""
:type root: TreeNode
:type low: int
:type high: int
:rtype: TreeNode
"""
def check(node):
ret = None
if not node:
return ret
if node.val<low:
ret = check(node.right)
elif node.val>high:
ret = check(node.left)
else:
ret = node
node.left = check(node.left)
node.right = check(node.right)
return ret
return check(root)
9/11 857. 雇佣 K 名工人的最低成本
单位质量需要的成本r = w/q
k个工人中找到权重r=w/q最大的 该工人按照最低工资
其他各个工人按照r的比例 都可以大于其最低工资
则质量和totalq*r=总工资
从小到大枚举r
是否可以减小totalq
如果减小了totalq 此时r必定改变
比较此时是否能降低成本
|