wordpress同步豆瓣,优化方案英语必修三,新手电商如何入门,建筑工人找活平台【LetMeFly】3200.三角形的最大高度#xff1a;枚举
力扣题目链接#xff1a;https://leetcode.cn/problems/maximum-height-of-a-triangle/
给你两个整数 red 和 blue#xff0c;分别表示红色球和蓝色球的数量。你需要使用这些球来组成一个三角形#xff0c;满足第 1 行…【LetMeFly】3200.三角形的最大高度枚举
力扣题目链接https://leetcode.cn/problems/maximum-height-of-a-triangle/
给你两个整数 red 和 blue分别表示红色球和蓝色球的数量。你需要使用这些球来组成一个三角形满足第 1 行有 1 个球第 2 行有 2 个球第 3 行有 3 个球依此类推。
每一行的球必须是 相同 颜色且相邻行的颜色必须 不同。
返回可以实现的三角形的 最大 高度。 示例 1 输入 red 2, blue 4 输出 3
解释 上图显示了唯一可能的排列方式。
示例 2 输入 red 2, blue 1 输出 2
解释 上图显示了唯一可能的排列方式。
示例 3 输入 red 1, blue 1 输出 1
示例 4 输入 red 10, blue 1 输出 2
解释 上图显示了唯一可能的排列方式。 提示
1 red, blue 100
解题方法枚举
使用一个大小为2的数组记录layer层所需两种颜色分别多少个。
使用layer从1层开始模拟每次两种颜色分别加上layer。如果球数不足则停止枚举layer。
时间复杂度 O ( min ( r e d , b l u d ) ) O(\min(\sqrt{red}, \sqrt{blud})) O(min(red ,blud ))因为 1 2 3 . . . k n ( n 1 ) 2 123...k\frac{n(n1)}{2} 123...k2n(n1)空间复杂度 O ( 1 ) O(1) O(1)
AC代码
C
class Solution {
public:int maxHeightOfTriangle(int red, int blue) {int cnt[2] {0, 0};int layer 1;while (true) {cnt[layer % 2] layer;if (!((cnt[0] red cnt[1] blue) || (cnt[0] blue cnt[1] red))) {return layer - 2;}}}
};Python
class Solution:def maxHeightOfTriangle(self, red: int, blue: int) - int:cnt [0, 0]for layer in range(1, 1000000):cnt[layer % 2] layerif not ((cnt[0] red and cnt[1] blue) or (cnt[0] blue and cnt[1] red)):return layer - 1return -1 # Fake Return同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/142967272
