LeetCode 每日一题 2022/9/5-2022/9/11

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

---

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)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

---

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

---

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

---

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)]


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

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)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

---

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

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

1
2
3

---