从0开始的秋招刷题路记录下所刷每道题的题解帮助自己回顾总结

213. 打家劫舍II

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

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

示例 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 = [0]
输出0

提示
1 <= nums.length <= 100
0 <= nums[i] <= 1000

解法一动态规划。如果去掉首尾房屋是相邻的限制条件该题就是打家劫舍Ⅰ的版本即每间房屋能够偷窃的最高金额为前一间房屋的最高偷窃金额和该房间与前一间的前一间的偷窃金额总和的最大值即nums[i] = Math.max(nums[i - 1], nums[i - 2] + nums[i])。
由于加入了首尾房屋相邻的限制条件因此偷了第一间房屋则不能偷窃最后一间房屋偷了最后一间则不能偷窃第一间房屋那么该题可转化为计算[0, n -2]与[1, n-1]两个数列的偷盗金额的最大值。

时间复杂度O(n)其中 n是数组长度。需要对数组遍历两次计算可以偷窃到的最高总金额。
空间复杂度O(1)。

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n == 1)
            return nums[0];
        if(n == 2)
            return Math.max(nums[0], nums[1]);
        
        int a = nums[0], b = Math.max(nums[0], nums[1]), c = Math.max(nums[0], nums[1]);
        for(int i = 2; i < n - 1; ++i){
            c = Math.max(a + nums[i], b);
            a = b;
            b = c;
        }

        a = nums[1];
        b = Math.max(nums[1], nums[2]);
        int d= Math.max(nums[1], nums[2]);
        for(int i = 3; i < n; ++i){
            d = Math.max(a + nums[i], b);
            a = b;
            b = d;
        }

        return Math.max(c, d);
    }
}

题目变种740.删除并获得点数

给你一个整数数组 nums 你可以对它进行一些操作。每次操作中选择任意一个 nums[i] 删除它并获得 nums[i] 的点数。之后你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

示例 1

输入nums = [3,4,2]
输出6
解释删除 4 获得 4 个点数因此 3 也被删除。之后删除 2 获得 2 个点数。总共获得 6 个点数。

示例 2

输入nums = [2,2,3,3,3,4]
输出9
解释删除 3 获得 3 个点数接着要删除两个 2 和 4 。之后再次删除 3 获得 3 个点数再次删除 3 获得 3 个点数。总共获得 9 个点数。

提示

1 <= nums.length <= 2 * 104
1 <= nums[i] <= 104

class Solution {
    public int deleteAndEarn(int[] nums) {
        //找最大值
        int max = nums[0];
        for(int num: nums)
            max = Math.max(max, num);
        
        //转化为打家劫舍问题
        int[] count = new int[max + 1];
        for(int num: nums)
            count[num] += num;
        
        if(max == 1)
            return count[1];

        int a = count[0], b = Math.max(count[0], count[1]), c = 0;
        for(int i = 2; i <= max; ++i){
            c = Math.max(b, a + count[i]);
            a = b;
            b = c; 
        }
        return c;
    }
}