LeetCode Daily Question 2022/7/25-2022/7/31

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

---

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

将节点放入队列中
从位置0算起 第iThe child node position of a position node is (i+1)*2-1 (i+1)*2
位置i的父节点为(i-1)//2 如果iis an even number for the right child node iThe odd number is the left child node

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

---

7/26 1206. 设计跳表

参考 https://leetcode.cn/problems/design-skiplist/solution/she-ji-tiao-biao-by-leetcode-solution-e8yh/
Think of each number as a node 节点最多有MAX_LEVAL层
如果对于某一层 该节点存在 then the position points to the next existing node
random_level The number of layers of this node is randomly determined

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

---

7/27 592. 分数加减运算

Extract the numerator and denominator, respectively
Multiply the different denominatorstotal Simultaneously change the molecule
Sum the molecules And divide the result of the sum with the product of the denominator to find the greatest common factor for simplification

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

---

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

---

7/29 593. 有效的正方形

Consider the point overlap case
dis计算a,bThe square of the line between the points
Choose three points get three sides
Form an equilateral right triangle
There needs to be two sides that are equal=bian The square of two sides is equal to the square of the other side
Right-angle vertices can be determined if they existding and two points on the hypotenuse
The length of the two sides connecting the fourth point to the two points of the hypotenuse Also needs to be equal tobian
At the same time, the length of the connection with the vertex is equal to the hypotenuse

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
        

---

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

并查集 将numand its factors are grouped together
遍历nums的每个num
找到num所有质因数
Divide it into a group with its prime factors

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

---

7/31

---