用手机域名做网站,厦门网站流量优化价格,在线设计名字,珠海视窗网题目
给你两个整数 red 和 blue#xff0c;分别表示红色球和蓝色球的数量。你需要使用这些球来组成一个三角形#xff0c;满足第 1 行有 1 个球#xff0c;第 2 行有 2 个球#xff0c;第 3 行有 3 个球#xff0c;依此类推。 每一行的球必须是 相同 颜色#xff0c;且相…题目
给你两个整数 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
答案
我的方法 我的方法思路非常简单我们既然要让他拼成一个三角形且是每一行的颜色都不一样那么第一行要么蓝色要么红色只要确定了第一行的颜色后面的就都确定了我分别让红色、蓝色作为第一行各自求出一个高度然后我们在将两个高度进行比较后输出就能得到最好的结果。 这个方法的时间复杂度为O(n)
class Solution:def maxHeightOfTriangle(self, red: int, blue: int) - int:high10high20red1redblue1bluefor i in range(red1blue1):if i%20:#红先放置red1red1-1-iif red10 and blue10:high11else:blue1blue1-i-1if blue10 and red10:high11for i in range(redblue):if i%20:#蓝先放置blueblue-i-1if blue0 and red0:high21else:redred-1-iif red0 and blue0:high21if high1high2:return high1else: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 1while True:if i % 2 1:x - iif x 0:return i - 1else:y - iif y 0:return i - 1i 1return max(maxHeight(red, blue), maxHeight(blue, red))官方的方法二 —— 直接计算出高度
思路与算法 我们也可以使用等差数列公式直接计算出高度。 对于从第一行开始的情况球的个数依次为 1,3,5,⋯,2k−1其中 2k−1 是最后一行那么总计个数为 135⋯(2k−1)[(1(2k−1))×k]/2 k^2 那么 k 的最大值即为 ⌊no⌋其中no是提供给奇数行的球的数量⌊⋅⌋ 表示向下取整。 同理对于从第二行开始的情况有 246⋯2k[(22k)×k]/2 k^2k 解方程可得 k 的最大值为 ⌊ [−1 (14ne)^(1/2)]/2⌋其中ne是提供给偶数行的球的数量。 因此最后一个奇数行为 2⌊no⌋−1最后一个偶数行为 2⌊ [−1 (14ne)^(1/2)]/2⌋最终的答案即为其中的较小值加 1。 def maxHeight(x: int, y: int) - int:odd 2 * int(sqrt(x)) - 1even 2 * int((-1 sqrt(1 4 * y)) / 2)return min(odd, even) 1return max(maxHeight(red, blue), maxHeight(blue, red))作者力扣官方题解 链接在这里 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
