NC564 牛牛打怪兽（四种语言+视频讲解）

- 题目描述：

- 题目链接：
https://www.nowcoder.com/practice/a3b055dd672245a3a6e2f759c237e449?tpId=196&&tqId=37252&rp=1&ru=/ta/job-code-total&qru=/ta/job-code-total/question-ranking

- 设计思想：

-视频讲解链接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
};