- 设计思想:
-视频讲解链接B站视频讲解
- 复杂度分析:
- 代码:
c++版本:
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 n个怪兽 * @param A int整型vector A数组代表每个怪兽的血量 * @return int整型 */ int slove(int n, vector<int>& A) { // write code here ///无法打死所有怪兽,返回-1 if(n < 3 || (n % 2 == 0)){ return -1; } int res = 0;//记录打死全部怪兽需要的次数 for(int i = n/2-1;i >= 0;i --){ //由于下标从0开始,所有 2*i 实际对应,2*i+1, 2*i+1对应2*i+2 int temp = max(A[2*i+1],A[2*i+2]);//最大值即为所需次数 A[i] = max(A[i] - temp,0); res += temp; } //由于每次都是先让下标较大的变为0,因此最后第一个数可能没有变0,所有需要加上A[0]次 return res + A[0]; } };
Java版本:
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 n个怪兽 * @param A int整型一维数组 A数组代表每个怪兽的血量 * @return int整型 */ public int slove (int n, int[] A) { // write code here ///无法打死所有怪兽,返回-1 if(n < 3 || (n % 2 == 0)){ return -1; } int res = 0;//记录打死全部怪兽需要的次数 for(int i = n/2-1;i >= 0;i --){ //由于下标从0开始,所有 2*i 实际对应,2*i+1, 2*i+1对应2*i+2 int temp = Math.max(A[2*i+1],A[2*i+2]);//最大值即为所需次数 A[i] = Math.max(A[i] - temp,0); res += temp; } //由于每次都是先让下标较大的变为0,因此最后第一个数可能没有变0,所有需要加上A[0]次 return res + A[0]; } }
Python版本:
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param n int整型 n个怪兽 # @param A int整型一维数组 A数组代表每个怪兽的血量 # @return int整型 # class Solution: def slove(self , n , A ): # write code here #无法打死所有怪兽,返回-1 if n < 3 or (n % 2 == 0): return -1 res = 0#记录打死全部怪兽需要的次数 for i in range((n//2-1),-1,-1): #由于下标从0开始,所有 2*i 实际对应,2*i+1, 2*i+1对应2*i+2 temp = max(A[2*i+1],A[2*i+2])#最大值即为所需次数 A[i] = max(A[i] - temp,0) res += temp #由于每次都是先让下标较大的变为0,因此最后第一个数可能没有变0,所有需要加上A[0]次 return res + A[0];
JavaScript版本:
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 n个怪兽 * @param A int整型一维数组 A数组代表每个怪兽的血量 * @return int整型 */ function slove( n , A ) { // write code here ///无法打死所有怪兽,返回-1 if(n < 3 || (n % 2 == 0)){ return -1; } let res = 0;//记录打死全部怪兽需要的次数 for(let i = parseInt(n/2)-1;i >= 0;i --){ //由于下标从0开始,所有 2*i 实际对应,2*i+1, 2*i+1对应2*i+2 let temp = Math.max(A[2*i+1],A[2*i+2]);//最大值即为所需次数 A[i] = Math.max(A[i] - temp,0); res += temp; } //由于每次都是先让下标较大的变为0,因此最后第一个数可能没有变0,所有需要加上A[0]次 return res + A[0]; } module.exports = { slove : slove };