为什么选php语言做网站/黑帽seo排名技术

记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步

---

9/5 652. 寻找重复的子树

一个子树的结构由根节点值 左子树 右子树构成
如果两个子树三部分都相同 可以看作相同
将各个不同的子树编号 空节点为0
如果编号相同 则结构相同

class TreeNode(object):def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef findDuplicateSubtrees(root):""":type root: TreeNode:rtype: List[TreeNode]"""def dfs(node):if not node:return 0tag = (node.val,dfs(node.left),dfs(node.right))if tag in m:tr,ind = m[tag]rep.add(tr)return indelse:global idxidx +=1m[tag] = (node,idx)return idxglobal idxm = {}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 defaultdictm = defaultdict(list)for i,c in enumerate(s):m[c].append(i)ans = 0for l in m.values():n = len(l)if len(l)==1:left = l[0]+1right = num-l[0]ans += left*rightcontinueleft = l[0]+1right = l[1]-l[0]ans += left*rightleft = l[n-1]-l[n-2]right = num-l[n-1]ans += left*rightfor i in range(1,n-1):left = l[i]-l[i-1]right = l[i+1]-l[i]ans +=left*rightreturn ans

---

9/7 1592. 重新排列单词间的空格

统计单词个数 空格个数
将空格均匀分配给各个

def reorderSpaces(text):""":type text: str:rtype: str"""words = []space = 0cur = ""for c in text:if c==" ":if cur!="":words.append(cur)space+=1cur = ""else:cur += cif cur!="":words.append(cur)n = len(words)-1if n==0:return words[0]+" "*spacenum = space//ns = " "*numans = 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+1ans = []while l<r:ans.append(l)ans.append(r)l+=1r-=1if 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 = 0for log in logs:if log[0]!=".":ans +=1elif 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 = valself.left = leftself.right = rightdef trimBST(root, low, high):""":type root: TreeNode:type low: int:type high: int:rtype: TreeNode"""def check(node):ret = Noneif not node:return retif node.val<low:ret = check(node.right)elif node.val>high:ret = check(node.left)else:ret = nodenode.left = check(node.left)node.right = check(node.right)return retreturn check(root)

---

9/11 857. 雇佣 K 名工人的最低成本

单位质量需要的成本r = w/q
k个工人中找到权重r=w/q最大的 该工人按照最低工资
其他各个工人按照r的比例 都可以大于其最低工资
则质量和totalq*r=总工资
从小到大枚举r
是否可以减小totalq
如果减小了totalq 此时r必定改变
比较此时是否能降低成本

---