美文网首页刷爆力扣
【36】魔塔游戏

【36】魔塔游戏

作者: 公孙剑人 | 来源:发表于2021-10-07 09:59 被阅读0次

    如题:

    LCP 30. 魔塔游戏

    思路

    参考力扣的大佬的思路,使用贪心算法解决

    1. 如果每个房间的血量加起来小于0,那么无解,返回-1即可;
    2. 我们使用先进先出的队列,来保存导致血量减小的房间(值);
      a). 当blood加当前层小于0,则表示当前层需要移动到最后,step加一,同时还原原血量;
    3. 遍历nums完成,则step为需要移动的房间数。

    代码

        public int magicTower(int[] nums) {
            int sum = 0;
            for (int temp : nums) {
                sum += temp;
            }
            if (sum < 0) {
                return -1;
            }
            int step = 0;
            long blood = 0;
            Queue<Integer> queue = new PriorityQueue<>();
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] < 0) {
                    queue.offer(nums[i]);
                    if (blood + nums[i] < 0) {
                        // 移动次数加1
                        step ++;
                        // 血量还原
                        blood -= queue.poll();
                    }
                }
                // 执行到这,表示血量不会小于0,直接累加即可
                blood += nums[i];
            }
            return step;
        }
    

    相关文章

      网友评论

        本文标题:【36】魔塔游戏

        本文链接:https://www.haomeiwen.com/subject/lgwanltx.html