leetcode 强制按钮向上刷系列 - [三角形的最大高度] - 答案
最编程
2024-10-16 15:15:05
...
我的方法
我的方法思路非常简单,我们既然要让他拼成一个三角形,且是每一行的颜色都不一样,那么第一行要么蓝色要么红色,只要确定了第一行的颜色,后面的就都确定了,我分别让红色、蓝色作为第一行,各自求出一个高度,然后我们在将两个高度进行比较后输出,就能得到最好的结果。
这个方法的时间复杂度为O(n)
class Solution:
def maxHeightOfTriangle(self, red: int, blue: int) -> int:
high1=0
high2=0
red1=red
blue1=blue
for i in range(red1+blue1):
if i%2==0:#红先放置
red1=red1-1-i
if red1>=0 and blue1>=0:
high1+=1
else:
blue1=blue1-i-1
if blue1>=0 and red1>=0:
high1+=1
for i in range(red+blue):
if i%2==0:#蓝先放置
blue=blue-i-1
if blue>=0 and red>=0:
high2+=1
else:
red=red-1-i
if red>=0 and blue>=0:
high2+=1
if high1>=high2:
return high1
else:
return high2
官方的方法一 —— 枚举高度
官方的方法一跟我的方法很像,虽然我也不知道自己用的是枚举法,但是官方说是那我就是。
思路与算法
我们可以递增地枚举三角形的高度,在第 i 行时,如果对应的颜色的剩余球数大于等于 i 个,那么就可以组成第 i 行,否则不能,三角形的最大高度为 i−1。
三角形的颜色布局有两种可能:即红蓝交替(第一行为红色)或者蓝红交替(第一行为蓝色),我们分别枚举这两种情况,并取二者高度的较大值即可。
class Solution:
def maxHeightOfTriangle(self, red: int, blue: int) -> int:
def maxHeight(x: int, y: int) -> int:
i = 1
while True:
if i % 2 == 1:
x -= i
if x < 0:
return i - 1
else:
y -= i
if y < 0:
return i - 1
i += 1
return max(maxHeight(red, blue), maxHeight(blue, red))
官方的方法二 —— 直接计算出高度
思路与算法
我们也可以使用等差数列公式直接计算出高度。
对于从第一行开始的情况,球的个数依次为 1,3,5,⋯,2k−1,其中 2k−1 是最后一行,那么总计个数为:
1+3+5+⋯+(2k−1)=[(1+(2k−1))×k]/2 =k^2
那么 k 的最大值即为 ⌊no⌋,其中no是提供给奇数行的球的数量,⌊⋅⌋ 表示向下取整。
同理,对于从第二行开始的情况,有:
2+4+6+⋯+2k=[(2+2k)×k]/2 =k^2+k
解方程可得 k 的最大值为 ⌊ [−1+ (1+4ne)^(1/2)]/2⌋,其中ne是提供给偶数行的球的数量。
因此最后一个奇数行为 2⌊no⌋−1,最后一个偶数行为 2⌊ [−1+ (1+4ne)^(1/2)]/2⌋,最终的答案即为其中的较小值加 1。
def maxHeight(x: int, y: int) -> int:
odd = 2 * int(sqrt(x)) - 1
even = 2 * int((-1 + sqrt(1 + 4 * y)) / 2)
return min(odd, even) + 1
return max(maxHeight(red, blue), maxHeight(blue, red))