LeetCode 每日一题 2022/7/25-2022/7/31

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

---

7/25 919. 完全二叉树插入器

将节点放入队列中
从位置0算起 第i个位置节点的子节点位置为(i+1)*2-1 (i+1)*2
位置i的父节点为(i-1)//2 如果i为偶数为右子节点 i为奇数为左子节点

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class CBTInserter(object):

    def __init__(self, root):
        """
        :type root: TreeNode
        """
        self.root = root
        self.li = []
        l = [root]
        while l:
            tmp = []
            for node in l:
                if node.left:
                    tmp.append(node.left)
                if node.right:
                    tmp.append(node.right)
                self.li.append(node)
            l = tmp[:]
        
        


    def insert(self, val):
        """
        :type val: int
        :rtype: int
        """
        node = TreeNode(val)
        loc = len(self.li)+1
        preloc = (loc-1)//2
        pre = self.li[preloc]
        if loc%2==1:
            pre.left = node
        else:
            pre.right = node
        self.li.append(node)
        return pre.val
        
        


    def get_root(self):
        """
        :rtype: TreeNode
        """
        return self.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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

---

7/26 1206. 设计跳表

参考 https://leetcode.cn/problems/design-skiplist/solution/she-ji-tiao-biao-by-leetcode-solution-e8yh/
将每个数字看作一个节点 节点最多有MAX_LEVAL层
如果对于某一层 该节点存在 则该位置指向下一个存在的节点
random_level 随机决定该节点层数

import random
MAX_LEVAL = 32
PRO = 0.25
def random_level():
    lv = 1
    while lv<MAX_LEVAL and random.random()<PRO:
        lv+=1
    return lv

class Node:
    __slots__ = ['val','forward']
    def __init__(self,val,maxlev=MAX_LEVAL):
        self.val = val
        self.forward = [None]*maxlev
        
class Skiplist(object):

    def __init__(self):
        self.head = Node(-1)
        self.level = 0


    def search(self, target):
        """
        :type target: int
        :rtype: bool
        """
        cur = self.head
        for i in range(self.level-1,-1,-1):
            while cur.forward[i] and cur.forward[i].val<target:
                cur = cur.forward[i]
        cur = cur.forward[0]
        if cur and cur.val==target:
            return True
        return False


    def add(self, num):
        """
        :type num: int
        :rtype: None
        """
        new = [self.head]*MAX_LEVAL
        cur = self.head
        for i in range(self.level-1,-1,-1):
            while cur.forward[i] and cur.forward[i].val<num:
                cur = cur.forward[i]
            new[i] = cur
        lv = random_level()
        self.level = max(self.level,lv)
        newnode = Node(num,lv)
        for i in range(lv):
            newnode.forward[i] = new[i].forward[i]
            new[i].forward[i] = newnode
            


    def erase(self, num):
        """
        :type num: int
        :rtype: bool
        """
        new = [self.head]*MAX_LEVAL
        cur = self.head
        for i in range(self.level-1,-1,-1):
            while cur.forward[i] and cur.forward[i].val<num:
                cur = cur.forward[i]
            new[i] = cur
        cur = cur.forward[0]
        if not cur or cur.val!=num:
            return False
        for i in range(self.level):
            if new[i].forward[i]!=cur:
                break
            new[i].forward[i] = cur.forward[i]
        while self.level>1 and not self.head.forward[self.level-1]:
            self.level-=1
        return True


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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

---

7/27 592. 分数加减运算

分别提取出分子和分母
将不同的分母求乘积total 同时变化分子
将分子求和 并将和的结果与分母乘积辗转相除求最大公因数化简

