【每日一题20220908】找出可能的矩形个数

兴趣爱好交流 每日一题
1

:woman_mage: 一个矩形可以分割成一个 1x1 正方形的网格，其数量等于矩形两个维度的乘积。根据矩形的大小，1x1 正方形的网格也可以分成更大的正方形，例如 3x2 矩形总共有 8 个正方形，因为有 6 个不同的 1x1 正方形和两个可能的 2x2 正方形。一个 4x3 的矩形包含 20 个正方形。

你的任务是编写一个函数find_squares，它返回任何给定矩形的正方形总数，其尺寸以两个整数的形式给出，第一个总是等于或大于第二个。

3x2 矩形的图示：

image 1 * 1 的小方块 6个

image
image 2 * 2 的方块 有两个

题目难度：较易
题目来源：https://www.codewars.com/kata/5a62da60d39ec5d947000093

def find_squares(x: int, y: int) -> int:
    # your code here

assert find_squares(3, 2) ==  8
assert find_squares(4, 3) == 20
assert find_squares(11, 4) == 100
assert find_squares(100, 52) == 114374
2 
def find_squares(x: int, y: int) -> int:
    number=0
    for i in range(x-1):
        if y-i>=1:
            number += (x - i) * (y - i)

    return number
find_squares(11, 4)
assert find_squares(3, 2) == 8
assert find_squares(4, 3) == 20
assert find_squares(11, 4) == 100
assert find_squares(100, 52) == 114374
3 
def func(x,y):
    return (x-1)*(y-1)

def find_squares(x: int, y: int) -> int:
    n = x * y
    while y>0:
        c=func(x,y)
        x-=1
        y-=1
        n=n+c
    return n
4

使用递归

def find_squares(x: int, y: int) -> int:
    """
    找出可能的矩形个数
    :param x: 高
    :param y: 宽
    :return: 矩形个数
    """
    if y == 1:
        return x * y
    else:
        return x * y + find_squares(x-1, y-1)


assert find_squares(3, 2) == 8
assert find_squares(4, 3) == 20
assert find_squares(11, 4) == 100
assert find_squares(100, 52) == 114374
5 
def findSquares(x,y):
    return sum((x-i+1)*(y-i+1) for i in range(1,y+1))
6 
def find_squares(x: int, y: int) -> int:
    res=0
    for j in range(1,y+1):
        w=y-j+1
        h=x-j+1
        s=w*h
        res+=s
    return res

assert find_squares(3, 2) ==  8
assert find_squares(4, 3) == 20
assert find_squares(11, 4) == 100
assert find_squares(100, 52) == 114374