213. House Robber II抢劫房子2 Java

你是一名职业劫匪，计划抢劫街道上的房屋。每个房子都藏着一定数量的钱。这个地方的所有房屋都排成一个圆圈。这意味着第一个房子是最后一个房子的邻居。同时，相邻的房屋都连接了一个安全系统，如果同一天晚上有两个相邻的房屋被闯入， 它会自动报警。

给定一个nums表示每所房子的钱数的整数数组，返回你今晚可以在不惊动警察的情况下抢劫的最大金额。

示例 1：
输入： nums = [2,3,2]
输出： 3
解释：你不能先抢房子 1（钱 = 2）然后再抢房子 3（钱 = 2），因为它们是相邻的房子。

示例 2：
输入： nums = [1,2,3,1]
输出： 4
解释：抢房子 1（钱 = 1），然后抢房子 3（钱 = 3）。
您可以抢劫的总金额 = 1 + 3 = 4。

示例 3：
输入： nums = [1,2,3]
输出： 3

约束：
1 <= nums.length <= 100
0 <= nums[i] <= 1000

思路

1. 在198抢房子的基础上, 这个第一位和最后一位是挨着的, 所以我们取第二位到最后一位和第一位到倒数第二位的最大值Math.max(nums[0]~nums[length-2], nums[1] ~nums[length-1])
2. 需要注意的是, 当长度为1时, 直接返回数组里面的数

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        return Math.max(solution(nums, 0, nums.length - 1), solution(nums, 1, nums.length));
    }
    static int solution(int[] nums,int start, int end) {
        int pre=0,res=0;
        for (int i=start;i 
时间复杂度O(n)
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5119244.html