LeetCode 每日一题 2022/8/22-2022/8/28

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

---

8/22 655. 输出二叉树

bfs两次
第一次 找出矩阵高度h
第二次 将值放入对应位置

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
def printTree(root):
    """
    :type root: TreeNode
    :rtype: List[List[str]]
    """
    h = 0
    l = [root]
    while l:
        tmp = []
        for node in l:
            if node.left:
                tmp.append(node.left)
            if node.right:
                tmp.append(node.right)
        l = tmp
        h+=1
    m = h
    n = 2**m-1
    ans = [[""]*n for _ in range(m)]
    l = [(root,0,(n-1)//2)]
    while l:
        tmp = []
        for node,r,c in l:
            ans[r][c] = str(node.val)
            if node.left:
                tmp.append((node.left,r+1,c-2**(m-2-r)))
            if node.right:
                tmp.append((node.right,r+1,c+2**(m-2-r)))
        l = tmp
    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

---

8/23 782. 变为棋盘

第一步 判断可行性
若需要变为棋盘 每一行或者每一列中1和0的个数差不超过1
对于某两行 i,j 行变换不会影响两行的对应位置差值
列变换同样不会影响两行所有位置差值和
例如 i:00110
j:11000
对于这两行 i,j 无论行列怎么变换必定存在某一列为两个0
所以若要变为棋盘 行的状态必定只能存在两种
并且两行内每个位置值相反
列状态也相同
第二部 计算移动次数
对于行来说 进行列移动改变状态
因为只存在两种相反状态的行
所以只需要将一行移动成功 对应的左右行也移动成功
只需考虑第一行移动成功的次数
如果每一行个数n为偶数 则有两种情况 判断成为0101…或者1010…哪一种次数少
如果n为奇数 则起始位置只能为个数多的1或者0一种情况
列的情况与行相同且互不影响
将两种情况相加即可
binvalue用来将数组l内的数组合为一个二进制数
numone用来统计二进制数内1的个数
mask0,mask1分别代表0101…,1010…两种状态结果

def movesToChessboard(board):
    """
    :type board: List[List[int]]
    :rtype: int
    """
    def binvalue(l):
        v = 0
        for i in l:
            v = (v<<1)+i
        return v
    def numone(v):
        ans = 0
        while v>0:
            if v&1==1:
                ans+=1
            v>>=1
        return ans
    
    n= len(board)
    row = sum(board[0])
    col = sum([board[i][0] for i in range(n)])
    if abs(2*row-n)>1 or abs(2*col-n)>1:
        return -1
    
    rowv = binvalue(board[0])
    colv = binvalue([board[i][0] for i in range(n)])       
    for i in range(1,n):
        tmpr = binvalue(board[i])
        if tmpr!=rowv and tmpr^rowv!=2**n-1:
            return -1
        tmpc = binvalue([board[j][i] for j in range(n)])
        if tmpc!=colv and tmpc^colv!=2**n-1:
            return -1
        
    mask0,mask1 = 0,0
    for i in range(n):
        mask0 = (mask0<<1)+(i%2)
        mask1 = (mask1<<1)+((i+1)%2)    
    total = 0
    if n%2==0:
        total += min(numone(rowv^mask0),numone(rowv^mask1))
        total += min(numone(colv^mask0),numone(colv^mask1))
    else:
        if row*2>n:
            total += numone(rowv^mask1)
        else:
            total += numone(rowv^mask0)
        if col*2>n:
            total += numone(colv^mask1)
        else:
            total += numone(colv^mask0)
    return total//2


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

---

8/24 1460. 通过翻转子数组使两个数组相等

只要两个数组内包含的数字相同 就可以满足
第一次反转可以使第1位相同 第二次翻转可以使第2位相同
以此类推 最多进行n次可以使所有n个位置都相同
排序后比较两个数组是否相同即可

def canBeEqual(target, arr):
    """
    :type target: List[int]
    :type arr: List[int]
    :rtype: bool
    """
    target.sort()
    arr.sort()
    return target==arr


1
2
3
4
5
6
7
8
9
10
11

---

8/25 658. 找到 K 个最接近的元素

二分在arr中找到第一个大于等于x的位置 i
双指针
向左从i-1开始[0~i-1]小于x
向右从i开始[i,n]大于等于x
比较两个方向哪个更接近x
存入队列中 直至取到k个

def findClosestElements(arr, k, x):
    """
    :type arr: List[int]
    :type k: int
    :type x: int
    :rtype: List[int]
    """
    ans = []
    n = len(arr)
    l,r = 0,n-1
    while l<=r:
        mid = (l+r)//2
        if arr[mid]<x:
            l = mid+1
        else:
            r= mid-1
    l,r=r,l
    print(l,arr[l],r,arr[r])
    while k>0:
        print(k,ans)
        if l==-1:
            ans.append(arr[r])
            r+=1
        elif r==n:
            ans = [arr[l]]+ans
            l-=1
        elif arr[r]-x<x-arr[l]:
            ans.append(arr[r])
            r+=1
        else:
            ans = [arr[l]]+ans
            l-=1
        k-=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
33
34
35
36

---

8/26 1464. 数组中两元素的最大乘积

排序 最大两数乘积

def maxProduct(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    nums.sort()
    return (nums[-1]-1)*(nums[-2]-1)


1
2
3
4
5
6
7
8
9

---

8/27 662. 二叉树最大宽度

从1开始给节点编号
BFS找到n层 最小编号v0 最大编号v1
则这一层为v1-v0+1

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
def widthOfBinaryTree(root):
    """
    :type root: TreeNode
    :rtype: int
    """
    ans = 1
    cur = 0
    l = [(root,1)]
    while l:
        tmp = []
        for node,v in l:
            if node.left:
                tmp.append((node.left,v*2))
            if node.right:
                tmp.append((node.right,v*2+1))
        first,v0 = l[0]
        last,v1 = l[-1]
        cur = v1-v0+1
        ans = max(ans,cur)
        l = tmp
    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

---

8/28 793. 阶乘函数后 K 个零

遇到5的倍数会产生0
如果有必定持续5个 第六个时必定又会有5的倍数
f(x) = x/5+x/25+x/125…x/(5**11)
产生k个0 最多为5*k
二分找到产生k的数
与产生k+1个的数差值是否存在即可

def preimageSizeFZF(k):
    """
    :type k: int
    :rtype: int
    """
    def check(x):
        ans = 0
        while x>0:
            ans += x//5
            x = x//5
        return ans
    def find(k):
        l,r=k,5*k
        while l<r:
            mid = (l+r)>>1
            if k<=check(mid):
                r = mid
            else:
                l = mid+1
        return l
    return find(k+1)-find(k)



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

---