(leetcode) 三日三题

 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

# 速度有点拉跨
def imageSmoother(self, img):
    import numpy as np
    import copy
    # 利用pad填充原矩阵，并且防止原矩阵有0，故填充-1
    padList = np.pad(img, ((1, 1), (1, 1)), 'constant', constant_values=-1)  
    # 不用深拷贝会报错
    # https://leetcode-cn.com/problems/image-smoother/comments/1461270
    newImg = copy.deepcopy(img) 
    # 获取img的行列
    m, n = len(img), len(img[0])
    for i in range(m):
        for j in range(n):
            # 深拷贝，防止后续修改padList
            zeroList = copy.deepcopy(padList[i: i + 3, j:j + 3])
            # 计算9个元素中哪些元素是原数组，即非 -1 就是原元素
            count = 9 - np.sum(zeroList == -1)
            # 遮罩层，重新置为0方便sum求和
            # 或者得到-1的个数重新加回去，减小内存开销
            mask = (zeroList == -1)
            zeroList[mask] = 0
            # 计算值
            newImg[i][j] = np.sum(zeroList) // count
            return newImg
# 修改版
def imageSmoother(self, img):
    import numpy as np
    padList = np.pad(img, ((1, 1), (1, 1)), 'constant', constant_values=-1)
    newImg = img
    m, n = len(img), len(img[0])
    for i in range(m):
        for j in range(n):
            zeroList = padList[i: i + 3, j:j + 3]
            count = np.sum(zeroList > -1)
            mask = (zeroList > -1)
            newImg[i][j] = np.sum(zeroList[mask])//count
    return newImg

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

m, n = len(img), len(img[0])
newImg = [[0] * n for _ in range(m)]
for idx in range(m * n):
    # 除以n非m
    cur_r = idx // n  # r行
    cur_c = idx % n  # c列
    x1, y1 = cur_r, cur_c
    x2, y2 = cur_r, cur_c
    sum1 = 0
    if cur_r - 1 >= 0:  # 上限 (-1, 0)    往上走不行
        x1 = cur_r - 1
    if cur_r + 1 < m:  # 下限 (m+1, 0)   往下走不行
        x2 = cur_r + 1
    if cur_c - 1 >= 0:  # 左限 (0, -1)    往左走不行
        y1 = cur_c - 1
    if cur_c + 1 < n:  # 右限 (0, n+1)   往右走不行
        y2 = cur_c + 1
    for i in range(x1, x2 + 1):
        for j in range(y1, y2 + 1):
            sum1 += img[i][j]
    count = (y2 - y1 + 1) * (x2 - x1 + 1)
    print(sum1)
    newImg[cur_r][cur_c] = sum1 // count
return newImg

 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

# list版 占13.9mb
def imageSmoother(self, img):
    res = []
    l1, l2 = len(img), len(img[0])
    expand = np.pad(img, ((1, 1), (1, 1)), 'constant', constant_values=-1)
    expand = expand.tolist()
    res = [[0] * l2 for _ in range(l1)]
    for i in range(l1):
        for j in range(l2):
            nine = [expand[i][j], expand[i][j + 1], expand[i][j + 2], expand[i + 1][j], expand[i + 1][j + 1],
                    expand[i + 1][j + 2], expand[i + 2][j], expand[i + 2][j + 1], expand[i + 2][j + 2]]
            num = nine.count(-1)
            res[i][j] = (sum(nine) + num) // (9 - num)
    return res
# numpy版 占25.3mb
def imageSmoother(self, img):
    import numpy as np
    l1, l2 = len(img), len(img[0])
    expand = np.pad(img, ((1, 1), (1, 1)), 'constant', constant_values=-1)
    expand = expand.tolist()
    res = [[0] * l2 for _ in range(l1)]
    for i in range(l1):
        for j in range(l2):
            nine = [expand[i][j], expand[i][j + 1], expand[i][j + 2], expand[i + 1][j], expand[i + 1][j + 1],
                    expand[i + 1][j + 2], expand[i + 2][j], expand[i + 2][j + 1], expand[i + 2][j + 2]]
            num = nine.count(-1)
            res[i][j] = (sum(nine) + num) // (9 - num)
    return res

1
2
3
4
5

img = [1,2,3] 
copyImg = img
copyImg[0] = 2 # 则img也同步修改
# 新建一个m*n列表
newImg = [[0] * n for _ in range(m)]

 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

"""
4 6 6 4
6 9 9 6 
6 9 9 6 
4 6 6 4
考虑46的情况可知x1y1,x2y2的坐标
"""
def tryImageAgain(img):
    m = len(img)
    n = len(img[0])
    ans = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            x1, x2 = i, i
            y1, y2 = j, j
            # 计算满足条件的x1y1x2y2的值
            # 如果计算违反条件的值，需要考虑的变量多
            # 如i-1<0时，表明当前在第一行，如果是[0][0]需要修改x2y2，如果是[0][1]需要修改x1y1x2y2，
            # 如果在左上角，则x1y1不用变，考虑后两个if
            if i-1 >= 0: x1 = i-1  # 如果[i][j]在第一行之后行，则左上标为[i-1][j]
            if j-1 >= 0: y1 = j-1  # 如果[i][j]在第一列之后列，则左上标为[i][j-1] 在第二行第二列则[i-1][j-1]
            # 如果在右下角，则x2y2不用变，考虑前两个if
            if i+1 < m: x2 = i+1  # 如果[i][j]在第m行之前行，则右下标为[i+1][j]
            if j+1 < n: y2 = j+1  # 如果[i][j]在第n列之前列，则右下标为[i][j+1]
            # 妙啊
            s = 0
            for x in range(x1, x2+1):
                s += sum(img[x][y1:y2+1])
            div = (y2-y1+1)*(x2-x1+1)
            ans[i][j] = s // div
    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

def trailingZeroes(n):
    count = 0
    p = 5  # 用p代替5，即可以推广到n!中p因子的个数
    while n:
        # p += n/5  # 直观解法
        # n/=5  # 使其维持n/p的格式，求n!中只含一个p的个数
                # 否则需要计算n/p+n/2*p+n/3*p...
        n //= p 
        count += n  
    return count

# 递归解法，来自力扣宫水三叶
def trailingZeroes(self, n: int) -> int:
    return n // 5 + self.trailingZeroes(n // 5) if n else 0

# 官解朴素版
# n!中质因子 5 的个数等于 [1,n] 的每个数的质因子 5 的个数之和，
# 我们可以通过遍历 [1,n] 的所有 5 的倍数求出。
def trailingZeroes(self, n: int) -> int:
    ans = 0
    for i in range(5, n + 1, 5):
        while i % 5 == 0:
            i //= 5
            ans += 1
    return ans

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

def calPoints(ops):
    i = 0
    while 1:
        if ops[i] == 'C':
            del ops[i-1:i+1]
            i -= 2
        elif ops[i] == 'D':
            ops[i] = int(ops[i-1]) * 2
        elif ops[i] == '+':
            ops[i] = int(ops[i - 1]) + int(ops[i - 2])
        else:
            ops[i] = int(ops[i])
        i += 1
        if i >= len(ops):
            break
    return sum(ops)