def fractionAddition(expression):
    """
    :type expression: str
    :rtype: str
    """
    fenzi = []
    fenmu = []
    cur = ""
    s = set()
    for c in expression:
        if c in ["+","-"]:
            if cur!="":
                fenmu.append(int(cur))
                s.add(int(cur))
            cur = c
        elif c =="/":
            fenzi.append(int(cur))
            cur = ""
        else:
            cur+=c
    fenmu.append(int(cur))
    s.add(int(cur))
    total = 1
    for v in s:
        total *= v
    for i in range(len(fenmu)):
        fenzi[i] *= total//fenmu[i]
    num = sum(fenzi)
    ans =""
    if num<0:
        ans = "-"
        num = -num
    if num==0:
        return "0/1"
    
    x,y = total,num
    while x%y>0:
        x,y = y,x%y  
    total //=y
    num //=y
    ans += str(num)+"/"+str(total)
    
    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
33
34
35
36
37
38
39
40
41
42
43
44
45

---

7/28 1331. 数组序号转换

def arrayRankTransform(arr):
    """
    :type arr: List[int]
    :rtype: List[int]
    """
    l = sorted(arr)
    m = {}
    num = 1
    print(l)
    for i,v in enumerate(l):
        if i>0 and l[i-1]<v:
            num +=1
        m[v] = num
    ans = [0]*len(arr)
    for i,v in enumerate(arr):
        ans[i] = m[v]
    return ans


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

---

7/29 593. 有效的正方形

考虑点重叠情况
dis计算a,b点之间的线的平方
任选三个点 得到三条边
构成等边直角三角形
需要存在两条边相等=bian 两条边平方等于另一条边平方
如果存在可以确定直角顶点ding 和斜边两个点
第四个点与斜边两点连接的两条边长度 也需要等于bian
同时与顶点连接长度等于斜边

def validSquare(p1, p2, p3, p4):
    """
    :type p1: List[int]
    :type p2: List[int]
    :type p3: List[int]
    :type p4: List[int]
    :rtype: bool
    """
    if p1==p2 or p3==p4:
        return False
    def dis(a,b):
        return (a[0]-b[0])**2+(a[1]-b[1])**2
    
    points = []
    ding = []
    a = dis(p1,p2)
    b = dis(p2,p3)
    c = dis(p3,p1)
    bian = 0
    if a==b and a+b==c:
        bian = a
        points = [p1,p3]
        ding = p2
    elif a==c and a+c==b:
        bian = a
        points = [p2,p3]
        ding = p1
    elif b==c and b+c==a:
        bian = b
        points = [p1,p2]
        ding = p3
    else:
        return False
        
    if dis(p4,ding)!=2*bian:
        return False
    
    for p in points:
        l = dis(p4,p)
        if l!=bian:
            return False
    return True
        


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
33
34
35
36
37
38
39
40
41
42
43
44
45

---

7/30 952. 按公因数计算最大组件大小

并查集 将num和其因数归为一组
遍历nums的每个num
找到num所有质因数
将其与其质因数划分为一组

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.rank[x] > self.rank[y]:
            self.parent[y] = x
        elif self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            self.rank[x] += 1

def largestComponentSize(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    from collections import Counter
    n = max(nums)+1
    uf = UnionFind(n)

    for num in nums:
        tmp = num
        i = 2
        while i*i<=tmp:
            if tmp%i==0:
                while tmp%i==0:
                    tmp //=i
                uf.union(num,i)
            i+=1
        if tmp>1:
            uf.union(num,tmp)
    return max(Counter(uf.find(x) for x in nums).values())


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
33
34
35
36
37
38
39
40
41
42
43
44
45

---

7/31 1161. 最大层内元素和

BFS 按层遍历

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
def maxLevelSum(root):
    """
    :type root: TreeNode
    :rtype: int
    """
    lel = 1
    maxv = float("-inf")
    l = [root]
    ans = 0
    while l:
        tmp = []
        total = 0
        for node in l:
            total += node.val
            if node.left:
                tmp.append(node.left)
            if node.right:
                tmp.append(node.right)
        if maxv<total:
            ans = lel
            maxv = total
        l = tmp
        lel+=1
    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

---