213. 打家劫舍 II --力扣 --JAVA

简介: 你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。

 题目

你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。

解题思路

    1. 将环断开,分情况为偷首节点和不偷首节点的情况;
    2. 限制起始和结束位置,对偷盗金额进行最大值计算;

    代码展示

    class Solution {
        public int rob(int[] nums) {
            if(nums.length == 1){
                return nums[0];
            }
            int n = nums.length;
            //分两种情况计算:偷首节点和不偷首节点
            return Math.max(nums[0] + rob1(nums, 2 , n - 1), rob1(nums, 1, n));
        }
        private int rob1(int[] nums, int start, int end){
            int steal0 = 0;     //上一节点未偷
            int steal1 = 0;     //当前节点最大值
            for (int i = start; i < end; i++){
                int max = Math.max( steal1, steal0 + nums[i]);
                steal0 = steal1;
                steal1 = max;
            }
            return steal1;
        }
    }

    image.gif


    目录
    相关文章
    |
    25天前
    |
    算法 Java
    LeetCode(一)Java
    LeetCode(一)Java
    |
    3月前
    |
    算法 Java
    LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
    LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
    49 6
    |
    3月前
    |
    存储 算法 Java
    LeetCode经典算法题:打家劫舍java详解
    LeetCode经典算法题:打家劫舍java详解
    65 2
    |
    3月前
    |
    人工智能 算法 Java
    LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
    LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
    48 1
    |
    3月前
    |
    存储 算法 Java
    LeetCode经典算法题:预测赢家+香槟塔java解法
    LeetCode经典算法题:预测赢家+香槟塔java解法
    49 1
    |
    3月前
    |
    存储 算法 Java
    LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
    LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
    75 0
    |
    3月前
    |
    算法 Java
    LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
    LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
    52 0
    |
    3月前
    |
    存储 算法 Java
    LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
    LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
    34 0
    |
    3月前
    |
    算法 Java 索引
    LeetCode初级算法题:寻找数组的中心索引+x的平方根+三个数的最大乘积+Leetcode 149:直线上最多的点数 Java详解
    LeetCode初级算法题:寻找数组的中心索引+x的平方根+三个数的最大乘积+Leetcode 149:直线上最多的点数 Java详解
    35 0
    |
    3月前
    |
    存储 算法 Java
    LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
    LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
    42 0